用c++移动盘子
桌子上有一叠盘子，桌子上只能同时放三叠盘子，小的盘子只能放在大的盘子上，为了不打碎盘子，一次只能移动一个，盘子从左边最快地移动到右边，请问在移动盘子时，某些情形是否可能出现？
n个盘子从左边最快移动到右边等价于
前n-1个盘子从左边最快移动到中间
第n个盘子从左边最快移动到右边
前n-1个盘子从中间最快移动到右边
n个盘子从左边最快移动到右边时，某些情形是否可能出现等价于
第n个盘子在左边时，前n-1个盘子从左边最快移动到中间时这些情形是否可能出现
第n个盘子在右边时，前n-1个盘子从中间最快移动到右边时这些情形是否可能出现先量化
13 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 <iostream>
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?"<<endl;
cin>>n;
for (int i=0; i<3; i++) {
//输入每个位置盘子数量
cout<<"How many dishes in the "<<(i==0?"left":(i==1?"middle":"right"))<<"?"<<endl;
cin>>m;
//输入盘子序列
cout<<"Whats the sequence of the dishes?"<<endl;
for (int j=0; j<m; j++) {
cin>>dish[i][j];
}
//指向最底端的盘子
bottom[i]=0;
}
cout<<"Wait a minute."<<endl;
//输出结果
cout<<(possible(n, 0, 2)?"Awesome!":"What a pity!")<<endl;
getchar();
getchar();
}
return 0;
}
补充：软件开发 , C++ ,
