# The Fourth Dimension Space

## 数学建模之——商人过河问题 算法核心:搜索法

//本程序在商人数<=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[10000001];

struct node2
{

int data1;

int data2;

int prex1;

int prey1;

int prex2;

int prey2;
}
;

node2 a[NMAX][NMAX];

int main ()
{

int N=15;

while(N--)

{
system(
"cls");
cout
<<endl<<endl<<endl<<endl<<endl<<endl;
cout
<<"     ☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆"<<endl;
cout
<<"     ★                                                                  ★"<<endl;
cout
<<"     ☆                                                                  ☆"<<endl;
cout
<<"     ★                   欢迎来到商人过河模型演示程序                   ★"<<endl;
cout
<<"     ☆                                                                  ☆"<<endl;
cout
<<"     ★                       制    作：罗伟涛（abilitytao）             ★"<<endl;
cout
<<"     ☆                       指导老师：许春根（南京理工大学应用数学系） ☆"<<endl;
cout
<<"     ★                                                                  ★"<<endl;
cout
<<"     ☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆"<<endl;
Sleep(
100);
system(
"cls");
cout
<<endl<<endl<<endl<<endl<<endl<<endl;
cout
<<"     ★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★"<<endl;
cout
<<"     ☆                                                                  ☆"<<endl;
cout
<<"     ★                                                                  ★"<<endl;
cout
<<"     ☆                   欢迎来到商人过河模型演示程序                   ☆"<<endl;
cout
<<"     ★                                                                  ★"<<endl;
cout
<<"     ☆                       制    作：罗伟涛（abilitytao）             ☆"<<endl;
cout
<<"     ★                       指导老师：许春根（南京理工大学应用数学系） ★"<<endl;
cout
<<"     ☆                                                                  ☆"<<endl;
cout
<<"     ★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★"<<endl;
Sleep(
100);
}

cout
<<"\n\n\n\n                                                   请按任意键进入演示程序"<<endl;

char any;
getch();

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int n;

int m;

int i,j;

int flagnum1;

int flagnum2;

while(1)

{
printf(
"请输入商人数：");
scanf(
"%d",&n);
printf(
"请输入随从数：");
scanf(
"%d",&m);

if(n>1000)

{
printf(
"本程序仅在1000以内保证其正确性，请重新输入\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 tempx=0;

int tempy=0;

int markx=0;

int marky=0;
printf(
"初始状态下，河南岸有%d个商人，%d个随从\n",n,m);

//Sleep(5000);

int flagforreturn=1;

int step=1;

while(1)

{

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 choice;
printf(
"如果您要继续测试，请输入1，退出请输入2:");
scanf(
"%d",&choice);

if(choice==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 11:07 abilitytao 阅读(9065) 评论(15)  编辑 收藏 引用

### 评论

@陈梓瀚(vczh)

回复  更多评论

#### #re: 数学建模之——商人过河问题 算法核心:搜索法 2009-02-26 15:32 winsty

BFS就可以了  回复  更多评论

@winsty

回复  更多评论

#### #re: 数学建模之——商人过河问题 算法核心:搜索法 2009-05-04 22:25 abilitytao

@马文旭
VC6.0肯定能运行的  回复  更多评论

@爱你

#### #re: 数学建模之——商人过河问题 算法核心:搜索法 2009-05-22 16:41 shizhanwei

3以上怎么不行？  回复  更多评论

@shizhanwei

@hyzdou