2.再将 A 上的一个圆盘移到 C 上；

    3.最后将 B 上的 n-1(等于 1)个圆盘移到 C 上。

    如果 n=3，则：

    谭浩强      C 语言程序设计               2001 年 5 月 1 日

    A. 将 A 上的 n-1(等于 2，令其为 n`)个圆盘移到 B(借助于 C)，步骤如下：

    (1)将 A 上的 n`-1(等于 1)个圆盘移到 C 上。

    (2)将 A 上的一个圆盘移到 B。

    (3)将 C 上的 n`-1(等于 1)个圆盘移到 B。

    B. 将 A 上的一个圆盘移到 C。

    C. 将 B 上的 n-1(等于 2，令其为 n`)个圆盘移到 C(借助 A)，步骤如下：

    (1)将 B 上的 n`-1(等于 1)个圆盘移到 A。

    (2)将 B 上的一个盘子移到 C。

    (3)将 A 上的 n`-1(等于 1)个圆盘移到 C。

    到此，完成了三个圆盘的移动过程。

    从上面分析可以看出，当 n 大于等于 2 时，移动的过程可分解为三个步骤：

    第一步  把 A 上的 n-1 个圆盘移到 B 上；

    第二步  把 A 上的一个圆盘移到 C 上；

    第三步  把 B 上的 n-1 个圆盘移到 C 上；其中第一步和第三步是类同的。

    当 n=3 时，第一步和第三步又分解为类同的三步，即把 n`-1 个圆盘从一个针移到另一

    个针上，这里的 n`=n-1。 显然这是一个递归过程，据此算法可编程如下：

    move(int n,int x,int y,int z)

    {

    if(n==1)

    printf("%c-->%c\n",x,z);

    else

    {

    move(n-1,x,z,y);

    printf("%c-->%c\n",x,z);

    move(n-1,y,x,z);

    }

    }

    main()

    {

    int h;

    printf("\ninput number:\n");

    scanf("%d",&h);

    printf("the step to moving %2d diskes:\n",h);

    move(h,'a','b','c');

    }

    从程序中可以看出,move 函数是一个递归函数，它有四个形参 n,x,y,z。n 表示圆盘数，

    x,y,z 分别表示三根针。move 函数的功能是把 x 上的 n 个圆盘移动到 z 上。当 n==1 时，直

    接把 x 上的圆盘移至 z 上，输出 x→z。如 n!=1 则分为三步：递归调用 move 函数，把 n-1 个

    圆盘从 x 移到 y；输出 x→z；递归调用 move 函数，把 n-1 个圆盘从 y 移到 z。在递归调用过

    程中 n=n-1，故 n 的值逐次递减，最后 n=1 时，终止递归，逐层返回。当 n=4 时程序运行的

    结果为：

    input number:

    4

    the step