汉诺塔问题C++递归算法浅析与思考此贴只供新手参考。。。高人可忽略。。。这个问题在高中数学课上也曾研究过，不
汉诺塔问题C++递归算法浅析与思考
此贴只供新手参考。。。高人可忽略。。。
这个问题在高中数学课上也曾研究过，不过记得那时班上整体效果奇差，题的基数只是3，最后结果却只有我得出，貌似就是汉诺塔的数学计算公式 sum=2^n-1
将64带入公式，可得出 sum(64)=2^64-1=18446744073709551615
好蛋疼的数据。
----------------------------------------------------长的像我的都是分割线--------------------------------------------
前日学习C++指针与引用一章时例题处出现这个本该属于递归函数的题，当日考虑了很久，依然是一头雾水，加上近日感冒头痛，也确实木有心情，想着就头痛啊。当晚请教高手，一句“单步调试”就打发，估计问多了人也烦了，但是尼玛我确实还不会单调啊，今天终于好转，借助百度，却全是只分析递归整体过程，绝不分析内部的流程，借其理解了不少，无奈还是得拿起笔自己一步一步跟踪程序走向（只有不会单调的苦逼才这么干吧?)，废去稿纸几篇，终于理清了头绪。
从头到尾只有一个感叹：写出这算法的不是人，abc移来移去如此复杂的东西居然几行代码就给搞得天衣无缝。
据说学递归不要太注意每一步，只要能把主要过程想明白了，限定条件设定正确，一切就ok了，但是每一步都还没明白怎么出总体思想啊！
-------------------------------------------------
先贴代码：
C/C++ code#include<stdafx.h>#include<iostream>#include<stdio.h>using namespace std;void move(int n,int x,int y,int z){ char c1=x,c2=z; if(n==1) cout<< c1<<"-->"<< c2<<endl; else{ move(n-1,x,z,y); cout<< c1<<" -->"<< c2<<endl; move(n-1,y,x,z); }}void main(){ int h; cout<<"input number:"<<endl; cin>>h; cout<<"the step to moving "<<h<<" diskes:"<<endl; move(h,'a','b','c');}
1.总体递归逻辑：设圆盘有n个
if(n==1)
cout<<a<<"-->"<<c<<endl;//只有一块圆盘，直接移至c
else{
move(n-1,a,c,b);//将a上的n-1块圆盘通过c移至b
cout<<a<<"-->"<<c<<endl;//将a上第n块圆盘移至c
move(n-1,b,a,c);//将b上的n-1块圆盘移至c
}
很抽象，但是后面一个大弯要靠其绕过。
2.逐步考虑的方法：列表格跟踪递归的每一步（n=3时如图）
值来源指的是实参的来源，也是一个需要好好理解的大弯，后面详解。
m1,m2分别指程序中第一和第二个hanoi(n-1,a,b,c)。
以上需自己动笔在草稿上考虑，一次过关终身受益。。。
3详解： 分析a=3的情况。。其它只有计算机才考虑得过来
1 void move(int n,char a,char b,char c)
{
2 if(n==1)
3 cout<<a<<"-->"<<c<<endl;
4 else{
5 move(n-1,a,c,b);
6 cout<<a<<"-->"<<c<<endl;
7 move(n-1,b,a,c);
}
}
}
main函数首先传来实参'a','b','c'，第1行初始值既为move(3,a,b,c),3>1,进入第4行else语句，开始第5行m1的递归，分别为move(2,a,c,b)、
move(1,a,b,c),此时n=1，执行语句2、3，完成第一步 a-->c;
m1的递归开始逐层返回，当然，这里只有move(2,a,c,b)（注意，这里是a,c,b，而不是n=1时最后的a,b,c,原因在于其实际各自调用一个函数，且后者在前者的函数内，n=1的值的改变不影响外层n=2的值，只在其自身函数作用域内有效。），程序继续执行第６行（一个递归引用相当于一个函数体，递归返回时便执行函数体内的语句），完成第二步 a-->b;
进入语句7，变为由move(2,a,c,b)变为move(1,c,a,b)，n=1，执行语句2、3，完成第三步 c-->b;
第四步最难理解，先说明：从进入函数，move(3)中实际包含三个部分：一是move(n=2,a,c,b)，二是cout<<a<<"-->"<<c<<endl，三是move(2,b,a,c),即实参下的5、6、7行语句，三个属于并列关系，上面已经完成三个输出的三个步骤都属于三个部分的第一部分move(n=2,a,c,b)，即第一部分已完成，于是将继续执行并列的语句6：cout<<a<<"-->"<<c<<endl，(需要注意的是，同上面一样，此时已近完成m1的递归，程序回到n=3的最外层，所以此时a,c的值分别从move(3,a,b,c)中获取）完成第四步 a->c;
以上理解透了，接下来就非常简单，程序进入语句7，开始递归m2，其过程与m1完全相同，也是最开始的三步，简单写出：
第5行，由move(2,b,a,c)下推出move（1,b,c,a),进入2、3行，完成第五步 b-->a;
第6行，a,c从move(2,b,a,c)取值，完成第六步 b-->c;
第七行，move(1,a,b,c)，完成第七步 a-->c;
-------------------------------------------------
本人新手一枚，出现任何低级或高级错误都很正常，还望发现的给以指教，先行谢过!
另，以上内容为百度大量资料学习后完成，字字虽均为幸苦打出，却也确实借鉴了不少内容，如有侵权还望海涵，图为自己填出，旨在加深自己理解，所看资料有知道新浪各种编程论坛csdn就不再列出。
-------------------------------------------------
[解决办法]楼主，谢谢！
但是在http://sznoi.cn/oj/ShowProblem?problemid=d093 中，要求将每一步是第几个板子写出来，怎么办？
