Jak ułożyć wierze Hanoi?

Z artykułu dowiesz się jak ułożyć wierze Hanoi?

Co to jest wieża Hanoi?

Wieża Hanoi składa się z zestawu kilku krążków o różnej wielkości. Są też 3 miejsca w których te krążki mogą się znajdować. Początkowe ułożenie jest takie, że wszystkie krążki są ułożone w jednym miejscu, zgodnie z wielkością tych krążków, czyli największy na spodzie. No i naszym celem jest przemieszczenie tych krążków na inne miejsce. No i trzeba przestrzegać następujących zasad:

Zasady układania wieży Hanoi:

• W jednym momencie może być podniesiony tylko jeden krążek.
• Można podnosić jedynie te krążki, które są na szczycie
• Dozwolone jest odłożyć krążek tylko w jedno z 3 możliwych miejsc i w żadne inne
• Można położyć krążek jedynie na większym krążku, albo na pustym miejscu. Innymi słowami Nie można położyć większego krążka na mniejszym krążku.

Jak ułożyć wieże Hanoi sposobem rekurencyjnym

No to zacznijmy Analizę. Na jej potrzeby ponumerujmy sobie miejsca w których krążki mogą się znajdować – po kolei 1, 2 i 3. No i teraz ustalmy że chcemy przenieść krążki z miejsca pierwszego na miejsce drugie.

Przypadek trywialny

No i zacznijmy analizę od przypadku najprostszego, czyli takiego, gdzie mamy przełożyć tylko jeden krążek. Oczywiście jest to problem trywialny. Wystarczy przenieść ten jedyny krążek z miejsca pierwszego na drugie. Więc taką więżę jesteśmy w sanie ułożyć za pomocą tylko jednego posunięcia.

Wieża składająca się z 2 elementów

Natomiast gdy mamy dwa krążki. To problem również jest prosty, jednak musimy już wykorzystać miejsce trzecie – tam najpierw przekładamy mniejszy krążek, dzięki czemu możemy bez przeszkód przełożyć większy krążek na drugie miejsce a na końcu mniejszy krążek kładziemy na większym. No i wieża została ułożona w 3 posunięciach.

Wieża składająca się z 3 elementów

Teraz zwiększmy poziom trudności do 3 krążków. Aby móc przełożyć największy krążek na drugie miejsce, to najpierw wszystkie pozostałe krążki muszą znajdować się na miejscu trzecim. Wszystkie pozostałe krążki czyli 2 – to my przenieść na inne miejsce już umiemy. Wykorzystując tym razem miejsce drugie jako pomocnicze przenosimy je na miejsce 3. No i teraz dopiero mamy wolną drogę aby przenieść największy krążek na miejsce drugie – a ostatnim krokiem będzie przeniesienie tych 2 mniejszych krążków na drugie miejsce tym razem jako pomocnicze jest wykorzystywane miejsce pierwsze. No i gotowe – zajęło nam to dokładnie 7 posunięć. Przełożenie wieży 2 elementowej zajmuje 3 posunięcia A żeby przełożyć wieżę 3 elementową najpierw przełożyliśmy wieżę 2 elementową, następnie przełożyliśmy największy element, a później znowu przełożyliśmy wieżę 2 elementową.

Wieża o dowolnej ilości elementów

Analogicznie będziemy to robić dla większej ilości elementów. Myślę że widzisz już zarys algorytmy który możemy wykorzystać do ułożenia. Jest to algorytm rekurencyjny. Przypadkiem podstawowym jest wieża jednoelementowa, którą przekładamy bezpośrednio z miejsca w którym się znajduje na miejsce docelowe. Natomiast dla wieży składającej się z n elementów: Najpierw musimy przenieść n-1 elementów w miejsce tymczasowe, następnie największy krążek przekładamy na miejsce docelowe, a na końcu te n-1 krążków przekładamy z miejsca tymczasowego na miejsce docelowe.

Algorytm rekurencyjny

n – ilość elementów wieży Hanoi;

1. Jeśli n = 1, przełóż element z miejsca początkowego na docelowe. (przypadek podstawowy)
2. Jeśli n > 1:
   Przełóż wieżę o (n-1) elementach z miejsca początkowego na miejsce tymczasowe
   Największy element przełóż na miejsce docelowe
   Przełóż wieżę o (n-1) elementach z miejsca tymczasowego na miejsce docelowe

Kod źródłowy z odcinka:

package pl.am.analizy.hanoi;

public class WiezaHanoi {

    public static int hanoi(int rozmiar, int miejscePoczatkowe, int miejsceDocelowe) {
        if (rozmiar == 1) {
            System.out.println("[element 1] z " + miejscePoczatkowe + " na " + miejsceDocelowe);
            return 1;
        }

        int iloscPosuniec = 0;
        int miejsceTymczasowe = 6 - miejsceDocelowe - miejscePoczatkowe;
        iloscPosuniec += hanoi(rozmiar - 1, miejscePoczatkowe, miejsceTymczasowe);
        System.out.println("[element " + rozmiar + "] z " + miejscePoczatkowe + " na " + miejsceDocelowe);
        iloscPosuniec++;
        iloscPosuniec += hanoi(rozmiar - 1, miejsceTymczasowe, miejsceDocelowe);
        return iloscPosuniec;
    }

    public static void main(String[] args) {
        int iloscPosuniec = hanoi(5, 1, 2);
        int iloscPosuniec3 = hanoi(3, 1, 2);
        System.out.println("iloscPosuniec = " + iloscPosuniec);
        System.out.println("iloscPosuniec3 = " + iloscPosuniec3);
    }
}