下图是一个5阶的汉诺塔：

目标是要把所有的盘子从最左边（柱子A）移动到最右边（柱子C），条件是

1）每次只能移动一个盘子；

2）小盘子只能放在大盘子之上；

首先考虑最简单的情况：只有1个盘子，那么只要A—>C就可以了，一步就ok。

这就是递归问题的基准条件，可用C语言描述如下：

void hanoi(int n, char A, char B, char C)

{

if (n==1)

printf("将编号为1的盘子从%c移到%c\n",A,C);

else

{

……

}

}

如果有两个盘子，那么移动顺序如下：先把最上面的盘子（1号盘）移动到B，然后2号盘移动到C，然后1号盘从B移动到C，总共需要3步。

如果是n个盘子呢？

可以用倒推法来考虑这个问题：无论怎么移动，最底下的那个最大号盘子（n号盘）一定是A—>C的，在这之前，我们一定要把所有的上面的小盘子（n-1个盘子）都移动到B上，否则n号盘是无法从A移动到C的。然后，一旦最大号的n号盘从A—>C，我们剩下的工作就是把所有的n-1个盘子从B移动到C。

所以虽然有n个盘子，但是思考的时候，只要把n个盘子看做2个部分就行：n号盘，以及n号盘之上的所有n-1个盘子。移动的时候的原则就如下表示：

第一阶段：（n-1）：A—>B（把所有的n-1个盘子从A移动到B上）

// 1 将A上编号为1到n-1的圆盘移到B，C作辅助塔

printf("hanoi(%d,%c,%c,%c)\n",n-1,A,C,B);

hanoi(n-1,A,C,B);

第二阶段：n： A—>C（把最底下的n号盘从A移动到C上）

// 2 将A上编号为n的圆盘移到C

printf("将编号为%d的盘子从%c移到%c\n",n,A,C);

第三阶段：（n-1：）B—>C（把n-1个盘子从B移动到C上）

// 3 将B上编号为1到n-1的圆盘移到C，B作辅助塔

printf("hanoi(%d,%c,%c,%c)\n",n-1,B,A,C);

hanoi(n-1,B,A,C);

所上面的代码合并到一起就行了：

void hanoi(int n, char A, char B, char C)

{

if (n==1)

printf("将编号为1的盘子从%c移到%c\n",A,C);

else

{

// 1 将A上编号为1到n-1的圆盘移到B，C作辅助塔

printf("hanoi(%d,%c,%c,%c)\n",n-1,A,C,B);

hanoi(n-1,A,C,B);

// 2 将A上编号为n的圆盘移到C

printf("将编号为%d的盘子从%c移到%c\n",n,A,C);

// 3 将B上编号为1到n-1的圆盘移到C，B作辅助塔

printf("hanoi(%d,%c,%c,%c)\n",n-1,B,A,C);

hanoi(n-1,B,A,C); //

}

}

我们来看看如何执行第三阶段，现在的状况是n号盘已经在C上面了，（n-1）个盘子都在B上，为了达成所有盘子都移动到C上的目标，我们要做的就是把B上的最底下的盘子——也就是（n-1）号盘也移到C上。那么（n-1）号盘上面的总共（n-2）个盘子怎么办呢？那当然只有往A上挪咯。

现在（n-2）个盘子都在A上，咋办呢？当然是跟上面步骤一样，第（n-2）号盘子放到C上去，剩下的所有（n-3）个盘子挪到B上。

同样的方法对待n-3、n-4......直到最后只剩下1号盘子。然后把刚才的方法逆序做一遍，就成功啦。

这里有个数学方法，叫递归，也就是我们对待n个盘子、n-1个盘子、n-2个盘子....的方法都是一样：都是把除了最底下以外的盘子移到别的柱子上去，然后把最底下的盘子移到C上。这个不停重复的过程，就是递归。

完整的C程序写法：

运行结果：

你如果掌握了第一个（最小的）盘子的移动规模，这个游戏你玩起来就会得心应手。

当n是奇数时，第一个盘子只能在柱子ACBACB……间循环移动；

当n是偶数时，第一个盘子只能在柱子ABCABC……间循环移动；

可以去以下小游戏站点试试：

附代码：

#include <stdio.h>

#include <stdlib.h>

void hanoi(int n, char A, char B, char C)

{

if (n==1)

printf("将编号为1的盘子从%c移到%c\n",A,C);

else

{

// 1 将A上编号为1到n-1的圆盘移到B，C作辅助塔

printf("hanoi(%d,%c,%c,%c)\n",n-1,A,C,B);

hanoi(n-1,A,C,B);

// 2 将A上编号为n的圆盘移到C

printf("将编号为%d的盘子从%c移到%c\n",n,A,C);

// 3 将B上编号为1到n-1的圆盘移到C，B作辅助塔

printf("hanoi(%d,%c,%c,%c)\n",n-1,B,A,C);

hanoi(n-1,B,A,C); //

}

}

int main()

{

int n;

printf("请输入盘子数量n: ");

scanf("%d",&n);

hanoi(n,'A','B','C');

system("pause");

return 0;

}

－End－