mirror of
https://github.com/renbaoshuo/202401-programming-assignments.git
synced 2024-11-27 08:26:20 +00:00
86 lines
1.6 KiB
Markdown
86 lines
1.6 KiB
Markdown
# 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，其他类似）。
|
||
|
||
### 函数接口定义：
|
||
```c++
|
||
void hanoi(int n, char from, char to, char by);
|
||
```
|
||
其中参数 `n`是圆盘数 、`from`是原来叠放圆盘的塔座 、`to`是最终叠放圆盘的塔座 、`by`是可借助的塔座。
|
||
|
||
### 裁判测试程序样例：
|
||
```c++
|
||
#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;
|
||
}
|
||
```
|
||
### 输入样例：
|
||
|
||
```in
|
||
3
|
||
4
|
||
```
|
||
|
||
### 输出样例：
|
||
|
||
```out
|
||
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
|
||
```
|
||
|
||
|