汉诺塔感悟.docx
《汉诺塔感悟.docx》由会员分享，可在线阅读，更多相关《汉诺塔感悟.docx（10页珍藏版）》请在冰点文库上搜索。
汉诺塔感悟
汉诺塔……..不废话了，算法用的是递归，代码如下，要说代码，估计都能写出来，关键是内在的内容不是很清楚。
下面来说一下，编译器下的汉诺塔代码执行顺序以及解释：
#include
usingnamespacestd;
voidhanoi（intn,charsrc,charmedium,chardest）
{
staticintk;
k=0;
if（n==1）
cout<"<else
{
1：
hanoi（n-1,src,dest,medium）;
2：
cout<"<3：
hanoi（n-1,medium,src,dest）;
}//代码前面的数字是为了方便说明以下的解释。
k++;
if（k==6）
{
cout<k=0;
}
}
intmain（）
{
intm;
cout<<"Enterthenumberofdiskes:
";
cin>>m;
cout<<"thestepstomoving"<hanoi（m,'A','B','C'）;
return0;
}
就以n=5，来作为例子：
毫无疑问，下表是编译器下执行语句1时递推过程：
本阶段
n
src
medium
dest
调用阶段
Hanoi（5,’A’,’B’,’C’）
5
A
B
C
1:
Hanoi（4,’A’,’C’,’B’）
Hanoi（4,’A’,’C’,’B’）
4
A
C
B
1:
Hanoi（3,’A’,’B’,’C’）
Hanoi（3,’A’,’B’,’C’）
3
A
B
C
1:
Hanoi（2,’A’,’C’,’B’）
Hanoi（2,’A’,’C’,’B’）
2
A
C
B
1:
Hanoi（1,’A’,’B’,’C’）
Hanoi（1,’A’,’B’,’C’）
1
A
B
C
输出：
AC
说明：
{
根据递归的特点，也就是栈：
先进的后出。
而我们的盘子是从下往上数的，也就是说最上面的那个盘子是第n个。
在语句1的递推阶段，第n个盘子是最先进栈的，那么就会最后一个出栈。
这正符合我们所想的。
由于
if（n==1）
cout<"<Hanoi（1,’A’,’B’,’C’）
1
A
B
C
输出：
AC
如果看到这个“3：
Hanoi（1,’C’,’A’,’B’）”和“1：
Hanoi（1,’B’,’C’,’A’）”代表的意思是：
执行语句3和执行语句1。
}
那么出栈顺序应该是：
接着就开始了编译器下语句1的回归之旅：
个人觉得这个旅途比较痛苦，但是痛苦只是暂时的，痛苦过后对于这个问题就通了。
所有还是值得的。
n=2.
本阶段
N
src
medium
dest
调用阶段
语句2
2
A
C
B
输出：
AB
语句3
2
A
C
B
3：
Hanoi（1,’C’,’A’,’B’）
Hanoi（1,’C’,’A’,’B’）
1
C
A
B
输出：
CB
n=3.
本阶段
n
src
medium
dest
调用阶段
语句2
3
A
B
C
输出：
AC
语句3
3
A
B
C
3：
Hanoi（2,’B’,’A’,’C’）
Hanoi（2,’B’,’A’,’C’）
2
B
A
C
1：
Hanoi（1,’B’,’C’,’A’）
Hanoi（1,’B’,’C’,’A’）
1
B
C
A
输出：
BA
语句2
2
B
A
C
输出：
BC
语句3
2
B
A
C
3：
Hanoi（1,’A’,’B’,’C’）
Hanoi（1,’A’,’B’,’C’）
1
A
B
C
输出：
AC
插入一段话:
从n=2和n=3可以看出一部分东西，尤其是n=3最为明显：
编译器在执行的时候，语句1，语句2，语句3是分工的。
打个比方：
语句1就只会把src针上的k-1个盘子借助dest针放到medium针上。
{这里不说A,B,C针是因为src,dest,medium只是代之不同的针，从上面的执行过程也可出}
语句3就只会把medium中的一个盘子放到dest处。
如果medium处多于一个盘子，那么语句3就调用函数，把medium中的盘子交给语句1，让其把medium中的盘子分成一个才可！
（从上面的批注[11][12]可以很好的理解。
）
{
if（n==1）
cout<"<}
至于语句2，其功能就是把语句1和语句3之间实现的每一个步骤打印出来。
}
n=4.
本阶段
n
src
medium
dest
调用阶段
语句2
4
A
C
B
输出：
AB
语句3
4
A
C
B
3：
Hanoi（3,’C’,’A’,’B’）
Hanoi（3,’C’,’A’,’B’）
3
C
A
B
1：
Hanoi（2,’C’,’B’,’A’）
Hanoi（2,’C’,’B’,’A’）
2
C
B
A
1:
Hanoi（1,’C’,’A’,’B’）
Hanoi（1,’C’,’A’,’B’）
1
C
A
B
输出：
CB
语句2
2
C
B
A
输出：
CA
语句3
2
C
B
A
3：
Hanoi（1,’B’,’C’,’A’）
Hanoi（1,’B’,’C’,’A’）
1
B
C
A
输出：
BA
语句2
3
C
A
B
输出：
CB
语句3
3
C
A
B
3：
Hanoi（2,’A’,’C’,’B’）
Hanoi（2,’A’,’C’,’B’）
2
A
C
B
1：
Hanoi（1,’A’,’B’,’C’）
Hanoi（1,’A’,’B’,’C’）
1
A
B
C
输出：
AC
语句2
2
A
C
B
输出：
AB
语句3
2
A
C
B
3：
Hanoi（1,’C’,’A’,’B’）
Hanoi（1,’C’,’A’,’B’）
1
C
A
B
输出：
CB
n=5.
本阶段
n
src
medium
dest
调用阶段
语句2
5
A
B
C
输出：
AC
语句3
5
A
B
C
3：
Hanoi（4,’B’,’A’,’C’）
Hanoi（4,’B’,’A’,’C’）
4
B
A
C
1：
Hanoi（3,’B’,’C’,’A’）
Hanoi（3,’B’,’C’,’A’）
3
B
C
A
1：
Hanoi（2,’B’,’A’,’C’）
Hanoi（2,’B’,’A’,’C’）
2
B
A
C
1：
Hanoi（1,’B’,’C’,’A’）
Hanoi（1,’B’,’C’,’A’）
1
B
C
A
输出：
BA
语句2
2
B
A
C
输出：
BC
语句3
2
B
A
C
3：
Hanoi（1,’A’,’B’,’C’）
Hanoi（1,’A’,’B’,’C’）
1
A
B
C
输出：
AC
语句2
3
B
C
A
输出：
BA
语句3
3
B
C
A
3：
Hanoi（2,’C’,’B’,’A’）
Hanoi（2,’C’,’B’,’A’）
2
C
B
A
1：
Hanoi（1,’C’,’A’,’B’）
Hanoi（1,’C’,’B’,’A’）
1
C
A
B
输出：
CB
语句2
2
C
B
A
输出：
CA
语句3
2
C
B
A
3：
Hanoi（1,’B’,’C’,’A’）
Hanoi（1,’B’,’C’,’A’）
1
B
C
A
输出：
BA
语句2
4
B
A
C
输出：
BC
语句3
4
B
A
C
3：
Hanoi（3,’A’,’B’,’C’）
Hanoi（3,’A’,’B’,’C’）
3
A
B
C
1：
Hanoi（2,’A’,’C’,’B’）
Hanoi（2,’A’,’C’,’B’）
2
A
C
B
1：
Hanoi（1,’A’,’B’,’C’）
Hanoi（1,’A’,’B’,’C’）
1
A
B
C
输出：
AC
语句2
2
A
C
B
输出：
AB
语句3
2
A
C
B
3：
Hanoi（1,’C’,’A’,’B’）
Hanoi（1,’C’,’A’,’B’）
1
C
A
B
输出：
CB
语句2
3
A
B
C
输出：
AC
语句3
3
A
B
C
3：
Hanoi（2,’B’,’A’,’C’）
Hanoi（2,’B’,’A’,’C’）
2
B
A
C
1：
Hanoi（1,’B’,’C’,’A’）
Hanoi（1,’B’,’C’,’A’）
1
B
C
A
输出：
BA
语句2
2
B
A
C
输出：
BC
语句3
2
B
A
C
3：
Hanoi（1,’A’,’B’,’C’）
Hanoi（1,’A’,’B’,’C’）
1
A
B
C
输出：
AC
如果看完，并看懂了就应该知道
if（n==1）
cout<"<else
{
1：
hanoi（n-1,src,dest,medium）;
2：
cout<"<3：
hanoi（n-1,medium,src,dest）;
}
的含义。
其中语句1就是针中的盘子在语句3的指令或者说配合下，把n个盘子一步步细化，分而治之。
递归就会把大问题先一股脑放到一个容器里，接着从中一点一点的拿出来，然后把这拿出来的小问题给解决掉。
再从容器里再拿出一小点出来，再把它解决掉。
就这样，慢慢的就把一个大问题解决完了。
而这个容器就是栈。
大化小，小化无。
就是这个道理。
一个大问题其实就是很多小而易的小问题堆积而成，只要找到了这个堆积入口，那么这个大问题不攻自破。
升级会员 