汉诺塔讲解
# include <stdio.h>
void hannuota(int n, char A, char B, char C)
{
/*
如果是1个盘子
直接将A柱子上的盘子从A移到c
否知
先将A柱子上的n-1个盘子借助C移到B
直接将A柱子上的盘子从A移到C
最后将B柱子上的n-1个盘子借助A移动C
*/
if (1 == n)
{
printf("将编号为%d的盘子直接从%c柱子移到%c柱子.\n\n", n, A, C);
}
else
{
hannuota(n-1, A, C, B);
printf("将编号为%d的盘子直接从%c柱子移到%c柱子.\n\n", n, A, C);
hannuota(n-1, B, A, C);
}
}
int main(void)
{
char ch1 = 'A';
char ch2 = 'B';
char ch3 = 'C';
int n;
printf("请输入要移动盘子的个数: ");
scanf("%d", &n);
hannuota(n, 'A', 'B', 'C');
return 0;
}
上面那个程序的算法我能看懂，但如果拿个数进去试，都不知道程序的流程了。大家帮忙讲解一下吧，比如输入3，程序的执行流程是怎样的。请详细说哦，要详细哦。
[解决办法]
将递归转化为非递归是理解递归的不二法门。
#include<stdio.h> #define MAX 100 typedef struct DATA { char x; char y; char z; int flag; //flag==1，表示还可以分解,若为0这不能分解 int num; //表示盘子个数 }DATATYPE; void Hanoi(int n,char x,char y,char z); int main() { int n; printf("请输入盘子的个数:"); scanf("%d",&n); Hanoi(n,'X','Y','Z'); return 0; } void Hanoi(int n,char x,char y,char z) { DATATYPE stack[MAX]; int x1,y1,z1,m,top=1; stack[top].num=n; stack[top].flag=1; stack[top].x=x; stack[top].y=y; stack[top].z=z; while(top) { if(stack[top].flag==1&&stack[top].num>1) { m=stack[top].num; //参数的传递==Hanoi(num,x,y,z); x1=stack[top].x; y1=stack[top].y; z1=stack[top].z; stack[top].num=m-1; //将第m-1个盘子经过x从y移到z==Hanoi(m-1,y,x,z) stack[top].flag=1; stack[top].x=y1; stack[top].y=x1; stack[top].z=z1; top++; stack[top].num=m; stack[top].flag=0; //将第m个盘子从x移到z==Move(m,x,z) stack[top].x=x1; stack[top].y=z1; top++; stack[top].num=m-1; stack[top].flag=1; stack[top].x=x1; //将第m-1个盘子从x经过z移到y==Hanoi(m-1,x,z,y) stack[top].y=z1; stack[top].z=y1; } while(top>0&&(stack[top].flag==0||stack[top].num==1)) { if(top>0&&stack[top].flag==0) //将第n个盘子从x移到z { printf("将第%d个圆盘从塔%c移动到%c\n",stack[top].num,stack[top].x,stack[top].y); top--; } if(top>0&&stack[top].num==1) //将第一个盘子从x移到z { printf("将第%d个圆盘从塔%c移动到%c\n",stack[top].num,stack[top].x,stack[top].z); top--; } } } } //请输入盘子的个数:3 //将第1个圆盘从塔X移动到Z //将第2个圆盘从塔X移动到Y //将第1个圆盘从塔Z移动到Y //将第3个圆盘从塔X移动到Z //将第1个圆盘从塔Y移动到X //将第2个圆盘从塔Y移动到Z //将第1个圆盘从塔X移动到Z //Press any key to continue