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

数学建模实验一陈说之吉白夕凡创作
实验题目：研究商人过河问题
一、实验目的：编写一个法式（可以是C,C++或Mathlab ）实现商人平安过河问题.
二、实验环境：Turbo c 2.0、、Matlab 6.0以上
三、实验要求：要求该法式不单能找出一组平安过河的可行方案, 还可以获得所有的平安过河可行方案.而且该法式具有一定的可扩展性, 即不单可以实现3个商人, 3个随从的过河问题.还应能实现
n 个商人, n 个随从的过河问题以及n 个分歧对象且每个对象有m 个元素问题(说明：对3个商人, 3个随从问题分别对应于n=2,m=3)的过河问题.从而给出课后习题5（n=4,m=1）的全部平安过河方案.
四、实验步伐：
第一步：问题分析.这是一个多步决策过程, 涉及到每一次船上的人员以及要考虑彼岸和彼岸上剩余的商人数和随从数, 在平安的条件下（两岸的随从数不比商人多）, 经有限步使全体人员过河. 第二步：分析模型的构成.记第k 次渡河前彼岸的商人数为k x , 随从数为k y , 2,1=k , n y x k k 2,1,=, （具有可扩展性）, 将）（k k y x ,界说为状态, 状态集合成为允许状态集合
（S ）.S={
2,1;3,2,1,0,3;3,2,1,0,0|,======y x y x y x y x ）（}记第k 次渡船
的商人数为k u , 随从数为k v , 决策为),(k k v u , 平安渡河条件下, 决策的集合为允许决策集合.允许决策集合记作D, 所以D={2,1,0,,21|,=<+<v u v u v u ）（|1<u+v<2,u,v=0,1,2},因为k 为奇数时船从彼岸驶向彼岸, k 为偶数时船由彼岸驶向彼岸, 所以状态k s 随决策k d 变动的规律是k k k k d s s )1(1-+=-, 此式为状态转移律.制定
平安渡河方案归结为如下的多步决策模型：求决策)2,1(n k D d k =∈, 使状态S s k ∈依照转移律, 由初始状态)3,3(1=s 经有限n 步达到)0,0(1=+n s
第三步：模型求解.
#include "stdio.h"
#include "string.h"
#include <memory>
#include <stdlib.h>
#include <iostream>
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",js);
fprintf(fp,"\n第%d种方法:\n",js);
int count=0;
while(p){ printf("%ld,%ld::%ld,%ld\t",p->m1,p->s1,p->m2,p->s2);
fprintf(fp,"%ld,%ld::%ld,%ld\t",p->m1,p->s1,p->m2,p->s2); p=p->next;
count++;
}
cout<<"一共有"<<count<<"步完成"<<endl;
}/*打印函数, 将p3所指的内容打印出来*/
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;i<total;i++){
fla=fla->next;
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(i<total-1){continue;}
else{
freeit(p3);
break;}}
int count1=0;
if(j==1){if(i<total-1){print(p3); count1++;
continue;}
else{print(p3);
freeit(p3);
break;}
//cout<<cout1<<endl;
printf("%d",count1);
printf("\n");
}
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","w+"))==0){
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",&n);
fprintf(fp,"\n%d\n",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",&p->m1,&p->s1);
fprintf(fp,"\n%ld,%ld\n",p->m1,p->s1);
/**********************************/
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 一共有12步完成
第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
一共有14步完成
第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 一共有12步完成
第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步完成
第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 一共有12步完成
第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步完成
第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 一共有12步完成
第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 一共有12步完成
第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
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 一共有12步完成
第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
一共有14步完成
第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 一共有12步完成
第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
一共有14步完成
第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 一共有16步完成
第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
一共有14步完成
第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 一共有14步完成
第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
一共有14步完成
第27种方法:
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
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
一共有14步完成
第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,3::4,0 0,1::4,2 2,1::2,2 1,0::3,3 1,1::3,2
0,0::4,3 一共有16步完成
第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
一共有14步完成
第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 一共有14步完成
第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
2,1::2,2 0,1::4,2 0,2::4,1 0,0::4,3
一共有14步完成
第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 一共有16步完成
第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
一共有14步完成
第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
1,1::3,2 0,0::4,3 一共有12步完成
第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
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 一共有12步完成
第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 一共有14步完成
第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 一共有12步完成
第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 一共有12步完成
第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 一共有14步完成
第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 一共有12步完成
第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 一共有12步完成
第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 一共有12步完成
第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
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步完成。