数学建模：研究商人过河问题
-
数学建模实验一报告
实验题目：
研究商人过河问题
一、实验目的：
编写一个程序（可以是
C,C
++
或
Mathlab
）实现商人安全
过河
问题。
二、实验环境：
Turbo c
2.0
、
Microsoft Visual C++
6.0
、
Matlab
6.0
以上
三、实验要求：
要求该程序不仅能找出一组安全过河的可行方案，还可以得
到所有的安全过河可行方案。
并且该程序具有一定的可扩展性，
即不仅可以实现
3
个商人，
3
个随从的过河问题。还应能实现
n
个商人，
n
个随从的过河问题以及<
/p>
n
个不同对象且每个对象有
m
个元素问题
(
说
明：
对于
3
个商人，
3
个随从问题分别对应于
n=2,m=3)
的过河问题。
从而给出课
后习题
5<
/p>
（
n=4,m=1
）的全部安全过河方案
。
四、实验步骤：
第一步：问题分析。这是一个多步
决策过程，涉及到每一次船上的人员以及
要考虑此岸和彼岸上剩余的商人数和随从数，<
/p>
在安全的条件下
（两岸的随从数不
比商人
多）
，经有限步使全体人员过河。
第二步：
分析模型的构成。
记第
k
次渡河前此岸
的商人数为
x
k
，
随从数为
y
k
，
< br>k
1
,
2
，
x
k
,
y
k
1
,
2
n
，
（具有可扩展性）
，将
定义为状态，状态集合
（
x
k
,
y
k
）
（
x
,
y
）
|
x
0
,
y
0
,
1
,<
/p>
2
,
3
;
x
3
,
y
0
,
1
,
2
,
3
;
x
y
1
,
2<
/p>
}
成为允许状态集合（
S
）
。
S={
记第
k
次渡船的商人数为
u
k<
/p>
，随从数为
v
k
，决策为
(
u
k
,
v
k
)
，
安全渡河条件下，
决
策
的
集
合
为
允
< br>许
决
策
集
合
。
允
许
决
策
集
合
记
作
D
，
所
以
（
u
,
v
）
|
1
< br>
u
v
2
,
u
,
v
0
,
1
,
2
k 变化的规律是 <
br> <
br>(
|1
因为
k
为奇数时船从此岸
D={
驶向彼岸，
k
为偶数时船由彼岸驶向此岸，所以状态
s
随决策
d
k
s
k
1
s
k
(
1
)
d
k
k
，
此式为状态转移律。制定安全渡河方案归结为如下的多步决
策模型：求决策
d
k
D
k
1
,
2
n
)
，使状态
s
k
S
按照转移律，由初始状态
s
1
(
3
,
3
)
经有限
n
步到达
s
n
1
(
0
,
0
)
第三步：模型求解。
#include
#include
#include
#include
#include
using namespace std;
#include
FILE
*fp;/*
设立文件指针，以便将它用于其他函数中
*/
struct a{
long m,s;
struct a *next;
};/*
< br>数组类型
a
：记录各种情况下船上的商人和仆人数，
m
：代表商人数
s
：代表仆人数
*/
struct a *jj,head;/*head
为头指针
的链表单元（船上的人数的各种情况的链表）
*/
int n
,total=0,js=0;/*total
表示船上各种情况总数
< br>*/
struct aim {
long
m1,s1,m2,s2;
int n;
struct
aim
*back,*next;};/*
< br>用于建立双向的指针链表，记入符合的情况，
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;
}/*
用于解决重复，算法思想：即将每次算出的链表单元与以前的相比较，若重复，<
/p>
则表示出现循环
*/
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;}
p
rintf(
第
%d
种方法
:n
fprintf(fp,
第
< br>%d
种方法
:n
int
count=0;
while(p){
printf(
fprintf(fp,
p=p->next;
count++;
}
cout<<
一共有
步完成
}/*
打印函数，将
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);
<
br>printf(
for(i=0;i
fla=fla->next;
copyit(p3,p);
p3->s1-=fla->m*f;
p3->m1-=fla->s*f;
p3->s2+=fla->m*f;
p3->m2+=fl
a->s*f;/*
运算过程，即过河过程
*/
j=determ(p3);/*
判断，
j
记录判断结果
*/
if(j==-1){
if(i
else{
freeit(p3);
break;}}
int count1=0;
if(j==1){if(i
count1++;
continue;}
else{print(p3);
freeit(p3);
break;}
//cout<
printf(
printf(
}
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(
printf(
exit(0);}
fp=fpt;
system(
printf(
问题描述：三个商人
各带一个随从乘船过河，一只小船只能容纳
X
人，由他们自己<
/p>
划船。
三个商人窃听到随从们密谋，
在河
的任意一岸上，
只要随从的人数比上人多，就杀掉
商人。但是如
何乘船渡河的决策权在商人手里，商人们如何安排渡河计划确保自身安全？
n
printf(
p=(struct aim
*)malloc(sizeof(struct aim));
p->back=NULL;
p->next=NULL;
p->s2=0;
p->m2=0;
p->n=1;/*
设立初始头指针
*/
fprintf(fp,
请输入船上的人
数
n
scanf(
fprintf(f
p,
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(
fprintf(fp,
sc
anf(
fprintf(fp,
/************
**********************/
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)
、
-
-
-