汉诺塔问题

问题

有三个塔a、b、c
a塔上有盘子若干，大小不等，小盘在上，大盘在下，每次只移动一个盘子，现需要将a塔上的全部盘子，移动到c塔上，且每次移动后各个塔上盘子都要保持下大上小的顺序。

分析

第一种情况，a塔上只有一个盘子：
直接将a塔上的盘子移动到c塔上。

第二种情况，a塔上有两个盘子：
1、将a塔上第一个盘子，移动到b塔上。
2、将a塔上第二个盘子，移动到c塔上。
3、将b塔上的第一个盘子，移动到c塔上。
这里，b塔作为中转塔。
同时还可推出，若塔上盘子大于1个，全部转移到另一个塔上且排列顺序不变，必要借助额外的中转塔。
事实上，这就是解决汉诺塔问题的最基础的模型，不信？我们看下一种情况！

第三种情况，a塔上有3个盘子：
将第一和第二个盘子看做一个整体，那么问题不就回到了第二种情况吗？
1、将a塔上头两个盘子，移动到b塔上。
2、将a塔上最后一个盘子，移动到c塔上。
3、将b塔上的两个盘子，移动到c塔上。

第四种情况，a塔上有三个盘子：
将第一和第二个盘子以及第三个盘子看做一个整体，解决办法同第二种情况。
1、将a塔上头三个盘子，移动到b塔上。（如何将三个盘子移动到b塔上，解决办法参考第三种情况）
2、将a塔上最后一个盘子，移动到c塔上。
3、将b塔上的三个盘子，移动到c塔上。（如何将三个盘子移动到c塔上，解决办法参考第三种情况）

第n中情况，a塔上有n个盘子：
将上面n-1个盘子看做一个整体，解决办法依然同第二种情况。
1、将a塔上n-1个盘子，移动到b塔上。（如何将n-1个盘子移动到b塔上，解决办法参考第n-1种情况）
2、将a塔上第n个盘子移动到c塔上。
3、将b塔上n-1个盘子，移动到c塔上。（如何将n-1个盘子移动到c塔上，解决办法参考第n-1种情况）

通过上面的分析，不难发现解决这一问题的方法是一个递归的过程，是将第二种情况不停重复执行的过程，而执行的终止条件就是第一种情况。

实现

c语言实现：

#include<stdio.h>
 
void move(int n,char a,char b,char c)
{
    if(n==1)
        printf("\t%c->%c\n",a,c);    //当n只有1个的时候直接从a移动到c
    else
    {
        move(n-1,a,c,b);            //第n-1个要从a通过c移动到b
        printf("\t%c->%c\n",a,c);
        move(n-1,b,a,c);            //n-1个移动过来之后b变开始盘，b通过a移动到c，这边很难理解
    }
}
 
main()
{
    int n;
    printf("请输入要移动的块数：");
    scanf("%d",&n);
    move(n,'a','b','c');
}