用c++移动盘子

桌子上有一叠盘子，桌子上只能同时放三叠盘子，小的盘子只能放在大的盘子上，为了不打碎盘子，一次只能移动一个，盘子从左边最快地移动到右边，请问在移动盘子时，某些情形是否可能出现？

n个盘子从左边最快移动到右边等价于
前n-1个盘子从左边最快移动到中间
第n个盘子从左边最快移动到右边
前n-1个盘子从中间最快移动到右边

n个盘子从左边最快移动到右边时，某些情形是否可能出现等价于
第n个盘子在左边时，前n-1个盘子从左边最快移动到中间时这些情形是否可能出现
第n个盘子在右边时，前n-1个盘子从中间最快移动到右边时这些情形是否可能出现

先量化



1

3 2

5 4

8 7 6


运行
How many dishes do you have
8
How many dishes in the left
4
Whats the sequence of the dishes
8 5 3 1
How many dishes in the middle
3
Whats the sequence of the dishes
7 4 2
How many dishes in the right
1
Whats the sequence of the dishes
6
Wait a minute.
What a pity!

//Copyright (c) LeafCore
#include
using namespace std;

//盘子数量
const int const_m=64;
//存放盘子次序
int dish[3][const_m];
//指向最底端的盘子
int bottom[3];

//n个盘子从from移动到to时情形是否可能出现
bool possible(int n, int from, int to)
{
//递归出口，只有一个盘子从from移动到to时情形是否可能出现
if (n==1) {
if (dish[from][bottom[from]]==1 || dish[to][bottom[to]]==1) {
return true;
} else {
return false;
}
}
//最大的盘子在左边
if (dish[from][bottom[from]]==n) {
//跳过最大的盘子
bottom[from]++;
//前n-1个盘子从from移动到from及to以外的另一个位置时情形是否可能出现
return possible(n-1, from, 3-from-to);
}
//最大的盘子在右边
if (dish[to][bottom[to]]==n) {
//跳过最大的盘子
bottom[to]++;
//前n-1个盘子从from及to以外的另一个位置移动到to时情形是否可能出现
return possible(n-1, 3-from-to, to);
}
return false;
}

int main()
{
int m, n;
while (true) {
//输入盘子数量
cout<<"How many dishes do you have "< cin>>n;
for (int i=0; i<3; i++) {
//输入每个位置盘子数量
cout<<"How many dishes in the "<<(i==0 "left":(i==1 "middle":"right"))<<" "< cin>>m;
//输入盘子序列
cout<<"Whats the sequence of the dishes "< for (int j=0; j cin>>dish[i][j];
}
//指向最底端的盘子
bottom[i]=0;
}
cout<<"Wait a minute."< //输出结果
cout<<(possible(n, 0, 2) "Awesome!":"What a pity!")< getchar();
getchar();
}
return 0;
}