C语言中关于hanoi塔问题中hanoi(n-1,one,three,two)的执行方式

C语言中关于hanoi塔问题中hanoi(n-1,one,three,two)的执行方式,第1张

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

的意思就是说要把1号柱子上的盘子通过3号柱子挪到2号柱子上;

move(one,three);

的意思就是把1号柱子上的盘子挪到3号柱子上;

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

的意思就是说要把2号柱子上的盘子通过1号柱子挪到3号柱子上;

#include <stdioh>

void hanoi(int n,char a,char b,char c)

{if(n>1)hanoi(n-1,a,c,b);

printf("%d from %c to %c\n",n,a,c);

if(n>1)hanoi(n-1,b,a,c);

}

int main()

{int n;

scanf("%d",&n);

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

return 0;

}

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

1 #include "stdioh"

2 main()

3 {void hanoi(int,char,char,char); <br/>4 int m; <br/>5 printf("input the number of disks:"); <br/>6 scanf("%d",&m); <br/>7 printf("The step to moving %d disks:\n",m); <br/>8 hanoi(m,'A','B','C'); <br/>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); <br/>15 move(a,c); <br/>16 hanoi(n-1,b,a,c); <br/>17 }

18 }

19 void move(char x,char y)

20 {printf("%c-->%c\n",x,y); <br/>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行类似的一系列的递归调用,我们就可以完成最终目标了。

#include<stdioh>

#define MAXSTACK 10   / 栈的最大深度 /

int c = 1; / 一个全局变量,表示目前移动的步数 /

struct hanoi { / 存储汉诺塔的结构,包括盘的数目和三个盘的名称 /

int n;

char x, y, z;

};

void move(char x, int n, char y) / 移动函数,表示把某个盘从某根针移动到另一根针 /

{

printf("%d Move disk %d from %c to %cn", c++, n, x, y);

}

void hanoi(int n, char x, char y, char z) / 汉诺塔的递归算法 /

{

if (1 == n)

move(x, 1, z);

else {

hanoi(n - 1, x, z, y);

move(x, n, z);

hanoi(n - 1, y, x, z);

}

}

void push(struct hanoi p, int top, char x, char y, char z,int n)

{

p[top+1]n = n - 1; 

p[top+1]x = x; 

p[top+1]y = y; 

p[top+1]z = z; 

}

void unreverse_hanoi(struct hanoi p) / 汉诺塔的非递归算法 /

{

int top = 0;

while (top >= 0) {

while (p[top]n > 1) { / 向左走到尽头 /

push(p, top, p[top]x, p[top]z, p[top]y, p[top]n);

top++;

}

if (p[top]n == 1) { / 叶子结点 /

move(p[top]x, 1, p[top]z);

top--;

}

if (top >= 0) { / 向右走一步 /

move(p[top]x, p[top]n, p[top]z);

top--;

push(p, top, p[top+1]y, p[top+1]x, p[top+1]z, p[top+1]n);

top++;

}

}

}

int main(void)

{

struct hanoi p[MAXSTACK];

printf("reverse program:n");

hanoi(3, 'x', 'y', 'z');

printf("unreverse program:n");

c = 1;

p[0]n = 3;

p[0]x = 'x', p[0]y = 'y', p[0]z = 'z';

unreverse_hanoi(p);

return 0;

}

递归算法是我前些天写的,非递归是刚才找的,里面含递归和非递归。\x0d\递归算法:\x0d\#include \x0d\//递归求汉诺塔问题\x0d\void hanoi(int n, char A, char B, char C, int time)\x0d\{\x0d\if (n>=1)\x0d\{\x0d\ hanoi(n-1, A, C, B, time);\x0d\ move(A, C);\x0d\ (time)++;\x0d\ hanoi(n-1, B, A, C, time);\x0d\ }\x0d\}\x0d\//打印出每一步的路径\x0d\void move(char a, char c)\x0d\{\x0d\printf(" %c-->%c\n", a, c);\x0d\}\x0d\\x0d\int main(void)\x0d\{\x0d\int n, time = 0;;\x0d\printf("请输入汉诺塔的盘数:");\x0d\scanf("%d", &n);\x0d\printf("%d个盘的汉诺塔移动方法是:", n);\x0d\printf("\n");\x0d\hanoi(n, 'A', 'B', 'C', &time);\x0d\printf("移动了%d次\n", time);\x0d\system("pause");\x0d\return 0;\x0d\}\x0d\\x0d\非递归算法:\x0d\#include \x0d\\x0d\#define MAXSTACK 10 / 栈的最大深度 /\x0d\\x0d\int c = 1; / 一个全局变量,表示目前移动的步数 /\x0d\\x0d\struct hanoi { / 存储汉诺塔的结构,包括盘的数目和三个盘的名称 /\x0d\int n;\x0d\char x, y, z;\x0d\};\x0d\\x0d\void move(char x, int n, char y) / 移动函数,表示把某个盘从某根针移动到另一根针 /\x0d\{\x0d\printf("%d-> %d from %c -> %c\n", c++, n, x, y);\x0d\}\x0d\\x0d\void hanoi(int n, char x, char y, char z) / 汉诺塔的递归算法 /\x0d\{\x0d\if (1 == n)\x0d\move(x, 1, z);\x0d\else {\x0d\hanoi(n - 1, x, z, y);\x0d\move(x, n, z);\x0d\hanoi(n - 1, y, x, z);\x0d\}\x0d\}\x0d\\x0d\void push(struct hanoi p, int top, char x, char y, char z,int n)\x0d\{\x0d\p[top+1]n = n - 1;\x0d\p[top+1]x = x;\x0d\p[top+1]y = y;\x0d\p[top+1]z = z;\x0d\}\x0d\\x0d\void unreverse_hanoi(struct hanoi p) / 汉诺塔的非递归算法 /\x0d\{\x0d\int top = 0;\x0d\\x0d\while (top >= 0) {\x0d\while (p[top]n > 1) { / 向左走到尽头 /\x0d\ push(p, top, p[top]x, p[top]z, p[top]y, p[top]n);\x0d\ top++;\x0d\}\x0d\if (p[top]n == 1) { / 叶子结点 /\x0d\ move(p[top]x, 1, p[top]z);\x0d\ top--;\x0d\}\x0d\if (top >= 0) { / 向右走一步 /\x0d\ move(p[top]x, p[top]n, p[top]z);\x0d\ top--;\x0d\ push(p, top, p[top+1]y, p[top+1]x, p[top+1]z, p[top+1]n);\x0d\ top++;\x0d\}\x0d\}\x0d\}\x0d\\x0d\int main(void)\x0d\{\x0d\int i;\x0d\printf("递归:\n");\x0d\hanoi(3, 'x', 'y', 'z');\x0d\printf("非递归:\n");\x0d\struct hanoi p[MAXSTACK];\x0d\c = 1;\x0d\p[0]n = 3;\x0d\p[0]x = 'x', p[0]y = 'y', p[0]z = 'z';\x0d\unreverse_hanoi(p);\x0d\\x0d\return 0;\x0d\}

#include<stdioh>

void move(char a,char b)

{

printf("%c->%c\n",a,b);

}

void f(int n,char a,char b,char c)

{

if(n==1) move(a,c);

else

{

f(n-1,a,c,b);

move(a,c);

f(n-1,b,a,c);

}

}

void main()

{

int n;

scanf("%d",&n);

f(n,'a','b','c');

}

这是我的代码 前面的是定义一个函数 这里递归体现在函数里面还有函数 于是会一次又一次的计算 直到最后把N-1以前的都移到B,最下面的移到C,再把其他的从B移到C。。 无返回的话 应该是这里用void 没有return返回数值

程序就会按照你带的参数去继续调用void hanoi(int n, char one, char two, char three)函数了。这就是调用。以下是我曾经分析过的这个问题。供你参考。附上源程序。

//解决汉诺塔的核心概念:需要将大的在下小的在上的n个盘子从A借助B移动到C,

//全部还是按照大的在下小的在上的原则。

//可以分解为简单的3个过程,以实现递归

//过程0:A的N个盘子借助B移动到C; //move(n,a,b,c); //PS1//备注1

//过程1:A的N-1个盘子借助C移动到B; //move(n-1,a,c,b);

//过程2:A的最后一个盘子直接移动到C //printf("%c->%c\n",a,c); //简化

//过程3:B的N-1个盘子借助A移动到C; //move(n-1,b,a,c);

//过程3实际上回到了假定的过程0 //move(n-1,b,a,c);//和PS1相比:参数AB位置发生变化,n变为n-1

//于是,开始了新一轮的过程1、2、3,并以此实现递归

//本程序关键在于理解递归算法

#include<stdioh>

#include<stringh>

#include<stdlibh>

long count;

void move(int n,char a,char b,char c)

{

if(n==1)

{

printf("\t第%d次移动%c->%c\n",++count,a,c); //当n只有1个的时候直接从a移动到c

}

else

{

move(n-1,a,c,b); //第n-1个要从a通过c移动到b

printf("\t第%d次移动%c->%c\n",++count,a,c); //用于显示移动的每一步//上面一个函数运行后的最后一个盘的移动路线

move(n-1,b,a,c); //n-1个移动过来之后b变开始盘,b通过a移动到c,这边很难理解//

}

}

int main(void)

{

int n;

count=0;

printf("请输入要移动的圆盘数:");

scanf("%d",&n);

move(n,'a','b','c');

printf("%d个圆盘共需移动%d次\n",n,count);

return(0);

}

//本人也新学,供参考

以上就是关于C语言中关于hanoi塔问题中hanoi(n-1,one,three,two)的执行方式全部的内容,包括:C语言中关于hanoi塔问题中hanoi(n-1,one,three,two)的执行方式、c语言编程问题,求解。(汉诺塔)、求C汉诺塔递归过程详解等相关内容解答,如果想了解更多相关内容,可以关注我们,你们的支持是我们更新的动力!

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zz/10108957.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023-05-05
下一篇 2023-05-05

发表评论

登录后才能评论

评论列表(0条)

保存