汉诺塔问题非递归算法集锦
汉诺塔问题非递归算法集锦巧若拙（欢迎转载，但请注明出处：http://blog.）
汉诺塔问题介绍：
在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片，一次只移动一片，不管在哪根针上，小片必在大片上面。当所有的金片都从梵天穿好的那根针上移到另外一概针上时，世界就将在一声霹雳中消灭，梵塔、庙宇和众生都将同归于尽。
汉诺塔问题递归算法思路简单且代码简洁，算得上最美代码之一：
int count = 0;//全局变量，累积操作步数
void Hanoi(int n, char a, char b, char c)//递归算法
{
if (n == 1)//如果只有一个盘，直接将其从a柱移动到c柱
printf("%d: %d %c -> %c ", ++count, n, a, c);
else
{
Hanoi(n-1, a, c, b); //利用c柱中转，将n-1个盘从a柱移动到b柱
printf("%d: %d %c -> %c ", ++count, n, a, c);//将第n个盘从a柱移动到c柱
Hanoi(n-1, b, a, c);//利用a柱中转，将n-1个盘从b柱移动到c柱
}
}
但是，非递归算法就没那么容易理解了，笔者搜集整理了以下几种方案（还有几种方案，由于本人一时未能理解，暂时不予贴出，同时请聪明的你补充简明易懂的算法，谢谢！）
常见的思路是利用栈对递归算法进行非递归转换，李春葆老师编著的《数据结构（c语言篇）——习题与解析》（清华大学出版社）一书中介绍了一种方法。该方法设计了一个数据结构 struct act {int flag, num; char x, y, z;} S[2000]; 存储当前操作信息，其中flag==0表示直接移动num号圆盘，否则需要进一步分解；num表示当前操作移动盘子的编号，x，y，z表示当前操作对应的3个塔柱，分别是出发柱，中点柱和目标柱。
算法的基本思路与中序遍历二叉树很类似，深入理解该算法后，我对书中的代码进行了一些改进，使其更简洁明了。代码如下：
void Hanoi_1(int n, char a, char b, char c)//非递归算法1
{
struct act {int flag, num; char x, y, z;} S[2000]; //存储当前操作信息，flag==0表示直接移动num号圆盘，否则需要进一步分解
int top, m;
char ta, tb, tc;
S[0].flag = 1;//初值入栈
S[0].num = n;
S[0].x = a;
S[0].y = b;
S[0].z = c;
top = 0;
count = 0;
while (top >= 0)
{
if (S[top].flag == 0 || S[top].num == 1)//直接将num号圆盘从x移动到z
{
printf("%d: %d %c -> %c ", ++count, S[top].num, S[top].x, S[top].z);
--top;
}
else
{ //提取栈顶信息
m = S[top].num;
ta = S[top].x;
tb = S[top].y;
tc = S[top].z;
//将 Hanoi(n-1, b, a, c); 操作入栈 ，覆盖原栈顶信息
S[top].num = m - 1;
S[top].x = tb;
S[top].y = ta;
S[top++].z = tc;
//将 将第m个盘从a柱移动到c柱 操作入栈
S[top].flag = 0;
S[top].num = m;
S[top].x = ta;
S[top++].z = tc;
//将 Hanoi(n-1, a, c, b); 操作入栈
S[top].flag = 1;
S[top].num = m - 1;
S[top].x = ta;
S[top].y = tc;
S[top].z = tb;
}
}
}
非递归算法1是对递归算法的模拟过程，但由于其把当前操作分成两种类型，即直接移动和进一步分解，人为地增加了算法的复杂度。实际上，仔细分析二叉树的中序遍历非递归算法（详见拙作《史上最简明易懂非递归遍历二叉树算法》http://blog.），我们可以发现，完全可以采用类似的方法把汉诺塔非递归算法转化为非递归算法，思维方式几乎一模一样。代码如下：
void Hanoi_2(int n, char a, char b, char c)//非递归算法2
{
struct act {int num; char x, y, z;} S[MAX]; //存储当前操作信息
int top = -1;
int count = 0;
while (n > 0 || top >= 0)
{
if (n > 0)//入栈，并搜索左孩子,即将 Hanoi(n-1, a, c, b); 操作入栈
{
S[++top].num = n--;
S[top].x = a;
S[top].y = b;
S[top].z = c;
a = S[top].x;
b = S[top].z;
c = S[top].y;
}
else//输出并退栈，搜索右孩子，即将 Hanoi(n-1, b, a, c); 操作入栈
{
printf("%d: %d %c -> %c ", ++count, S[top].num, S[top].x, S[top].z);
n = S[top].num - 1;
a = S[top].y;
b = S[top].x;
c = S[top--].z;
}
}
}
非递归算法1和2是利用栈模拟递归过程的基本方法，我们还可以从另外一个角度来分析汉诺塔问题。对于有n个盘子的汉诺塔问题，需要操作的步骤为2^n – 1，如果每一个步骤看成一个节点，则刚好构成一棵满二叉树，树高h与盘子数量的关系为h==n。结点所在的层数与对应盘子的编号关系为level==n+1-level，即盘子1在第n层，盘子n在第1层；若某个结点的操作为“盘子n从A->C”，则其左孩子操作为“盘子n-1从A->B”，右孩子操作为“盘子n-1从B->C”；中序遍历满二叉树，结点的编号恰好对应移动的次序。
因此我们可以构造一棵满二叉树，然后中序遍历该二叉树即可。代码如下：
void Hanoi_3(int n, char a, char b, char c)//非递归算法3，缺点是需要辅助空间太大
{
struct act {int num; char x, y, z;} BT[132000]; //存储每一步操作的满二叉树，假设n<=17.
int S[MAX] = {0};
int i, top, count = 0;
BT[1].num = n;//为根结点赋值
BT[1].x = a;
BT[1].y = b;
BT[1].z = c;
n = pow(2, n-1);
for (i=1; i<n; i++)//为每个节点的左右孩子赋值
{
BT[i+i].num = BT[i+i+1].num = BT[i].num - 1;
BT[i+i].x = BT[i+i+1].y = BT[i].x;
BT[i+i].z = BT[i+i+1].x = BT[i].y;
BT[i+i].y = BT[i+i+1].z = BT[i].z;
}
//中序遍历满二叉树
n += n;
i = 1;
top = -1;
while (i < n || top >= 0)
{
if (i < n)//入栈，并搜索左孩子
{
S[++top] = i;
i += i;
}
else//输出并退栈，搜索右孩子
{
i = S[top--];
printf("%d: %d %c -> %c ", ++count, BT[i].num, BT[i].x, BT[i].z);
i += i + 1;
}
}
}
算法3的思路简明易懂，代码也很简洁，但是有一个致命缺陷，就是需要的辅助空间太多，当n较大时不太适用。有没有更好的方法呢？
其实已经走到这一步了，再仔细观察一下这棵满二叉树，可以发现更多的规律（请读者自行画出满二叉树图，以便于理解算法）。以下是我的观察结果：
①树高h与盘子数量的关系为h==n。结点所在的层数与对应盘子的编号关系为level==n+1-level，即盘子1在第n层，盘子n在第1层;
②中序遍历满二叉树，结点的编号恰好对应移动的次序。
③第n层共2^(n-1)个结点，它们能被2^0整除且不能被2^1整除: 1,3,5,7,9,...2^n - 1.
第n-1层共2^(n-2)个结点，它们能被2^1整除且不能被2^2整除: 2,6,10,14,...2^n - 2.
......
第3层 共2^2个结点，它们不能被2^(n-2)整除: 2^(n-3) * 1, 2^(n-3) * 2, 2^(n-3) * 3, 2^(n-3) * 4
第2层 共2^1个结点，它们不能被2^(n-1)整除: 2^(n-2) * 1, 2^(n-2) * 2
第1层 共2^0个结点，它不能被2^n整除: 2^(n-1) * 1
④奇数层各个结点的操作依次是：A->C、C->B、B->A、A->C、C->B、B->A、…模3循环;
偶数层各个结点的操作依次是：A->B、B->C、C->A、A->B、B->C、C->A、…模3循环;
综合以上分析,得出以下结论
①盘子数N确定后,步骤总数m=2^n-1;
②第i(0<i<2^n)步所处的层数是确定的,当i能被2^(n-j)整除且不能被2^(n+1-j)整除时,i处在第j层;
③第i(0<i<2n)步在第j层的顺序号(从0开始)k=i/s，其中s = 2<<(n-j);
根据上述分析，我们可以给出相应的代码：
void Hanoi_4(int n, char a, char b, char c)//非递归算法4，根据满二叉树的规律输出
{
int i, level, k, s;
int m = 1<<n;
for (i=1; i<m; i++)
{
for (s=2,level=n; i%s==0; s=s<<1)//判断是第几层的结点
{
--level;
}
k = i / s; //是第leve层第k+1个结点
printf("%d: %d ", i, n+1-level);
if (level & 1)//奇数层
{
switch (k % 3)
{
case 0: printf("A -> C "); break;
case 1: printf("C -> B "); break;
case 2: printf("B -> A ");
}
}
else //偶数层
{
switch (k % 3)
{
case 0: printf("A -> B "); break;
case 1: printf("B -> C "); break;
case 2: printf("C -> A ");
}
}
}
}
算法3和4属于利用满二叉树特征而得出的方法，谈祥柏老师在《数学营养菜》中提到过一位美国学者发现的方法，只要轮流进行两步操作就可以了。
首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上。根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；若n为奇数，按顺时针方向依次摆放 A C B。
（1）按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。
（2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。
（3）反复进行（1）（2）操作，最后就能按规定完成汉诺塔的移动。
有了这个步骤说明，代码是很容易写出来的。代码如下：
void Hanoi_5(int n, char a, char b, char c)//非递归算法5
{
struct pillars {int S[MAX], top; char pos;} P[3]; //存储各个柱子上的盘子信息
int i, count, next, pre;
for (i=0; i<n; i++)
{
P[0].S[i] = n - i;
}
P[0].pos = a;
P[0].top = n - 2; //1号盘不入栈
P[1].top = P[2].top = -1;
if (n % 2 == 0)
{
P[1].pos = b;
P[2].pos = c;
}
else
{
P[1].pos = c;
P[2].pos = b;
}
n = pow(2, n) - 1;
count = i = 0;
while (count < n)
{
printf("%d: 1 %c -> %c ", ++count, P[i%3].pos, P[(i+1)%3].pos);//将1号盘从顺时针移动到下一个柱子
if (count == n)
break;
++i;
next = (i+ 1) % 3;
pre = (i - 1) % 3;
if (P[next].top < 0 || P[pre].top >= 0 && P[pre].S[P[pre].top] < P[next].S[P[next].top])
{
P[next].S[++P[next].top] = P[pre].S[P[pre].top--];//将前一根柱子上的盘子移动到下一根柱子上
printf("%d: %d %c -> %c ", ++count, P[next].S[P[next].top], P[pre].pos, P[next].pos);
}
else
{
P[pre].S[++P[pre].top] = P[next].S[P[next].top--];//将下一根柱子上的盘子移动到前一根柱子上
printf("%d: %d %c -> %c ", ++count, P[pre].S[P[pre].top], P[next].pos, P[pre].pos);
}
}
}
汉诺塔问题博大精深，我稍微搜集整理了一下，就得到如此多方法，还有好些方法一时不能理解，没有贴出来，请广大网友共同探讨，分享更多更好的方法。
