引用
汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上安大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。
传说
在印度,有这么一个古老的传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。
不管这个传说的可信度有多大,如果考虑一下把64片金片,由一根针上移到另一根针上,并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n片,移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7,且f(k+1)=2*f(k)+1。此后不难证明f(n)=2^n-1。n=64时,
f(64)= 2^64-1=18446744073709551615
假如每秒钟一次,共需多长时间呢?一个平年365天有 31536000 秒,闰年366天有31622400秒,平均每年31556952秒,计算一下,
18446744073709551615/31556952=584554049253.855年
这表明移完这些金片需要5845亿年以上,而地球存在至今不过45亿年,太阳系的预期寿命据说也就是数百亿年。真的过了5845亿年,不说太阳系和银河系,至少地球上的一切生命,连同梵塔、庙宇等,都早已经灰飞烟灭。
public class Hanoi {/**
*
* @param n
* 盘子的数目
* @param origin
* 源座
* @param assist
* 辅助座
* @param destination
* 目的座
*/
public void hanoi(int n,char origin,char assist,char destination) {
if (n == 1) {
move(origin,destination);
} else {
hanoi(n - 1,origin,destination,assist);
move(origin,destination);
hanoi(n - 1,assist,origin,destination);
}
}
// Print the route of the movement
private void move(char origin,char destination) {
System.out.println("Direction:" + origin + "--->" + destination);
}
public static void main(String[] args) {
Hanoi hanoi = new Hanoi();
hanoi.hanoi(3,'A','B','C');
}
}
分享到:
相关推荐
用C++实现汉诺塔的递归算法,定义了类和方法。
用非递归算法,用栈解决问题,C#语言,来解决汉诺塔移动问题
用C语言实现汉诺塔的递归算法,另外还有用栈来实现的方式:http://download.csdn.net/detail/jason19905/6419427
汉诺塔非递归算法 用栈作为辅助存储结构 和数据结构中中序遍历二叉树的方法类似
汉诺塔问题的递归算法,附详细代码以及运行结果,有详细的算法描述。
C#汉诺塔(递归调用)
汉诺塔的非递归实现,c++实现的,很简单,只有50多行,从递归的汉诺塔改编而来,将原来递归时的参数状态保存在栈中,入栈代替递归,出栈代替递归返回。
用栈来实现汉诺塔,要明白递归就是栈的重要应用之一,递归是系统自动调用栈来处理。
适应于大学生学习算法
非递归汉诺塔算法,并带有一片武汉大学的算法描述。
汉诺塔的非递归实现,估计课后作业应该有的O(∩_∩)O~
本人原创,思路想法里面都有。是根绝一些规律写的非递归,不是用递归改的。
用于学习帮助,汉诺塔非递归演算程序代码 使用C语言编写的。供大家学习参考,希望能派上用场。
汉诺塔的非递归解法,十分神奇,值得借鉴! 汉诺塔的非递归解法,十分神奇,值得借鉴! 汉诺塔的非递归解法,十分神奇,值得借鉴! 汉诺塔的非递归解法,十分神奇,值得借鉴! 汉诺塔的非递归解法,十分神奇,值得...
C# 实现汉诺塔问题 递归+Recursion 本人收藏了3年的资源 现放出 都是总结了很多系统 软件项目实施过程中的经验的 慢慢积累的
汉诺塔-汉诺塔的非递归实现源码和原理讲解---从网上整理的
汉诺塔递归与非递归结果对比,结果是no differences,说明非递归算法没错。递归算法参考了csdn另一名博主的博客。
其中有汉诺塔非递归的源代码以及运行结果 强烈推荐
首先把三根柱子按顺序排... (3)反复进行(1)(2)操作,最后就能按规定完成汉诺塔的移动。 所以结果非常简单,就是按照移动规则向一个方向移动金片。 如3阶汉诺塔的移动: A→C,A→B,C→B,A→C,B→A,B→C,A→C
汉诺塔(非递归)数据结构实验