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

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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了汉诺塔问题非递归算法集锦，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6479字，纯文字阅读大概需要10分钟。

内容图文

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

巧若拙（欢迎转载，但请注明出处： 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; 
		}
	}
}

非递归算法1是对递归算法的模拟过程，但由于其把当前操作分成两种类型，即直接移动和进一步分解，人为地增加了算法的复杂度。实际上，仔细分析二叉树的中序遍历非递归算法（详见拙作《史上最简明易懂非递归遍历二叉树算法》http://blog.csdn.net/qiaoruozhuo/article/details/40586443），我们可以发现，完全可以采用类似的方法把汉诺塔非递归算法转化为非递归算法，思维方式几乎一模一样。代码如下：

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

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

原文：http://blog.csdn.net/qiaoruozhuo/article/details/41623633

内容总结

以上是互联网集市为您收集整理的汉诺塔问题非递归算法集锦全部内容，希望文章能够帮你解决汉诺塔问题非递归算法集锦所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1300782.html

来源：【匿名】

【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【汉诺塔问题非递归算法集锦】教程文章相关的互联网学习教程文章

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

汉诺塔问题非递归算法集锦巧若拙（欢迎转载，但请注明出处：http://blog.csdn.net/qiaoruozhuo）汉诺塔问题介绍：在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片，一次只移动一片，不管在哪根针上，小...

python3实现二叉树的遍历与递归算法解析【代码】【图】

1、二叉树的三种遍历方式二叉树有三种遍历方式：先序遍历，中序遍历，后续遍历即：先中后指的是访问根节点的顺序 eg:先序根左右中序左根右后序左右根　　遍历总体思路：将树分成最小的子树，然后按照顺序输出　　1.1 先序遍历　　　　a 先访问根节点　　　　b 访问左节点　　　　c 访问右节点　　　　a（b ( d ( h ) )( e ( i ) )）( c ( f )( g )) -- abdheicfg 　　1.2 中序遍历　...

两道递归算法题【代码】

第一题: 给出{1, 2, 3,…, n}的入栈顺序, 输出所有可能的出栈顺序#include "stdafx.h" #include <stack> #include <queue> #include <iostream> #include <cstdio> #include <cstdlib> usingnamespace std; int n = 0; typedef stack<int> Stack; typedef queue<int> Queue;void dfs(int level,Stack s, Queue buf, constint LEVEL);/** 每一次递归都只有一个元素(level)入栈, 但是可能有0个元素出栈, 也可能有至少一个元素出栈* @...

给定程序中函数fun的功能是：用递归算法求形参a的平方根。求平方根的迭代公式如下：

X1=1/2(x0+a/x0)例如，a为2时，平方根值：1.414214 #include <stdio.h>#include <math.h>double fun(double a, dounle x0){ double x1, y; x1=(x0+ a/x0)/2.0;if( fabs(x1-x0)>=0.00001 ) y=fun(a,x1); else y=x1; return y;}main( ){ double x; printf("Enter x: "); scanf("%lf",&x); printf("The square root of %lf is %lf\n",x,fun(x,1.0));}原文：http://www.cnblogs.com/lozjl/p/7775045.html

oracle中 connect by prior 递归算法

Oracle中start with...connect by prior子句使用方法connect by 是结构化查询中用到的，其基本的语法是： select ... from tablename start with 条件1 connect by 条件2 where 条件3;例：select * from tablestart with org_id = ‘HBHqfWGWPy‘connect by prior org_id = parent_id; 简单说来是将一个树状结构存储在一张表里，比方一个表中存在两个字段: org_id,parent_id那么通过表示每一条记录的parent是谁，就能够形成一个树状...

递归算法--写实例----阶乘问题---整数划分问题【代码】

一个自己或间接调用自身的算法叫递归算法。 1、求阶乘n! 第一步：递推表达式 f(n) = {1,n*f(n-1)} 前者：当 n=0(递归终止条件) 后者：n>0 第二步：清楚返回值是什么调用f(0) 返回值为 1 调用f(1) 返回值为 1*f(0) 调用f(2) 返回值为 1*f(1) 调用f(3) 返回值为 1*f(2) 依次类推调用f(n) 返回值为 n*f(n-1) ...

２４点牌递归算法【代码】

# -*- coding: utf-8 -*- import sysclass My24(int):def __new__(cls, int_num, trace=‘‘, last_opt=‘‘):obj = int.__new__(cls, int_num)return objdef __init__(self, int_num=0, trace=‘‘, last_opt=‘‘):self.val = int_numself.trace = trace if trace else str(int_num)self.last_opt = last_optsuper(int, self).__init__(int_num)def __hash__(self):return hash(self.trace)def adjust_trace(self, opt):if opt i...

递归算法【图】

算法思路:递归算法,就是一种直接或者间接地调用自身的算法.递归算法的具体实现过程一般通过函数或者子过程来完成,在函数或子过程的内部,编写代码直接或者间接地调用自己,即可完成递归操作.这里列举出求阶乘和数制转换的递归操作实例.?实例1:求阶乘 public static int jiecheng(int i) {if(i!=1){return i*jiecheng(i-1);}return 1;} public static void main(String[] args) {System.out.println(jiecheng(8));}?运行结果??...

23 遍历二叉树的非递归算法【代码】【图】

例子：中序遍历非递归算法实现代码：//中序遍历的非递归算法int InOrderTraverse_No_DiGui(BiTree T){BiTree p; //顶底指向二叉树中节点的游标InitStack(S); //初始化栈p = T; //p指向所给的二叉树根节点while(p || !StackEmpty(S)){if(p){ //若当前节点非空Push(S, p); //将当前节点入栈p = p->lchild; //游标指向当前节点的左孩子}else{Pop(S, q); //出栈，将栈顶节点返回到一个二叉树节点...

一些常见的递归算法动态规划算法【代码】

最大值的递归算法对于一个数组有A[ 1...n ]算法调用的时候调用max(n)max（i） if i = 1return A[i] elseif A[i]>max(i-1) return A[i]elsereturn max(i-1)end if end if平均值的递归算法对于数组 a[ 1...n ]sum 初值为 0 index 初值则为1 调用该算法使用 Ave（a,sum,index）Ave(int a[],int sum,int index)if(index > n) 　　　　 return sum/(index-1)elsereturn Ave(a,sum+=a[index],index+1)汉诺塔的递归算法void move(int ...

Domino 使用递归算法获取视图值【代码】【图】

在关系数据库中，有两字段是父子关系。通过递归算法，输入一个父ID，能够获取全部相应的子ID。这种数据结构在组织架构中常常使用。显示一般使用树形结构。在Domino中相同能够处理这种情况，下面是个小demo，希望对大家有帮助。交流QQ 873968102 1)视图的数据结构（这数据结构使用在一些应用其中，这是前台UI xpages domino动态编辑树） 2)下面是使用LS的递归算法，通过输入一个父ID，把全部子ID带出来。通过 : 分隔，...

JAVA递归算法

1、什么是递归算法递归算法就是直接或间接调用自己的算法2、递归思想递归就是方法里调用自身在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口递归算法代码显得很简洁，但递归算法解题的运行效率较低。所以不提倡用递归设计程序。在递归调用的过程中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等，所以一般不提倡用递归算法设计程序。要点： ...

递归算法(转)

递归算法设计的基本思想是：对于一个复杂的问题，把原问题分解为若干个相对简单类同的子问题，继续下去直到子问题简单到能够直接求解，也就是说到了递推的出口，这样原问题就有递推得解。关键要抓住的是：（1）递归出口（2）地推逐步向出口逼近例子: example：求5的阶乘。。如下： Java代码 public class Test { static int multiply(int n){ if(n==1||n==0) return n; else...

Java简单递归算法(两种例子)【代码】

例子一: 程序结束口:表达式(n==-1)为true,代表n(100)被递减完了,已经不能被递减了, 如不是-1,则代表还有数值可以被递减,此题及计算结果为偶数总和,递减时应当判断当前n是否为偶数如果是偶数,则 sum(偶数总和) = n(当前数值)+ 调用此方法(n(当前数值)-1(每次递减1)) 如果不是偶数,则不需要添加到sum 里面,直接再次调用自己本身方法,n-1,进入下一轮/*** 计算1-100以内偶数的总和* n为要计算的数值(100)* sum为总和*/ public static...

递归算法实例【代码】【图】

在数学与计算机科学中，递归是指在函数的定义中使用函数自身的方法。　　递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。递归算法解决问题的特点：(1) 递归就是在过程或函数里调用自身。(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所...

递归算法 - 相关标签

递归算法

算法 - 最热教程

浅谈SQLServer查询优化器中的JOIN算法有没那种可逆算法是密文比明文短的呢？...javascript-类似Excel里面的NORMDIST函...C++中的分治算法及常见题目汇总压缩感知重构算法综述-学习笔记 c++中内置函数qsort（快速排序）和bsea...一、fpga图像处理算法整合基于遗传算法（deap）的非线性函数寻优...集成学习-Bagging集成学习算法随机森林...机器学习笔记（九）聚类算法及实践（K-...

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

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

内容导读

内容图文

内容总结

内容备注

内容手机端

【汉诺塔问题非递归算法集锦】教程文章相关的互联网学习教程文章

递归算法 - 相关标签

算法 - 最新教程

算法 - 最热教程