c语言汉诺塔问题递归算法

维普资讯 ２００６年６月　河北北方学院学报（自然科学版）　第３期　

上操作的实质是把移动ｎ个盘子的问题转化为移动ｎ一１个盘．那一、三步如何解决？事实上，上述方法　

设盘子数为ｎ，ｎ可为任意数，该法同样适用于移动ｎ一１个盘．因此，依据上法，可解决ｎ一１个盘子从　

Ａ杆移到Ｂ杆（第一步）或从Ｂ杆移到Ｃ杆（第三步）问题．现在，问题由移动ｎ个盘子的操作转化为　

移动ｎ一２个盘子的操作．依据该原理，层层递推，即可将原问题转化为解决移动ｎ一２、ｎ一３……３、２、　

直到移动１个盘的操作，而移动一个盘的操作是可以直接完成的．至此，我们的任务算作是真正完成了．　

而这种由繁化简，用简单的问题和已知的操作运算来解决复杂问题的方法，就是递归法．在计算机设计语　

言中，用递归法编写的程序就是递归程序．　

２递归程序定义及实现条件　

２．１递归程序定义　

《Ｃ程序设计》、《数据结构》等教科书中，都对递归程序给出了基本相同的定义，归纳如下：在调用　

一个函数的过程中，又直接或间接地调用了该函数本身，称为函数的递归调用，使用了递归调用函数的程　

序称为递归程序．从上述定义中我们就会发现，递归程序中的函数都是自己调用了自己，不管是直接调用　

还是间接调用．那什么样的问题可用递归法解决呢？　

２．２实现递归条件　

用递归法解决的问题，应该符合以下３个条件：　

（１）能够把原问题转化成一个新问题，且新问题的求解方法与原问题相同．　

（２）将原问题转化成新问题后，能使求解算法的规模减小．　

（３）递归有一个明显的出口，或称为递归的边界，而边界问题的解是显而易见的或已知的．　

３用Ｃ语言编程　

Ｃ语言是一种在国内外广泛流行的高级程序设计语言，它的语言功能丰富，表达力强，使用灵活，应　

用面广，是深受广大编程者喜爱的结构化程序设计语言．它的语言特点决定了可用其实现递归程序．　

３．１　Ｃ语言实现递归程序的可行性　

Ｃ语言的变量按作用域分为全局变量和局部变量．全局变量所有的函数都可使用，可增加递归调用中　

汉诺塔游戏：递归经典问题

汉诺塔游戏，是非常著名的智力趣味题，在很多算法书籍和智力竞赛中都有涉及。

汉诺塔游戏的基本规则是：在一块板子上，有三根编号分别为A、B、C的杆，在A杆上按自下而上、由大到小的顺序放置着64个（或其他数目）圆盘，每次只能移动一个圆盘，并且在移动过程中三根杆上都始终保持大盘在下、小盘在上的状态，操作过程中圆盘可以在A、B、C任意一杆上，要如何把A杆上的圆盘全部移到C杆上？

以3个圆盘为例：将3个圆盘按由小到大的顺序分别记作P1、P2、P3。按照规则将三个圆盘从A杆移至C杆，则需以下步骤：（1）先将P1移至C杆，再将P2移至B杆，然后将P1移至B杆，此时P1和P2均在B杆上（需3步）；（2）将P3移至C杆（需1步）；（3）将P1移至A杆，将P2移至C杆，最后将P1移至C杆（需3步）。

在此过程中，要将P3移至C杆，先将C杆当作中介，将P1移至C杆；再将P1、P2先移至B杆，借用B杆做中介；再将P2移至C杆时，又先将P1移至A杆，借用了A杆做中介。（总共7步完成）

以此为例，如何完成其他数量圆盘的移动操作呢？

当n=1时，只需将编号为1的圆盘从A柱直接移至C柱上即可。

当n=2时，利用B柱作为辅助柱，先将圆盘1移至B柱，再将圆盘2由A柱直接移至C柱，然后再将圆盘1由B柱移至C柱。

当n=3时，同样利用B柱作为辅助柱，依照上述原则，先设法将圆盘1、2移至B柱，待圆盘3由A柱移至C柱后，再依照上述原则设法将圆盘1、2移至C柱。

......

依此类推，当n>1时，需利用B柱作为辅助柱，先设法将压在编号为n的圆盘上的n-1个圆盘从A柱（依照上述原则）移至C柱，待编号为n的圆盘从A柱移至C柱后，再将B柱上的n-1个圆盘（依照上述原则）移至C柱。

游戏的移动操作很简单，但是如何将64个圆盘从一根杆子上移到另一根杆子上，并且始终保持上小下大的顺序，一共需要移动多少次才是让人头疼的问题。游戏过程中不难发现：不管把哪一个圆盘移到另一根杆子上，移动的次数都要比移动上面一个增加一倍。这样，移动第1个只需1次，第2个需2次，第3个需4次……第64个需263次。

#include

void hano( int n, char from, char to, char temp )

//n代表盘子的个数

//from代表盘子当前所在的位置

//to代表盘子要移动到的位置

//temp作为盘子移动过程中的中转站

{

If( n>0 )

{

hano( n-1, from, temp, to );//先把上方的n-1个盘子从from移动到temp

printf( “%d %c ==>%c\n”, n, from, to );//把最下面的盘子从from移动到to

hano( n-1, temp, to, from );再把n-1个盘子从temp移动到to

}

}

void hanoEx( int top, int n, char from, char to, char temp )

//top代表要移动的盘子的最上方的号码（从1开始到n）

//n代表盘子的个数

//from代表盘子当前所在的位置

//to代表盘子要移动到的位置

//temp作为盘子移动过程中的中转站

{

If( n==1 )

printf( “%d %c==>%c\n”, top, from, to );

else

{

hanoEx( top, n-1, from, temp, to ); //先把上方的n-1个盘子从from移动到temp

hanoEx( top+n-1, 1, from, to, temp ); //把最下面的盘子从from移动到to，号码为top+n-1

hanoEx( top, n-1, temp, to, from ); 再把n-1个盘子从temp移动到to

}

}

int main()

{

hano( 3, „a‟, „b‟, „c‟ );

hanoEx( 1, 3, „a‟, „b‟, „c‟ );

return 0;

}

汉诺塔递归算法及详解

汉诺塔（Hanoi Tower）是一种数学谜题，由法国数学家Édouard

Lucas在19世纪中期提出。这个谜题由三根柱子和一组圆盘组成，圆盘从上到下按照从小到大的顺序放置在柱子上。问题的目标是将所有圆盘从一个柱子移动到另一个柱子，每次只能移动一个圆盘，并且不能将大的圆盘放在小的圆盘上面。

解决汉诺塔问题的一种常见方法是使用递归算法。递归是一种数学和计算机科学中常见的方法，通过将复杂的问题分解为更小的相同问题的子问题来解决。

汉诺塔的递归算法主要包含以下步骤：

1.将N-1个圆盘从起始柱子移动到中间柱子上，这可以通过将起始柱子作为源柱子，中间柱子作为辅助柱子，目标柱子为空柱子来实现。这个步骤可以通过递归调用来实现，将起始柱子作为源柱子，中间柱子作为辅助柱子，目标柱子作为空柱子。

2.将第N个圆盘从起始柱子移动到目标柱子上。

3.将N-1个圆盘从中间柱子移动到目标柱子上，这可以通过将中间柱子作为源柱子，目标柱子作为辅助柱子，起始柱子作为空柱子来实现。这个步骤可以通过递归调用来实现，将中间柱子作为源柱子，目标柱子作为辅助柱子，起始柱子作为空柱子。

下面是一个示例代码，使用递归算法解决汉诺塔问题：

```python

def hanoi(n, source, target, auxiliary): if n > 0:

#将N-1个圆盘从起始柱子移动到中间柱子

hanoi(n-1, source, auxiliary, target)

#将第N个圆盘从起始柱子移动到目标柱子

print("Move disk", n, "from", source, "to", target)

#将N-1个圆盘从中间柱子移动到目标柱子

hanoi(n-1, auxiliary, target, source)

#测试

n=3

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

```

上述代码中，`hanoi(`函数接受四个参数：圆盘的数量n，起始柱子source，目标柱子target和辅助柱子auxiliary。函数首先检查圆盘的数量，如果圆盘数量大于0，则递归调用`hanoi(`函数来移动N-1个圆盘。然后，将第N个圆盘从起始柱子移动到目标柱子，并再次递归调用`hanoi(`函数来移动N-1个圆盘。