汉诺塔问题非递归算法集锦

汉诺塔问题非递归算法集锦

巧若拙（欢迎转载，但请注明出处：http://blog.csdn.net/qiaoruozhuo）

汉诺塔问题介绍：

在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的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; 
		}
	}
}

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); 
		}
	}
}

汉诺塔问题博大精深，我稍微搜集整理了一下，就得到如此多方法，还有好些方法一时不能理解，没有贴出来，请广大网友共同探讨，分享更多更好的方法。