计算汉诺塔移动次数与递归编程实现

计算汉诺塔移动次数与递归编程实现

汉诺塔与递归

1.汉诺塔

规则如下：

在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘.

圆盘从上到下一次标记为1、2、3.....n.

情况1：假设只有1个圆盘则只需要从A移动到C，总共移动1次。

情况2：假设只有2个圆盘则只需要把第1个移动到B，然后把第2个移动到C，最后再把第1个移动到C，总共移动3次。

情况3：**假设有3个圆盘则只需要把第1个移动到C，把第2个移动到B，再把第1个移动到B，接着把第3个移动到C，再把第1个移动到A，再把第2个移动到C，最后把第1个移动到C，总共7步。

......

可以从假设有2个圆盘和假设有3个圆盘这两种情况的移动步骤中总结出一个规律：

类比情况3和情况2，可以把情况3步骤简化为3步，想象第1个和第2个是一个整体，然后与第3个组成2个圆盘就变成了情况2，第一步把第1个和第2个这个整体放倒B柱上，第二步把第1个放到C柱上，第三步把第1个和第2个这个整体放到C柱上就完成。

可能会有疑问为什么把第1个和第2个看做一个整体，注意我们这里是简化它的步骤，回到情况3，执行到第3步的时候是不是就相当于类比中第一步把第1个和第2个这个整体放倒B柱上。情况3执行到第4步的时候就相当于类比情况第二步把第1个放到C柱上。情况3中剩下的第567步相当于类比情况的第三步。

也就是说无论有多少个圆盘都可以像情况三中简化为总共三个步骤。

那么我们可以根据这观察三步列出一个数学公式，假设n个圆盘移动F(n)次。还是用情况3来举例子。那么第一步把第1个和第2个这个整体放倒B柱上需要移动F(3-1)次，第二步把第1个放到C柱上，因为只有一个也只移动1次，第三步把第1个和第2个这个整体放到C柱上需要移动F(3-1)次。那么总共移动多少次结果为:

F(3)=F(3-1)+1+F(3-1)

化简得：F(3)=2*F(2)+1，但是这里我们不知道F(2)和F(3)等于多少。但是我们知道圆盘只有一个时就是移动一次即F(1)=1。那么我们可以计算情况2需要多少次，F(2)=F(2-1)+1+F(2-1)化简为F(2)=2XF(1)+1，因为F(1)=1,代入得F(2)=3。得到了F(2)我们就可以得到F(3)=2X3+1=7次。

那么当圆盘为n个时就可以根据三个步骤同理列出公式

F(n)=F(n-1)+1+F(n-1)=>F(n)=2*F(n-1)+1

又因为一个圆盘为1次，两个圆盘为3次，3个圆盘为7次，根据1,3,7数字规律得出了一个快速计算汉诺塔次数的公式：2^n-1.

2.递归

编写程序计算汉诺塔移动次数

我们可以根据公式：F(n)=2*F(n-1)+1利用递归原理来编程实现计算。把return看做=号，又因为计算机不知道F(0)等于多少，何时终结程序，所以加一个if条件语句告诉计算机F(0)=0。然后递归也涉及到了栈的原理，外部调用这个f函数时会把这个函数压入栈，然后当return 2xf(n-1)+1时又调用了f函数，所以先把当前的函数再次压入栈,直到n==0时，计算机知道F(0)=0了，那么也就知道F(1)=1，然后就又知道F(2)....F（n)，在这个过程中被压入栈的函数也依次弹出来了。

 int f(n){if（n==0）return 0;elsereturn 2*f(n-1)+1;}