文件名称:汉诺塔问题的非递归算法
文件大小:41KB
文件格式:DOC
更新时间:2011-11-14 15:37:07
汉诺塔 河内塔 非递归算法
汉诺塔(河内塔)的经典非递归算法 开天辟地的神勃拉玛(和中国的盘古差不多的神吧)在一个庙里留下了三根金刚石的棒,第一根上面套着64个圆的金片,最大的一个在底下,其余一个比一个小,依次叠上去,庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上,规定可利用中间的一根棒作为帮助,但每次只能搬一个,而且大的不能放在小的上面。计算结果非常恐怖(移动圆片的次数)18446744073709551615,众僧们即便是耗尽毕生精力也不可能完成金片的移动了。 算法介绍: 其实算法非常简单,当盘子的个数为n时,移动的次数应等于2^n - 1(有兴趣的可以自己证明试试看)。 后来一位美国学者发现一种出人意料的简单方法,只要轮流进行两步操作就可以了。