c语言用递归实现汉诺塔

见代码注释，还有不懂可以问。

#include <stdioh>

void move(char x,char y)

{

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

}

//hannuota函数的作用：把n个圆盘从one柱子借助two柱子放到three柱子 

void hannuota(int n,char one,char two,char three)

{

    if(n==1)//如果只有一个柱子 

        move(one,three);//直接移动即可 

    else

    {

        hannuota(n-1,one,three,two);//先把one柱子上的n-1个圆盘借助three柱子移动到柱子two 

        move(one,three);//把第一个柱子的剩下那一个(第n个)移动到第三个柱子

//由于原来one柱子上的n-1个圆盘已经移动到了two柱子上，因此不会有圆盘挡住n圆盘出来 

        hannuota(n-1,two,one,three);

        //最后再把那n-1个圆盘从two柱子借助one柱子移动到three柱子

//(上面第一句话hannuota(n-1,one,three,two)已经移动到了two柱子，因此这里是从two柱子移动到three柱子) 

    }

}

int main()

{

    int m;

    printf("input the number of diskes:");

    scanf("%d",&m);

    printf("The step to move %d diskes:\n",m);

    hannuota(m,'A','B','C');

    return 0;

}

要看懂递归程序，往往应先从最简单情况看起。

先看hanoi(1, one, two, three)的情况。这时直接将one柱上的一个盘子搬到three柱上。注意，这里one柱或three柱到底是A、B还是C并不重要，要记住的是函数第二个参数代表的柱上的一个盘被搬到第四个参数代表的柱上。为方便，将这个动作记为：

one =》three

再看hanoi(2, one, two, three)的情况。考虑到hanoi(1)的情况已经分析过了，可知这时实际上将产生三个动作，分别是：

one =》two

one =》three

two =》three

很显然，这实际上相当于将one柱上的两个盘直接搬到three柱上。

再看hanoi(3, one, two, three)的情况。分析

hanoi(2, one , three, two)

one =》three

hanoi(2, two, one, three)

即：先将one柱上的两个盘搬到two柱上，再将one柱上的一个盘搬到three柱上，最后再将two柱上的两个盘搬到three柱上。这不就等于将one柱上的三个盘直接搬到three柱上吗？

运用归纳法可知，对任意n，

hanoi(n-1, one , three, two)

one =》three

hanoi(n-1, two, one, three)

就是先将one柱上的n-1个盘搬到two柱上，再将one柱上的一个盘搬到three柱上，最后再将two柱上的n-1个盘搬到three柱上。这就是我们所需要的结果！

您好，可以这样

汉诺塔（Hanoi）是必须用递归方法才能解决的经典问题。它来自于印度神话。上帝创造世界时作了三根金刚石柱子，在第一根柱子上从下往上按大小顺序摞着64片黄金圆盘，如图7-3所示。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放到第二根柱子上，并且规定，每次只能移动一个圆盘，在小圆盘上不能放大圆盘。有人预言说，这件事完成时宇宙会在一瞬间闪电式毁灭，也有人相信婆罗门至今仍在一刻不停地搬动着圆盘。

输入格式要求："%d" 提示信息："Input the number of disks:"

输出格式要求："Steps of moving %d disks from A to B by means of C:\n" "Move %d: from %c to %c\n"

程序运行示例如下：

Input the number of disks:3

Steps of moving 3 disks from A to B by means of C:

Move 1: from A to B

Move 2: from A to C

Move 1: from B to C

Move 3: from A to B

Move 1: from C to A

Move 2: from C to B

Move 1: from A to B

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

1 #include "stdioh"

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行类似的一系列的递归调用，我们就可以完成最终目标了。

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

input the number of disks:3

the step to moving 3 disks

A-->C

A-->B

C-->B

A-->C

B-->A

B-->C

A-->C

纸笔画了我老半天。。。楼主给个精

以上就是关于c语言用递归实现汉诺塔全部的内容，包括:c语言用递归实现汉诺塔、C语言汉诺塔、在编写C语言程序求解汉诺塔问题时怎样表示每一步是第几步等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！