汉诺塔递归算法是什么？

汉诺塔是经典递归问题：

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘。

游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。 *** 作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上， *** 作过程中盘子可以置于A、B、C任一杆上。

如果A只有一个（A->C）。

如果A有两个（A->B）,(A->C),(B->C)。

如果A有三个（A->C）,(A->B),(C->B),(A->C),(B->A),(B->C),(A->C)。

如果更多，那么将会爆炸式增长。

递归：就是函数自己调用自己。 子问题须与原始问题为同样的事，或者更为简单；递归通常可以简单的处理子问题，但是不一定是最好的。

其实递归在某些场景的迟脊哪效率是很低下的。尤其是斐波那契.从图你就可以发现一个简单的 *** 作有多次重复。因为它的递归调用俩个自己。那么它的递归的膨胀率是指数级别的，重复了大量相同计算。

起源：

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具野没。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。

大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不码码能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

汉诺塔可以理解为一个移动塔的游戏，把一个n层的塔从一个柱子移动到另一个柱子上

2.这就是汉诺塔递归原型 hannuota（n, A,C）--n层的塔从A柱移动到C柱；每次必须回搭备归到这个原型才算一次递归完成！

<就像1-100的递归累颤枝歼加f(n)=f(n-1)+n； 此时f(n)是递归原型，回归到f(n-1)>

3.中间需要借助一个柱子B，汉诺塔原型写成hunnuota(n,A,B,C)--n层塔从A柱借助B柱移动到C柱，这一步应该能够理解吧；

4.递归都要求有一个出口，也即是控制条件，当n=1时直接把塔从A移动到C即可，这就是出口

<如果n=2则需要移动两次才行，无法一次完成，不能出去>

5.n>1时,这一步是理解汉诺塔递归的关键，必须形成n-1层往C柱移动的形式，分为三步：

a. n层无法一次移动，那么可以理解为先把A上面的n-1层移动到B柱

<hannuota(n-1,A,C,B)>-------

b A柱剩下第n层的塔移动到C，

C 然后形成茄冲B柱上的n-1层移动到C柱上--

<hannuota（n-1,B,A,C）此时已经形成了递归的原型 不同的只是中间借助的柱子不同罢了>

递归完成

解决汉诺塔的基本思想是先把n个盘子除了最下面的盘子以外的所有盘子从第一根柱子(初始柱子)移动到中间那个柱子上(辅助柱子)，然后把最下面的盘子移动到最后一李敏根柱子上(目标柱子)。最后把剩下的盘子移动到目标柱子上。这样，然而，完成第一步和第三步也同样是一个移动n-1个盘子的汉诺塔问题。于是，递归调用在这里不可避免。程序你已经写的很清楚，给你解释一下。现把你的程序画上行以便说明。

1

#include

"stdio.h"

2

main()

3

{void

hanoi(int,char,char,char)

4

int

m

5

printf("input

the

number

of

disks:")

6

scanf("%d",&m)

7

printf("The

step

to

moving

%d

disks:\n",m)

8

hanoi(m,'A','B','C')

9

}

10

void

hanoi(int

n,char

a,char

b,char

c)

11

{//void

move(char,char)

12

if(n==1)

move(a,c)

13

else

14

{hanoi(n-1,a,c,b)

15

move(a,c)

16

hanoi(n-1,b,a,c)

17

}

18

}

19

void

move(char

x,char

y)

20

{printf("%c-->%c\n",x,y)

21

}

当卖扰余m=4时，程序走到第8行，调用函数hanoi(int

n,char

a,char

b,char

c)。此时，实参把值传递给了形参，于是此时，n=4,a=A,b=B,c=C。我把第11行的void

move(char,char)

注释掉了，应该知道这一句的意思。因为这一行虽然可以让程序更加完整，但是解释的时候加上它会很麻烦。程序走到第12行，因为此时n=4,而不等于1，程序直接走第13行。于是调用第14行的hanoi(n-1,a,c,b)。这是一个递归调用。此时，n=3,a=A,c=B,b=C。要清楚，A，B，C代表的意义。A代表初始柱子，B代表辅助柱子，C代表目标柱子。而a代表第一根柱子,b代表第二根柱子,c代表第三根柱子。这是不一样的。程序继续走，到12行时n依然不等于1。走到14行调用hanoi(n-1,a,c,b)。此时，n=2,a=A,c=C,b=B。程序再走，到12行时n依然不等于1，走到14行调用hanoi(n-1,a,c,b)。此时，n=1,a=A,c=B,b=C。程序走到12行时发现n=1,程序开始走15行。调用move(char

x,char

y)到20行时输出A-->B。调用结束，回到上一个调用即n=2,a=A,c=C,b=B。程序回到第15行，输出

A-->B。再走第16行，调用hanoi(n-1,b,a,c)。此时n=1,b=A,a=B,c=C。程序中滚回到12行再调用19行输出B-->C。调用结束，回到上一个调用n=3,a=A,c=B,b=C。程序走到15行，输出A-->C，这时，第一根柱子上有一个盘子，第二根柱子上有一个盘子，第三根柱子上有两个盘子。再调用16行就可以完成把第三根柱子里的所有盘子都移动到第二根柱子上。这样。我们就完成了整体目标的第一步。把n个盘子除了最下面的盘子以外的所有盘子从第一根柱子(初始柱子)移动到中间那个柱子上(辅助柱子)，调用完成后程序回到15行，此时n=3,a=A,c=B,b=C。15行时输出A-->C，这时便完成了整体目标的第二步，最下面的盘子移动到最后一根柱子上(目标柱子)。再根据程序走到16行，经过跟14行类似的一系列的递归调用，我们就可以完成最终目标了。

我也是现学现卖了，不知道这样说你能不能明白。我感觉光看这么麻烦的字是有点糊涂，但是根据程序看我说的应该可以明白吧，祝你成功了~

---