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

更新時間：2022年08月03日 11:26:46 作者：渡上舟(每天都要堅持學(xué)習(xí)鴨)

遞歸是一種非常重要的算法思想,無論你是前端開發(fā),還是后端開發(fā),都需要掌握它,下面這篇文章主要給給大家介紹了關(guān)于JavaSE遞歸求解漢諾塔問題的思路與方法,文中通過實例代碼介紹的非常詳細(xì),需要的朋友可以參考下

1. 漢諾塔的介紹和玩法

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

一共有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為中轉(zhuǎn)位置，C為最終位置。我們需要將A柱子最上面的兩個盤子先想辦法移到中轉(zhuǎn)位置B柱子上，然后將A柱子最下面的那個盤子移動到C柱子上，最后再將B柱子上面的盤子想辦法移動到C柱子上。

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

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

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

網(wǎng)上找的動圖，更易于理解

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

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

所以漢諾塔問題用遞歸實現(xiàn)最好解決。

3. 用遞歸的代碼實現(xiàn)

public class HanoiGame {
/*
* 第一個參數(shù)用來放給的盤子數(shù)，
 *第二個參數(shù)用來放起始位置
 *第三個參數(shù)用來放中轉(zhuǎn)位置
 *第四個參數(shù)用來放最終位置
 * */
    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'；隨著遞的次數(shù)的不一樣，對應(yīng)不同的值。
            return;
        }
        hanoi(n-1,pose1,pose3,pose2);//這n-1個盤子是要借助 C 移動到 B 上的。
               //所以 對于這n-1個盤子來說，起始位置是'A'，中轉(zhuǎn)位置是'C',最終位置是'B'
        move(pose1,pose3);
        hanoi(n-1,pose2,pose1,pose3);
 
    }
    /*
    * 第一個參數(shù)用來放起始位置
    * 第二個參數(shù)用來放最終位置 */
    public static void move(char pose4,char pose5){
        System.out.println(pose4+" -> "+ pose5);
 
    }
    public static void main(String[] args) {
        hanoi(3,'A','B','C');
    }
}