Przeczytaj

Implementacja rozwiązania w języku Python

Ciekawostka

Liczba ruchów niezbędnych do przeniesienia wszystkich krążków ze słupka A na słupek C wynosi (2Indeks górny n - 1), czyli rośnie wykładniczo wraz ze zwiększaniem liczby krążków. Jeśli przyjmiemy, że jeden krążek przemieszczamy w ciągu jednej sekundy, to rozwiązanie łamigłówki dla trzech krążków zajmuje tylko siedem sekund, podczas gdy w przypadku 20 krążków czas ten wydłuża się już do 1 048 576 sekund (ponad 17 000 minut, czyli około 11 dni).

Jeden z najszybszych współczesnych komputerów, MareNostrum 4, wykonuje $13, 667 \times 10^{12}$ operacji na sekundę. By rozwiązać zagadkę dla 64 krążków potrzebowałby nieco ponad dwóch tygodni.

Przykład 1

Zdefiniujmy funkcję, która wykorzystując podany wcześniej algorytm, zapisze listę ruchów koniecznych do rozwiązania łamigłówki Wież Hanoi.

def hanoi(n, a, b, c):
	if n > 0:
		hanoi(n - 1, a, c, b)
		print(f"przenieś {a} -> {b}")
		hanoi(n - 1, c, b, a)

Wywołajmy funkcję dla trzech krążków. Otrzymamy listę ruchów potrzebnych do przeniesienia krążków ze słupka A na słupek C przy użyciu słupka B.

hanoi(3, 'A', 'C', 'B')

przenieś A -> C
przenieś A -> B
przenieś C -> B
przenieś A -> C
przenieś B -> A
przenieś B -> C
przenieś A -> C

Po podwojeniu liczby krążków lista operacji wydłuża się dziewięciokrotnie. Krążków jest sześć, należy zatem wykonać 63 ruchy (2Indeks górny 6 - 1).

Linia 1. hanoi otwórz nawias okrągły 6 przecinek cudzysłów A cudzysłów przecinek cudzysłów B cudzysłów przecinek cudzysłów C cudzysłów zamknij nawias okrągły. Linia 3. przenieś A minus zamknij nawias ostrokątny C. Linia 4. przenieś A minus zamknij nawias ostrokątny B. Linia 5. przenieś C minus zamknij nawias ostrokątny B. Linia 6. przenieś A minus zamknij nawias ostrokątny C. Linia 7. przenieś B minus zamknij nawias ostrokątny A. Linia 8. przenieś B minus zamknij nawias ostrokątny C. Linia 9. przenieś A minus zamknij nawias ostrokątny C. Linia 10. przenieś A minus zamknij nawias ostrokątny B. Linia 11. przenieś C minus zamknij nawias ostrokątny B. Linia 12. przenieś C minus zamknij nawias ostrokątny A. Linia 13. przenieś B minus zamknij nawias ostrokątny A. Linia 14. przenieś C minus zamknij nawias ostrokątny B. Linia 15. przenieś A minus zamknij nawias ostrokątny C. Linia 16. przenieś A minus zamknij nawias ostrokątny B. Linia 17. przenieś C minus zamknij nawias ostrokątny B. Linia 18. przenieś A minus zamknij nawias ostrokątny C. Linia 19. przenieś B minus zamknij nawias ostrokątny A. Linia 20. przenieś B minus zamknij nawias ostrokątny C. Linia 21. przenieś A minus zamknij nawias ostrokątny C. Linia 22. przenieś B minus zamknij nawias ostrokątny A. Linia 23. przenieś C minus zamknij nawias ostrokątny B. Linia 24. przenieś C minus zamknij nawias ostrokątny A. Linia 25. przenieś B minus zamknij nawias ostrokątny A. Linia 26. przenieś B minus zamknij nawias ostrokątny C. Linia 27. przenieś A minus zamknij nawias ostrokątny C. Linia 28. przenieś A minus zamknij nawias ostrokątny B. Linia 29. przenieś C minus zamknij nawias ostrokątny B. Linia 30. przenieś A minus zamknij nawias ostrokątny C. Linia 31. przenieś B minus zamknij nawias ostrokątny A. Linia 32. przenieś B minus zamknij nawias ostrokątny C. Linia 33. przenieś A minus zamknij nawias ostrokątny C. Linia 34. przenieś A minus zamknij nawias ostrokątny B. Linia 35. przenieś C minus zamknij nawias ostrokątny B. Linia 36. przenieś C minus zamknij nawias ostrokątny A. Linia 37. przenieś B minus zamknij nawias ostrokątny A. Linia 38. przenieś C minus zamknij nawias ostrokątny B. Linia 39. przenieś A minus zamknij nawias ostrokątny C. Linia 40. przenieś A minus zamknij nawias ostrokątny B. Linia 41. przenieś C minus zamknij nawias ostrokątny B. Linia 42. przenieś C minus zamknij nawias ostrokątny A. Linia 43. przenieś B minus zamknij nawias ostrokątny A. Linia 44. przenieś B minus zamknij nawias ostrokątny C. Linia 45. przenieś A minus zamknij nawias ostrokątny C. Linia 46. przenieś B minus zamknij nawias ostrokątny A. Linia 47. przenieś C minus zamknij nawias ostrokątny B. Linia 48. przenieś C minus zamknij nawias ostrokątny A. Linia 49. przenieś B minus zamknij nawias ostrokątny A. Linia 50. przenieś C minus zamknij nawias ostrokątny B. Linia 51. przenieś A minus zamknij nawias ostrokątny C. Linia 52. przenieś A minus zamknij nawias ostrokątny B. Linia 53. przenieś C minus zamknij nawias ostrokątny B. Linia 54. przenieś A minus zamknij nawias ostrokątny C. Linia 55. przenieś B minus zamknij nawias ostrokątny A. Linia 56. przenieś B minus zamknij nawias ostrokątny C. Linia 57. przenieś A minus zamknij nawias ostrokątny C. Linia 58. przenieś A minus zamknij nawias ostrokątny B. Linia 59. przenieś C minus zamknij nawias ostrokątny B. Linia 60. przenieś C minus zamknij nawias ostrokątny A. Linia 61. przenieś B minus zamknij nawias ostrokątny A. Linia 62. przenieś C minus zamknij nawias ostrokątny B. Linia 63. przenieś A minus zamknij nawias ostrokątny C. Linia 64. przenieś A minus zamknij nawias ostrokątny B. Linia 65. przenieś C minus zamknij nawias ostrokątny B.

hanoi(6, "A", "B", "C")

przenieś A -> C
przenieś A -> B
przenieś C -> B
przenieś A -> C
przenieś B -> A
przenieś B -> C
przenieś A -> C
przenieś A -> B
przenieś C -> B
przenieś C -> A
przenieś B -> A
przenieś C -> B
przenieś A -> C
przenieś A -> B
przenieś C -> B
przenieś A -> C
przenieś B -> A
przenieś B -> C
przenieś A -> C
przenieś B -> A
przenieś C -> B
przenieś C -> A
przenieś B -> A
przenieś B -> C
przenieś A -> C
przenieś A -> B
przenieś C -> B
przenieś A -> C
przenieś B -> A
przenieś B -> C
przenieś A -> C
przenieś A -> B
przenieś C -> B
przenieś C -> A
przenieś B -> A
przenieś C -> B
przenieś A -> C
przenieś A -> B
przenieś C -> B
przenieś C -> A
przenieś B -> A
przenieś B -> C
przenieś A -> C
przenieś B -> A
przenieś C -> B
przenieś C -> A
przenieś B -> A
przenieś C -> B
przenieś A -> C
przenieś A -> B
przenieś C -> B
przenieś A -> C
przenieś B -> A
przenieś B -> C
przenieś A -> C
przenieś A -> B
przenieś C -> B
przenieś C -> A
przenieś B -> A
przenieś C -> B
przenieś A -> C
przenieś A -> B
przenieś C -> B

Dla zainteresowanych

Możemy sprawdzić, ile razy wykonywana jest funkcja rekurencyjna, czyli taka, która wywołuje wielokrotnie siebie samą. W celu sprawdzenia liczby wykonywanych przez nią operacji posłużymy się zmienną, która istnieje w przestrzeni nazwprzestrzeń nazwprzestrzeni nazw poza funkcją. Aby zmieniać jej wartość, zadeklarujmy ją za pomocą słowa kluczowego global. Dzięki temu będziemy mogli zmieniać wartość zmiennej, która istnieje poza funkcją.

Zdefiniujmy funkcję, która obliczy liczbę wywołań funkcji, niezbędnych dla rozwiązania zagadki Wież Hanoi. Przyjmijmy założenie, że jedno wywołanie trwa 1 sekundę.

W celu zobrazowania wyników obliczeń posłużymy się biblioteką matplotlibmatplotlibmatplotlib i napiszemy program wyświetlający wykres zależności liczby kroków od liczby krążków. Przyjmiemy, że przeniesienie 1 krążka trwa 1 sekundę. Wyniki podamy w dobach, a więc na wykresie 1 jednostka osi Y będzie odpowiadać 86400 sekund (przenosin krążków).

RAqWRzS97fXUz

Linia 1. import matplotlib kropka pyplot as plt. Linia 3. def hanoi otwórz nawias okrągły n przecinek a przecinek b przecinek c zamknij nawias okrągły dwukropek. Linia 4. global zlicz. Linia 6. if n znak równości znak równości 0 dwukropek. Linia 7. return None. Linia 8. if n zamknij nawias ostrokątny 0 dwukropek. Linia 9. hanoi otwórz nawias okrągły n minus 1 przecinek a przecinek c przecinek b zamknij nawias okrągły. Linia 10. zlicz plus znak równości 1. Linia 11. hanoi otwórz nawias okrągły n minus 1 przecinek c przecinek b przecinek a zamknij nawias okrągły. Linia 13. kratka przygotowujemy listę przecinek dla której będziemy obliczać. Linia 14. X znak równości otwórz nawias kwadratowy x for x in range otwórz nawias okrągły 3 przecinek 28 przecinek 3 zamknij nawias okrągły zamknij nawias kwadratowy. Linia 15. Y znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 17. kratka w pętli wykonujemy kolejne obliczenia. Linia 18. for e in X dwukropek. Linia 19. zlicz znak równości 0. Linia 20. hanoi otwórz nawias okrągły e przecinek cudzysłów A cudzysłów przecinek cudzysłów B cudzysłów przecinek cudzysłów C cudzysłów zamknij nawias okrągły. Linia 21. y znak równości round otwórz nawias okrągły zlicz prawy ukośnik 86400 przecinek 0 zamknij nawias okrągły. Linia 22. print otwórz nawias okrągły f cudzysłów Liczę dla dwukropek otwórz nawias klamrowy e zamknij nawias klamrowy krążków znak równości otwórz nawias klamrowy zlicz zamknij nawias klamrowy kroków przecinek otwórz nawias klamrowy y zamknij nawias klamrowy dni kropka cudzysłów zamknij nawias okrągły. Linia 23. Y kropka append otwórz nawias okrągły y zamknij nawias okrągły. Linia 25. kratka generujemy wykres. Linia 26. plt kropka plot otwórz nawias okrągły X przecinek Y zamknij nawias okrągły. Linia 27. plt kropka grid otwórz nawias okrągły True zamknij nawias okrągły. Linia 28. plt kropka xlabel otwórz nawias okrągły cudzysłów Liczba krążków do przeniesienia kropka cudzysłów zamknij nawias okrągły. Linia 29. plt kropka ylabel otwórz nawias okrągły cudzysłów Liczba dni otwórz nawias okrągły 1 znak równości 86400 sekund zamknij nawias okrągły kropka cudzysłów zamknij nawias okrągły. Linia 30. plt kropka legend otwórz nawias okrągły otwórz nawias kwadratowy cudzysłów Wykres minus czas niezbędny do rozwiązania zagadki wież Hanoi kropka cudzysłów zamknij nawias kwadratowy zamknij nawias okrągły. Linia 31. plt kropka show otwórz nawias okrągły zamknij nawias okrągły. Linia 33. kratka wyniki. Linia 34. kratka Liczę dla dwukropek 3 krążków znak równości 7 kroków przecinek 0 kropka 0 dni kropka. Linia 35. kratka Liczę dla dwukropek 6 krążków znak równości 63 kroków przecinek 0 kropka 0 dni kropka. Linia 36. kratka Liczę dla dwukropek 9 krążków znak równości 511 kroków przecinek 0 kropka 0 dni kropka. Linia 37. kratka Liczę dla dwukropek 12 krążków znak równości 4095 kroków przecinek 0 kropka 0 dni kropka. Linia 38. kratka Liczę dla dwukropek 15 krążków znak równości 32767 kroków przecinek 0 kropka 0 dni kropka. Linia 39. kratka Liczę dla dwukropek 18 krążków znak równości 262143 kroków przecinek 3 kropka 0 dni kropka. Linia 40. kratka Liczę dla dwukropek 21 krążków znak równości 2097151 kroków przecinek 24 kropka 0 dni kropka. Linia 41. kratka Liczę dla dwukropek 24 krążków znak równości 16777215 kroków przecinek 194 kropka 0 dni kropka. Linia 42. kratka Liczę dla dwukropek 27 krążków znak równości 134217727 kroków przecinek 1553 kropka 0 dni kropka.

import matplotlib.pyplot as plt

def hanoi(n, a, b, c):
	global zlicz

	if n == 0:
		return None
	if n > 0:
		hanoi(n - 1, a, c, b)
		zlicz += 1
		hanoi(n - 1, c, b, a)

# przygotowujemy listę, dla której będziemy obliczać
X = [x for x in range(3, 28, 3)]
Y = []

# w pętli wykonujemy kolejne obliczenia
for e in X:
	zlicz = 0
	hanoi(e, "A", "B", "C")
	y = round(zlicz / 86400, 0)
	print(f"Liczę dla: {e} krążków = {zlicz} kroków, {y} dni.")
	Y.append(y)

# generujemy wykres    
plt.plot(X, Y)
plt.grid(True)
plt.xlabel("Liczba krążków do przeniesienia.")
plt.ylabel("Liczba dni (1 = 86400 sekund).")
plt.legend(["Wykres - czas niezbędny do rozwiązania zagadki wież Hanoi."])
plt.show()

# wyniki
# Liczę dla: 3 krążków = 7 kroków, 0.0 dni.
# Liczę dla: 6 krążków = 63 kroków, 0.0 dni.
# Liczę dla: 9 krążków = 511 kroków, 0.0 dni.
# Liczę dla: 12 krążków = 4095 kroków, 0.0 dni.
# Liczę dla: 15 krążków = 32767 kroków, 0.0 dni.
# Liczę dla: 18 krążków = 262143 kroków, 3.0 dni.
# Liczę dla: 21 krążków = 2097151 kroków, 24.0 dni.
# Liczę dla: 24 krążków = 16777215 kroków, 194.0 dni.
# Liczę dla: 27 krążków = 134217727 kroków, 1553.0 dni.

Ważne!

Musimy pamiętać, że język Python jest dynamicznie typowany, a więc każda zmienna może w dowolnym momencie przechowywać dane różnego typu. Dodatkowo jest to interpreter, a nie kompilator. Z tych powodów nawet proste obliczenia zajmują dużo czasu procesora, dlatego odradzamy liczenie w taki sposób dla więcej niż 30 krążków. Na komputerze wyposażonym w procesor Core i5 obliczenia dla 33 i więcej krążków trwają kilka godzin.

Problem 1

Zadanie:

Zapisz program wykorzystujący rekurencję, który wypisze kolejne kroki, jakie trzeba wykonać, aby przenieść wieżę składającą się z n krążków o różnej średnicy ze słupka A na słupek C. Swój program przetestuj dla 3 krążków.

Zasady gry:

Gra składa się z trzech słupków i zestawu krążków o różnych średnicach.
Na jednym słupku umieszczona jest wybudowana wieża.
Celem gry jest odbudowanie wieży na trzecim słupku.
Nie wolno położyć krążka o większej średnicy na krążku o mniejszej średnicy.
Na raz można przenosić tylko jeden krążek (znajdujący się na szczycie wieży).
Do przenoszenia można wykorzystać dodatkowy słupek.

Specyfikacja:

Dane:

n – liczba krążków w grze, liczba naturalna
A, B, C – symboliczne nazwy słupków, znaki

Wynik:

Program na wyjściu standardowym wypisuje w kolejnych linijkach kroki, które prowadzą do rozwiązania zagadki Wież Hanoi.

R9mntKFs8m9eM

Polecenie 1

Porównaj swoje rozwiązanie z przedstawionym w filmie.

RoxU7lRTafplf1

Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Już wiesz

Podsumujmy najważniejsze informacje:

liczba operacji niezbędnych do rozwiązania zagadki Wież Hanoi rośnie wykładniczo wraz ze wzrostem liczby krążków składających się na wieżę,
operacje przenoszenia krążków składających się na Wieże Hanoi przypominają sposób odwoływania się procesora do elementów stosu.

Słownik

funkcja rekurencyjna

funkcja, która wywołuje samą siebie, aż do momentu osiągnięcia stanu początkowego – każda taka funkcja zawiera tzw. warunek zakończenia rekurencji (zwany także warunkiem początkowym) oraz przynajmniej jedno miejsce, w którym procedura wywołuje samą siebie

matplotlib

biblioteka służąca do przedstawienia obrazów złożonych z punktów o współrzędnych (x, y), np. wykresów, histogramów, rozkładów itp.; moduł matplotlib nie jest dostępny w standardowej instalacji języka Python - można go zainstalować, korzystając z mechanizmu pip

przypadek rekurencyjny

warunek w funkcji rekurencyjnej, po spełnieniu którego funkcja ponownie wywołuje siebie samą

przypadek bazowy

warunek w funkcji rekurencyjnej, po spełnieniu którego funkcja nie wywołuje samej siebie po raz kolejny

rekurencja

proces polegający na wywoływaniu funkcji przez siebie samą do momentu rozwiązania określonego zadania

stos

struktura danych, w której informacje są pobierane ze szczytu i na niego odkładane; struktura typu LIFO (Last In, First Out – ostatni na wejściu, pierwszy na wyjściu)

zagadka Wież Hanoi

łamigłówka polegająca na odbudowaniu, z zachowaniem kształtu, wieży z krążków o różnych średnicach; podczas przekładania nie wolno kłaść krążka o większej średnicy na mniejszy, ani przekładać kilku krążków jednocześnie

Wprowadzenie

Symulacja interaktywna

Implementacja rozwiązania w języku Python

Słownik