Java實現經典漢諾塔問題

介紹

漢諾塔問題，是一道經典的遞歸問題，它是源於印度一個古老傳說的益智玩具。遊戲需要三個柱子和一些大小不等的圓盤，開始時所有盤子都放在一個柱子上，且按照大小順序從上到下排列好，目標是將所有盤子移動到另一個柱子上，移動過程中可以藉助第三個柱子，但每次只能移動一個盤子，而且大盤子不能放置在小盤子上面。

在本篇文章中，我們將使用Java編程語言實現這個問題。

正文

選擇數據結構

在實現漢諾塔問題時，我們可以使用棧（Stack）這種數據結構，因為棧是一種後進先出（LIFO）的數據結構，符合漢諾塔問題的要求。我們可以使用Java自帶的Stack類來實現棧的功能。

演算法思路

下面是本文實現漢諾塔問題的核心演算法：

public void move(Stack A, Stack B, Stack C, int n) {
    // 遞歸終止條件
    if (n == 1) {
        // 將A柱子的盤子移動到C柱子上
        int x = A.pop();
        C.push(x);
        System.out.println("Move " + x + " from " + A.toString() + " to " + C.toString());
    } else {
        // 將A柱子上面的n-1個盤子移動到B柱子上
        move(A, C, B, n - 1);
        // 將A柱子上最後一個盤子移動到C柱子上
        int x = A.pop();
        C.push(x);
        System.out.println("Move " + x + " from " + A.toString() + " to " + C.toString());
        // 將B柱子上的n-1個盤子移動到C柱子上
        move(B, A, C, n - 1);
    }
}

演算法思路很清晰，我們使用遞歸來處理這個問題。首先我們需要考慮遞歸終止條件——當只有一個盤子時，我們可以直接將其從A柱子移動到C柱子上；當盤子數量大於1時，我們需要將A柱子上的n-1個盤子通過C柱子移動到B柱子上，在將A柱子上最後一個盤子移動到C柱子上，最後將B柱子上的n-1個盤子通過A柱子移動到C柱子上。

完整代碼示例

import java.util.Stack;

public class HanoiTower {
    public static void main(String[] args) {
        Stack A = new Stack();
        Stack B = new Stack();
        Stack C = new Stack();
        int n = 4;
        for (int i = n; i >= 1; i--) {
            A.push(i);
        }
        move(A, B, C, n);
    }

    public static void move(Stack A, Stack B, Stack C, int n) {
        // 遞歸終止條件
        if (n == 1) {
            // 將A柱子的盤子移動到C柱子上
            int x = A.pop();
            C.push(x);
            System.out.println("Move " + x + " from " + A.toString() + " to " + C.toString());
        } else {
            // 將A柱子上面的n-1個盤子移動到B柱子上
            move(A, C, B, n - 1);
            // 將A柱子上最後一個盤子移動到C柱子上
            int x = A.pop();
            C.push(x);
            System.out.println("Move " + x + " from " + A.toString() + " to " + C.toString());
            // 將B柱子上的n-1個盤子移動到C柱子上
            move(B, A, C, n - 1);
        }
    }
}

小結

通過使用Java編程語言，我們實現了經典的漢諾塔問題。這個問題利用了遞歸的思想，同時藉助棧（Stack）這種數據結構，使得我們的程序變得更加簡潔和高效。希望大家能夠通過這個例子了解遞歸的思想，並且掌握使用Java編寫遞歸程序的基本方法。