Żeby przenieść n krążków, musisz najpierw odsunąć górne n − 1, potem przenieść największy krążek raz, a następnie ułożyć tamte n − 1 z powrotem na nim. Zatem M(n) = 2M(n − 1) + 1 przy M(1) = 1, co rozwiązuje się do 2ⁿ − 1: osiem krążków wymaga 255 ruchów, a trzy 7, na pierwszych dwóch linkach. 255 będzie znajome każdemu, kto czyta rozmiary pamięci — to największa wartość, jaką mieści bajt bez znaku, dokładnie z tego powodu.
Wersja Lucasa miała sześćdziesiąt cztery złote krążki i przepowiednię, że świat skończy się, gdy stos zostanie przeniesiony. Przy jednym ruchu na sekundę to 2⁶⁴ − 1 = 1.844674407371⋅10+19 ruchów (trzeci link), około 585 miliardów lat, ponad czterdzieści razy wiek wszechświata — a łamigłówka z ośmioma krążkami przed tobą zajmuje półtorej minuty. To samo podwajanie, które czyni mały przypadek trywialnym, czyni duży geologicznym, i na tym polega cały sens wykładniczości: 255 i 1.844674407371⋅10+19 to ta sama reguła, oddalona o sześćdziesiąt podwojeń.
Odpowiedź
255
Jak to czytać
2⁸ − 1 na warsztacie. Drugi link to trzy krążki; trzeci to liczba dla sześćdziesięciu czterech krążków, która kończy świat.
Źródło
Édouard Lucas marketed the Tower of Hanoi in 1883 as the towers of Brahma at Benares; the minimum for n disks is 2ⁿ − 1, forced by the recurrence M(n) = 2M(n − 1) + 1
Rozwiąż w kalkulatorze
Te linki otwierają właściwy kalkulator z już wpisanymi liczbami tego zadania. Powyższa linia to to, co powinien pokazać ekran — sprawdź sam.