著名的汉诺塔问题:
有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆环,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至B杆:
1.每次只能移动一个圆盘;
2.大盘不能叠在小盘上面。
解决这类问题有以下方案:
现在假设我们要将 t 个盘子从柱子 x 放到柱子 y,则我们可以先想办法把上面的 t-1个盘子放到另一个柱子上,然后将最大的盘子放到y上,最后将那t-1个盘子放到第 y 个柱子上。那么移动 t-1 个盘子就变成了一个子问题。
给定 n ,求问:按照上述策略,依次输出进行了那些操作。
输入格式:
一个正整数 n
输出格式:
若干行,表示操作。
格式见样例。
样例输入1:
2
样例输出1:
A->C
A->B
C->B
#include<iostream>
using namespace std;
int n;
void move(char x,char y)
{
cout<<x<<"->"<<y<<endl;
}
void hanoi(int n,char A,char B,char C)
{
if(n==1)
move(A,C);
else
{
hanoi(n-1,A,C,B);
move(A,C);
hanoi(n-1,B,A,C);
}
}
int main()
{
cin>>n;
hanoi(n,'A','B','C');
return 0;
}
望帮忙改正