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 $n-1$n, minus, 1 (pamiętaj, że $n = 3$n, equals, 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 $n-1$n, minus, 1 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:

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$n, equals, 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$n, equals, 4:

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$n, equals, 1, po prostu przenosisz dysk 1. W przeciwnym przypadku, dla $n \geq 2$n, is greater than or equal to, 2, rozwiązujesz problem w trzech następujących krokach:

Po drugie, rozwiązanie problemu z $n$n dyskami wymaga $2^n - 1$2, start superscript, n, end superscript, minus, 1 kroków. Sprawdziliśmy, że to prawda dla:

Rozwiązanie problemu z $n-1$n, minus, 1 dyskami wymaga $2^{n-1} - 1$2, start superscript, n, minus, 1, end superscript, minus, 1 ruchów, po czym możesz rozwiązać problem $n$n dysków w $2^n - 1$2, start superscript, n, end superscript, minus, 1 ruchach. Będziesz potrzebować:

Jeśli dodasz liczbę kroków, otrzymasz $2^n - 1$2, start superscript, n, end superscript, minus, 1.

Wróćmy do mnichów. Ich zadanie polega na przeniesieniu $n = 64$n, equals, 64 dysków, a więc będą musieli przenieść dysk $2^{64} - 1$2, start superscript, 64, end superscript, minus, 1 razy. Mnisi są wysportowani i silni. Przenoszą jeden dysk na sekundę, w dzień i w nocy.

Ile to będzie $2^{64} - 1$2, start superscript, 64, end superscript, minus, 1 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.