The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

数学建模——商人过河问题 Beta2.0

早知道要写这么长 就用类写了 呵呵

//copyright by abilitytao,Nanjing University of Science and Technology
//thanks to Mr Xu Chungen
//本程序在商人数<=1000,随从数<=1000时测试通过,其余数据不能保证其正确性.
#include<iostream>
#include <windows.h>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include<time.h>
#include<conio.h>
using namespace std;
#define NMAX 1001


struct node
{
 int x;
 int y;
}line[100000001];

struct node2
{
 int data1;
 int data2;
 int prex1;
 int prey1;
 int prex2;
 int prey2;
};

node2 a[NMAX][NMAX];
int showpath[NMAX][NMAX];

int main ()
{
  
  int N=30;
  while(N--)
  {
   system("cls");
   cout<<endl<<endl<<endl<<endl<<endl;
   cout<<"     ☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆"<<endl;
   cout<<"     ★                                                                  ★"<<endl;
   cout<<"     ☆                                                                  ☆"<<endl;
   cout<<"     ★                   欢迎来到商人过河模型演示程序                   ★"<<endl;
   cout<<"     ☆                                                                  ☆"<<endl; 
   cout<<"     ★                       制    作:罗伟涛(weitao)                 ★"<<endl;
   cout<<"     ☆                       指导老师:许春根(南京理工大学应用数学系) ☆"<<endl;
   cout<<"     ★                                                                  ★"<<endl;
   cout<<"     ☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆"<<endl<<endl<<endl;
   
   Sleep(150);
   system("cls");
   cout<<endl<<endl<<endl<<endl<<endl;
   cout<<"     ★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★"<<endl;
   cout<<"     ☆                                                                  ☆"<<endl;
   cout<<"     ★                                                                  ★"<<endl;
   cout<<"     ☆                   欢迎来到商人过河模型演示程序                   ☆"<<endl;
   cout<<"     ★                                                                  ★"<<endl;
   cout<<"     ☆                       制    作:罗伟涛(weitao)                 ☆"<<endl;
   cout<<"     ★                       指导老师:许春根(南京理工大学应用数学系) ★"<<endl;
   cout<<"     ☆                                                                  ☆"<<endl;
   cout<<"     ★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★"<<endl<<endl<<endl;
   
   Sleep(150);
  }
  cout<<"问题描述: 三个商人各带一个随从乘船过河,一只小船只能容纳2人,由他们自己划船。三个商人窃听到随从们密谋,在河的任意一岸上,只要随从的人数比商人多,就杀掉商人。但是如何乘船渡河的决策权在商人手中,商人们如何安排渡河计划确保自身安全?"<<endl;
  cout<<"\n\n\n\n                                                   请按任意键进入演示程序..."<<endl;
  char any;
  getch();

 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 int n;
 int m;
 int i,j;
 int flagnum1;
 int flagnum2;
 while(1)
 { 
  memset(showpath,0,sizeof(showpath));
  printf("请输入商人数:");
  scanf("%d",&n);
  printf("请输入随从数:");
  scanf("%d",&m);
  if(n>1000)
  {
   printf("本程序仅在1000以内保证其正确性,请重新输入\n");
   continue;
  }
  if(n<m)
  {
   printf("商人数显然不可能少于随从数,请重新输入\n");
   continue;
  }


 


  for(i=0;i<=n;i++)
  {
   for(j=0;j<=m;j++)
   {
    if(i==0||i==n)
    {
     a[i][j].data1=1;
     a[i][j].data2=1;
     continue;
    }
    if(i>=j&&n-i>=m-j)
    {
     a[i][j].data1=1;
     a[i][j].data2=1;
    }
     
   }
  }
  ////////////////////////////////////////////////////////////////////以上为初始化////////////////////////////////////////////////////////////////////////////////
  int flag;
  int front=1;
  int rear=1;
  line[rear].x=n;
  line[rear].y=m;
  flag=1;
  flagnum1=1;
  flagnum2=0;
  while(front<=rear)
  {
   if(line[front].x==0&&line[front].y==0)
    break;
   if(flag==1)
   {
    if(a[line[front].x][line[front].y].data1!=1)
    {
     flagnum1--;
     if(flagnum1==0)
      flag=2;
     front++;
     continue;
    }
    
    a[line[front].x][line[front].y].data1=0;
    flagnum1--;
    if(flagnum1==0)
     flag=2;
    if(line[front].x-1>=0&&a[line[front].x-1][line[front].y].data2==1)
    {
     rear++;
     line[rear].x=line[front].x-1;
     line[rear].y=line[front].y;
     a[line[rear].x][line[rear].y].prex2=line[front].x;
     a[line[rear].x][line[rear].y].prey2=line[front].y;
     flagnum2++;
    }
    if(line[front].y-1>=0&&a[line[front].x][line[front].y-1].data2==1)
    {
     rear++;
     line[rear].x=line[front].x;
     line[rear].y=line[front].y-1;
     a[line[rear].x][line[rear].y].prex2=line[front].x;
     a[line[rear].x][line[rear].y].prey2=line[front].y;
     flagnum2++;
    }
    if(line[front].x-1>=0&&line[front].y-1>=0&&a[line[front].x-1][line[front].y-1].data2==1)
    {
     rear++;
     line[rear].x=line[front].x-1;
     line[rear].y=line[front].y-1;
     a[line[rear].x][line[rear].y].prex2=line[front].x;
     a[line[rear].x][line[rear].y].prey2=line[front].y;
     flagnum2++;
    }
    if(line[front].x-2>=0&&a[line[front].x-2][line[front].y].data2==1)
    {
     rear++;
     line[rear].x=line[front].x-2;
     line[rear].y=line[front].y;
     a[line[rear].x][line[rear].y].prex2=line[front].x;
     a[line[rear].x][line[rear].y].prey2=line[front].y;
     flagnum2++;
    }
    if(line[front].y-2>=0&&a[line[front].x][line[front].y-2].data2==1)
    {
     rear++;
     line[rear].x=line[front].x;
     line[rear].y=line[front].y-2;
     a[line[rear].x][line[rear].y].prex2=line[front].x;
     a[line[rear].x][line[rear].y].prey2=line[front].y;
     flagnum2++;
    }
    front++;
    continue;
   }
   else if(flag==2)
   {
    if(a[line[front].x][line[front].y].data2!=1)
    {
     flagnum2--;
     if(flagnum2==0)
      flag=1;
     front++;
     continue;
     
    }
    if(line[front].x==0&&line[front].y==0)
     break;
    a[line[front].x][line[front].y].data2=0;
    flagnum2--;
    if(flagnum2==0)
     flag=1;
    if(line[front].x+1<=n&&a[line[front].x+1][line[front].y].data1==1)
    {

    
    rear++;
    line[rear].x=line[front].x+1;
    line[rear].y=line[front].y;
    a[line[rear].x][line[rear].y].prex1=line[front].x;
    a[line[rear].x][line[rear].y].prey1=line[front].y;
    flagnum1++;
    }
    if (line[front].y+1<=m&&a[line[front].x][line[front].y+1].data1==1)
    {
    
     rear++;
     line[rear].x=line[front].x;
     line[rear].y=line[front].y+1;
     a[line[rear].x][line[rear].y].prex1=line[front].x;
     a[line[rear].x][line[rear].y].prey1=line[front].y;
     flagnum1++;
    }
    if(line[front].x+1<=n&&line[front].y+1<=m&&a[line[front].x+1][line[front].y+1].data1==1)
    {
     rear++;
     line[rear].x=line[front].x+1;
     line[rear].y=line[front].y+1;
     a[line[rear].x][line[rear].y].prex1=line[front].x;
     a[line[rear].x][line[rear].y].prey1=line[front].y;
     flagnum1++;
    }
    if(line[front].x+2<=n&&a[line[front].x+2][line[front].y].data1==1)
    {
     rear++;
     line[rear].x=line[front].x+2;
     line[rear].y=line[front].y;
     a[line[rear].x][line[rear].y].prex1=line[front].x;
     a[line[rear].x][line[rear].y].prey1=line[front].y;
     flagnum1++;
    }
    if(line[front].y+2<=m&&a[line[front].x][line[front].y+2].data1==1)
    {

    
    rear++;
    line[rear].x=line[front].x;
    line[rear].y=line[front].y+2;
    a[line[rear].x][line[rear].y].prex1=line[front].x;
    a[line[rear].x][line[rear].y].prey1=line[front].y;
    flagnum1++;
    
    }
    front++;
    continue;
   }
   front++;
  }
  if(front>rear)
  {
   cout<<"没有可行的方案"<<endl;
   int choice;
   printf("如果您要继续测试,请输入1,退出请输入2:");
   scanf("%d",&choice);
   if(choice==1)
    continue;
   else
    break;
  }
  /////////////////////////////////////////////////////////////////以上为搜索过程/////////////////////////////////////////////////////////////////////
  int choiceforaction;
  int tempx=0;
  int tempy=0;
  int markx=0;
  int marky=0;
  int flagforreturn=1;
  int step=1;
  ////////////////////////////////////////////////////////以上是演示变量初始化//////////////////////////////////////////////////////////
  printf("请问您需要动态演示还是文字演示(1/0)?:");
  scanf("%d",&choiceforaction);
  if(choiceforaction==1)
  {
   if(n>37)
   {
    printf("商人数大于37时会造成显示错误,请用文字模式显示\n");
    continue;
   }
   printf("由于屏幕宽度的原因,商人数和随从数必须<=37,并且在观看过程中请保证屏幕最大化\n");
   system("pause");
   


   int i,j;
   system("cls");
   showpath[n][m]=1;
   for(i=m;i>=0;i--)
   {
    cout<<i<<' ';
    for(j=0;j<=n;j++)
    {

     if(showpath[j][i]==1)
      cout<<'*'<<' ';
     else
      cout<<"  ";
    }
    cout<<endl;
   }
   for(i=-1;i<=n;i++)
   {
    if(i==-1)
    {
     cout<<"* ";
     continue;
    }
    else
     cout<<i%10<<' ';
   }
   cout<<endl;
   cout<<"此时坐标为("<<n<<','<<m<<')'<<endl;
   Sleep(1000);
   
   
   
   
   
   while(1)
   {
    if (flagforreturn==1)
    {
     if(markx==n&&marky==m)
      break;
     flagforreturn=2;
     tempx=a[markx][marky].prex2;
     tempy=a[markx][marky].prey2;
     showpath[n-tempx][m-tempy]=1;
     system("cls");
     for(i=m;i>=0;i--)
     {
      cout<<i<<' ';
      for(j=0;j<=n;j++)
      {

       if(showpath[j][i]==1)
        cout<<'*'<<' ';
       else
        cout<<"  ";
      }
      cout<<endl;
     }
     for(i=-1;i<=n;i++)
     {
      if(i==-1)
      {
       cout<<"* ";
       continue;
      }
      else
       cout<<i%10<<' ';
     }
     cout<<endl;
     cout<<"此时坐标为("<<n-tempx<<','<<m-tempy<<')'<<endl;
     Sleep(1000);


     markx=tempx;
     marky=tempy;
     step++;
   
    }
    else if(flagforreturn==2)
    {
     if(markx==n&&marky==m)
      break;
     flagforreturn=1;
     tempx=a[markx][marky].prex1;
     tempy=a[markx][marky].prey1;
     showpath[n-tempx][m-tempy]=1;

     system("cls");
     for(i=m;i>=0;i--)
     {
      cout<<i<<' ';
      for(j=0;j<=n;j++)
      {

       if(showpath[j][i]==1)
        cout<<'*'<<' ';
       else
        cout<<"  ";
      }
      cout<<endl;
     }
     for(i=-1;i<=n;i++)
     {
      if(i==-1)
      {
       cout<<"* ";
       continue;
      }
      else
       cout<<i%10<<' ';
     }
     cout<<endl;
     cout<<"此时坐标为("<<n-tempx<<','<<m-tempy<<')'<<endl;
     Sleep(1000);
     markx=tempx;
     marky=tempy;
     step++;
     //Sleep(5000);
    }
   }
   int choiceforcontinue;
   printf("如果您要继续测试,请输入1,退出请输入2:");
   scanf("%d",&choiceforcontinue);
   if(choiceforcontinue==1)
    continue;
   else
    break;
  }

  //-----------------------------------------------------------------------------------------------------------------------//

  else
  {
   printf("初始状态下,河南岸有%d个商人,%d个随从\n",n,m);
   while(1)
   {
    
    //Sleep(5000);
    
    if (flagforreturn==1)
    {
     if(markx==n&&marky==m)
      break;
     flagforreturn=2;
     tempx=a[markx][marky].prex2;
     tempy=a[markx][marky].prey2;
     printf("第%d步:河南岸有%d个商人,%d个随从,此时,对岸有%d个商人,%d个随从(此时船在北岸)\n\n",step,n-tempx,m-tempy,tempx,tempy);
     ///////////////////////////////////////////////////////////////////////////////////正确性检测/////////////////////////////////////////////////////////////////////////////////////
    /* if(tempx==0||tempx==n||(tempx>=tempy&&n-tempx>=m-tempy)&&(n-markx+m-marky>n-tempx+m-tempy))
      cout<<"此步正确"<<endl;
     else
      cout<<"此步错误"<<endl;*///
     ////////////////////////////////////////////////////////////////////////////////////////正确性检测/////////////////////////////////////////////////////////////////////////////////////
     markx=tempx;
     marky=tempy;
     step++;
     //Sleep(5000);
    }
    else if(flagforreturn==2)
    {
     if(markx==n&&marky==m)
      break;
     flagforreturn=1;
     tempx=a[markx][marky].prex1;
     tempy=a[markx][marky].prey1;

     printf("第%d步:河南岸有%d个商人,%d个随从,此时,对岸有%d个商人,%d个随从(此时船在南岸)\n\n",step,n-tempx,m-tempy,tempx,tempy);

     ////////////////////////////////////////////////////////////////////////////////////////正确性检测/////////////////////////////////////////////////////////////////////////////////////
     /* if(tempx==0||tempx==n||(tempx>=tempy&&n-tempx>=m-tempy)&&(n-markx+m-marky<n-tempx+m-tempy))
      cout<<"此步正确"<<endl;
     else
      cout<<"此步错误"<<endl;*/
     ////////////////////////////////////////////////////////////////////////////////////////正确性检测/////////////////////////////////////////////////////////////////////////////////////
     markx=tempx;
     marky=tempy;
     step++;
     //Sleep(5000);
    }
   }
   int choiceforcontinue;
   printf("如果您要继续测试,请输入1,退出请输入2:");
   scanf("%d",&choiceforcontinue);
   if(choiceforcontinue==1)
    continue;
   else
    break;
  }
 }
 //////////////////////////////////////////////////以上为动画演示及文字演示部分////////////////////////////////////////////////////////
 

 

 


 ///////////////////////////////////////////////////////////////////以下是结束动画部分/////////////////////////////////////////////////////////////////////////////
  N=20;
 while(N--)
 {
  system("cls");
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                              谢谢您的使用!再见!                             "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                            ·                                                 "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                      ·                       "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  Sleep(10);
  system("cls");
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                              谢谢您的使用!再见!                             "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                            │                                                 "<<endl;
  cout<<"                         \    /                                              "<<endl;
  cout<<"                       ─        ─                   │                       "<<endl;
  cout<<"                         /    \                  \    /                    "<<endl;
  cout<<"                            │                   ─        ─                  "<<endl;
  cout<<"                                                   /    \                    "<<endl;
  cout<<"                                                      │                       "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  Sleep(10);
  system("cls");
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                              谢谢您的使用!再见!                             "<<endl;        
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                            │                                                 "<<endl;
  cout<<"                       \        /                                            "<<endl;
  cout<<"                                                      │                       "<<endl;
  cout<<"                     ─            ─            \        /                  "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                       /        \            ─            ─                "<<endl;
  cout<<"                            │                                                 "<<endl;
  cout<<"                                                 /        \                  "<<endl;
  cout<<"                                                      │                       "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  Sleep(10);
  system("cls");
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                              谢谢您的使用!再见!                             "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  cout<<"                                                                               "<<endl;
  Sleep(10);
 }

system("pause");
 return 0;
}


 

posted on 2009-02-26 20:06 abilitytao 阅读(3533) 评论(9)  编辑 收藏 引用

评论

# re: 数学建模——商人过河问题 Beta2.0 2009-02-27 08:30 临风

不错,N年前参加数学建模的时候还写过这样的程序~~  回复  更多评论   

# re: 数学建模——商人过河问题 Beta2.0 2009-02-27 17:12 匿名

cout<<" \ / "<<endl;
这个输出不是有问题?  回复  更多评论   

# re: 数学建模——商人过河问题 Beta2.0[未登录] 2009-02-27 20:52 abilitytao

@匿名
程序可以运行啊 应该没问题吧
  回复  更多评论   

# re: 数学建模——商人过河问题 Beta2.0 2009-03-02 10:00 匿名

@abilitytao
要想输出“\”,代码不是要cout<<" \\"<<endl; 的吗?  回复  更多评论   

# re: 数学建模——商人过河问题 Beta2.0[未登录] 2009-03-02 13:01 abilitytao

你编译看看就知道咯  回复  更多评论   

# re: 数学建模——商人过河问题 Beta2.0 2009-03-05 20:12 @匿名

你好,能不能把注释也写上呢?大部分都看不懂呀!我的QQ是515305325!  回复  更多评论   

# re: 数学建模——商人过河问题 Beta2.0 2009-03-05 20:19 匿名

写了注释可以给我的邮箱发一份吗?谢谢你了,我 才学C++,有很多都不懂,所以才要写注释的!我的邮箱是lgw1860@yahoo.cn 。  回复  更多评论   

# re: 数学建模——商人过河问题 Beta2.0 2009-03-07 23:05 匿名

太棒了,佩服!!!  回复  更多评论   

# re: 数学建模——商人过河问题 Beta2.0[未登录] 2009-03-09 22:36 abilitytao

如果有问题可以在qq上直接问我 这样更有针对性一点呵  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理