汉诺塔

题目

传说贝拿勒斯神庙里有三根钻石柱，串着 64 个纯金圆盘，从上到下越来越大。僧侣们要把整座塔从一根柱搬到另一根，规则只有两条：

1. 每次只能移动一个圆盘；
2. 任何时候，大盘都不能压在小盘上面。

传说当 64 个圆盘全部移完，世界就终结。那么，最少需要移动多少次？

答案与解析

设移 $n$ 个盘最少需要 $T_n$ 次。想清楚递归结构：

• 要移动最底下的第 $n$ 个大盘，必须先把上面 $n-1$ 个盘整体挪到中间柱当“跳板”，这需 $T_{n-1}$ 次；
• 然后把最大的盘挪到目标柱，1 次；
• 再把那 $n-1$ 个盘从中间柱挪到目标柱，又需 $T_{n-1}$ 次。

所以 $T_n = 2T_{n-1}+1$，且 $T_1=1$。解得：

$T_n = 2^n - 1$

对 64 个盘：

$T_{64} = 2^{64}-1 \approx 1.84\times 10^{19}\ \text{次}$

若每秒移一次、日夜不停，也要约 5845 亿年——远比宇宙年龄还长。世界大概很安全。

背后的数学

汉诺塔是递归思想最经典的训练题：把“移 n 个盘”的问题，归约成“移 n−1 个盘”的同一类子问题，直到最小的 1 个。

它直接对应递推关系与指数增长：$2^n-1$ 这条曲线说明，哪怕每次只多一个盘，难度也会翻倍。计算机科学里无数算法（如归并排序、快速排序）的“分而治之”套路，和汉诺塔的递归如出一辙。