Java實現漢諾塔算法

一、什麼是漢諾塔？

漢諾塔是一種數學問題，同時也是一種益智遊戲。其規則如下：

將所有的盤子從起點柱子移動到目標柱子，每次只能移動一個盤子，並且大盤子不能放在小盤子上面。起始柱子上的盤子按大小順序由下到上依次編號為1至n，目標柱子上無盤子。

二、算法思路

假設有三個柱子分別為A、B、C，現在要從A柱子上將n個盤子移至C柱子，那麼漢諾塔算法的解題步驟如下：

Step1： 將A柱子上編號為1至n-1的盤子移動至B柱子，此時空出A柱子的最底下一個盤子。

Step2： 將A柱子上編號為n的盤子移動至C柱子，此時A柱子上無盤子。

Step3： 將B柱子上編號為1至n-1的盤子移動至C柱子，此時漢諾塔遊戲成功結束。

以上便是漢諾塔問題求解的遞歸思路。接下來，我們將這個思路用Java語言實現。

三、Java代碼實現

public class HanoiTower {
    public static void hanoi(int n, char A, char B, char C) {
        if (n == 1) {//遞歸出口：只有一個盤子的情況
            System.out.println(A + "->" + C);
            return;
        }
        hanoi(n - 1, A, C, B);//Step1
        System.out.println(A + "->" + C);//Step2
        hanoi(n - 1, B, A, C);//Step3
    }
    public static void main(String[] args) {
        int n = 3;//漢諾塔的盤子數量
        hanoi(n, 'A', 'B', 'C');
    }
}

四、程序演示

運行上述代碼，可以得到如下輸出結果：

A->C

A->B

C->B

A->C

B->A

B->C

A->C

五、優化思路

當盤子數較大時，遞歸代碼的執行效率較低。為了提高程序的效率，可以使用非遞歸方式實現漢諾塔算法。具體方法為：

Step1： 直接將A柱子上編號為1至n的盤子移動至C柱子，此時A柱子上無盤子，B柱子是備用柱子。

Step2： 當n為奇數時，將B柱子作為中間柱子，依次將C柱子上編號為1至n的奇數盤子（從C柱子底部開始）移動至B柱子，再將A柱子上編號為1至n的偶數盤子依次移動至C柱子，最後將B柱子上的所有盤子依次移動至C柱子。當n為偶數時，將A柱子作為中間柱子，重複以上操作。

以上方法可以通過棧數據結構實現，具體實現方式可參考下方代碼：

import java.util.Stack;

public class HanoiTower {
    static Stack s1 = new Stack();//表示A柱子
    static Stack s2 = new Stack();//表示B柱子
    static Stack s3 = new Stack();//表示C柱子
    
    public static void main(String[] args) {
        int n = 3;//漢諾塔的盤子數量
        for (int i = n; i >= 1; i--) {
            s1.push(i);//向A柱子中壓入n個圓盤
        }
        hanoi(n);//移動n個盤子
    }

    public static void hanoi(int n) {
        int from = 1;//表示起始塔
        int to = 3;//表示目標塔
        if (n % 2 == 0) {
            to = 2;//當n為偶數時，將B柱子作為中間柱子
        }
        int mid = 6 - from - to;//表示中間塔
        int count = 0;//用於計數
        boolean isUp = true;//用於表示彈出的盤子是否向上
        while (s3.size() < n) {//當C柱子上的盤子數量不足n時
            if (isUp) {//彈出A或B柱子的棧頂元素向上
                int x;
                if (!s1.empty() && (s2.empty() || s1.peek() < s2.peek())) {
                    x = s1.pop();//從A柱子彈出元素
                    System.out.println("Move " + x + " from " + from + " to " + to);
                    s2.push(x);//將元素壓入B柱子
                    if (s3.size() == n) {//當圓盤全部移動到C柱子上時，退出循環
                        break;
                    }
                } else if (!s2.empty() && (s1.empty() || s2.peek() < s1.peek())) {
                    x = s2.pop();//從B柱子彈出元素
                    System.out.println("Move " + x + " from " + (from + 1) % 3 + " to " + to);
                    s1.push(x);//將元素壓入A柱子
                    if (s3.size() == n) {//當圓盤全部移動到C柱子上時，退出循環
                        break;
                    }
                }
                count++;//計數器加1
                if (count == n) {//當計數器值為n時，改變彈出元素的方向
                    isUp = false;
                }
            } else {//彈出C柱子的棧頂元素向下
                int x;
                if (!s1.empty() && (s3.empty() || s1.peek() < s3.peek())) {
                    x = s1.pop();//從A柱子彈出元素
                    System.out.println("Move " + x + " from " + from + " to " + mid);
                    s3.push(x);//將元素壓入C柱子
                } else if (!s3.empty() && (s1.empty() || s3.peek() < s1.peek())) {
                    x = s3.pop();//從C柱子彈出元素
                    System.out.println("Move " + x + " from " + to + " to " + from);
                    s1.push(x);//將元素壓入A柱子
                }
                count--;//計數器減1
            }
        }
    }
}

六、總結

漢諾塔算法作為一種數學問題和益智遊戲，可以啟發人們思考和鍛煉邏輯思維能力。在Java語言中，漢諾塔算法可以通過遞歸和非遞歸方式實現，並且非遞歸方式能夠有效提高程序的執行效率。