三人三鬼

三人三鬼

时间: 1ms        内存:128M

描述:

*目标是将东岸的33鬼通过一只小船转移到西岸,希望以尽可能少的摆渡次数。

*船的容量有限,一次最多只能坐2人(或2鬼或11鬼)。

*无论是在河的东岸还是在河的西岸,一旦鬼数多于人数,则人被鬼扔到河中。

*怎样渡河的大权掌握在人的手中。

*只求一种渡河方案。依次输出东岸的状态。

输入:

无输入

输出:

依次输出东岸的状态

示例输入:

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;
  }

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注