移到C，见图5.5(h)。
到此，完成了三个圆盘的移动过程。
从上面分析可以看出，当n大于等于2时， 移动的过程可分解为
三个步骤：
第一步 把A上的n-1个圆盘移到B上；
第二步 把A上的一个圆盘移到C上；
第三步 把B上的n-1个圆盘移到C上；其中第一步和第三步是类同的。
当n=3时，第一步和第三步又分解为类同的三步，即把n`-1个圆盘从一个针移到另一个针上，这里的n`=n-1。 显然这是一个递归过
程，据此算法可编程(www.cppentry.com)如下：
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(int n,int x,int y,int z)
{
if(n==1)
printf("%-->%c\n",x,z);
else
{
move(n-1,x,z,y);
printf("%c-->%c\n",x,z);
move(n-1,y,x,z);
}
}
main()
{ ……
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 to moving 4 diskes:
a→b
a→c
b→c
a→b
c→a
c→b
a→b
a→c
|