algorytm.org

Problem wież Hanoi

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Problem wież Hanoi
Ocena użytkowników:***** / 40
SłabyŚwietny 
Wpisany przez Piotr Łabudziński, 17 listopada 2005 20:38

Wieże Hanoi – dane mamy krążki o różnych średnicach, ułożonych na sobie od najmniejszego do największego. Problem polega na odbudowaniu (przeniesieniu wszystkich klocków wieży na ostatni palik), z zachowaniem kształtu, wieży składającej się z kolistych klocków o różnych średnicach. Na raz można przenosić tylko jeden krążek. Podczas przekładania wolno się posługiwać buforem, reprezentowanym przez dodatkową podstawkę na klocki, przy ogólnym założeniu, że nie można kłaść klocka o większej średnicy na mniejszy.
Zagadka ta wywodzi się z Tybetańskiej legendy, według której mnisi rozwiązują tą łamigłówkę dla 64 krążków. Legenda mówi, że gdy mnisi zakończą zadanie, nastąpi koniec świata.

Na początek proponuje zapoznać się z algorytmem dla 1,2 i 3-ch krążków, aby następnie można było wyprowadzić sobie algorytm na N ilość krążków.
  • Problem dla 1 krążka:
    Problem dla jednego krazka

  • Dla 2 krążków:
    Problem dla dwóch krazków

  • Dla 3 krążków:
    rozwiązanie dla 3 krążków składa się z 7 ruchów:
    kolejne etapy to:
    • przenieś krążek o najmniejszej średnicy na palik docelowy,
    • krążek o średnicy większej przenieś na palik pomocniczy,
    • krążek najmniejszy przenieś na palik pomocniczy,
    • następnie krążek największy przenieś na palik docelowy a najmniejszy na źródłowy,
    • na największym połóż średni i potem najmniejszy,
    • koniec


  • Rozwiązanie dla N elementów:
    Cały problem przeniesienia krążków hanoi przy uzyciu 3 palików składa się z trzech podstawowych "kawałków":
    • przenieś N-1 górnych krążków z palika początkowego na palik pomocniczy,
    • przenieś N-ty krążek na palik docelowy,
    • przenieś N-1 górnych krążków z palika pomocniczego na docelowy.

Jak widać problem wież hanoi jest problemem, w którym liczba kroków rośnie wykładniczo w zależności od liczby krążków do przełożenia.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 24
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 8
Tomasz LubińskiJava
.java
.java
***** / 6
Łukasz KominekPython
.py
.py
***** / 2
Łukasz KominekPythonKrótsza wersja.
.py
.py
***** / 1
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 09 czerwca 2011 21:09
Komentarze
photo
-2 # kominekl 2013-02-23 13:42
Cytat:
Zagadka ta wywodzi się z Tybetańskiej legendy, według której mnisi rozwiązują tą łamigłówkę dla 64 krążków. Legenda mówi, że gdy mnisi zakończą zadanie, nastąpi koniec świata.


Legenda ta została zmyślona o ile się nie mylę przez Lucas`a.

Cytat:
Jak widać problem wież hanoi jest problemem, w którym liczba kroków rośnie wykładniczo w zależności od liczby krążków do przełożenia.


No tak. Najmniejsza liczba wymaganych ruchów wynosi 2 do potęgi n-1 [2^(n-1)], przy czym n jest liczbą krążków.

Cytat:
Komentarz reasumacyjny.


Brakuje mi tu informacji o zastosowaniach problemu, ale ogólnie ciekawie przedstawiony zarys problemu ;) . Ode mnie dorzucam implementację w Python ;) .
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # Kato 2013-05-14 17:49
No tak. Najmniejsza liczba wymaganych ruchów wynosi 2 do potęgi n-1 [2^(n-1)], przy czym n jest liczbą krążków.

Raczej 2 do potęgi n minus 1 tzn. (2^n)-1
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz