Kod programu zaprezentowanego w filmie:

Przedstawienie problemu

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

Mamy zatem trzy słupki: A, B, C oraz n krążków. Początkowo wszystkie krążki położone są na słupku A, w kolejności od największego do najmniejszego. Docelowo wszystkie krążki mają znaleźć się na słupku C w tej samej kolejności, w jakiej znajdowały się na słupku A. 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 rozwiązania w języku Java

Problem Wież Hanoi można rozwiązać w sposób iteracyjny, czyli za pomocą pętli. Jest on jednak bardzo dobrym przykładem sytuacji, gdzie możemy zastosować rozwiązanie rekurencyjnefunkcja rekurencyjnarekurencyjne, czyli takie, w którym używamy metody „dziel i zwyciężaj”. Operacje niezbędne do umieszczenia coraz mniejszych krążków na słupku docelowym (C) są takie same jak w przypadku pierwszego, największego krążka – z tym zastrzeżeniem, że zmienia się słupek pomocniczy. Najpierw (czyli po przeniesieniu największego krążka na słupek C) będzie nim A. Później rolę słupka pomocniczego będą na przemian odgrywać słupki B i A. Zauważmy, że słupek docelowy się nie zmienia.

Przypadkiem rekurencyjnymprzypadek rekurencyjnyPrzypadkiem rekurencyjnym będzie sytuacja, w której na słupku A pozostał co najmniej jeden krążek. Instrukcje składające się na funkcję rekurencyjną hanoi() będą wówczas wykonywane. Przypadkiem bazowymprzypadek bazowyPrzypadkiem bazowym będzie sytuacja, w której na słupku A nie ma już żadnego krążka. Aktualne wywołanie funkcji hanoi() przestanie być wtedy wykonywane.

Oto implementacja algorytmu w języku Java dla 5 krążków:

public class Main {
	// n – liczba krążków, A – miejsce początkowe
    // B – słupek pomocniczy, C – miejsce docelowe
	public static void hanoi(int n, char A, char B, char C) {
		if (n > 0) {
			//wywołanie rekurencyjne
			hanoi(n - 1, A, C, B);
			System.out.println("Przeniesienie z " + A + " do " + C);
			//wywołanie rekurencyjne
			hanoi(n - 1, B, A, C);
		}
	}

	public static void main(String[] args) {
		hanoi(5, 'A', 'B', 'C');
	}
}

Po uruchomieniu programu otrzymamy następujący wynik:

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
Przeniesienie z A do B
Przeniesienie z C do B
Przeniesienie z C do A
Przeniesienie z B do A
Przeniesienie z C do B
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
Przeniesienie z B do A
Przeniesienie z C do B
Przeniesienie z C do A
Przeniesienie z B do A
Przeniesienie z B do C
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

Jest to gotowe rozwiązanie problemu Wież Hanoi dla 5 krążków.

Złożoność czasowa i pamięciowa

Jak możemy zauważyć, do rozwiązania problemu Wież Hanoi dla 5 krążków potrzebne było 31 ruchów. Gdybyśmy uruchomili ten program dla 10 krążków, potrzebne byłyby aż 1023 ruchy.

Aby rozwiązać problem Wież Hanoi dla $n$ krążków, należy przenieść jeden krążek oraz rozwiązać dwukrotnie ten problem dla $n-1$. Oznacza to, że liczba wykonanych przeniesień jest równa $2^{n}-1$. Algorytm ma zatem złożoność wykładniczą $O(2^{n})$.

Złożoność pamięciowa tego algorytmu jest liniowa, czyli równa $O(n)$. Wynika to z faktu, że funkcje wywołane w jednej funkcji rekurencyjnej nie wywołają się jednocześnie — drugie wywołanie pojedynczej funkcji będzie miało miejsce dopiero po zakończeniu całości pierwszego wywołania. Zatem pamięć ta może być użyta ponownie. W tym samym momencie aktywnych będzie maksymalnie $O(n)$ funkcji.

Słownik