Tower of Hanoi
Move all discs from the first peg to the last peg. You can only move one disc at a time, and a larger disc can never go on top of a smaller one.
FAQ
Wieża Hanoi to matematyczna łamigłówka z krążkami ułożonymi według rozmiaru na jednym słupku. Przesuń wszystkie krążki na inny słupek, po jednym na raz, nigdy nie kładąc większego krążka na mniejszym.
Minimalna liczba ruchów dla n krążków to 2^n - 1. Więc 3 krążki potrzebują 7 ruchów, 5 krążków — 31, a 7 krążków — 127. Łamigłówka rośnie wykładniczo trudniej.
Francuski matematyk Édouard Lucas wynalazł tę łamigłówkę w 1883 roku. Stworzył legendę o mnichach przesuwających 64 złote krążki, twierdząc, że świat skończy się, gdy ukończą (zajęłoby to 585 miliardów lat).
About this test
Wieża Hanoi to klasyczna łamigłówka matematyczna wynaleziona w 1883 roku. Demonstruje wzrost wykładniczy i rekurencyjne rozwiązywanie problemów w namacalny, satysfakcjonujący sposób.
Jak to działa
Przesuń stos krążków ze słupka startowego na docelowy. Możesz przesuwać tylko jeden krążek na raz i żaden krążek nie może być położony na mniejszym. Rozwiąż to w minimalnej liczbie ruchów.
Algorytm
Rozwiązanie jest z natury rekurencyjne: by przenieść n krążków, najpierw przenieś n-1 krążków na zapasowy słupek, przenieś dolny krążek na cel, a następnie przenieś n-1 krążków z zapasowego na cel.
Wskazówki
- Zawsze przesuwaj najmniejszy krążek na kolejny słupek w konsekwentnym kierunku
- Minimalne rozwiązanie polega na naprzemiennym przesuwaniu najmniejszego krążka i wykonywaniu jedynego innego legalnego ruchu
- Zacznij od 3 krążków, by poznać wzorzec