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, ciąg dalszy

Rozwiązując problem Wież Hanoi dla trzech dysków, musiałeś odsłonić dysk, który znajdował się na dnie, dysk 3, tak abyś mógł przenieść go z kołka A na kołek B. Aby odsłonić ten dysk, musiałeś przenieść dyski 1 i 2 z kołka A na tymczasowy kołek C:
Chwileczkę—to wygląda tak, jakbyś przeniósł dwa dyski w jednym kroku, naruszając pierwszą zasadę. Ale przecież nie przeniosłeś ich w jednym kroku. Zgodziłeś się na to, że przeniesiesz dysk 1 i 2 z dowolnego kołka na inny dowolny kołek, robiąc trzy kroki. Powyższa sytuacja pokazuje moment, który otrzymałeś po wykonaniu trzech kroków. (Przenieś dysk 1 z kołka A na kołek B; przenieś dysk 2 z kołka A na kołek C; przenieś dysk 1 z kołka B na kołek C.)
Co więcej, poprzez przeniesienie dysku 1 i 2 z kołka A na kołek C, w sposób rekurencyjny rozwiązałeś podproblem: przenieś dyski od 1 do n1 (pamiętaj, że n=3) z kołka A na kołek C. Gdy już rozwiązałeś ten podproblem, możesz przenieść dysk 3 z kołka A na kołek B:
Aby zakończyć zadanie, musiałeś rekurencyjnie rozwiązać podproblem przenoszenia dysków od 1 do n1 z koła C na kołek B. Można to znów zrobić w trzech krokach. (Przenieś dysk 1 z kołka C na kołek A; przenieś dysk 2 z kołka C na kołek B; przenieś dysk 1 z kołka A na kołek B.) I gotowe:
I—wiedziałeś, że przyjdzie czas na to pytanie—czy ważny jest fakt, na jakie kołki przenosiłeś i z jakich kołków ściągałeś dyski od 1 do 3? Mogłeś przenosić dyski z dowolnego kołka na dowolny kołek. Spójrzmy na przykład przenoszenia z kołka B na kołek C:
  • Rekurencyjnie rozwiąż podproblem przenoszenia dysków 1 i 2 z kołka B na tymczasowy kołek A. (Przenieś dysk 1 z kołka B na kołek C; przenieś dysk 2 z kołka B na kołek A; przenieś dysk 1 z kołka C na kołek A.)
  • Teraz jedynie dysk 3 znajduje się na kołku B, przenieś go na kołek C.
  • Rekurencyjnie rozwiąż podproblem przenoszenia dysków 1 i 2 z kołka A na kołek C. (Przenieś dysk 1 z kołka A na kołek B; przenieś dysk 2 z kołka A na kołek C; przenieś dysk 1 z kołka B na kołek C.)
Niezależnie od tego, jak to rozwiążesz, możesz przenieść dyski od 1 do 3 z dowolnego kołka na dowolny kołek, przenosząc dyski siedem razy. Przenosisz bowiem dyski trzy razy w każdym z dwóch rekurencyjnych rozwiązań podproblemów przenoszenia dysków 1 i 2 oraz raz przenosisz dysk 3.
A co w sytuacji, gdy n=4? Ponieważ możesz rekurencyjnie rozwiązać podproblem przenoszenia dysków od 1 do 3 z dowolnego kołka na dowolny kołek, możesz również rozwiązać zadanie dla n=4:
  • Rozwiąż rekurencyjnie podproblem przenoszenia dysków od 1 do 3 z kołka A na kołek C, przenosząc dyski siedem razy.
  • Przenieś dysk 4 z kołka A na kołek B.
  • Rekurencyjnie rozwiąż podproblem przenoszenia dysków od 1 do 3 z kołka C na kołek B, przenosząc dyski siedem razy.
W tym rozwiązaniu przenosisz dyski 15 razy (7 + 1 + 7) i - tak jak myślisz - możesz przenosić dyski od 1 do 4 z dowolnego kołka na dowolny kołek.
W tym momencie mogłeś już zauważyć dwie prawidłowości. Pierwsza: możesz rozwiązać problem Wież Hanoi rekurencyjnie. Jeśli n=1, po prostu przenosisz dysk 1. W przeciwnym przypadku, dla n2, rozwiązujesz problem w trzech następujących krokach:
  • Rekurencyjnie rozwiąż podproblem przenoszenia dysków od 1 do n1 z jakiegokolwiek kołka na dowolny kołek tymczasowy.
  • Przenieś dysk n z kołka, na którym się znajduje, na ten, na którym powinien znaleźć się na końcu.
  • Rekurencyjnie rozwiąż podproblem przenoszenia dysków od 1 do n1 z kołka tymczasowego na kołek końcowy.
Po drugie, rozwiązanie problemu z n dyskami wymaga 2n1 kroków. Sprawdziliśmy, że to prawda dla:
  • n=1 (211=1, Potrzebny jest tylko jeden ruch)
  • n=2 (221=3, potrzebne są trzy ruchy)
  • n=3 (231=7, potrzeba siedmiu ruchów)
  • n=4 (241=15, potrzeba 15 ruchów).
Rozwiązanie problemu z n1 dyskami wymaga 2n11 ruchów, po czym możesz rozwiązać problem n dysków w 2n1 ruchach. Będziesz potrzebować:
  • 2n11 kroków aby rekurencyjnie rozwiązać problem przeniesienia dysków od 1 do n1
  • 1 ruch, aby przenieść dysk n
  • 2n11 ruchów (znowu), aby przenieść dyski od 1 do n1
Jeśli dodasz liczbę kroków, otrzymasz 2n1.
Wróćmy do mnichów. Ich zadanie polega na przeniesieniu n=64 dysków, a więc będą musieli przenieść dysk 2641 razy. Mnisi są wysportowani i silni. Przenoszą jeden dysk na sekundę, w dzień i w nocy.
Ile to będzie 2641 sekund? Jeśli oszacujemy w przybliżeniu że rok ma około 365,25 dni, dostaniemy 584 542 046 090,6263 lat. Czyli 584+ miliardów lat. Nasze Słońce ma jeszcze przed sobą jakieś pięć do siedmiu miliardów lat zanim wypali się zawarty w nim wodór. Tak, nasz świat się skończy, ale nastąpi to na długo zanim mnisi dadzą radę przenieść wszystkie 64 dyski na kołek B.
Zastanawiasz się do czego jeszcze można użyć tego algorytmu, poza przewidywaniem końca świata? Oto lista na Wikipedii kilkunastu interesujących aplikacji.

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?

Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.