If you're seeing this message, it means we're having trouble loading external resources on our website.

Jeżeli jesteś za filtrem sieci web, prosimy, upewnij się, że domeny *.kastatic.org i *.kasandbox.org są odblokowane.

Główna zawartość

Wieże Hanoi

Jeśli przerobiłeś już rozdział o rekurencjii, jesteś teraz gotowy by zająć się innym problemem, gdzie wielokrotna rekurencja może nam naprawdę pomóc. Zwany jest on Wieżami Hanoi. Dany jest zestaw trzech kołków oraz n dysków, gdzie każdy z nich jest różnej wielkości. Kołki nazwijmy A, B i C, a dyski niech mają numery od 1 dla najmniejszego, do n dla największego. Na początku wszystkie n dyski są na kołku A, w kolejności malejącej od góry do dołu, tak że dysk n jest na dole a dysk 1 na górze. Poniżej mamy rysunek jak Wierze Hanoi wyglądają dla n=5 dysków:
Trzy kołki oznaczone jako A, B, oraz C. Na kołku A są dyski 5, 4, 3, 2 i 1. Dysk 5 znajduje się na dole, a dysk 1 na górze. Na kołkach B i C nie ma dysków.
Celem jest przeniesienie wszystkich n dysków z kołka A na kołek B:
Trzy kołki oznaczone jako A, B, oraz C. Na kołku B są dyski 5, 4, 3, 2 i 1. Dysk 5 znajduje się na dole, a dysk 1 na górze. Na kołkach A i C nie ma dysków.
Brzmi łatwo, prawda? To nie jest do końca tak proste, ponieważ musisz przestrzegać dwóch reguł:
  1. Możesz przenieść tylko 1 dysk w jednym momencie.
  2. Żaden dysk nie może zostać na szczycie mniejszego. Na przykład, jeśli dysk 3 jest na kołku, wtedy wszystkie dyski poniżej muszą mieć numery większe od 3.
Możesz pomyśleć, że ten problem nie jest aż tak strasznie ważny, Wręcz przeciwnie! Legenda głosi, że gdzieś w Azji (Tybet, Wietnam, Indie — wybierz ten, który najbardziej Ci odpowiada), mnisi rozwiązują ten problem w z wykorzystaniem 64 dysków i — jak mówi historia — mnisi wierzą, że jeśli przeniosą wszystkie 64 dyski z kołka A na kołek B z zachowaniem dwóch wymienionych wcześniej zasad, nastąpi koniec świata. Jeśli mnisi się nie mylą, to czy nie powinniśmy się obawiać?
Na początku, zobaczmy jak rozwiązać ten problem rekurencyjnie. Możemy zacząć od naprawdę prostego przypadku, gdzie n=1. Przypadek n=1 będzie naszym bazowym. Możesz zawsze przenieść dysk 1 z kołka A na kołek B, ponieważ wiemy, że każdy dysk poniżej musi być większy. I nie ma nic specjalnego w kołkach A i B. Możesz przełożyć dysk 1 z kołka B na kołek C jeśli chcesz, albo z kołka C na kołek A, albo z dowolnego kołka na dowolny kołek. Rozwiązanie problemu Wież Hanoi z jednym dyskiem jest banalne, gdyż wymaga przeniesienia tylko jednego dysku.
A co z dwoma dyskami? Jak rozwiążesz problem gdy n=2? Możesz wykonać to w trzech ruchach. Oto jak będzie to wyglądać na początku:
Trzy kołki oznaczone jako A, B, oraz C. Na kołku A są dyski 2 i 1. Dysk 2 znajduje się na dole, a dysk 1 na górze. Na kołkach B i C nie ma dysków.
Po pierwsze, przenieś dysk 1 z kołka A na kołek C:
Trzy kołki oznaczone jako A, B, oraz C. Na kołku A jest dysk 1. Na kołku B nie ma dysków. Na kołku C jest dysk 1.
Należy zauważyć, że używając kołka C jako tymczasowego, mamy możliwość przełożyć na niego dysk 1 w celu uwolnienia dysku 2. Teraz dysk 2 —dolny dysk— jest wolny, możemy go przenieść na kołek B.
Trzy kołki oznaczone jako A, B, oraz C. Na kołku A nie ma dysków. Na kołku B jest dysk 2. Na kołku C jest dysk 1.
Ostatecznie, przenieś dysk 1 z kołka C na kołek B:
Trzy kołki oznaczone jako A, B, oraz C. Na kołku A nie ma dysków. Na kołku są dyski 2 i 1. Dysk 2 jest na dole, a dysk 1 na górze. Na kołku C nie ma dysków.
To rozwiązanie ma trzy kroki, po raz kolejny możemy zobaczyć, że nie ma nic trudnego w przeniesieniu 2 dysków z kołka A na kołek B. Możesz przełożyć je z kołka B na kołek C z wykorzystaniem kołka A jako tymczasowego: przełóż dysk 1 z kołka B na kołek A, następnie przełóż dysk 2 z kołka B na kołek C, i na koniec przenieś dysk 1 z kołka A na kołek C. Czy zgodzisz się, że można przełożyć dyski 1 i 2 z dowolnego kołka na dowolny kołek w trzech krokach? (Powiedz"TAK.")

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormena i Devina Balkcoma oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.

Chcesz dołączyć do dyskusji?

Na razie brak głosów w dyskusji
Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.