数据结构递归学习，汉诺塔问题，计数对于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，永远也搬不完