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 n, minus, 1 (pamiętaj, że 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, 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:
- 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, 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, equals, 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, equals, 1, po prostu przenosisz dysk 1. W przeciwnym przypadku, dla n, is greater than or equal to, 2, rozwiązujesz problem w trzech następujących krokach:
- Rekurencyjnie rozwiąż podproblem przenoszenia dysków od 1 do n, minus, 1 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 n, minus, 1 z kołka tymczasowego na kołek końcowy.
Po drugie, rozwiązanie problemu z n dyskami wymaga 2, start superscript, n, end superscript, minus, 1 kroków. Sprawdziliśmy, że to prawda dla:
- n, equals, 1 (2, start superscript, 1, end superscript, minus, 1, equals, 1, Potrzebny jest tylko jeden ruch)
- n, equals, 2 (2, squared, minus, 1, equals, 3, potrzebne są trzy ruchy)
- n, equals, 3 (2, cubed, minus, 1, equals, 7, potrzeba siedmiu ruchów)
- n, equals, 4 (2, start superscript, 4, end superscript, minus, 1, equals, 15, potrzeba 15 ruchów).
Rozwiązanie problemu z n, minus, 1 dyskami wymaga 2, start superscript, n, minus, 1, end superscript, minus, 1 ruchów, po czym możesz rozwiązać problem n dysków w 2, start superscript, n, end superscript, minus, 1 ruchach. Będziesz potrzebować:
- 2, start superscript, n, minus, 1, end superscript, minus, 1 kroków aby rekurencyjnie rozwiązać problem przeniesienia dysków od 1 do n, minus, 1
- 1 ruch, aby przenieść dysk n
- 2, start superscript, n, minus, 1, end superscript, minus, 1 ruchów (znowu), aby przenieść dyski od 1 do n, minus, 1
Jeśli dodasz liczbę kroków, otrzymasz 2, start superscript, n, end superscript, minus, 1.
Wróćmy do mnichów. Ich zadanie polega na przeniesieniu n, equals, 64 dysków, a więc będą musieli przenieść dysk 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, 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.
Chcesz dołączyć do dyskusji?
- kiedy Xayoo w Lekko Nie Bedzie(5 głosów)