UC知道求汉诺塔C递归算法详细解答
来源：百度知道 编辑：UC知道 时间：2024/05/13 09:59:15
void move(char x,char y){
printf("%c-->%c\n",x,y);
}
void hanoi(int n,char one,char two,char three){
/*将n个盘从one座借助two座，移到three座*/
if(n==1) move(one,three);
else{
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
}
}
main(){
int n;
printf("input the number of diskes:");
scanf("%d",&n);
printf("The step to moving %3d diskes:\n",n);
hanoi(n,'A','B','C');
}
当n=3的时候，请高手帮我详细写出程序递归执行的过程。该程序中没有计算的表达式，就 hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
靠个参数传递，怎么传递啊？我还是不明白啊，高手帮帮我，我一定要弄明白位置，我太笨了。
谭先生的C教程电子版哪有下载啊？
Hanoi塔问题, 算法分析如下，设A上有n个盘子。
如果n=1，则将圆盘从A直接移动到C。
如果n=2，则：
（1）将A上的n-1（等于1）个圆盘移到B上；
（2）再将A上的一个圆盘移到C上；
（3）最后将B上的n-1（等于1）个圆盘移到C上。
如果n=3，则：
A）将A上的n-1（等于2，令其为n`）个圆盘移到B（借助于C），步骤如下：
（1）将A上的n`-1（等于1）个圆盘移到C上。
（2）将A上的一个圆盘移到B。
（3）将C上的n`-1（等于1）个圆盘移到B。
B）将A上的一个圆盘移到C。
C）将B上的n-1（等于2，令其为n`）个圆盘移到C（借助A），步骤如下：
（1）将B上的n`-1（等于1）个圆盘移到A。
（2）将B上的一个盘子移到C。
（3）将A上的n`-1（等于1）个圆盘移到C。到此，完成了三个圆盘的移动过程。
从上面分析可以看出，当n大于等于2时， 移动的过程可分解为三个步骤：第一步 把A上的n-1个圆盘移到B上；第二步 把A上的一个圆盘移到C上；第三步 把B上的n-1个圆盘移到C上；其中第一步和第三步是类同的。 当n=3时，第一步和第三步又分解为类同的三步，即把n`-1个圆盘从一个针移到另一个针上，这里的n`=n-1。
Hanoi塔问题中函数调用时系统所做工作
一个函数在运行期调用另一个函数时，在运行被调用函数之前，系统先完成3件事：
①将所有的实参、返回地址等信息传递给被调用函数保存。
②为被调用函数的局部变量分配存储区；
③将控制转移到被调用函数的入口。
从被调用函数返回调用函数前，系统也应完成3件事：
①保存被调用函数的结果；
②释放被调用函数的数据区；
③依照被调用函数保存的返回地址将控制转移到调用函数。
当有多个函数构成嵌套调用时，按照“后调用先返回”的原则（LIFO），上述函数之间的信息传递和控制转移必须通过“栈”来实现，即系统将整个程序运行