http://b82.photo.store.qq.com/http_imgload.cgi?/rurl4_b=a3de204a7706c294d5f33e7ab9ea2aca7d533ddfb259f5e808620512da007a0bedb62169604a587f82cb9e862953aad04813962b0c794cd7e7a435a24131947a74029f70ac2b1fa4596737b51def21028480fafb&a=82&b=82
汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上安大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
这个问题在高中数学课上也曾研究过，不过记得那时班上整体效果奇差，题的基数只是3，最后结果却只有我得出，貌似就是汉诺塔的数学计算公式
sum=2^n-1
将64带入公式，可得出 sum(64)=2^64-1=18446744073709551615
很蛋疼的数据。
然后的然后，下面的东西看不懂的可以直接绕道了。。。。。
----------------------------长的像我的都是分割线--------------------------------
前日学习C++指针与引用一章时例题处出现这个本该属于递归函数的题，当日考虑了很久，依然是一头雾水，加上近日感冒头痛，也确实木有心情，想着就头痛啊。当晚请教高手，一句“单步调试”就打发，估计问多了人也烦了，但是尼玛我确实还不会单调啊，今天终于好转，借助百度，却全是只分析递归整体过程，绝不分析内部的流程，借其理解了不少，无奈还是得拿起笔自己一步一步跟踪程序走向（只有不会单调的苦逼才这么干吧?)，废去稿纸几篇，终于理清了头绪。
从头到尾只有一个感叹：写出这算法的不是人，abc移来移去如此复杂的东西居然几行代码就给搞得天衣无缝。
据说学递归不要太注意每一步，只要能把主要过程想明白了，限定条件设定正确，一切就ok了，但是每一步都还没明白怎么出总体思想啊！
-------------------------------------------------------------------------------------
先贴代码：
http://b77.photo.store.qq.com/http_imgload.cgi?/rurl4_b=a3de204a7706c294d5f33e7ab9ea2aca930d3ebdb0a74d01a134c8524a43dd51e2eedd1c0f6c5db02ca47f0d199ba497037d678cc50384ae187cee51ca440228fe939b5ade0af297901bd48afc38b7c45fdea286&a=77&b=77（文尾附文字代码）
-------------------------------------------------------------------------------------
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分别指程序中第一和第二个move(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就不再列出。
-------------------------------------------------------------------------------------
附：完整代码
#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');
}
加载中…
(2011-08-25 18:34:03)