首页 > 代码库 > 汉诺塔 Hanoi Tower
汉诺塔 Hanoi Tower
一个古老的印度传说:在世界的中心贝拿勒斯的圣庙里,一块黄铜板上插着三支宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上穿好了由大到小的64片金片,这就是所谓的汉诺塔(Hanoi Tower)。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。
僧侣们预言,当所有的金片从梵天穿好的金片上移到另一根针上时,世界末日就会来临,而梵塔、寺庙和众生也会随之灭亡......
故事不多说了,汉诺塔是递归思想的典型应用,上代码:
1 #include <stdio.h> 2 3 // 将n个金片,借助y,从x移动到z 4 void move(int n, char x, char y, char z) 5 { 6 if ( 1 == n) 7 printf("%c -> %c\n",x,z); 8 else 9 {10 move(n-1, x, z, y); //将 n-1 个金片从x,借助z,移动到y11 printf("%c -> %c\n",x,z); //将第 n 个金片从 x 移动到 z12 move(n-1, y, x, z); //将 n-1 个金片从y,借助x,移动到z13 }14 }15 16 int main()17 {18 int n;19 printf("请输入汉诺塔的层数:");20 scanf("%d",&n);21 move(n,‘X‘,‘Y‘,‘Z‘);22 23 return 0;24 }
最后,考虑金片移动的步数和金片数的关系:
每增加一个金片,它的移动的步数就等于原来步数的两倍加1。递推公式为:f(n+1) = 2*f(n) + 1,不难得到f(n) = 2^n - 1。
例如3个金片步数为7,那么4个金片步数为2*7+1=15步,5个金片步数为2*15+1=31步。
至此,可以推算金片数为64时,移动的步数为:18446744073709551615步。假设1秒钟移动一次,所需时间为:18446744073709551615秒,大约5845亿年,到时宇宙还在不在......
汉诺塔 Hanoi Tower
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。