Wieża Hanoi🗼: Klasyczne wyzwanie logiczne – przewodnik początkującego programisty💡

Wieża Hanoi (ang. Hanoi Tower). To zadanie, choć proste w swojej idei, stanowi doskonałe pole do ćwiczenia umiejętności programistycznych i logicznego myślenia. Zapraszam do zgłębienia tajemnic tej zagadki, która od ponad wieku fascynuje zarówno matematyków, jak i programistów na całym świecie.

Wieża Hanoi – wprowadzenie

Z tego materiału dowiesz się:

• Czym jest Wieża Hanoi?
• Jaką naturę ma Wieża Hanoi?
• Jak rozwiązać Wieżę Hanoi?
• Jak Wieżę Hanoi wykorzystuje się w programowaniu?

Wieża Hanoi – jaki jest problem?

Wieża Hanoi to łamigłówka, która najprawdopodobniej powstała w Azji. Natomiast w Europie rozpropagował ją francuski matematyk Édouard Lucas. Zadanie polega na przeniesieniu stosu różnej wielkości dysków z jednego słupka na inny, z wykorzystaniem trzeciego słupka jako pomocniczego, z zachowaniem zasady, że na mniejszym dysku nie może spoczywać dysk większy.

Wieża Hanoi – hierarchiczna natura

Główna zasada Wież Hanoi mówi, że żaden większy dysk nie może spoczywać na mniejszym dysku. Ta reguła wprowadza zależność między dyskami, ustalając hierarchię, w której mniejsze dyski zawsze muszą leżeć na większych, niezależnie od słupka, na którym są umieszczone. Taka organizacja wymaga od gracza strategicznego planowania i przewidywania, jak przeniesienie jednego dysku wpłynie na możliwości przeniesienia innych dysków w przyszłości

Wieża Hanoi – rozwiązanie – algorytm

Rozważmy rozwiązanie problemu dla 3 dysków.

Proces rozwiązywania Wież Hanoi może być opisany następująco:

• Przenieś n-1 dysków na słupek pomocniczy, co pozwala na odsłonięcie największego dysku.

• Przenieś najmniejszy dysk na słupek pomocniczy, a największy dysk na docelowy słupek.

• Teraz największy dysk jest już na swoim miejscu i nie będzie już więcej przenoszony.

• Przenieś n-1 dysków z pomocniczego słupka na docelowy, co kończy proces.

Każdy z tych kroków jest zależny od poprzedniego, tworząc złożoną sieć zależności, która musi być przestrzegana, aby osiągnąć cel.

Możemy obliczyć minimalną liczbę ruchów potrzebnych do rozwiązania zadania za pomocą wzoru 2ⁿ-1.

gdzie n to ilość dysków.

Wieża Hanoi – rekurencyjne podejście

W praktyce rozwiązanie Wież Hanoi opiera się na rekurencyjnym podziale problemu na mniejsze części. Rekurencyjna natura rozwiązania wiąże się bezpośrednio z zależnościami między dyskami. Na przykład, przeniesienie największego dysku (podstawy) na celowy słupek jest możliwe tylko wtedy, gdy wszystkie mniejsze dyski są już na innym, pomocniczym słupku. To z kolei wymaga rozwiązania mniejszego problemu Wież Hanoi dla tych mniejszych dysków na pomocniczym słupku.

➡ ZOBACZ 👉: Rekurencja ➿ rekursja ➿ rekurencja

Wieża Hanoi – programowanie

Gra w Wieże Hanoi nie tylko rozwija zdolności rekurencyjnego myślenia, ale także uczy strategii i planowania. Jest również świetnym wprowadzeniem do stosów w informatyce, ponieważ dyski można traktować jako elementy stosu, co dodatkowo ilustruje zasady LIFO (Last In, First Out).

➡ ZOBACZ 👉: Stos (Stack) – 7+ tajników implementacji LIFO

Wieża Hanoi – Java

Algorytm, który rozwiązuje łamigłówkę i prezentuje każdy krok rozwiązania.

class HanoiTowers {
    public static void main(String[] args) {
        int numberOfDisks = 8;
        solveHanoi(numberOfDisks, 'A', 'C', 'B');
    }
    public static void solveHanoi(int disk, char start, char end, char auxiliary) {
        if (disk == 1) {
            System.out.println("Przenieś dysk 1 z " + start + " na " + end);
            return;
        }
        solveHanoi(disk - 1, start, auxiliary, end);
        System.out.println("Przenieś dysk " + disk + " z " + start + " na " + end);
        solveHanoi(disk - 1, auxiliary, end, start);
    }
}

Funkcja solveHanoi() Jest to rekurencyjna funkcja, która rozwiązuje problem Wież Hanoi. Przyjmuje cztery parametry: liczbę dysków (disk), oraz oznaczenia słupków: startowego (start), docelowego (end) i pomocniczego (auxiliary). Jeśli jest tylko jeden dysk, funkcja po prostu przenosi dysk bezpośrednio z słupka startowego na docelowy i kończy działanie. W przeciwnym razie przenosi dyski zgodnie z wcześniej omówionymi zasadami.

Kiedy uruchomisz ten program, wyświetlą się instrukcje na konsoli, które pokazują dokładną kolejność ruchów potrzebną do rozwiązania łamigłówki Wież Hanoi dla określonej liczby dysków. Możesz łatwo zmieniać liczbę dysków, modyfikując wartość zmiennej numberOfDisks w funkcji main().

Wieża Hanoi – wizualizacja

Jeśli kod powyżej jest dla Ciebie niewystarczający, to sprawdź rozwiązanie, które dodatkowo wizualizuje w konsoli położenie dysków w trakcie rozwiązywania zadania.

class VisualHanoi {
    private static Stack<Integer>[] towers = new Stack[3];

    public static void main(String[] args) {
        int numberOfDisks = 3;  // Ustaw liczbę dysków tutaj
        setupTowers(numberOfDisks);
        printTowers();
        solveHanoi(numberOfDisks, 0, 2, 1);
    }

    private static void setupTowers(int disks) {
        for (int i = 0; i < 3; i++) {
            towers[i] = new Stack<>();
        }
        for (int disk = disks; disk > 0; disk--) {
            towers[0].push(disk);
        }
    }

    private static void solveHanoi(int disk, int start, int end, int auxiliary) {
        if (disk == 1) {
            towers[end].push(towers[start].pop());
            System.out.println("Przenieś dysk 1 z " + (char) ('A' + start) + " na " + (char) ('A' + end));
            printTowers();
            return;
        }
        solveHanoi(disk - 1, start, auxiliary, end);
        towers[end].push(towers[start].pop());
        System.out.println("Przenieś dysk " + disk + " z " + (char) ('A' + start) + " na " + (char) ('A' + end));
        printTowers();
        solveHanoi(disk - 1, auxiliary, end, start);
    }

    private static void printTowers() {
        System.out.println("A Tower: " + towers[0] + " B Tower: " + towers[1] + " C Tower: " + towers[2]);
        System.out.println("-------------------");
    }
}

UWAGA! Ostrożnie z ilością dysków, no chyba że masz całą wieczność. 🙃

Wieża Hanoi – zastosowanie

Problem Wież Hanoi znajduje zastosowanie w nauce o algorytmach, teorii gier, a nawet w psychologii, badając sposób, w jaki ludzie i maszyny podejmują sekwencyjne decyzje. Powiązany jest również z takimi koncepcjami, jak algorytmy sortowania, przeszukiwanie przestrzeni stanów oraz algorytmy planowania.

Wieża Hanoi – ciekawostka

Rozwiązanie łamigłówki staje się coraz trudniejsze wraz ze wzrostem ilości dysków. W zasadzie nie tyle trudniejsze ponieważ sekwencja ruchów się nie zmienia, co bardziej czasochłonne. Przełożenie wieży z 8 dyskami, zajmuje około 7 minut. Gdy zwiększymy ilość dysków do 30, i poświęcilibyśmy tylko jedną sekundę na przełożenie każdego dysku, zajęłoby nam to 33 lata.

Wieża Hanoi – podsumowanie

Wieża Hanoi to znakomity przykład na to, jak prosty problem matematyczny może być użyty do nauczania kluczowych pojęć informatycznych i programistycznych. Przez próbę rozwiązania tej zagadki, programiści mogą nauczyć się nie tylko rekurencji i stosów, ale również sposobów optymalizacji i efektywnego rozwiązywania problemów. Uczy metody podziału problemów na mniejsze, co jest fundamentalną umiejętnością w programowaniu i inżynierii. Uczy również zarządzania zasobami i przestrzegania określonych ograniczeń, co ma zastosowanie w projektowaniu algorytmów, optymalizacji systemów i wielu innych dziedzinach technicznych.