引入
传说越南河内某间寺院有三根银棒
- 其中一根银棒上串 64 个金盘
- 金盘从上到下,由小至大。
- 一次只移动一片,不管在那根针上
- 但小片必须在大片上
- 从一根银棒按照同样的要求,全部移动到另外一根银棒上,任务完成
若传说属实,僧侣们需要 $2^{64}-1$步才能完成这个任务
若他们每秒可完成一个盘子的移动,就需要 5845 亿年才能完成。整个宇宙现在也不过 137 亿年。
汉诺塔玩具
在真实玩具中,一般 N=8;最少需移动 255 次。
如果 N=10,最少需移动 1023 次。
如果N=15,最少需移动32767次;
这就是说,如果一个人从 3 岁到 99 岁,每天移动一块圆盘,他最多仅能移动 15 块。
如果 N=20,最少需移动 1048575 次,即超过了一百万次。
如何用递归的算法求解汉诺塔呢?
这是一个经典的递归问题,我们可以这样考虑
- ABC 三根柱子,A 上面从小到大排列着64个圆盘
- 我们把 A 上的63个圆盘移动到 B 上面
- 然后把A 最大的64号圆盘移动到 C 上面
- 然后再把 B 上的63个盘子逆向的移动到C上面
算法
1 |
|
解题思路,其实就是每次递归按照我们的要求移动一个碟子,你可以这么想
tower(n-1,a,c,b);
,a 借助 c 移动到 bprintf("%c 移动到 %c\n",a,c);
,第 n 个盘子从 a 移动到 ctower(n-1,b,a,c);
,b 借助 a 移动到 c
尾巴
这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。