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汉诺塔递归过程详解等相关内容解答,如果想了解更多相关内容,可以关注我们,你们的支持是我们更新的动力!
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)