Wieże Hanoi

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
Rozwiązanie łamigłówki dla czterech krążków

Wieże Hanoiproblem 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[edytuj | edytuj kod]

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: Wszechświat ma około 13,7 mld lat.

Algorytm[edytuj | edytuj kod]

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[edytuj | edytuj kod]

Algorytm rekurencyjny składa się z następujących kroków:

  1. przenieś (rekurencyjnie) krążków ze słupka A na słupek B posługując się słupkiem C,
  2. przenieś jeden krążek ze słupka A na słupek C,
  3. przenieś (rekurencyjnie) krążków ze słupka B na słupek C posługując się słupkiem A

Przykładowe implementacje

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)
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
#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;
}
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[edytuj | edytuj kod]

Algorytm iteracyjny składa się z następujących kroków:

  1. przenieś najmniejszy krążek na kolejny (*) słupek,
  2. wykonaj jedyny możliwy do wykonania ruch, nie zmieniając położenia krążka najmniejszego,
  3. 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[edytuj | edytuj kod]

Równanie określające liczbę ruchów potrzebnych do rozwiązania problemu wież Hanoi dla krążków:

Dowód[edytuj | edytuj kod]

Ł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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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.

Hanoi przy dowolnym układzie krążków. Jaki jest pierwszy ruch?

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ż[edytuj | edytuj kod]

Przypisy[edytuj | edytuj kod]

  1. Wieże Hanoi (pol. • ang. • niem.). 1999-08-21. [dostęp 2020-01-08].

Linki zewnętrzne[edytuj | edytuj kod]