汉诺塔问题的C语言实现（非常详细）

Hanoi（汉诺）塔是一个典型的只能用递归方法解决的问题。本文我们使用C语言递归函数来实现 Hanoi 塔指针的移动。

有 3 根针 A、B、C，如果 A 针上有 5 个盘子，盘子大小不等，大的在下，小的在上（如图所示）。要求把这 5 个盘子从 A 针移到 C 针，仍然按照大在下、小在上的原则摆放，在移动过程中可以借助 B 针，每次只允许移动一个盘子，且在移动过程中，在 3 根针上都保持大盘在下、小盘在上。要求编程序打印出移动的步骤。

C语言汉诺塔问题的代码如下所示：

#include<stdio.h>
void printdisk(char x,char y)       /*定义打印函数*/
{
   printf("%c----->%c\n",x,y);
}
void hanoi(int n,char a,char b,char c) /*定义递归函数hanoi()完成移动*/
{
   if(n==1)                   /*如果A针上的盘子数只剩下最后一个，移到C针上*/
      printdisk(a,c);
   else                        /*如果A针上的盘子数多于一个，执行以下语句*/
   {
      hanoi(n-1,a,c,b);          /*将A针上的n-1个盘子借助C针先移到B针上*/
      printdisk(a,c);                /*将A针上剩下的一个盘子移到C针上，即打印移动方式*/
      hanoi(n-1,b,a,c);          /*将n-1个盘从B针借助A针移到C针上*/
   }
}
int main()
{
   int n;
   printf("Input n:");
   scanf("%d",&n);               /*由键盘输入盘子数*/
   hanoi(n,'A','B','C');              /*调用hanoi()函数*/
}

运行结果：

Input n:4
A----->B
A----->C
B----->C
A----->B
C----->A
C----->B
A----->B
A----->C
B----->C
B----->A
C----->A
B----->C
A----->B
A----->C
B----->C

本例将 n 个盘子从 A 针移到C针可以分解为以下 3 个步骤。

• 将 A 针上 n-1 个盘子借助 C 针先移到 B 针上。
• 把 A 针上剩下的一个盘子移到 C 针上。
• 将 n-1 个盘子从 B 针借助 A 针移到 C 针上。

这 3 个步骤分成两类操作。

• 当n>1时，将n-1个盘子从一个针移到另一个针上，这是一个递归的过程。
• 将最后一个盘子从一个针上移到另一个针上。

本程序分别用两个函数实现上面的两类操作，用 hanoi() 函数实现 n>1 时的操作，用 printf() 函数实现 n=1 时将一个盘子从一个针上移到另一个针上。