Wieże Hanoi
Wieże Hanoi to klasyczna łamigłówka matematyczna. Trzy pręty, stos krążków różnej wielkości i dwie ścisłe zasady: przenoś po jednym krążku i nigdy nie kładź większego krążka na mniejszym.
Trzy pręty i stożek z krążków
Plansza ma trzy pręty. Wszystkie krążki mają różne rozmiary i nasuwa się je na pręty. Na początku cały zestaw leży na jednym pręcie, ułożony według wielkości, największy na dole, a najmniejszy na górze, więc stos tworzy stożek. Celem jest przeniesienie całej wieży na inny pręt.
Trzy zasady
1. Przenoś tylko jeden krążek naraz. 2. Ruch polega na zdjęciu górnego krążka ze stosu i położeniu go na innym stosie albo na pustym pręcie. 3. Większy krążek nigdy nie może leżeć na mniejszym. Te trzy zasady to cała gra. Dzięki nim każda dozwolona pozycja jest sposobem rozdzielenia krążków między pręty tak, by każdy pręt pozostał uporządkowany.
Najkrótsze rozwiązanie to 2ⁿ − 1
Najmniejsza liczba ruchów rozwiązująca wieżę z n krążków to 2ⁿ − 1. Jeden krążek wymaga 1 ruchu. Dwa krążki wymagają 3. Trzy wymagają 7, cztery 15, a pięć 31. Każdy nowy krążek podwaja poprzednie rozwiązanie i dodaje jeden ruch, który przenosi największy krążek: jeśli n − 1 krążków wymaga T ruchów, to n krążków wymaga 2T + 1. Ta rekurencja daje dokładnie 2ⁿ − 1. Osiem krążków, największa wieża w aplikacji PictorX, wymaga 255 ruchów. Nie ma krótszej dozwolonej drogi.
Jak działa rekurencja
Aby przenieść n krążków z pręta startowego na pręt docelowy, używając pozostałego pręta jako pomocniczego: 1. Przenieś górne n − 1 krążków z pręta startowego na pręt pomocniczy. 2. Przenieś największy krążek z pręta startowego prosto na pręt docelowy. 3. Przenieś n − 1 krążków z pręta pomocniczego na pręt docelowy, na największy krążek. Krok 2 jest dozwolony, bo największy krążek może leżeć na dowolnym pręcie. Kroki 1 i 3 to ta sama łamigłówka, o jeden krążek mniejsza. Wywołanie kończy się na pojedynczym krążku, który przenosi się raz. Po rozwinięciu daje to 2ⁿ − 1 ruchów, a żaden krok nigdy nie kładzie większego krążka na mniejszym.
Legenda o 64 złotych krążkach
Francuski matematyk Édouard Lucas przedstawił łamigłówkę w 1883 roku. Dołączył do niej legendę o indyjskiej świątyni w Kashi Vishwanath, w której kapłani według tych samych zasad przenoszą stos 64 złotych krążków. Gdy wykonają ostatni ruch, mówi legenda, nastąpi koniec świata. Sześćdziesiąt cztery krążki wymagają 2⁶⁴ − 1 ruchów: 18 446 744 073 709 551 615. Przy jednym bezbłędnym ruchu na sekundę, dniem i nocą, to około 585 miliardów lat. Kapłani nie skończą.
Zagraj w PictorX
Otwórz Wieże Hanoi, a na pręcie startowym będzie już wieża z czterech krążków. Minimum to piętnaście ruchów. Przeciągnij górny krążek na inny pręt albo kliknij pręt, a potem ten, który chcesz. Klawisze 1, 2 i 3 działają tak samo. Większy krążek na mniejszym zostanie odrzucony. Krążki mają zakres od 1 do 8, więc możesz porównać 1, 3, 7, 15, 31, 63, 127 i 255 ze wzorem. Krok odtwarza jeden ruch najkrótszego rozwiązania. Rozwiąż odtwarza resztę. „Obejrzyj 3 krążki” pokazuje strategię rekurencyjną w ruchu. Cofnij i Ponów przechodzą przez twoje ruchy. Zapisz PNG albo otwórz planszę w edytorze PictorX.
Często zadawane pytania
Jakie są zasady wież Hanoi?
Przenoś po jednym krążku. Zdejmij górny krążek z pręta i połóż go na innym pręcie. Nigdy nie kładź większego krążka na mniejszym. Cała wieża zaczyna na jednym pręcie i musi skończyć na innym.
Ile ruchów wymaga najkrótsze rozwiązanie?
2ⁿ − 1. Jeden krążek to 1 ruch, dwa krążki 3, trzy 7, cztery 15, a pięć 31. Każdy dodany krążek podwaja poprzednie rozwiązanie i dodaje jeden ruch.
Kto wymyślił wieże Hanoi?
Francuski matematyk Édouard Lucas przedstawił ją w 1883 roku. Opowieść o kapłanach i 64 złotych krążkach w Kashi Vishwanath to legenda, którą dołączył do łamigłówki.
Ile trwałoby przeniesienie 64 krążków?
2⁶⁴ − 1 ruchów, czyli 18 446 744 073 709 551 615. Przy jednym ruchu na sekundę to około 585 miliardów lat.
Powiązane narzędzia
Wieże Hanoi
Przenieś w przeglądarce wieżę z krążków między trzema prętami. Po jednym krążku, nigdy większy na mniejszy. Najkrótsze rozwiązanie to 2ⁿ − 1 ruchów.
Igła Buffona
Upuszczaj igły na podłogę w linie w przeglądarce. Policz przecięcia i zobacz, jak eksperyment Buffona z 1777 roku szacuje π.
Igła Buffona
Problem igły Buffona z 1777 roku: dlaczego igła upuszczana na równoległe linie pozwala oszacować π, jak prawdopodobieństwo 2l/(πd) dla krótkiej igły wynika z pola pod sinusoidą i dlaczego eksperyment zbiega powoli.
Koła mnożenia
Połącz każdą liczbę na okręgu z jej wielokrotnością. Narysuj tabliczkę mnożenia, kardioidę lub figurę z nici na papierze, kredą albo na drewnie.
Hipoteza Collatza
Poznaj problem Collatza 3n+1 w przeglądarce. Śledź ciągi gradowe, wyhoduj geometryczne drzewo Collatza i przybliżaj ciągły fraktal Collatza.
Mrówka Langtona
Uruchom mrówkę Langtona w przeglądarce. Zobacz symetrię, chaos i autostradę o cyklu 104 kroków, a potem wypróbuj reguły wielokolorowe, kilka mrówek, siatkę sześciokątną i turmity.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Zagraj w wieże Hanoi