Hanoi问题

题目:

有三根杆子A,B,C。
A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:

每次只能移动一个圆盘;
大盘不能叠在小盘上面。

提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆,但都必须遵循上述两条规则。

问:如何移?最少要移动多少次?

我的理解:

当只有一个盘子时 直接A->C;

当两个盘子 A->B,A->C,B->C;

当三个以上盘子时,将部分看成整体,将有第二个盘子这种迭代。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <iostream>
using namespace std;

void hanoi(int n,char a,char b,char c){
if(n==0)
return ;
if (n==1)
{
cout << "move" << n << "form" << a << "to" << c <<endl;
}
else
{

hanoi(n-1,a,c,b);
cout << "move" << n << "form" << a << "to" << b <<endl;
hanoi(n-1,b,a,c);
}

}


int main(int argc, char const *argv[])
{
int n;
cin >> n;
hanoi(n,"A","B","C");


return 0;
}
script>