数学建模作业(商人过河问题)
-
数学建模作业（四）——商人过河问题
一．
问题描述
有四名商人各带一名仆人过
河，
但船最多能载二人，
商人已获得仆人的阴谋：
在河的任一岸，
只要仆人数超过商人数，
仆人会将商
人杀死并窃取财物且安排如
何乘船的权力掌握在商人手中。试为商人制定一个安全过河的
方案。
二．解决方案
用递归的源程序如下：
开始时商人，强盗所在的河的这边设为
0
状态，另
一边设为
1
状态（也就是船
开始时的一
边设为
0
，当船驶到对岸是设为
1
状态，在这两个状态时，都必须符
合条件）
#include
struct
node
/*
建立一个类似栈的数据结构并且
可以浏览每一个数据点
*/
{
int
x;
int
y;
int
state;
struct
node
*next;
};
typedef
struct
node
state;
typedef
state
*link;
link
PPointer1=NULL;
link
PPointer2=NULL;
int
a1,b1;
int
a2,b2;
/*
栈中
每个数据都分为
0
，
1
状态
*/
void
Push(int
a,int
b,int
n)
{
link
newnode;
newnode=(link)malloc(sizeof(state));
newnode-> x=a;
newnode-> y=b;
newnode-> state=n;
newnode-> next=NULL;
if(PPointer1==NULL)
{
PPointer1=newnode;
PPointer2=newnode;
}
else
{
PPointer2-> next=newnode;
PPointer2=newnode;
}
}
void
Pop()
/*
弹栈
*/
{
link
pointer;
if(PPointer1==PPointer2)
{
free(PPointer1);
PPointer1=NULL;
PPointer2=NULL;
}
pointer=PPointer1;
while(pointer->
next!=PPointer2)
pointer=pointer-> next;
free(PPointer2);
PPointer2=pointer;
PPointer2-> next=NULL;
}
int
history(int
a,int
b,int
n)
/*
比较输入的数据和栈中是否有重复的
*/
{
link
pointer;
if(PPointer1==NULL)
return
1;
else
{
pointer=PPointer1;
while(pointer!=NULL)
{
if(pointer-> x==a&&pointer->
y==b&&pointer->
state==n)
return
0;
pointer=pointer-> next;
}
return
1;
}
}
int
judge(int
a,int
b,int
c,int
d,int
n)
/*
判断
这个状态是否可行，其中使用了
history
函数
*/
{
if(history(a,b,n)==0)
return
0;
if(a> =0&&b> =0&&a <=3&&b <=3&&c>
=0&&d> =0&&c <=3&&d
<=3&&a+c==3&&b+d==3)
{
switch(n)
{
case
1:
{
if(a==3)
{
Push(a,b,n);
return
1;
}
else
if(a==0)
{
Push(a,b,n);
return
1;
}
else
if(a==b)
{
Push(a,b,n);
return
1;
}
else
return
0;
}
case
0:
{
if(a==3)
{
Push(a,b,n);
return
1;
}