Wieże Hanoi

Wieże Hanoi to jeden z klasycznych problemów, z którymi musi się zmierzyć każdy początkujący programista. Legenda głosi, że na Dalekim Wschodzie mnisi przenoszą stos złotych dysków z jednego diamentowego kołka na inny (rysunek 18.10). Początkowo stos zawiera 64 dyski na jednym kołku ułożone od najmniejszego (na górze) do największego (na dole). Mnich przenosi dyski z jednego
kołka na drugi, ale przy dwóch warunkach: w danym momencie przenosi tylko jeden dysk i nie może położyć mniejszego dysku na większym. Stosuje się trzy kołki, z których jeden służy jako tymczasowy. Załóżmy, że świat się skończy, gdy mnich ukończy zadanie, więc nie chcemy wspomagać go w tych wysiłkach.

 


Rysunek 18.10. Wieże Hanoi w przypadku czterech dysków

 

Przypuśćmy, że mnich przenosi dyski z kołka 1 na kołek 3. Chcemy napisać algorytm, który wyświetli precyzyjną sekwencję każdego kolejnego przeniesienia dysku z kołka na kołek.

Jeśli spróbujemy znaleźć rozwiązanie iteracyjne, najprawdopodobniej zaplączemy się w zarządzanie dyskami. Próba zaatakowania problemu od strony rekurencyjnej szybko pozwala znaleźć rozwiązanie. Przeniesienie n dysków można potraktować jako przeniesienie tylko n – 1 dysków (rekurencja), jeśli:

1) przeniesiemy n – 1 dysków z kołka 1 na kołek 2, używając kołka 3 jako tymczasowego;
2) przeniesiemy ostatni dysk (największy) z kołka 1 na kołek 3;
3) przeniesiemy n – 1 dysków z kołka 2 na kołek 3, używając kołka 1 jako tymczasowego.

Proces kończy się zadaniem, które wymaga przeniesienia tylko jednego dysku (n = 1; przypadek bazowy). Zadanie to wykonuje się, przenosząc dysk bez korzystania z kołka tymczasowego.

Rysunek 18.11 zawiera metodę solveTowers (wiersze od 5. do 22.), który rozwiązuje problem wieży Hanoi po podaniu łącznej liczby dysków (w tym przypadku 3), kołka początkowego, kołka końcowego i kołka tymczasowego.

Przypadek bazowy (wiersze od 8. do 11.) ma miejsce, gdy należy przenieść tylko jeden dysk z kołka początkowego na końcowy. Krok rekurencyjny (wiersze od 15. do 21.) przenosi disks - 1 dysków (wiersz 15.) z pierwszego kołka (sourcePeg) na tymczasowy (tempPeg). Gdy wszystkie dyski poza jednym zostały przeniesione na kołek tymczasowy, wiersz 18. przenosi największy dysk w docelowe miejsce. Wiersz 21. kończy pozostałe kroki, wywołując metodę solveTowers, aby rekurencyjnie przeniosła disks - 1 dysków z kołka tymczasowego (tempPeg) na docelowy (destinationPeg), ale tym razem stosując pierwszy kołek (sourcePeg) jako tymczasowy. Wiersz 31. z main wywołuje rekurencyjną metodę solveTowers, która wyświetla informację o każdym przeniesieniu.

 

1 // Rysunek 18.11. TowersOfHanoi.java
2 // Rozwiązanie problemu wieży Hanoi w sposób rekurencyjny
3 public class TowersOfHanoi {
4     // Rekurencyjnie przenoś dyski między wieżami
5     public static void solveTowers(int disks, int sourcePeg,
6         int destinationPeg, int tempPeg) {
7         // Przypadek bazowy -- tylko jeden dysk do przeniesienia
8         if (disks == 1) {
9             System.out.printf("%n%d --> %d", sourcePeg, destinationPeg);
10           return;
11       }
12
13       // Krok rekurencyjny -- przeniesienie (disk - 1) dysków z sourcePeg
14       // do tempPeg przy użyciu destinationPeg
15       solveTowers(disks - 1, sourcePeg, tempPeg, destinationPeg);
16
17       // Przeniesienie ostatniego dysku z sourcePeg do destinationPeg
18       System.out.printf("%n%d --> %d", sourcePeg, destinationPeg);
19
20       // Przeniesienie (disks - 1) dysków z tempPeg do destinationPeg
21       solveTowers(disks - 1, tempPeg, destinationPeg, sourcePeg);
22    }
23
24    public static void main(String[] args) {
25        int startPeg = 1; // Wartość 1 służy do oznaczenia kołka początkowego
26        int endPeg = 3; // Wartość 3 służy do oznaczenia kołka końcowego
27        int tempPeg = 2; // Wartość 2 służy do oznaczenia kołka tymczasowego
28        int totalDisks = 3; // Liczba dysków
29
30        // Początkowe wywołanie nierekurencyjne -- przenosi wszystkie dyski
31        solveTowers(totalDisks, startPeg, endPeg, tempPeg);
32    }
33 }

 

1 --> 3
1 --> 2
3 --> 2
1 --> 3
2 --> 1
2 --> 3
1 --> 3


Rysunek 18.11. Rozwiązanie problemu wieży Hanoi w sposób rekurencyjny

 

Programowanie w Javie. Solidna wiedza w praktyce. Wydanie XI, Autorzy: Paul Deitel, Harvey Deitel, Wydawnictwo: Helion

Podobne artykuły

Podziel się ze znajomymi tym artykułem - udostępnij na FB lub wyślij e-maila korzystając z poniższych opcji:

wszystkie oferty