Przedstawienie problemu

Wiesz już, że zagadka Wież Hanoizagadka Wież Hanoizagadka Wież Hanoi polega na przeniesieniu krążków o różnych średnicach z jednego słupka na drugi. Warunkiem poprawnego rozwiązania zadania jest pojedyncze przenoszenie każdego krążka, który znajduje się na szczycie, a także brak możliwości położenia krążka o większej średnicy na krążku o mniejszej średnicy. Do dyspozycji mamy jednak pomocniczy słupek, na który możemy tymczasowo nakładać krążki.

Zatem mamy trzy słupki: A, B, C oraz n krążków. Początkowo wszystkie krążki położone są na słupku A. Docelowo wszystkie krążki mają znaleźć się na słupku C. Pomocniczym słupkiem jest słupek B. Celem naszego zadania jest przedstawienie ciągu ruchów, opisującego rozwiązanie zagadki Wież Hanoi.

R18lEEYeXYasj

Ilustracja przedstawia dwa rzędy słupków: A, B, C.
W pierwszym rzędzie na słupku A umieszczone jest 5 krążków w kolejności od największego do najmniejszego.
Słupki B oraz C są puste.
W drugim rzędzie słupków, na słupku C znajduje się 5 krążków ułożonych w kolejności od największego do najmniejszego.
Słupki A oraz B są puste.

Implementacja algorytmu w języku C++

Zagadkę Wież Hanoi dla n krążków rozwiążemy w sposób rekurencyjnyalgorytm rekurencyjnyrekurencyjny. Program przetestujemy dla trzech krążków.

Specyfikacja:

Dane:

• n – liczba krążków; liczba naturalna dodatnia

• A – nazwa słupka początkowego; znak

• B – nazwa słupka pomocniczego; znak

• C – nazwa słupka docelowego; znak

Wynik:

Program na standardowym wyjściu wypisuje ciąg ruchów opisujący rozwiązanie zagadki wież Hanoi dla n krążków, gdzie początkowo wszystkie znajdują się na słupku A. Na końcu wszystkie krążki mają znaleźć się na słupku C, a pomocniczym słupkiem jest B.

Tworzymy funkcję o nazwie hanoi(), której przyjmowanymi parametrami wejściowymi będzie n, czyli liczba krążków, a następnie A, B, C, czyli nazwy słupków: początkowego, pomocniczego, a także końcowego.

#include <iostream>
using namespace std;

void hanoi(int n, char A, char B, char C) {

}

Następnie, gdy liczba krążków jest większa od 0 (dla liczby krążków równej 0 zajdzie przypadek bazowyprzypadek bazowyprzypadek bazowy), możemy wykonywać algorytm. Wywołamy na początku rekurencyjnie funkcję hanoi, która zrealizuje przeniesienie n - 1 górnych krążków ze słupka A na słupek B. Na słupku A pozostanie tylko jeden, n-ty, największy krążek. Reszta krążków będzie nałożona na słupek B.

#include <iostream>
using namespace std;

void hanoi(int n, char A, char B, char C) {
	if (n > 0) {
		hanoi(n - 1, A, C, B);
	}
}

Operację przeniesienia n - 1 górnych krążków ze słupka A na słupek B przedstawia ilustracja:

R5gonJQUjp5Be

Ilustracja przedstawia dwa rzędy słupków: A, B, C.
W pierwszym rzędzie na słupku A umieszczone jest 6 krążków w kolejności od największego do najmniejszego, a słupki B oraz C są puste.
Pierwszy największy krążek w słupku A  jest koloru niebieskiego, a reszta czerwonego
W drugim rzędzie słupków na słupku A znajduje się pojedynczy duży krążek koloru niebieskiego.
W drugim rzędzie na słupku B znajduje się 5 krążków ułożonych w kolejności od największego do najmniejszego koloru czerwonego.
Słupek C jest pusty.

Największy krążek musi zostać przełożony na słupek docelowy C. Wypisujemy zatem na ekran komunikat: „Przeniesienie z” A „do” C.

#include <iostream>
using namespace std;

void hanoi(int n, char A, char B, char C) {
	if (n > 0) {
		hanoi(n - 1, A, C, B);
		cout << "Przeniesienie z " << A << " do " << C  << endl;
	}
}

Operację przeniesienia n-tego krążka na słupek docelowy C, przedstawia rysunek:

R1Z3QddHibMDU

Ilustracja przedstawia dwa rzędy słupków: A, B, C.
Na słupku A umieszczony jest pojedynczy duży krążek koloru czerwonego.
Na słupku B umieszczonych jest 5 krążków w kolejności od największego do najmniejszego koloru niebieskiego.
W drugim rzędzie słupków na słupku B umieszczonych jest 5 krążków w kolejności od największego do najmniejszego koloru niebieskiego.
Na słupku C umieszczony jest pojedynczy duży krążek koloru czerwonego.

Na koniec musimy jeszcze wywołać rekurencyjnie funkcję hanoi, aby przenieść n - 1 krążków ze słupka B na słupek C, na którym położony jest już największy krążek.

Aby to zrealizować, pierwszym przyjmowanym argumentem będzie n - 1, ponieważ chcemy przenieść właśnie taką liczbę krążków. Drugim argumentem będzie B, ponieważ tym razem ten słupek jest słupkiem początkowym. Następnie umieszczamy A, ponieważ w tej sytuacji będzie on słupkiem pomocniczym, a na końcu słupek docelowy C.

#include <iostream>
using namespace std;

void hanoi(int n, char A, char B, char C) {
	if (n > 0) {
		hanoi(n - 1, A, C, B);
		cout << "Przeniesienie z " << A << " do " << C  << endl;
		hanoi(n - 1, B, A, C);
	}
}

R1ev9uJhTaw90

Ilustracja przedstawia dwa rzędy słupków: A, B, C.
Na słupku B umieszczonych jest 5 krążków w kolejności od największego do najmniejszego koloru czerwonego.
Na słupku C znajduje się pojedynczy duży krążek koloru niebieskiego.
W drugim rzędzie na słupku C umieszczonych jest 6 krążków w kolejności od największego do najmniejszego.
Pierwszy największy krążek jest koloru niebieskiego, a reszta czerwonego.

Teraz wystarczy wywołać funkcję hanoi, np. dla trzech krążków z nazwami słupków: A, B, C.

#include <iostream>
using namespace std;

void hanoi(int n, char A, char B, char C) {
	if (n > 0) {
		hanoi(n - 1, A, C, B);
		cout << "Przeniesienie z " << A << " do " << C  << endl;
		hanoi(n - 1, B, A, C);
	}
}

int main() {
	hanoi(3, 'A', 'B', 'C');
	return 0;
}

Ciąg ruchów otrzymany w wyniku wywołania funkcji dla trzech krążków będzie wyglądał następująco:

• Przeniesienie z A do C

• Przeniesienie z A do B

• Przeniesienie z C do B

• Przeniesienie z A do C

• Przeniesienie z B do A

• Przeniesienie z B do C

• Przeniesienie z A do C

Zobaczmy jeszcze, jak będzie wyglądało drzewo wywołań rekurencyjnych dla wywołania funkcji hanoi(3, 'A', 'B', 'C'). Dzięki niemu, będziemy mogli zobaczyć wszystkie wywołania funkcji hanoi. Lewa strzałka odchodząca od danej funkcji, będzie wskazywała na pierwsze wywołanie funkcji, umieszczone w szóstej linijce naszego kodu, natomiast prawa strzałka wskaże nam drugie wywołanie, z ósmej linijki. Aby odczytać rozwiązanie problemu z drzewa wywołań rekurencyjnych, najpierw musimy odczytać ruchy z lewego poddrzewa węzła, następnie ruch należący do węzła – ojca, a na końcu ruchy z prawego poddrzewa.

Zagadka wież Hanoi jest przykładem zadania, którego złożność obliczeniowa wzrasta bardzo szybko wraz z liczbą krążków n. Przedstawiony algorytm ma złożoność wykładniczązłożoność wykładniczawykładniczą, to znaczy $O\left(2^n\right)$.

Słownik