数学建模：研究商人过河问题

数学建模实验一报告

实验题目：研究商人过河问题

一、实验目的：编写一个程序（可以是C,C++或Mathlab）实现商人安全过河

问题。

二、实验环境：Turbo c 2.0、Microsoft Visual C++ 6.0、Matlab 6.0以上 三、实验要求：要求该程序不仅能找出一组安全过河的可行方案，还可以得

到所有的安全过河可行方案。并且该程序具有一定的可扩展性，即不仅可以实现3个商人，3个随从的过河问题。还应能实现

n个商人，n个随从的过河问题以及n个不同对象且每个对象有m个元素问题(说明：对于3个商人，3个随从问题分别对应于n=2,m=3)的过河问题。从而给出课后习题5（n=4,m=1）的全部安全过河方案。

四、实验步骤：

第一步：问题分析。这是一个多步决策过程，涉及到每一次船上的人员以及

要考虑此岸和彼岸上剩余的商人数和随从数，在安全的条件下（两岸的随从数不比商人多），经有限步使全体人员过河。

第二步：分析模型的构成。记第k次渡河前此岸的商人数为xk，随从数为yk，

（xk,yk）（具有可扩展性），将定义为状态，状态集合k1,2，xk,yk1,2n，

（x,y）|x0,y0,1,2,3;x3,y0,1,2,3;xy1,2}成为允许状态集合（S）。S={

记第k次渡船的商人数为uk，随从数为vk，决策为(uk,vk)，安全渡河条件下，决策的集合为允许决策集合。允许决策集合记作D，所以

（u,v）|1uv2,u,v0,1,2|1.

.

岸驶向彼岸，k为偶数时船由彼岸驶向此岸，所以状态sk随决策dk变化的规律是

sk1sk(1)kdk，此式为状态转移律。制定安全渡河方案归结为如下的多步决

策模型：求决策dkD(k1,2n)，使状态skS按照转移律，由初始状态

s1(3,3)经有限n步到达sn1(0,0)

第三步：模型求解。

#include \"stdio.h\" #include \"string.h\" #include #include #include using namespace std; #include \"conio.h\"

FILE *fp;/*设立文件指针，以便将它用于其他函数中*/ struct a{ long m,s;

struct a *next;

};/*数组类型a：记录各种情况下船上的商人和仆人数，m：代表商人数 s：代表仆人数*/ struct a *jj,head;/*head为头指针的链表单元（船上的人数的各种情况的链表）*/ int n,total=0,js=0;/*total表示船上各种情况总数*/ struct aim {

long m1,s1,m2,s2; int n;

struct aim *back,*next;};/*用于建立双向的指针链表，记入符合的情况，m1，s1表示要过岸的商人数和仆人数；m2，s2表示过岸了的商人数和仆人数，n表示来回的次数*/ int k1,k2;

void freeit(struct aim *p){ struct aim *p1=p; p1=p->back; free(p); if(p1!=NULL) p1->next=NULL; return;

}/*释放该单元格，并将其上的单元格的next指针还原*/

int determ(struct aim *p) { struct aim *p1=p;

if(p->s1>k2)return -1;/*仆人数不能超过总仆人数*/ if(p->m1>k1)return -1;/*商人数不能超过总商人数*/

.

.

if(p->s2>k2)return -1;/*对岸，同上*/ if(p->m2>k1)return -1;/*对岸，同上*/ if(p->s1<0)return -1;/*仆人数不能为负*/ if(p->s2<0)return -1;/*商人数不能为负*/ if(p->m1<0)return -1;/*对岸，同上*/ if(p->m2<0)return -1;/*对岸，同上*/ if(p->m1!=0)

if(p->s1>p->m1)return -1; if(p->m2!=0)

if(p->s2>p->m2)return -1;/*两岸商人数均不能小于仆人数*/ while(p1!=NULL){ p1=p1->back; if(p1!=NULL)

if(p1->n%2==p->n%2) if(p1->s1==p->s1) if(p1->s2==p->s2) if(p1->m1==p->m1) if(p1->m2==p->m2)

return -1;}/*用于解决重复，算法思想：即将每次算出的链表单元与以前的相比较，若重复，则表示出现循环*/ if(p->s1==0&&p->m1==0) if(p->n%2==0)return 1;

else return -1;/*显然如果达到条件就说明ok了*/ return 0;}/*判断函数*/ int sign(int n){ if(n%2==0)return -1; return 1;}/*符号函数*/

void copyit(struct aim *p3,struct aim *p){ p3->s1=p->s1; p3->s2=p->s2; p3->m1=p->m1; p3->m2=p->m2; p3->n=p->n+1; p3->back=p; p3->next=NULL; p->next=p3;

}/*复制内容函数，将p中的内容写入p3所指向的链表单元中*/ void print(struct aim *p3){ struct aim *p=p3; js++;

while(p->back){p=p->back;} printf(\"\\n第%d种方法:\\n\fprintf(fp,\"\\n第%d种方法:\\n\

.

.

int count=0;

while(p){ printf(\"%ld,%ld::%ld,%ld\\fprintf(fp,\"%ld,%ld::%ld,%ld\\p=p->next; count++; }

cout<<\"一共有\"<void trans(struct aim *p){

struct aim *p3;/*p3为申请的结构体指针*/ struct a *fla; int i,j,f; fla=&head;

p3=(struct aim *)malloc(sizeof(struct aim)); f=sign(p->n);

for(i=0;inext; copyit(p3,p); p3->s1-=fla->m*f; p3->m1-=fla->s*f; p3->s2+=fla->m*f;

p3->m2+=fla->s*f;/*运算过程，即过河过程*/ j=determ(p3);/*判断，j记录判断结果*/ if(j==-1){

if(ifreeit(p3); break;}}

int count1=0;

if(j==1){if(ielse{print(p3); freeit(p3); break;}

//cout<if(j==0)trans(p3); }

return;

}/*转移函数，即将人转移过河*/

.

.

/*n=0*/

void main()

{ struct aim *p,*p1;int j,a,e,f;

struct a *flag;/*flag是用与记录头指针*/ FILE*fpt;

if((fpt=fopen(\"c:result.dat\printf(\"can't creat it\\n\"); exit(0);} fp=fpt;

system(\"cls\");

printf(\"问题描述：三个商人各带一个随从乘船过河，一只小船只能容纳X人，由他们自己划船。三个商人窃听到随从们密谋，在河的任意一岸上，只要随从的人数比上人多，就杀掉商人。但是如何乘船渡河的决策权在商人手里，商人们如何安排渡河计划确保自身安全？\\n\");

printf(\"\\n\");

p=(struct aim *)malloc(sizeof(struct aim)); p->back=NULL; p->next=NULL; p->s2=0; p->m2=0;

p->n=1;/*设立初始头指针*/

printf(\"please input the total of people on the board\\n\"); fprintf(fp,\"\\n请输入船上的人数\\n\"); scanf(\"%d\

fprintf(fp,\"\\n%d\\n\flag=&head;

for(e=0;e<=n;e++) for(f=0;f<=n;f++) if(e+f>0&&e+f<=n) { total++;

jj=(struct a*)malloc(sizeof(struct a)); jj->m=e; jj->s=f;

flag->next=jj; jj->next=NULL; flag=jj; }

/*********************************/

printf(\"please input the total of merchant and salvent as follow: mechant,salvent;\\n\");

fprintf(fp,\"\\nplease input the total of merchant and salvent as follow:

.

.

mechant,salvent;\\n\");

scanf(\"%ld,%ld\

fprintf(fp,\"\\n%ld,%ld\\n\/**********************************/ k1=p->m1; k2=p->s1; trans(p); fclose(fpt); getch(); }

第一步：三个商人，三个随从的模型求解答案为： 运行后的结果为： 第 1 种方案：(3,3) 到 (0,0)、(3,1) 到 (0,2)、(3,2) 到 (0,1)、(3,0) 到 (0,3)、(3,1) 到 (0,2)、(1,1) 到 (2,2)、(2,2) 到 (1,1)、(0,2) 到 (3,1)、(0,3) 到 (3,0)、(0,1) 到 (3,2)、(0,2) 到 (3,1)、(0,0) 到 (3,3) 第 2 种方案：(3,3) 到 (0,0)、(3,1) 到 (0,2)、(3,2) 到 (0,1)、(3,0) 到 (0,3)、(3,1) 到 (0,2)、(1,1) 到 (2,2)、(2,2) 到 (1,1)、(0,2) 到 (3,1)、(0,3) 到 (3,0)、(0,1) 到 (3,2)、(1,1) 到 (2,2)、(0,0) 到 (3,3) 第 3 种方案：(3,3) 到 (0,0)、(2,2) 到 (1,1)、(3,2) 到 (0,1)、(3,0) 到 (0,3)、(3,1) 到 (0,2)、(1,1) 到 (2,2)、(2,2) 到 (1,1)、(0,2) 到 (3,1)、(0,3) 到 (3,0)、(0,1) 到 (3,2)(、0,2) 到 (3,1)、(0,0) 到 (3,3) 第 4 种方案：(3,3) 到 (0,0)、(2,2) 到 (1,1)、(3,2) 到 (0,1)、(3,0) 到 (0,3)、(3,1) 到 (0,2)、(1,1) 到 (2,2)、(2,2) 到 (1,1)、(0,2) 到 (3,1)、(0,3) 到 (3,0)、(0,1) 到 (3,2)、(1,1) 到 (2,2)(0,0) 到 (3,3) 第二步：四个商人三个随从，其结果为： 第1种方法:

4,3::0,0 3,2::1,1 4,2::0,1 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,2 1,1::3,2 0,0::4,3 一共有12步完成 第2种方法:

4,3::0,0 3,2::1,1 4,2::0,1 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,2 2,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 一共有14步完成 第3种方法:

4,3::0,0 3,2::1,1 4,2::0,1 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,2 0,2::4,1 0,0::4,3 一共有12步完成 第4种方法:

4,3::0,0 3,2::1,1 4,2::0,1 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,2 1,1::3,2 0,0::4,3 一共有12步完成 第5种方法:

4,3::0,0 3,2::1,1 4,2::0,1 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,2

.

.

0,2::4,1 0,0::4,3 一共有12步完成 第6种方法:

4,3::0,0 3,2::1,1 4,2::0,1 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,3

1,1::3,2 0,1::4,2 0,2::4,1 0,0::4,3 一共有14步完成 第7种方法:

4,3::0,0 3,2::1,1 4,2::0,1 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 一共有12步完成 第8种方法:

4,3::0,0 3,2::1,1 4,2::0,1 4,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,2 1,1::3,2 0,0::4,3 第9种方法:

4,3::0,0 3,2::1,1 4,2::0,1 4,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,2 2,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 第10种方法:

4,3::0,0 3,2::1,1 4,2::0,1 4,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,2 0,2::4,1 0,0::4,3 第11种方法:

4,3::0,0 3,2::1,1 4,2::0,1 4,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,2 1,1::3,2 0,0::4,3 第12种方法:

4,3::0,0 3,2::1,1 4,2::0,1 4,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,2 0,2::4,1 0,0::4,3 第13种方法:

4,3::0,0 3,2::1,1 4,2::0,1 4,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,3 1,1::3,2 0,1::4,2 0,2::4,1 0,0::4,3 第14种方法:

4,3::0,0 3,2::1,1 4,2::0,1 4,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 第15种方法:

4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,2 1,1::3,2 0,0::4,3 第16种方法:

4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,2

.

一共有12步完成 一共有12步完成 一共有12步完成 一共有12步完成 一共有12步完成 一共有12步完成 14步完成 14步完成 一共有一共有.

2,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 一共有14步完成 第17种方法:

4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,2 0,2::4,1 0,0::4,3 一共有12步完成 第18种方法:

4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,2 1,1::3,2 0,0::4,3 一共有12步完成 第19种方法:

4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,2 0,2::4,1 0,0::4,3 第20种方法:

4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,3 1,1::3,2 0,1::4,2 0,2::4,1 0,0::4,3 第21种方法:

4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 第22种方法:

4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 4,2::0,1 4,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,2 1,1::3,2 0,0::4,3 第23种方法:

4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 4,2::0,1 4,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,2 2,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 第24种方法:

4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 4,2::0,1 4,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,2 0,2::4,1 0,0::4,3 第25种方法:

4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 4,2::0,1 4,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 1,1::3,2

2,1::2,2 0,1::4,2 1,1::3,2 0,0::4,3 第26种方法:

4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 4,2::0,1 4,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,2 0,2::4,1 0,0::4,3 第27种方法:

4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 4,2::0,1

.

一共有12步完成 一共有12步完成 一共有16步完成 一共有14步完成 一共有14步完成 一共有14步完成 一共有14步完成一共有14步完成 .

4,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,3 1,1::3,2 0,1::4,2 0,2::4,1 0,0::4,3 一共有16步完成 第28种方法:

4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 4,2::0,1 4,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 1,1::3,2

2,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 一共有14步完成 第29种方法:

4,3::0,0 4,1::0,2 4,2::0,1 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,2 1,1::3,2 0,0::4,3 第30种方法:

4,3::0,0 4,1::0,2 4,2::0,1 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,2 2,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 第31种方法:

4,3::0,0 4,1::0,2 4,2::0,1 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,2 0,2::4,1 0,0::4,3 第32种方法:

4,3::0,0 4,1::0,2 4,2::0,1 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 1,1::3,2

2,1::2,2 0,1::4,2 1,1::3,2 0,0::4,3 第33种方法:

4,3::0,0 4,1::0,2 4,2::0,1 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,2 0,2::4,1 0,0::4,3 第34种方法:

4,3::0,0 4,1::0,2 4,2::0,1 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,3 1,1::3,2 0,1::4,2 0,2::4,1 0,0::4,3 第35种方法:

4,3::0,0 4,1::0,2 4,2::0,1 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 第36种方法:

4,3::0,0 4,1::0,2 4,2::0,1 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,2 1,1::3,2 0,0::4,3 第37种方法:

4,3::0,0 4,1::0,2 4,2::0,1 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,2

.

一共有16步完成 一共有16步完成 一共有12步完成 一共有14步完成 一共有14步完成 一共有14步完成 一共有14步完成 14步完成 一共有.

2,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 一共有14步完成 第38种方法:

4,3::0,0 4,1::0,2 4,2::0,1 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,2 0,2::4,1 0,0::4,3 一共有12步完成 第39种方法:

4,3::0,0 4,1::0,2 4,2::0,1 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,2 1,1::3,2 0,0::4,3 一共有12步完成 第40种方法:

4,3::0,0 4,1::0,2 4,2::0,1 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,2 0,2::4,1 0,0::4,3 第41种方法:

4,3::0,0 4,1::0,2 4,2::0,1 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,3

1,1::3,2 0,1::4,2 0,2::4,1 0,0::4,3 第42种方法:

4,3::0,0 4,1::0,2 4,2::0,1 2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 第43种方法:

4,3::0,0 4,1::0,2 4,2::0,1 4,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,2 1,1::3,2 0,0::4,3 第44种方法:

4,3::0,0 4,1::0,2 4,2::0,1 4,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,2

2,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 第45种方法:

4,3::0,0 4,1::0,2 4,2::0,1 4,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,2 0,2::4,1 0,0::4,3 第46种方法:

4,3::0,0 4,1::0,2 4,2::0,1 4,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,2 1,1::3,2 0,0::4,3 第47种方法:

4,3::0,0 4,1::0,2 4,2::0,1 4,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,2 0,2::4,1 0,0::4,3 第48种方法:

4,3::0,0 4,1::0,2 4,2::0,1 4,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,3

.

一共有12步完成 一共有12步完成 一共有12步完成 一共有12步完成 一共有12步完成 一共有12步完成 一共有14步完成 一共有14步完成 .

1,1::3,2 0,1::4,2 0,2::4,1 0,0::4,3 一共有14步完成 第49种方法:

4,3::0,0 4,1::0,2 4,2::0,1 4,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 一共有12步完成

.