我的数据结构学习从汉诺塔开始，这个简单的算法我可是整整想了一晚上，现在终于有点明白了，上机单步了几遍，有所了解，
，还是写点什么以供以后参考，也希望能对正在学算法的盆友有所裨益······
总得来说汉诺塔就是层叠递归调用的典型例子，一直是利用A—>B A-->C B-->C这样的单个步骤。
具体来说，当盘数大于一时，不违背原则下（过程中总是大在下小的在上），A先借助B再放到C上。总是把盘数看成两个来解决问题。
比如说，当盘数为二时，顾名思义，这个很简单只要三下即可完成。这个时候，可以这样想，如果是三个，就相当于二个完成，还有一个待完成，（注意要有把问题简化为两个盘的思想,这样是递归思想的思想实现），那么把完成的看成一个，剩下待完成的看成一个（带完成的还可以把最近要完成的看成一个，剩下的先别管），这样问题就回到了二个盘数时的第一步完成状态，接下来就是递归的精华了（我是膜拜数学的强大，一个式子可以表达万种情感），然后C上的（二个看成一个那）在借助B放到A上，这样第三个就可以从B放到C上，接下来又是二个了（这个是真正的二个），看基本步骤完成。当盘数是N时，也是利用这种思想，一步一步简化，递归完成。
接下来谈一下N个盘要几次完成问题
书上说是2^n-1次，经过计算验证是正确的。当然我有我的思考计算，哈哈····思考如下：
当完成n个时设用M(n)次，那么，如上我说的算法当完成n个（也就是n+1个时了）还有一个，这时需要把在C上的看成一个，借助B移动到A上（这时最后一个已到B上），当然要做M（n）次搬动了，完成后，B上的最后一个（（n+1）个）搬动到C上。这时，问题又回到了n次开始，当然需要M(n)次了。这么一来就是M（n）*2次，加上最后一个的两次，总共是M(n)*2+2=M(n+1)次，好了现在是纯数学问题了，可以利用数学知识算出来最后结果，（我还没算，哈哈，我数学不好呀），步骤没错的话，应该结果是M（n）=2^n-1.
以上只是个人体会，写的有些弱智，有什么不正确的还请高人指教。
下面是程序具体实现，（上面为C下面C++）仅供参考
······
- #include<stdio.h>
- int a=0;
- void hanoi(int n, char A, char B, char C)
- {
- a++;
- if(n==1)
- {
- printf("Move sheet %d from %c to %c\n",n,A,C);
- }
- else
- {
- hanoi(n-1,A,C,B);
- printf("Move sheet %d from %c to %c\n",n,A,C);
- hanoi(n-1,B,A,C);
- }
- printf("a是：%d\n",a);
- }
- int main()
- {
- int n;
- printf("请输入盘数：");
- scanf("%d",&n);
- hanoi(n,"A","B","C");
- return 0;
- }
- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
- #include<iostream>
- using namespace std;
- void move(int n, char s, char d)
- {
- cout<<n<<","<<s<<"->"<<d<<endl;
- }
- void hanoi(int n, char A='A', char B='B',char C='C')
- { if(1==n)
- move(n,A,C);
- else
- {
- hanoi(n-1,A,C,B); move(n,A,C); hanoi(n-1,B,A,C);
- }
- }
- int main()
- {
- int i=0;
- cout<<"请输入盘数：";
- cin>>i;
- hanoi(i);
- return 0;
- }
- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~