202401-programming-assignments/【实践课外】11.函数2/6-5 汉诺塔.md

6-5 汉诺塔

汉诺（Hanoi）塔问题是一个经典的递归问题。

设有A、B、C三个塔座；开始时，在塔座A上有若干个圆盘，这些圆盘自下而上，由大到小地叠在一起。要求将塔座A上的圆盘移到塔座B上，并仍按同样顺序叠放。在移动过程中要求遵守如下规则：

• 每次只能移动一个圆盘；
• 任何时刻都不允许将较大的圆盘压在较小的圆盘之上；
• 在满足前两条规则的前提下，可将圆盘移至A、B、C中任何一塔座上。

例如，3个圆盘的初始状态如下：

则移动过程如下： A->B A->C B->C A->B C->A C->B A->B

要求实现一个递归函数，模拟输出$n(1<=n<=8)$个圆盘从塔座A借助塔座C移动到塔座B上的过程（用A->B表示将圆盘从A移到B，其他类似）。

函数接口定义：

void hanoi(int n, char from, char to, char by);

其中参数 n是圆盘数 、from是原来叠放圆盘的塔座 、to是最终叠放圆盘的塔座 、by是可借助的塔座。

裁判测试程序样例：

#include<iostream>
using namespace std;

//将n个圆盘借助by从from移到to
void hanoi(int n, char from, char to, char by);

//输入n，输出将原来在A上的n个圆盘借助C移动到B上的移动过程，控制到文件尾
int main() {
	int n, cnt=0;
	while(cin>>n) {
		cnt++;
		if (cnt>1) cout<<endl;
		hanoi(n, 'A', 'B', 'C');
	}
	return 0;
}

输入样例：

3
4

输出样例：

A->B
A->C
B->C
A->B
C->A
C->B
A->B

A->C
A->B
C->B
A->C
B->A
B->C
A->C
A->B
C->B
C->A
B->A
C->B
A->C
A->B
C->B