直接写出移盘步骤的非递归非栈的汉诺塔算法
大概在初中的时候，玩起了汉诺塔小游戏，曾经还乐此不疲。慢慢的总结出了一些规律。无论几个盘子，都能很快的以最少步搬完。后来学C语言，看到了谭浩强那本书上关于汉诺的观点，心里有点疑惑。再后来张小东老师给我们上操作系统，一次在课后向张老师谈起了汉诺塔，说到曾经的一点想法。得到张老师的鼓励，于是有了半个月废寝忘食的投入。得出了两种非递规非栈算法。写完了，有点不力量力，整理成了小论文，本来有点想法。后来一直封存在电脑里。想想还是发到这里，分享一下想法，或者可以当作一种参考。如何在必要的时候抛弃用栈去转化递规算法。。
内容有点长，代码我发部分上来，两种解法我称之为：树解汉诺塔算法和图解汉诺塔算法。其实本身和树与图没什么太大得联系，只是描述起来有点类似。方便起见我这样称呼。
直接写出移盘步骤的非递归非栈的汉诺塔算法
――――一种可以在PC机上移动任意多个盘子的汉诺塔算法
指导教师：哈工大（威海）计算机科学与技术学院 张小东
哈工大（威海）数学系04级： 王逸群
一：概要
关于汉诺塔的移盘算法，常规的做法是用递归来做。或者是用将递归用栈转化的解决一般递归问题的非递归算法来做。这样的算法有个共性：耗内存。并且占用的内存随盘子数量N的增大呈指数级数增长。面对30个盘子的移动步骤，1G内存心有余而力不足。
对汉诺塔移动规律进行深入的分析，我发现汉诺塔的规律是有迹可循的。继而我导出了两种不用栈的的非递归算法，一个是从树形规律发祥的，不妨称为：树解汉诺塔算法；二是从图形规律发现的，不妨称为：图解汉诺塔。这两种算法都不用递归来做，对N个盘子的移动，消耗的内存在3N到4N之间。和2的N次方指数幂相比，优化是很可观的。
二：移动规律
下面将给出两种算法的基本思路，在此之前，先将两个算法的理论依据即规律在此说明，首先约定几个规则：
一：首先将汉诺塔的三根柱子标记为：柱S（盘子初始位置），柱T（临时存放盘子的堆），柱D（盘子搬运的目的地）；
二：将S,T,D三柱按D,S,T摆放（这样做不会影响移动）,并将它们循环看待,即从D到S为向右移，T到D也看为向右移动。同理，S到D和D到T都看为是向左移；
三：将初始盘子从低（最大盘子）到顶（最小盘子）按1到N标上序号，并规定在移动过程中各盘子的序号总是不变的。
有了上面的三个规则，下面给出汉诺塔移动规律：
A：在移动过程中，任一步骤，必满足奇偶规则，这个奇偶规则是：移动的盘子若是奇数，则必向左移，若是偶数，则必向右移动（注意：这里的左右是有上面三个约定前提而定的）
B：这个规律稍复杂一些，首先，对于N个盘子，移动所需最小步骤为2的N次方减一，
这个由数学归纳法很明显证明。将N个盘子的移动步骤分为N大步，第一大步为将序号为1盘子移至D，则必先
a：将上面N－1个盘子移至T，由上面的最小步骤数需要2^(N－1)－1步（2^X表示2的X次方）步；
b：将1号盘子从S移至D，为一步
上述两步相加：2^（N－1）－1＋1＝2^（N－1）
依此类推，对于第M大步，它是将序号为N－M的盘子移至D堆（注意：此时未必是从S到D）显然它需要的步骤数为2^（N－M－1），因为要先将上面的N－M－1个盘子移到另一柱，
则最小步数为2^(N－M－1)－1，最后将N－M移至D，共2^(N－M－1)步。
第N大步为将N号盘子移动到D，显然是2^(N－N)=1步。
第M大步涉及到移动的盘子显然是N－M号盘到N号盘共M个盘，将每大步内的2^(N－M－1)步称为小步，都从1到2^(N－M－1)表示，那么小步骤small_step和移动的盘子序号满足下面关系（将移动时要移动的盘子称为操作数（data_op）），移动N－J号盘子时（M<N－J<N），其步骤数必满足：2^(J+1)*K＋2^J(0=<K,且(2^(J+1)*K+2^J)<=2^(N－J)),则只要满足(STEP－2^J) MOD 2^(J+1) =0 的步骤STEP，该步骤移动的盘子的序号必是N－J。
三：两种解法思路
A,B两个移动规律我将在后面给出证明，这里先给出两种算法的思路：
1：树解汉诺塔算法
分析指明，若将小步骤数按大步序号分层排列，并将每个小步看为一个节点，把大步看为层数，则整个移动步骤数按上述规定构成一个高为N的完全二叉树。（确切的说是一颗倒立的二叉树），按正常二叉树看待，节点满足，所有右节点为N，所有左节点为N减去右节点。如图：
从该图就很明显看出汉诺塔的递规规律乐，每一大步可分为两部分，前一部分为下一步的重复，后一部分仅将最后一小步的盘子序号减小1。若将结点写成两子结点的差，则上图变为：
对与N个盘子分为N大步搬，这里就要用N个循环for(Big_step=1;Bg_step<=N;Big_step++)
在每个大步骤Big_step里一小步如此移动：
1：首先根据步骤STEP找出该步要移动的盘子序号，这个盘子序号的取得由规律B中算出，从P到N扫描，若满足(STEP－2^J) MOD 2^(J+1) =0，则该步骤移动的盘子为H+1－J(事实上由于P本身不可能达到N，这点由上面B的K范围可以看出，同样由上面，P一定能在它本身的范围找到，所以这里不用在设置它的范围，只要取个最大的数，保证循环能把所有的情况取完就可以了，而且比较次数的平均值是能算出来的。)，下面给出该函数的C++代码，这里用2^P做为循环，因为整形数据用LOG函数的话会损失精度，这里用两个变量跟踪数据变化，可以避免每次计算pow(2,P)的值，从而缩短运行时间.
int Get_data_op(int step)//取得操作数函数
{
if(step%2==1)
return H;//奇数位步骤为H
else{
int Max_pow_H=int(pow(2,H));
int m2=2;int e2=2;
while(e2<=Max_pow_H)
{
if ((step-e2)%(e2*2)==0)
return (H+1-m2);
m2++;
e2*=2;
}
}return 0;
}
（这样做一定不会出现对本不是该类的步骤却返回了同一个盘子序号的情况，见证明A_1）
2：接下来这步就比较简单了，根据int Get_data_op(int step)返回的盘子序号寻找该盘子所在柱，由于只能移动每个柱子的顶端的盘子，所以用三各循环，依次比较三个柱子顶元素即可。
3：寻找移入的柱子，这个也简单，由于该步移动的盘子序号已经知道，那么可以知道它的奇偶性，再者又由上面2知道了移出的柱子，根据规律A就可以知道移入柱子了。
上面三步就可以移动盘子了，下面给出这个解法的从C++源代码：
分析：该算法由步骤数STEP给出该步骤移动盘子序号，当盘子过大时由于数字太大，可以解决大数运算的方法解决，这已不是这里关心的问题。但这样会影响算法的执行效率。
而图解汉诺塔法则要好得很多。
证明A_1:
设有两个步骤STEP1和STEP2，设STEP1=2^(I+1)×K＋2^I，STEP2=2^(J+1)*K+2^J（i!=j）
(这里上面两式要满足上面得条件)
（1）：第一种情况是i>j
这时 （2^(i+1)*k+2^i－2^j）/(2^(j+1)=2(i－j)*k+2^(i－j－1)－1/2
（a）
容易知道(a)必不为整数；
（2）：第二种情况时i<j
这时（2^(i+1)*k+2^i－2^j）/(2^(j+1)＝2^(i—j)*k+2^(i－j－1)－1/2
设b=j－i(b>=1)则有2^(—b)*k+2^(－b－1)－1/2=k/(2^(－b))+1/(2^(b+1))－1/2
(b)
从（b）式看1/(2^(b+1))－1/2=－(2^b－1)/(2^(b+1))分母为一个2^(b+1)项而前项k/(2^(－b))不可能分解为一个整数和一个分母为2^(b+1)数量级的和。那么上式必不可能分解为一个整数式。
由上面两种情况知道，按减后作模对自然数的等价类划分是可行的，也就是说按上面的做法，不可能会出现下面两种错误：
1：原本对应小模的差，没有在作小模的时候找到对应的操作数，而错误的对应了后面的大模对应操作数；
2：原本应作大模差对应的操作数，在错误的在作小模就找到了一个错误的操作数。
树解汉诺塔的c++代码：
#include<iostream.h>
#include<stdio.h>
#include<conio.h>
#include<io.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
FILE *fptr;//用于将移动步骤保存到文本文件里
#define MAXSIZE_H 100000000//移动盘子数量
int string[MAXSIZE_H];//用来输出时的暂存的
typedef struct data_home{
int body[MAXSIZE_H];
int ta_h;
char data_flag;
}data_home;//用来存储每个柱子的盘子
data_home *s;
data_home *d;
data_home *t;//三个柱子的盘子
data_home *now_data;//指向移入的柱子
data_home *last_data;//指向移出的柱子
int now_data_f=0;//表示当前柱子，与data_home->data_flag对应
int H;//表示塔的高度
int Get_data_op(int step);//取得操作数函数
void Move_data_op();//移动盘子函数
data_home *Get_data_home_out(int data_op);//取得移出柱子
data_home *Get_data_home_in(int now_data_f);//取得移入柱子
void Print_data_home();//输出函数
//////////////////////////////////////////////////
void main()
{
s=new(data_home);
s->data_flag ='s';
t=new(data_home);
t->data_flag ='t';
d=new(data_home);
d->data_flag ='d';//申请三个柱子空间，这里三个柱子都申请了H个空间
now_data=s;
last_data=s;
while(1)//选择菜单，便于调试数据
{
char ifstart;
cout<<"按s开始移塔"<<endl;
cout<<"按q退出"<<endl;
ifstart=getch();
if(ifstart=='q')
exit(0);
else if(ifstart=='s')
{
Move_data_op();//移盘函数
}
}
}
2007年5月
代码实在太长，发上来后我又删除了绝大部分，有人感兴趣的话我再发。奇偶规律的证明和图解汉诺算法我暂作保留。如果必要我再考虑发上来。
在这里也要感谢张小东老师那时耐心的听我条理不清的证明论述！
(再者，代码中大部分的头文件是没必要的，编程时习惯了把各种常用的头文件加上。初始时给每个“塔”放真正的“盘子”其实也时没有必要的，而且因此看不到结果（我运行了半个多小时，大概才放上2000000个盘子）去了之后，可以直接看到结果，还有是如果盘子数过大，可能提示数组过大，但一定程度内还是可以运行的，只要把初始赋值去了，只出每次结果就可以）
电邮:yiqunwang1985@yahoo.com.cn
QQ 405441695
这个是程序运行的结果图，为了显示明了，我用了很多回车，所以这里只能显示一部分。见谅
上图也可以看出，每步都真正的为塔上放上了盘子，这样很方便的分析结果，但是运行速度大大降低，去了后就快多了。
感谢子小吉吉耐耐心心的看完我冗长的证明，并指出其中的错误。其中
移动N－J号盘子时（M<N－J<N），其步骤数必满足：2^(J+1)*K＋2^J(0=<K,且(2^(J+1)*K+2^J)<=2^(N－J)),则只要满足(STEP－2^J) MOD 2^(J+1) =0 的步骤STEP，该步骤移动的盘子的序号必是N－J。
的做法后边也提到了
在每个大步骤Big_step里一小步如此移动：
1：首先根据步骤STEP找出该步要移动的盘子序号，这个盘子序号的取得由规律B中算出，从P到N扫描，若满足(STEP－2^J) MOD 2^(J+1) =0，则该步骤移动的盘子为H+1－J(事实上由于P本身不可能达到N，这点由上面B的K范围可以看出，同样由上面，P一定能在它本身的范围找到，所以这里不用在设置它的范围，只要取个最大的数，保证循环能把所有的情况取完就可以了，而且比较次数的平均值是能算出来的。)
我把各各盘号对应的步骤做一张表格就明了了：
首步骤到0的距离 对应盘号 步骤数
1 N 1 3 5 7 9。。。
2 N-1 2 6 10 14 18。。。。
4 N-2 4 12 20 28 。。。
8 N-3 8 24 30 46。。。。
这样，等价类的关系和上面的证明就很明了了!
[ 本帖最后由 yiyanwan77 于 2007-11-6 09:45 编辑 ]
附件: 您所在的用户组无法下载或查看附件
搜索更多相关主题的帖子:
汉诺塔 递归 算法 汉诺塔 递归 算法
