C语言递归实现汉诺塔

汉诺塔

汉诺塔问题是指：一块板上有三根针 A、B、C。A 针上套有 64 个大小不等的圆盘，按照大的在下、小的在上的顺序排列，要把这 64 个圆盘从 A 针移动到 C 针上，每次只能移动一个圆盘，移动过程可以借助 B 针。但在任何时候，任何针上的圆盘都必须保持大盘在下，小盘在上。从键盘输入需移动的圆盘个数，给出移动的过程。

思路：

1. n==1时，只移动一个圆盘时，直接将圆盘从 A 针移动到 C 针
2. n>1时，
   把 (n-1) 个圆盘从 A 针移动到 B 针（借助 C 针）；
   A 针上的最后一个圆盘移动到 C 针；
   B 针上的 (n-1) 个圆盘移动到 C 针（借助 A 针）。
   每做一遍，移动的圆盘少一个，逐次递减，最后当 n 为 1 时，完成整个移动过程

算法实现

long count=0;
void han(int n,char a,char b,char c)
{
    if(n==1)  //n==1，直接将圆盘从A针移动到C针，作为递归结束条件
    {
        count++;
        printf("%d,%c->%c\n",count,a,c);
    }
    else
    {
     han(n-1,a,c,b);
     ++count;
     printf("%d,%c->%c\n",count,a,c);
     han(n-1,b,a,c);
    }
}
int main()
{


    int n;
    scanf("%d",&n);
    han(n,'A','B','C');
    return 0;

}

实例

当有3个盘子时