1. 漢諾塔的介紹和玩法

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

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

2. 漢諾塔問題的思路

若A柱子上只有1個(gè)盤子，只需要移動(dòng)1步：A->C

若A柱子上有2個(gè)盤子，需要移動(dòng)3步：A->B,A->C,B->C

此時(shí)需要借助B柱子，才能將A柱子的盤子移到C柱子上。

那么若A柱子上有3個(gè)盤子，會怎么移動(dòng)呢？

思路：此時(shí)，A為起始位置，B為中轉(zhuǎn)位置，C為最終位置。我們需要將A柱子最上面的兩個(gè)盤子先想辦法移到中轉(zhuǎn)位置B柱子上，然后將A柱子最下面的那個(gè)盤子移動(dòng)到C柱子上，最后再將B柱子上面的盤子想辦法移動(dòng)到C柱子上。

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

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

所以，最終三個(gè)盤子的移動(dòng)路徑是  A->C,A->B,C->B,A->C,B->A,B->C,A->C，需要移動(dòng)7步

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

那么A柱子上有n個(gè)盤子時(shí)，該怎么移動(dòng)呢？

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

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

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

public class HanoiGame {
/*
* 第一個(gè)參數(shù)用來放給的盤子數(shù)，
 *第二個(gè)參數(shù)用來放起始位置
 *第三個(gè)參數(shù)用來放中轉(zhuǎn)位置
 *第四個(gè)參數(shù)用來放最終位置
 * */
    public static void hanoi(int n,char pose1,char pose2,char pose3){ // 3 'A' 'B' 'C'
        if(n == 1){
            move(pose1,pose3);//若只有一個(gè)盤子，只需從起始位置移到最終位置這1步。
            // 這里的pose1不一定等于'A',pose3不一定等于'C'；隨著遞的次數(shù)的不一樣，對應(yīng)不同的值。
            return;
        }
        hanoi(n-1,pose1,pose3,pose2);//這n-1個(gè)盤子是要借助 C 移動(dòng)到 B 上的。
               //所以 對于這n-1個(gè)盤子來說，起始位置是'A'，中轉(zhuǎn)位置是'C',最終位置是'B'
        move(pose1,pose3);
        hanoi(n-1,pose2,pose1,pose3);
 
    }
    /*
    * 第一個(gè)參數(shù)用來放起始位置
    * 第二個(gè)參數(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');
    }
}

總結(jié)

到此這篇關(guān)于JavaSE遞歸求解漢諾塔問題的思路與方法的文章就介紹到這了,更多相關(guān)JavaSE遞歸求解漢諾塔內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論