Wieże Hanoi
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
edytujZagadka 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
edytujWież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
edytujAlgorytm 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
edytujAlgorytm 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
edytujRównanie określające liczbę ruchów potrzebnych do rozwiązania problemu wież Hanoi dla krążków:
Dowód
edytujŁ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
edytujPowyż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
edytujMimo 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ł.[1]
W psychologii łamigłówka ta jest jednym z testów na kojarzenie.
Zobacz też
edytujPrzypisy
edytuj- ↑ Wieże Hanoi. 1999-08-21. [dostęp 2020-01-08]. (pol. • ang. • niem.).
Linki zewnętrzne
edytuj- Joanna Jaszuńska , Wieże Hanoi, „Delta”, luty 2016, ISSN 0137-3005 [dostęp 2024-10-30] .
- Gra Wieże Hanoi – online w trzech językach
- Eric W. Weisstein , Tower of Hanoi, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12] (ang.).
- Grant Sanderson, Binary, Hanoi and Sierpinski (ang.), kanał 3blue1brown na YouTube, 25 listopada 2016 [dostęp 2021-03-15].