right|frame|Rozwiązanie łamigłówki dla czterech krążków Wieże Hanoi – problem polegający na odbudowaniu, z zachowaniem kształtu, wieży z krążków o różnych średnicach (popularna układanka), przy czym podczas przekładania wolno się posługiwać buforem (reprezentowanym w tym przypadku przez dodatkowy słupek), jednak przy ogólnym założeniu, że nie wolno kłaść krążka o większej średnicy na mniejszy ani przekładać kilku krążków jednocześnie. Jest to przykład zadania, którego złożoność obliczeniowa wzrasta niezwykle szybko w miarę zwiększania parametru wejściowego, tj. liczby elementów wieży.
Pochodzenie Zagadka wież Hanoi powstała prawdopodobnie w Azji Wschodniej w XIX wieku lub wcześniej. Krążki były ceramiczne, produkowane w Chinach, Japonii i Wietnamie. Gra ta została sprowadzona na Zachód po raz pierwszy przez francuskiego matematyka Édouarda Lucasa w 1883 roku. Do sprzedawanego zestawu dołączona była tybetańska legenda, według której mnisi w świątyni Brahmy rozwiązują tę łamigłówkę dla 64 złotych krążków. Legenda mówi, że gdy mnisi zakończą zadanie, nastąpi koniec świata. Zakładając, że wykonują 1 ruch na sekundę, ułożenie wieży zajmie 264 −1 = 18 446 744 073 709 551 615 (blisko 18 i pół tryliona) sekund, czyli około 584,6 miliardów lat. Dla porównania: od Wielkiego Wybuchu minęło około 14 mld lat.
Algorytm thumb|300px|Od lewej: słupek A z całą wieżą, pusty słupek B pełniący rolę bufora i pusty słupek docelowy C Wieże Hanoi można łatwo rozwiązać za pomocą prostego algorytmu rekurencyjnego lub iteracyjnego. Oznaczmy kolejne słupki literami A, B i C. Niech będzie liczbą krążków, które chcemy przenieść ze słupka A na słupek C posługując się słupkiem B jako buforem.
Rozwiązanie rekurencyjne Algorytm rekurencyjny składa się z następujących kroków: przenieś (rekurencyjnie) krążków ze słupka A na słupek B posługując się słupkiem C, przenieś jeden krążek ze słupka A na słupek C, przenieś (rekurencyjnie) krążków ze słupka B na słupek C posługując się słupkiem A
Przykładowe implementacje w Pythonie: def hanoi(n:int, A:list, B:list, C:list): """słupki A, B, C są listami""" if n > 0: hanoi(n-1, A, C, B) C.insert(0, A.pop(0)) hanoi(n-1, B, A, C)
w Elixirze: defmodule Hanoi do # Jeśli brak krążków -> wszystko ok, nic nie trzeba robić def hanoi(0, _, _, _), do: :ok
# Jeśli jeden krążek -> przełożyć na docelowy słupek def hanoi(1, a, _, c) do IO.puts "#{a}->#{c}" end
# Więcej niż jeden -> rozwiąż rekurencyjnie def hanoi(n, a, b, c) do hanoi(n-1, a, c, b) hanoi(1, a, b, c) hanoi(n-1, b, a, c) end end
w C++: #include <iostream> using namespace std;
void hanoi(int n, char A, char B, char C) { // przekłada n krążków z A korzystając z B na C if (n > 0)
hanoi(n-1, A, C, B); cout << A << " -> " << C << endl; hanoi(n-1, B, A, C);
int main(int argc, char *argv[]) { hanoi(3, 'A', 'B', 'C'); return 0; }
w C#: using System;
namespace Hanoi { public class WiezeHanoi
// przekłada n krążków z A, korzystając z B, na C static void Hanoi(int n, char A, char B, char C)
if(n > 0)
Hanoi(n - 1, A, C, B); Console.WriteLine("\t{0} -> {1}", A, C); Hanoi(n - 1, B, A, C);
static void Main()
Console.WriteLine("Wieże Hanoi\n"); Console.WriteLine("Algorytm przełożenia trzech krążków z wieży A na wieżę C z wykorzystaniem wieży B\n"); Hanoi(3, 'A', 'B', 'C'); Console.WriteLine("Naciśnij dowolny klawisz..."); Console.ReadKey();
Algorytm rozwiązywania wież Hanoi jest klasycznym przykładem algorytmu rekurencyjnego używanego w nauczaniu informatyki.
Rozwiązanie iteracyjne Algorytm iteracyjny składa się z następujących kroków: przenieś najmniejszy krążek na kolejny (*) słupek, wykonaj jedyny możliwy do wykonania ruch, nie zmieniając położenia krążka najmniejszego, powtarzaj punkty 1 i 2, aż do odpowiedniego ułożenia wszystkich krążków.
(*) Kolejny słupek wyznaczamy w zależności od liczby krążków. Jeśli liczba krążków jest parzysta, kolejnym słupkiem jest ten po prawej stronie (gdy dojdziemy do słupka C w następnym ruchu używamy słupka A). Natomiast jeśli liczba krążków jest nieparzysta, kolejnym słupkiem jest ten po lewej stronie (gdy dojdziemy do słupka A w następnym ruchu używamy słupka C).
Najmniejsza liczba wymaganych ruchów Równanie określające liczbę ruchów potrzebnych do rozwiązania problemu wież Hanoi dla krążków:
Dowód Łatwo pokazać, że w pierwszym kroku przekładamy krążków na jeden słupek (bez straty ogólności załóżmy, że jest to krążek nr 3) – wymaga to co najmniej ruchów przekładamy -ty krążek na drugi słupek – wymaga to jednego ruchu przekładamy pozostałe krążki ze słupka 3. na -ty krążek leżący na 2. słupku – wymaga to co najmniej ruchów
a więc
Aby wykazać, że można przeprowadzić poniższe rozumowanie.
Aby móc ruszyć -ty krążek, trzeba najpierw zdjąć wszystkie leżące na nim krążki, tak by po ich zdjęciu jeden ze słupków pozostał wolny (aby na jego „dno” mógł trafić -ty krążek). A więc ze słupka 1 przekładamy krążki na słupek 3. Ponieważ aż do momentu gdy na drążku 1 pozostanie tylko -ty krążek nie ma znaczenia czy rzeczywiście się on tam znajduje, a więc do tego momentu sytuacja upraszcza się do rozwiązania problemu wież Hanoi dla krążków (którego minimalna liczba ruchów wynosi ). Na przełożenie krążka -tego potrzeba co najmniej jeden ruch. Po jego przełożeniu znów potrzeba przełożyć krążki – jest to oczywiście znów sytuacja krążków (wymagająca co najmniej ruchów).
A więc
co w połączeniu z górnym ograniczeniem na daje równość
Postać jawna wzoru na liczbę ruchów Powyższe równanie rekurencyjne można w łatwy sposób przekształcić do postaci jawnej, tj. nie korzystającej z rekursji:
Niech
Wtedy
jest to równanie określające ciąg geometryczny o ilorazie równym 2 takie, że
Po powrocie do otrzymujemy
Zastosowanie Mimo swojego wieku łamigłówka jest stale tematem prac matematyków i znane są jej bardziej rozbudowane wersje np. z więcej niż trzema słupkami.
Bardziej wymagająca myślenia wersja polega na znalezieniu najkrótszej drogi do ułożenia przypadkowo ułożonych krążków na wyznaczony stos. Takie zadanie przypomina sytuację mnicha, który kontynuuje układanie stosu w miejscu, w którym jego poprzednik przerwał.
W psychologii łamigłówka ta jest jednym z testów na kojarzenie.
Zobacz też
kod Graya rekurencja stos
Przypisy
Linki zewnętrzne
Gra Wieże Hanoi – online w trzech językach
Grant Sanderson, Binary, Hanoi and Sierpinski , kanał 3blue1brown na YouTube, 25 listopada 2016 [dostęp 2021-03-15].
Kategoria:Układanki Kategoria:Teoria obliczeń Kategoria:Automaty komórkowe Kategoria:Gry Kategoria:Rekurencja