4147:汉诺塔问题(Hanoi)递归

题目

汉诺塔问题

有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆： 每次只能移动一个圆盘； 大盘不能叠在小盘上面。 提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。

输入
输入为一个整数后面跟三个单字符字符串。
整数为盘子的数目，后三个字符表示三个杆子的编号。

输出
输出每一步移动盘子的记录。一次移动一行。
每次移动的记录为例如3:a->b 的形式，即把编号为3的盘子从a杆移至b杆。
我们约定圆盘从小到大编号为1, 2, …n。即最上面那个最小的圆盘编号为1，最下面最大的圆盘编号为n。

样例输入
3 a b c
样例输出
1:a->c
2:a->b
1:c->b
3:a->c
1:b->a
2:b->c
1:a->c

思路

经典问题，递归解决。
最关键的是找到递归基，就是递归返回的条件。

对于移动n个盘子从a借助c移动到b，可以简单的理解为只需要三步

1. 将n-1个盘子移动从a移动到c（借助b)
2. 将第n个盘子移动直接从a移动到b
3. 将n-1个盘子从c移动到b（借助a）

只有第二步是可以直接完成的，其他都不能直接完成。显然对于$n\ge 2$,都是成立的。对于n=1时，直接移动就行。

#include <stdio.h>using namespace std;int N = 3;void moving(int n, char s,char aim){printf("%d:%c->%c\n",n,s,aim);
}
void han(int n,char s ,char aim ,char t){//printf("%d\n",n);if(n == 1){moving(n,s,aim); return ;}han(n-1,s,t,aim);moving(n,s,aim);han(n-1,t,aim,s);
}int main(){char n[4];scanf("%d %c %c %c",&N,&(n[0]),&(n[1]),&(n[2]));han(N,n[0],n[2],n[1]);
}