[C++知识库]设计递归函数模拟汉诺塔游戏

题目描述：

Description：

下面程序的功能是通过递归函数模拟汉诺塔游戏。请将程序补充完整。

#include<stdio.h>
void move(int,char,char,char);
int main()
{
? ? int n;
? ? scanf("%d",&n);
? ? printf("the step to moving %2d diskes:\n",n);
? ? move(n,'a','b','c');
? ? return 0;
}
//你提交的代码将放在这里

Input

盘子数n（正整数）。

Output

按照样例要求格式输出盘子移动过程。

Sample Input 1?

3

Sample Output 1

the step to moving  3 diskes:
a-->c
a-->b
c-->b
a-->c
b-->a
b-->c
a-->c

经典的递归，首先，我们要了解汉诺塔问题：

有a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n，现要求塔座a上的这一叠圆盘移到塔座c上，并仍按原来同样顺序叠置。在移动圆盘时应该遵守以下移动规则。
??规则(1)：每次只能移动1个圆盘；
??规则(2)：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；
??规则(3)：在满足移动规则(1)和(2)的前提下，可将圆盘移至a,b,c中任一塔座上。
??

分析：

那么，我们先来看看最基础的三个盘子：

起初，a柱上有从小到大编号为1，2，3的三个盘子，然后我们将1-->c,2-->b,1-->b,3-->c,1-->a,2-->c,1-->c,即可完成移动。

对于四个盘子，我们将前三个盘子看成一个整体，我们需要将这个整体移动到b,再把第四个盘子从a移动到c,最后将三个盘子组成的整体从b移动到c。需要注意的是，移动前三个盘子的方法与只有三个盘子时移动的方法是一样的。

那么，对于n个盘子，我们要把n-1个盘子构成的整体从a柱移动到b柱,再把n号盘从a柱移动到c柱，最后把把n-1个盘子从b移动到c。

我们现在回到这个题，题目要求输出移动的过程，我们只需要按照这三个步骤移动，写一个递归函数，注意递归停止条件为n==1即可。

代码如下：

#include<stdio.h>
void move(int,char,char,char);
int main()
{
    int n;
    scanf("%d",&n);
    printf("the step to moving %2d diskes:\n",n);
    move(n,'a','b','c');
    return 0;
}
void move(int n,char a,char b,char c)
{
	if(n==1) {printf("%c-->%c\n",a,c);return; }//当只有一个盘子时，直接从起始柱移到目标柱
	
	move(n-1,a,c,b);//第一步：将n-1个盘子由a移动到b,注意此时起始柱是a,中转柱是c,目标柱是b; 
	printf("%c-->%c\n",a,c); //第二步:将盘子从起始柱移到目标柱
	move(n-1,b,a,c); //第三步：将n-1个盘子由b移动到c,注意此时起始柱是b,中转柱是a,目标柱是c; 
}