Hanoi Tower

题目描述

在19世纪有一种hanoi游戏,游戏的装置是一块铜板,上面有三根金刚石的针,针上放着从小到达64个盘子。游戏的目标是从一根针上移到另一根针上,还有一个针作为中间过渡。游戏规定每次只能够动一个盘子,而且大盘子永远在小盘子下面。问题: 由于移动的次数太多,标志着世界末日的到来,所以计算机不要求你计算如此多的移动方式,只要你可以算出7以内即可,
输入n =3 输出:A->C A->B C->B A->C B->A B->C A->C

题解

我们考虑一般的情况:如果想将n个盘子从a移动到c,可以划分阶段,先将n-1个盘子从a通过c移动到b,然后将a中剩下的一个盘子移动到c,最后再将n-1个盘子从b通过a移动到c。这样本来是n个盘子的问题,变成了与n-1个盘子有关的问题。所以本题可以使用递归,重复这个过程,每次n减1,直到n=1时,直接移动盘子就可以了。

Hanoi Tower

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream> //这道题目很基础,只是大学学C语言,于是我就把它翻出来了。
using namespace std;

void move(int n,char a,char b,char c);

int main() {
int n;
cin>>n;
move(n,'A','B','C');
return 0;
}

void move(int n,char a,char b,char c) {
if (n==1) cout<<a<<"->"<<c<<endl;
else {
move(n-1,a,c,b);
cout<<a<<"->"<<c<<endl;
move(n-1,b,a,c);
}
}