知识点回顾
原始状态下的汉诺塔如下：
Step1 X->Z：
Step2 X->Y：
Step3 Z->Y：
Step4 X->Z：
Step5 Y->X：
Step6 Y->Z：
Step7 X->Z：
对于上述游戏的玩法，可以简单分解为三个步骤：
1. 将前 63 个盘子从 X 移动到 Y上，确保大盘在小盘下。
2. 将最底下的第 64 个盘子从 X 移动到 Z 上。
3. 将 Y 上的 63 个盘子移动到 Z 上。
在游戏中，由于每次只能移动一个圆盘，所以在移动的过程中显然要借助另外一根针才可以实施。也就是说，步骤 1 将 1~63 个盘子移到 Y 上，需要借助 Z；步骤 3 将 Y 针上的 63 个盘子移到 Z 针上，需要借助 X。
所以我们把新的思路聚集为以下两个问题：
· 问题一：如何将 X 上的 63 个盘子借助 Z 移到 Y 上？
· 问题二：如何将 Y 上的 63 个盘子借助 X 移到 Z 上？
解决这两个问题的方法跟解决“如何将 X 上的 64 个盘子借助 Y 移动到 Z 上？”这个问题是一样的，都是可以拆解成 1、2、3 三个步骤来实现。
问题一（“如何将 X 上的 63 个盘子借助 Z 移到 Y 上？”）拆解为：
1. 将前 62 个盘子从 X 移动到Z上，确保大盘在小盘下。
2. 将最底下的第 63 个盘子移动到 Y 上。
3. 将 Z 上的 62 个盘子移动到 Y 上。
问题二（“如何将 Y 上的 63 个盘子借助 X 移到 Z 上？”）拆解为：
1. 将前 62 个盘子从 Y 移动到 X 上，确保大盘在小盘下。
2. 将最底下的第 63 个盘子移动到 Z 上。
3. 将 X 上的 62 个盘子移动到 Y 上。
没错，汉诺塔的拆解过程刚好满足递归算法的定义，因此，对于如此难题，使用递归来解决，问题就变得相当简单了！
#include <stdio.h>
void hanoi(int n, char x, char y, char z);
void hanoi(int n, char x, char y, char z)
{
if (n == 1)
{
printf("%c --> %c\n", x, z); // 剩下底部的那个圆盘
}
else
{
hanoi(n-1, x, z, y); // 将n-1个圆盘从x移动到y
printf("%c --> %c\n", x, z);
hanoi(n-1, y, x, z); // 将n-1个圆盘从y移动到z
}
}
int main(void)
{
int n;
printf("请输入汉诺塔的层数：");
scanf("%d", &n);
hanoi(n, 'X', 'Y', 'Z');
return 0;
}