一个自带传说的谜题
汉诺塔由法国数学家爱德华·卢卡斯于1883年提出,据说当时还附带了一个传说:僧侣们不断移动64个金圆盘,预言称一旦他们完成,世界就会终结。以64个圆盘计算,最少步数超过1800亿亿步,如果每秒移动一步,大约需要5850亿年才能完成——这恰好生动地说明了指数增长的惊人威力。
为什么这个递归策略总是有效
这个递归解法之所以有效,是因为谜题的规则其实根本不关心一小叠圆盘究竟是"怎样"被放到某根柱子上的,只关心它是否处于合法的递减顺序中。这意味着任何能够正确移动n-1个圆盘的方法,都可以原封不动地当作解决n个圆盘问题的一个基础模块来重复使用。这正是同一个简单的三步套路能够适用于任意数量圆盘的原因。
常见问题
为什么2的n次方减1是"最少"步数,而不只是一个大概的估计?
可以证明,要移动最下面(最大)的那个圆盘,必须先把它上面的n-1个圆盘全部挪到另一根柱子上;而移动完最大圆盘之后,这n-1个圆盘又必须再次被移动到它上面。也就是说,n个圆盘所需的步数,总是恰好等于n-1个圆盘所需步数的两倍再加一步,按这个规律展开计算,结果正好是2的n次方减1。
起始柱和目标柱的选择会影响所需的步数吗?
不会。最少步数只取决于圆盘的数量,与从哪根柱子开始、以哪根柱子为目标无关——无论选择哪两根柱子,公式"2的n次方减1"都始终成立。