三人三鬼
时间： 1ms 内存：128M
描述：
目标是将东岸的3人3鬼通过一只小船转移到西岸，希望以尽可能少的摆渡次数。
船的容量有限，一次最多只能坐2人（或2鬼或1人1鬼）。
无论是在河的东岸还是在河的西岸，一旦鬼数多于人数，则人被鬼扔到河中。
怎样渡河的大权掌握在人的手中。
只求一种渡河方案。依次输出东岸的状态。
输入：
无输入
输出：
依次输出东岸的状态
示例输入：
NO示例输出：
x:(a,b)
....提示：
参考答案（内存最优[1264]）：
#include<iostream>
using namespace std;
//定义布尔变量，描述状态安全和重复
bool AQ,CHF;
void display(int k); //声明有输出渡河状态函数
//定义描述渡河状态东岸人数 与鬼数的结构变量
struct state
{
int r; //状态中的人数
int g; //状态中的鬼数
};
state s[15]; //结构数组记录渡河时的状态转移过程
state d[7]={{0,0},{0,-2},{-1,-1},
{- 2,0},{0,1},{1,1},{1,0}};
//渡河策略
int flag1=0; //东岸尚未达1人1鬼状态标志预置0
int flag2=0; //东岸尚未达2人2鬼状态标志预置0
int k=0; //状态号预置0
int main() // 主函数
{ //主函数开始
s[1].r=3; //初始状态东岸有3人
s[1].g=3; //初始状态东岸有3鬼
int u=3,v=3; //初始状态东岸有3人3鬼
int a,mu,mv; //中间变量
while(!(u==0 && v==0))
{
k++; // 状态号加1
if (k%2 == 0)
a=4; // k为偶数表示船东渡，策略号从4开始
else
a=1; // k为奇数表示船西渡，策略号从1开始
// 枚举各种渡河决策，看哪个安全
for (int i=a; i<=a+2; i++)
{
// 按第i号策略走1步东岸的人数
mu = u + d[i].r;
// 按第i号策略走1步东岸的鬼数
mv = v + d[i].g;
if ( mu>3 || mv>3 || mu<0 || mv<0 ||
(mu==3 && mv==3 ))
continue; // 取消越界和重复
AQ = ((mu==3) || (mu==0) ||
(mu==1 && mv==1) ||
(mu==2 && mv==2) ); // 状态是否安全
CHF = (flag1) && (flag2); // 状态是否重复
//如果3人已达西岸，或安全且不重复
if (mu==0 || AQ && (!CHF) )
{
u = mu; //存东岸人数
v = mv; //存东岸鬼数
s[k+1].r=u; //存东岸人数
s[k+1].g=v; //存东岸鬼数
if(u==1&&v==1) flag1++;
//已达到过“1人1鬼”状态
if(u==2&&v==2) flag2++;
//已达到过“2人2鬼”状态
break;
} //if
} //for结束
} //while循环体结束
display(k+1); //显示渡河过程
return 0;
} //主函数结束
void display(int p) //显示渡河过程子函数
{
for(int i=1;i<=p;i++) cout << i
<< ":(" << s[i].r << "," << s[i].g << ")"
<< endl;
}
参考答案（时间最优[0]）：
#include<iostream>
using namespace std;
//定义布尔变量，描述状态安全和重复
bool AQ,CHF;
void display(int k); //声明有输出渡河状态函数
//定义描述渡河状态东岸人数 与鬼数的结构变量
struct state
{
int r; //状态中的人数
int g; //状态中的鬼数
};
state s[15]; //结构数组记录渡河时的状态转移过程
state d[7]={{0,0},{0,-2},{-1,-1},
{- 2,0},{0,1},{1,1},{1,0}};
//渡河策略
int flag1=0; //东岸尚未达1人1鬼状态标志预置0
int flag2=0; //东岸尚未达2人2鬼状态标志预置0
int k=0; //状态号预置0
int main() // 主函数
{ //主函数开始
s[1].r=3; //初始状态东岸有3人
s[1].g=3; //初始状态东岸有3鬼
int u=3,v=3; //初始状态东岸有3人3鬼
int a,mu,mv; //中间变量
while(!(u==0 && v==0))
{
k++; // 状态号加1
if (k%2 == 0)
a=4; // k为偶数表示船东渡，策略号从4开始
else
a=1; // k为奇数表示船西渡，策略号从1开始
// 枚举各种渡河决策，看哪个安全
for (int i=a; i<=a+2; i++)
{
// 按第i号策略走1步东岸的人数
mu = u + d[i].r;
// 按第i号策略走1步东岸的鬼数
mv = v + d[i].g;
if ( mu>3 || mv>3 || mu<0 || mv<0 ||
(mu==3 && mv==3 ))
continue; // 取消越界和重复
AQ = ((mu==3) || (mu==0) ||
(mu==1 && mv==1) ||
(mu==2 && mv==2) ); // 状态是否安全
CHF = (flag1) && (flag2); // 状态是否重复
//如果3人已达西岸，或安全且不重复
if (mu==0 || AQ && (!CHF) )
{
u = mu; //存东岸人数
v = mv; //存东岸鬼数
s[k+1].r=u; //存东岸人数
s[k+1].g=v; //存东岸鬼数
if(u==1&&v==1) flag1++;
//已达到过“1人1鬼”状态
if(u==2&&v==2) flag2++;
//已达到过“2人2鬼”状态
break;
} //if
} //for结束
} //while循环体结束
display(k+1); //显示渡河过程
return 0;
} //主函数结束
void display(int p) //显示渡河过程子函数
{
for(int i=1;i<=p;i++) cout << i
<< ":(" << s[i].r << "," << s[i].g << ")"
<< endl;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。