零、汉诺塔问题
在印度,有这么一个古老的传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。
问题描述:ABC三柱,把圆盘从下面开始按大小顺序从A重新摆放在另一根柱子C上,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。
一、递归算法
思想:每次将剩下的最大的圆盘的上面的n-1个盘子们 都 搬移到 非目标柱上(可以是A 或B 或C),然后将最大的圆盘n搬移到 目标柱上(最后都是C柱子,在过程中可以是A/B之一),最后将n-1个柱子们搬移到 C柱。 递归的临界条件是:当只剩下有一个圆盘1(最小的圆盘),直接将其搬到目标柱子上{Move(1,a,c);}。
Hannoi(int n,char a ,char b, char c)定义为将n号圆盘搬从a搬到c, 之所以需要b参数,是因为在递归时,需要将n-1号圆盘从a搬到b,然后移动n号圆盘从a到c,然后将n-1号圆盘从b移动到c(因此需要传递b这个中间柱子变量)。
二、非递归方法
思想:一位美国学者发现一种出人意料的简单方法,只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型,把所有的圆盘按从大到小的顺序放在柱子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)操作,最后就能按规定完成汉诺塔的移动。
所以结果非常简单,就是按照移动规则向一个方向移动金片:
如3阶汉诺塔的移动:A→C,A→B,C→B,A→C,B→A,B→C,A→C
分享到:
相关推荐
汉诺塔问题汉诺塔问题汉诺塔问题汉诺塔问题汉诺塔问题汉诺塔问题
任意输入N个盘,在三个柱子上实现汉诺塔问题的非递归求解,用栈进行
算法分析设计中三柱汉诺塔算法的拓展,四柱汉诺塔的设计算法代码
---汉诺塔源代码--- ---汉诺塔源代码--- ---汉诺塔源代码--- ---汉诺塔源代码--- ---汉诺塔源代码---
汉诺塔问题C/C++;解决汉诺塔问题的算法;递归
利用状态空间法对汉诺塔定义状态,用广度优先的方法解决汉诺塔问题,人工智能.(属于学校学习课程所做,非商业内容)
汉诺塔变形问题 .doc汉诺塔变形问题 .doc汉诺塔变形问题 .doc汉诺塔变形问题 .doc汉诺塔变形问题 .doc汉诺塔变形问题 .doc
C++语言递归算法求解原始汉诺塔问题,邻近移动汉诺塔问题,循环移动汉诺塔问题,奇偶汉诺塔问题
双色汉诺塔是由之前所介绍过的汉诺塔规则衍生而来。 盘子的颜色有两种
汉诺塔问题
汉诺塔问题 java解决方案汉诺塔问题 java解决方案汉诺塔问题 java解决方案
在印度,有这么一个古老的传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好...故汉诺塔问题又被称为“世界末日问题。”
网上看来的,比较详细。包含了递归以及不用递归的代码。 C和C++版的都有。
多柱汉诺塔问题研究 by 清华大学计算机科学与技术系 刘铎 戴一奇
汉诺塔问题,图文说明,代码说明,每步细节演示。
汉诺塔问题C语言实现
设A、B、C三个塔座,在A上叠加着从大到小的n个圆盘,要求把A上的圆盘移到C上,打印每一个圆盘移动轨迹: 每次只能移动一个圆盘; 任何时刻不允许将大圆盘放在小圆盘之上; 可借助辅助塔B
利用函数递归调用的方法,实现了汉诺塔问题
二、实验内容或题目 汉诺塔问题。程序结果:给出程序执行过程中栈的变化过程与圆盘的搬动状态。 三、实验步骤与源程序 源程序: / *编译环境Visual C++6.0 */ #include "stdafx.h" #include<stdio.h> #include...
汉诺塔JAVA汉诺塔的问题