再议汉诺塔一
(2007-05-01 23:00)
分类： 数据结构
汉诺塔作为递归或堆栈的经典例题存在于各种数据结构，程序设计算法等各种书籍中存在好多年了。然而，可能有人并不知道汉诺塔的问题的典故，汉诺塔来源于印度传说的一个故事，上帝创造世界时作了三根金刚石柱子，在一根柱子上从下往上按大小顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一回只能移动一个圆盘。有预言说，这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今仍在一刻不停地搬动着圆盘。恩，当然这个传说并不可信，如今汉诺塔更多的是作为一个玩具存在。
最近在杭电上做了几题关于汉诺塔的题目，有点心得，现记下，权当做题笔记。
一，经典汉诺塔
问题描述：假设有3个分别命名为X，Y，Z的塔座，在塔座X上插有n个直径大小各不相同、依小到大编号为1，2，……n个圆盘。现要求将X轴上的n个圆盘移至塔座Z上并仍按同样顺序叠排，圆盘移动时必须遵守下列规则：
（1）每次只能移动一个圆盘；
（2）圆盘可以插在X，Y和Z中的任一塔座上；
（3）任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。
求n个盘至少需移动的次数。
分析：设F[n]表示将n个盘从按规则从X柱移到Z柱至少需要移动的次数，显然，当n=1时，F[n]=1；当n>1时，我们将移动盘之的过程分为三步：
1，将X柱上的n-1个盘依靠Z柱移到Y柱上，这个需要F[n-1]步；
2，将X柱上剩下的一个盘（最大的盘）移到Z柱上，这个需要1步；
3，将Y柱上的n-1个盘依靠X柱移到Z柱上，这个需要F[n-1]步；
所以移完n个至少需要的步数F[n]=F[n-1]+1+F[n-1]=2*F[n-1]+1; 而F[1]=1；由以上两个等式可以推出求F[n]的一般式，即F[n]=2^n-1;
C++实现：略。
另外一种方法，是使用递归，分析上一种方法的第一步，其实将n-1个盘从X柱上依靠Z柱移到Y柱上，这又是一个汉诺塔，只是问题的规模小1，因此可以用同样的方法求解。设步数计数器int count=0;
则可用以下算法算出count.
C++实现：
void hanoi(int n,char x,char y,char z)
{
//将塔座X上按直径大小由小到大且自上而下编号为1至n的n个圆盘按规则搬到塔座Z上，Y可用作辅
//塔。
if(n==1） count++;//count为全局变量，初值为0；
else
{
hanoi(n-1,x,z,y);
count++;
hanoi(n-1,y,x,z);
}
}
由此可以计算出至少需要移动的次数。
待续……