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.
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 --> 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
