一，问题描述：
法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。
不管这个传说的可信度有多大，如果考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n片，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7，且f(k+1)=2*f(k)+1。此后不难证明f(n)=2^n-1。n=64时，假如每秒钟一次，共需多长时间呢？一个平年365天有31536000 秒，闰年366天有31622400秒，平均每年31556952秒，计算一下：18446744073709551615秒。这表明移完这些金片需要5845.54亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845.54亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。
图1 模拟图
二，问题分析
1，分解问题
在这个问题中，我们发现由于每次只能移动一个圆盘，所以在移动的过程中显然要借助另外一根针才行。也就是说第1步将1到63个盘子借助Z移动到Y上，第3步将Y针上的63个盘子借助X移动到Z针上。那么我们把所有新的思路聚集为以下两个问题：
问题一：将X上的63个盘子借助Z移动到Y上；
问题二：将Y上的63个盘子借助X移动到Z上。
2，分解解答
问题一的圆盘移动步骤为：
（1）先将前62个盘子移动到Z上，确保大盘在在小盘下
（2）再将最底下的第63个盘子移动到Y上
（3）最后将Z上的62个盘子移动到Y上
问题二的圆盘移动步骤：
（1）先将前62个盘子移动到X上，确保大盘在小盘下
（2）再将最底下的63个盘子移动到Z上
（3）最后将X上的62个盘子移动到Y上。
三，代码分析
#include <stdio.h> void move(int n, char x, char y, char z) { if( 1 == n) { printf("%c-->%c\n", x,z); } else { move(n-1,x,z,y); //将n-1个盘子从x借助z移动到y上面 printf("%c-->%c\n",x,z); //将第n个盘子从x上移动到z上 move(n-1,y,x,z); //将n-1个盘子从u上借助x移动到z上 } } int main() { int n; printf("请输入汉诺塔的层数：\n"); scanf("%d",&n); printf("移动的步骤如下：\n"); move(n,'x','y','z'); return 0; }
在上面的代码中可以看到其中使用了递归的思想，不断地调用move函数则最终可以说实现移动的效果。当n=3时的结果为图2结果图所示，有移动的步骤。
