Obracanie kwadratowej tabeli

Algorytm

Obracanie tabeli to dla człowieka łatwe zadanie, ale dla komputera jest ono bardzo czasochłonne. Kwadratowa tabelka o rozmiarze n×n zawiera n₂ i każdy należy conajmniej raz odczytać i raz conajmniej zapisać. Z tego powodu należy używać tego algorytmu tylko w uzasadnionych przypadkach i jeśli to możliwe zaimplementować obracanie w inny sposób.

Obracanie tabeli jest tutaj rozpatrywane dla tabel kwadratowych. Jest to prosty przypadek, który nie wymaga sprawdzania jakiego rozmiaru będzie tabelka m×n czy n×m. Przykładowo dana jest poniższa tabelka:

Po obróceniu o 90° tabelka będzie wyglądać następująco:

Jak można zauważyć każda warstwa otoczki jest oddzielnie przesuwana o jedną pozycję zgodnie ze wskazówkami zegara. Rozwiązaniem tego problemu jest poniższa instrukcja, która podpowiada co należy zrobić, aby obrócić tabelę o dowolną ilość w prawo lub lewo.

Instrukcja

• Obrót o 90° w prawo:
  1. Transponuj
  2. Zapisz wspak każdy z wierszy
• Obrót o 90° w lewo (analogicznie do obrotu w prawo):
  1. Zapisz wspak każdy z wierszy
  2. Transponuj
• Obrót o 180° w lewo (można dwa razy w lewo/prawo o 90° lub):
  1. Zapisz wspak każdy z wierszy
  2. Zapisz wspak każdą z kolumn

Implementacja

Nowa tabelka

Rozwiązanie proste polega na utworzeniu dodatkowej tabeli n×n do której będą przepisywane dane z wprowadzonej tabeli. Jest to rozwiązanie mało ekonomiczne, ponieważ zużywa bardzo dużo pamięci. Zasada działania tego algorytmu opiera się na połączeniu obu procesów jednocześnie.

1. int** obroc90(int** tab, int n) {
2.   int** wynik = utworznxn(n);
3.   for (int i = 0; i < n; i++) {
4.     for (int j = 0; j < n; j++) {
5.       wynik[i][j] = tab[n - j - 1][i];
6.     }
7.   }
8.   return wynik;
9. }

(1.) Algorytm przyjmuję tablicę do obrócenia tab oraz jej rozmiar n. Początkowo (2.) tworzona jest nowa tablica. (3.) Dla każdego wiersza oraz (4.) każdej kolumny: (5.) pobierany jest odpowiedni element. Transpozycja jest dokonywana poprzez zamianę zmiennych i oraz j wskazujących na konkretną współrzędną. Z kolei odczytywania wspak zapewnia dodanie n - j - 1.

Obracanie w miejscu

Zakładając jednak, że nie istnieje potrzeba przechowywania starej wersji tabeli zdecydowanie lepiej byłoby operować bezpośrednio na tablicy bez potrzeby deklarowania dodatkowej pamięci. Jest to możliwe jeśli zapisze się funkcja dokonujące transpozycję, zamiana wierszy wspak oraz kolumn. Wszystkie napisane funkcje będą miały złożoność, ale będą potrzebowały tylko jednej dodatkowej zmiennej, aby zamienić wartości miejscami.

1. void transponuj(int** tab, int n) {
2.   for (int i = 0; i < n; i ++)
3.     for (int j = i + 1; j < n; j ++)
4.       swap(tab[i][j], tab[j][i]);
5. }

1. void wspakWiersze(int** tab, int n) {
2.   for (int i = 0; i < n; i ++)
3.     for (int j = 0; j < n / 2; j ++)
4.       swap(tab[i][j], tab[i][n - 1 - j]);
5. }

1. void wspakKolumny(int** tab, int n) {
2.   for (int i = 0; i < n/2; i ++)
3.     for (int j = 0; j < n; j ++)
4.       swap(tab[i][j], tab[n - 1 - i][j]);
5. }

Wtedy główna funkcja obracająca o 90° wygląda następująco:

1. void obroc90(int** tab, int n) {
2.   transponuj(tab, n);
3.   wspakWiersze(tab, n);
4. }

Bezpośrednia zamiana

Istnieje jeszcze jedna metoda obracająca tabelę w miejscu. Do wykonania zadania również potrzebuje tylko dodatkowo jednej zmiennej. Jej działanie opiera się na zamianie czterech pozycji w każdej iteracji. Przykładowo zamieniane są wszystkie narożne wartości. Ze względu na swoje działanie funkcja ogranicza się do wyboru punktów początkowych jedy nie w lewej, górnej połówce tabeli.

1. void obroc90(int** tab, int n) {
2.   int temp;
3.   for (int i = 0; i < n / 2; i++) {
4.     for (int j = i; j < n - i - 1; j++) {
5.       temp = tab[n - j - 1][i];
6.       tab[n - j - 1][i] = tab[n - i - 1][n - j - 1];
7.       tab[n - i - 1][n - j - 1] = tab[j][n - i - 1];
8.       tab[j][n - i - 1] = tab[i][j];
9.       tab[i][j] = temp;
10.     }
11.   }
12. }

Tego typu rozwiązanie można uznać na najprostsze do napisania. Ponadto warto zauważyć, że posiada najlepsze cechy dwóch poprzednich rozwiązań. Gwarantuje dokładnie tylko jedną ustawienie i odczytanie każdego pola (jak w pierwszej metodzie) oraz nie wymaga dodatkowej tabeli na dane (jak w drugiej metodzie).

Testowanie funkcji

Poniższa funkcja main() obróci utworzoną tabelę o 90° cztery razy i za każdym razem wypisze wynik na konsolę. W celu uproszczenia kodu zostały napisane dodatkowe funkcje:

• utworznxn(n) - tworzy tabelkę 2D o rozmiarze n×n
• wypisz(tab, n) - wypisuje tabelkę tab na ekran o rozmiarze n×n
• usun(tab, n) - usuwa tabelkę tab o rozmiarze n×n

1. int main() {
2.   int n = 4;
3.   int** tab = utworznxn(n);
4.   for (int i = 0; i < n; i++) {
5.     for (int j = 0; j < n; j++) {
6.       tab[i][j] = i*n + j;
7.     }
8.   }
9.   wypisz(tab, n);
10.   for (int i = 1; i < 5; i++) {
11.     obroc90(tab, n);
12.     cout << "\nPo obroceniu o " << 90 * i << " st:\n";
13.     wypisz(tab, n);
14.   }
15.   system("pause");
16.   return 0;
17. }

W przypadku pierwszego kodu źródłowego funkcja main() różni częściowo od linijki (11.) gdzie wynik działania funkcji jest inaczej interpretowany.

• Kod źródłowy Nowa tabelka
• Kod źródłowy Obracanie w miejscu
• Kod źródłowy Bezpośrednia zamiana

Zadania

Zadanie 1

Napisz funkcję obróć, która będzie przyjmowała trzy argumenty: tab - dwuwymiarową tablicę, n - rozmiar tablicy oraz k - kąt obrotu. Funkcja powinna obrócić tablicę o k stopni jeśli jest wielokrotnoscią 90. Jeśli nie to program powinien wypisać stosowny komunikat na ekran. Przetestuj działanie funkcji.

• Kod źródłowy Zadanie 1