資料結構遞歸學習，漢諾塔問題，計數對于n個圓盤的搬運，一共需要搬運多少次

6/11

漢諾塔問題

三根杆子ABC，A上有N個穿孔圓盤，圓盤尺寸由下到上依次變小，将所有圓盤移動到C槽并遵守如下規則：

• a每次隻能移動一個圓盤；

• b始終保持大盤在下小盤再上。

  最後計數對于n個圓盤的搬運，一共需要搬運多少次

  思想：

分而治之：把一個富足的大規模問題分解成若幹相似的小規模子問題，等問題規模足夠小的時候就可以直接得到小規模問題的解再把小規模問題的解組合起來就是大規模問題的解。

1. A盤上隻有一個圓盤時，直接起始杆到目标杆（A-C）
2. A盤上有兩個圓盤時，把最上面的一個圓盤搬運到輔助杆，再做步驟1，再把輔助杆上的第一個圓盤放到目标盤
3. A盤上有三個圓盤時，把上面兩個圓盤搬運到輔助杆，在做步驟1，剩下的兩個圓盤在輔助杆上，再做步驟二
4. 可以總結，n個圓盤時，把上面n-1個圓盤先搬到輔助盤，再做步驟1，無論n為多少，都把它當成兩個盤，n是一個，n-1作為一個整體，是一個，進行第二步的執行。

N個圓盤：最大的圓盤的搬運&最大圓盤上面的n-1個圓盤的搬運

public class Hanoi {
    public static void main(String[] args) {
        move(3, 'A', 'B', 'C');
    }
//n：漢諾塔盤子數量
//move:将n個盤子從start杆借助help杆放到target杆上
    public static void move(int n, char start, char help, char target) {
        if (n == 1) {
            System.out.println(A + "->" + C);
        } else {
            move(n - 1, A, C, B);
            System.out.println(A + "->" + C);
            move(n - 1, B, A, C);
        }
    }
    //計數對于n個圓盤的搬運，一共需要搬運多少次
    public static long count(int n){
        //遞歸出口
        if(n==1){
            return 1;
        }
        //move(n - 1, A, C, B); 
        long count1=count(n-1);
       // move(n - 1, B, A, C);
        long count2=count(n-1);
        return count1+1+count2;
    }
}
           

可以發現對于n個盤子的搬運次數，count1+count2+1=2count1+1

count1=2count1(n-1)………………

結果剛好是2^n+1

指數級的上升，是以64個盤子就是2^64+1，永遠也搬不完