C语言初学者的汉诺塔
引言 在印度，有这样一个古老的传说。在世界中心贝拿勒斯的圣庙里， 一块黄铜板上插着3根宝石针。印度教的主神梵天在创造世界的时候， 在其中一根针上从下到上地穿好了由大到小的64片金盘， 这就是所谓的汉诺塔(Tower of Hanoi)。 不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金盘到另一根针上： 一次只移动一片，而且小片必在大片上面。 当所有的金盘都从梵天穿好的那根针上移动到第三根针上时， 世界就将在一声霹雳中消灭，梵塔、庙宇和众生都将同归于尽…… 分析问题 什么是汉诺塔 总结如下： 有 A, B, C 三根柱子，A 柱上有 n(n > 1) 个金盘，金盘的尺寸由下到上依次变小。 每次只能移动一片金盘，且大金盘不能位于小金盘之上，使得所有金盘都移动到 C 柱。 问：如何移？最少要移动多少次？ 一个最简单的例子 当 n = 1 时，只需1步就能解决：A-->C ( A-->C 表示把 A 柱最上面的一个金盘移动到 C 柱，下同) 一个很简单的例子 当 n = 2 时，只需3步： A-->B A-->C B-->C 一个简单的例子 当 n = 3 时，用一张图来解决： 用语言表述如下： A-->C A-->B C-->B A-->C B-->A B-->C A-->C 共需7步 扩展到 n 当 n = 4, 5, 6 甚至 20 时，又该怎么办呢？ 这个问题看起来很复杂，其实是有规律可循的 根据数学方法计算得出，移动 n 层的汉诺塔所需次数为 $2^n - 1$ ...