JavaSE遞迴求解漢諾塔問題的思路與方法

2022-08-03 14:03:36

1. 漢諾塔的介紹和玩法

漢諾塔（Tower of Hanoi），又稱河內塔，是一個源於印度古老傳說的益智玩具。

一共有3根柱子（A、B、C），A柱子由下到上放著由大到小的盤子，我們需要將A柱子上的盤子移到C柱子上，每次只能移動一個盤子，且在任意一次移動中，大盤子都必須處於小盤子下方。

2. 漢諾塔問題的思路

若A柱子上只有1個盤子，只需要移動1步：A->C

若A柱子上有2個盤子，需要移動3步：A->B,A->C,B->C

此時需要藉助B柱子，才能將A柱子的盤子移到C柱子上。

那麼若A柱子上有3個盤子，會怎麼移動呢？

思路：此時，A為起始位置，B為中轉位置，C為最終位置。我們需要將A柱子最上面的兩個盤子先想辦法移到中轉位置B柱子上，然後將A柱子最下面的那個盤子移動到C柱子上，最後再將B柱子上面的盤子想辦法移動到C柱子上。

將A柱子最上面的兩個盤子想辦法移到B柱子上：那對於這兩個盤子來說，A是起始位置，B是最終位置，C是中轉位置，需要藉助C將A上的兩個盤子移動到B上。具體移法：要先將A柱子最上面的一個盤子移動到中轉位置C上，然後將A柱子上下面那個盤子移到最終位置B柱子上，最後將C柱子上的盤子移到B柱子上。

將B柱子上面的盤子想辦法移動到C柱子上：那對於B柱子上的這兩個盤子來說，B為起始位置，A為中轉位置，C為最終位置，需要藉助A將B上的兩個盤子移動到C上。具體移法：要先將B柱子最上面的一個盤子移動到中轉位置A上，然後將B柱子上下面那個盤子移到最終位置C柱子上，最後將A柱子上的盤子移到C柱子上。

所以，最終三個盤子的移動路徑是 A->C,A->B,C->B,A->C,B->A,B->C,A->C，需要移動7步

網上找的動圖，更易於理解

那麼A柱子上有n個盤子時，該怎麼移動呢？

以此類推，先將A柱子上面n-1個盤子想辦法移到B柱子上，然後將A柱子上最後一個盤子移動到C柱子上，最終再將B柱子上的n-1個盤子想辦法移到C柱子上。 想辦法：其實就是柱子上有n-1個盤子，該怎麼移動這個問題。

所以漢諾塔問題用遞迴實現最好解決。

3. 用遞迴的程式碼實現

public class HanoiGame {
/*
* 第一個引數用來放給的盤子數，
 *第二個引數用來放起始位置
 *第三個引數用來放中轉位置
 *第四個引數用來放最終位置
 * */
    public static void hanoi(int n,char pose1,char pose2,char pose3){ // 3 'A' 'B' 'C'
        if(n == 1){
            move(pose1,pose3);//若只有一個盤子，只需從起始位置移到最終位置這1步。
            // 這裡的pose1不一定等於'A',pose3不一定等於'C'；隨著遞的次數的不一樣，對應不同的值。
            return;
        }
        hanoi(n-1,pose1,pose3,pose2);//這n-1個盤子是要藉助 C 移動到 B 上的。
               //所以 對於這n-1個盤子來說，起始位置是'A'，中轉位置是'C',最終位置是'B'
        move(pose1,pose3);
        hanoi(n-1,pose2,pose1,pose3);
 
    }
    /*
    * 第一個引數用來放起始位置
    * 第二個引數用來放最終位置 */
    public static void move(char pose4,char pose5){
        System.out.println(pose4+" -> "+ pose5);
 
    }
    public static void main(String[] args) {
        hanoi(3,'A','B','C');
    }
}

總結

到此這篇關於JavaSE遞迴求解漢諾塔問題的思路與方法的文章就介紹到這了,更多相關JavaSE遞迴求解漢諾塔內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

JavaSE遞迴求解漢諾塔問題的思路與方法

目錄

1. 漢諾塔的介紹和玩法

2. 漢諾塔問題的思路

3. 用遞迴的程式碼實現

總結

熱門文章