汉诺威递归算法BY:Merlin
1 .递归算法是计算机科学中通过将问题反复分解为同类子问题来解决问题的方法。
2 .汉诺威递归算法大梵天创造世界时创造了三根钻石柱子。 一根柱子上从下到上按大小顺序堆叠着64张黄金圆盘。 梵天命令hxdhy将圆盘按照大小顺序重新排列在另一根柱子上。 在小圆盘上圆盘不能变大,三根柱子之间一次只能移动一个圆盘。 64根柱子移动结束的日子,就是世界毁灭的时候。 也就是说,如果用第二个柱子将第一个柱子的圆盘移动到第三个柱子上,一次一定只有一个圆盘,小的不能总是放在大柱子上。 移动64张金唱片需要多少次?
3 .算法流程目前将三个柱分别标记为a、b、c、n表示圆盘的个数。 最上面是1号盘,从小到大依次去n号盘。
1.k=1时,可以说a移动到了c
A----B
2 .在2.k=2的情况下,第一步只要把a的第一盘移动到b,然后把a的第二盘移动到c,然后把b移动到c即可
a---b a---c B--- c
3.k=3时,
1 .把a的第一盘移到c
2 .把a的2号盘移到b
3 .将c移至b
4 .将a移至c
5 .把b移至a
6 .将b移至c
7 .将a移至c
a---ca---BC---ba---c B----a B--- c B--- ca-- c
4 .当4.k=n时,上面的n-1个盘子可以看作一个整体,第一步把上面的n-1个盘子通过c依次移动到b,第二步再把第n个盘子从a移动到c,再把n-1个盘子通过a移动到c
4.python码展示defHanoi(n,a,b,c ) : # )是由n个盘子从a经过b到cifn0:Hanoi(n-1,a,c,b )打印)从%s到%s
5 .当汉诺威递归算法的数学表示K=1时,sum=1
当K=2时,sum=3
如果K=3,则sum=7
水平。
水平。
水平。
当K=n时,sum=2^n - 1
因此,在盘子数为64情况下,sum=18、446、744、073、709、551、615
假设hxdhy每秒搬运一个盘子,共计需要5800亿年。 因此,预测hxdhy搬运完所有盘子的时候就是地球毁灭的时候。