数学建模论文Word格式.docx
- 文档编号:907973
- 上传时间:2023-04-29
- 格式:DOCX
- 页数:20
- 大小:350.70KB
数学建模论文Word格式.docx
《数学建模论文Word格式.docx》由会员分享,可在线阅读,更多相关《数学建模论文Word格式.docx(20页珍藏版)》请在冰点文库上搜索。
根据题意,可以作出商人渡河初始状态的示意图:
A→B
渡河目的:
→
(选择
岸为参考点)
4.2C++程序解决
根据
(1)
(2)(3)式,通过利用matlab编写一段程序来求解多步决策问题是可行的,但是当商人和仆人数都不多的情况下还可以用平面坐标法解此模型更为方便。
接下来,我们先用平面坐标法求解此模型,最后再使用计算机仿真,对求解的结果进行验证,并给予推广。
4.2.1C++程序代码
//约束条件:
岸上仆人数不能多于商人数
#include<
iostream>
usingnamespacestd;
structNode
{intnMer;
intnSer;
intlength;
};
classA
{
public:
A();
~A();
voidTspt();
//过河的动作
voiddoLeft(intnhead,intntail,intnlength);
private:
boolislegal(intnm,intns);
//判断是否满足约束条件,满足为true
Node*funTspt(intnm,intns,boolflag);
//添加STEP[head]可以向后延伸的节点
boolnoRepeat(intnm,intns);
//没有重复返回TRUE
voidfunshow(inta[][2],intntail);
boolfunLeft(Nodend,intb1,intb2,intn);
voidshow(ints[],intp[][2],int&
top,int&
count,inta[]);
inthead;
inttail;
intn;
//商仆的对数
intnB;
//船最多的载人数目
Node*STEP;
A:
:
~A()
free(STEP);
}
A()
cout<
<
"
请输入商仆的对数S="
;
F:
cin>
>
n;
if(n==1)
{
nB=2;
船最多载人的数目K="
nB;
}
elseif(n==2)
cout<
船最多载人的数目可以取:
for(intx=n;
x<
=2*n;
x++)
{
cout<
、"
}
endl;
请输入船最多载人的数目K="
elseif(n==3)
for(intx=n-1;
elseif(n==4)
elseif(n>
=5&
&
n<
=100)
for(intx=4;
elseif(n<
1||n>
100)
本程序仅在S=(0…100)以内保证其正确性"
请重新输入商仆的对数S="
gotoF;
STEP=(Node*)malloc(sizeof(Node)*10000);
memset(STEP,0,sizeof(Node)*10000);
head=tail=0;
STEP[0].nMer=STEP[0].nSer=n;
intmain()
问题描述:
13对商仆乘船渡河,在河的任意一岸,一旦仆人数多于商人数,商人就有危险.船一次载多少人商人们才可以安全渡河"
Aa;
a.Tspt();
return0;
voidA:
show(ints[],intp[][2],int&
count,inta[])
if(top==-1)
return;
//已找到目标状态需,输出数据
if(top==STEP[head].length)
***********"
++count<
***********"
funshow(p,top+1);
B:
top--;
if(top==-1)
return;
C:
s[top]--;
if(STEP[(s[top])].length!
=top)//退过了
s[top]=a[top];
gotoB;
if(funLeft(STEP[(s[top])],p[top-1][0],p[top-1][1],top-1)==false)
gotoC;
p[top][0]=STEP[(s[top])].nMer;
p[top][1]=STEP[(s[top])].nSer;
show(s,p,top,count,a);
//在中间加入节点STEP[(s[top+1])]
if(funLeft(STEP[(s[top+1])],p[top][0],p[top][1],top)==true)//符合条件
{
top++;
else//不符合条件
E:
s[top+1]--;
if(STEP[(s[top+1])].length==top)//退过了,到了下一层
s[top+1]=a[top+1];
D:
s[top]--;
if(STEP[(s[top])].length!
=top)//退过了,到了下一层
{
for(inti=top;
i<
=STEP[head].length;
i++)
s[i]=a[i];
top--;
if(top==-1)
return;
gotoD;
}
if(top==0)
return;
if(funLeft(STEP[(s[top])],p[top-1][0],p[top-1][1],top-1)==false)
p[top][0]=STEP[(s[top])].nMer;
p[top][1]=STEP[(s[top])].nSer;
show(s,p,top,count,a);
if(funLeft(STEP[(s[top+1])],p[top][0],p[top][1],top)==false)
gotoE;
}
doLeft(intnhead,intntail,intnlength)
inta[1000];
inta1[1000];
intsp[1000][2];
boolflag=false;
memset(a,0xff,4000);
memset(a1,0xff,4000);
memset(sp,0xff,8000);
if(STEP[head].length%2==0)
flag=true;
while(STEP[head].length==nlength-1)
{
funTspt(STEP[head].nMer,STEP[head].nSer,flag);
head++;
for(inti=0;
head+1;
a[(STEP[i].length)]=i;
a1[(STEP[i].length)]=i;
sp[0][0]=sp[0][1]=n;
STEP[head].nMer=STEP[head].nSer=0;
inttop=0;
intcount=0;
show(a1,sp,top,count,a);
boolA:
funLeft(Nodend,intb1,intb2,intn)
boolflag=abs(nd.nMer-b1)+abs(nd.nSer-b2)<
nB+1
&
abs(nd.nMer-b1)+abs(nd.nSer-b2)>
0;
if(flag==false)
returnfalse;
if(n%2==0&
b1>
=nd.nMer&
b2>
=nd.nSer)
returntrue;
if(n%2==1&
b1<
b2<
returnfalse;
Tspt()
{
Node*temp=newNode;
temp=NULL;
while(head<
=tail)
if(STEP[head].length%2==0)
flag=true;
else
flag=false;
temp=funTspt(STEP[head].nMer,STEP[head].nSer,flag);
if(NULL!
=temp)
break;
if(head>
tail)
此问题无解!
exit
(1);
doLeft(temp->
nMer,temp->
nSer,temp->
length);
//temp->
nMer表示head
deletetemp;
Node*A:
funTspt(intnm,intns,boolflag)
{//flag==true向对岸运输
Node*nd=NULL;
inttemp=1;
inttM=STEP[head].nMer;
//可供运输的商人数
inttS=STEP[head].nSer;
//可供运输的仆人数
if(flag==false)//向此岸运输
tM=n-STEP[head].nMer;
tS=n-STEP[head].nSer;
temp=-1;
tM+1&
nB+1;
i++)//i表示运输的商人数
for(intj=0;
j<
tS+1&
nB-i+1;
j++)//j表示运输的仆人数
if(i+j==0)
continue;
intp=STEP[head].nMer-temp*i;
intq=STEP[head].nSer-temp*j;
if(islegal(p,q)==true&
noRepeat(p,q)==true)
if(p==0&
q==0)
{
tail++;
STEP[tail].length=STEP[head].length+1;
STEP[tail].nMer=p;
STEP[tail].nSer=q;
nd=(Node*)malloc(sizeof(Node));
nd->
length=STEP[head].length+1;
nMer=head;
nSer=tail;
returnnd;
}
tail++;
STEP[tail].length=STEP[head].length+1;
STEP[tail].nMer=p;
STEP[tail].nSer=q;
}
}
returnnd;
noRepeat(intnm,intns)
intj1=0;
j1=1;
for(inti=j1;
tail+1;
if(STEP[i].length%2==j1&
nm==STEP[i].nMer&
ns==STEP[i].nSer)
returnfalse;
returntrue;
islegal(intnm,intns)
{//商人数少于仆人数或者商人数为0
if((nm==0)||(nm==n)||(nm==ns))
funshow(inta[][2],intntail)
商人数仆人数"
ntail;
第"
i<
次"
a[i][0]<
"
a[i][1]<
if(i!
=ntail-1&
i%2==0)
-->
("
abs(a[i+1][0]-a[i][0])<
"
<
abs(a[i+1][1]-a[i][1])<
)"
elseif(i!
i%2==1)
<
--("
图1:
4.2.2运行结果显示
图2:
图3:
从图中看出当商仆对数为13时候,船的容量为2时,此问题无解,即这种情况无法安全渡河。
图4:
从图中可以看出,当商仆为13对,船的容量为4人时,有解,即可以安全过河。
图5:
图6:
图7:
从图中可以看出,商仆对数为13,容量为4―26人的时候,均可以安全过河。
当容量为4时并且有361种方式。
通过计算机运行此c++程序,当题目中给定出任意数量的商人,仆人,以及规定出任意船的容量,都可以判断出“商人们能否安全渡河?
”以及解决“如果能,那么安全渡河的方案是什么?
”的问题。
从而使这个模型更具有一定的推广价值。
5模型的评价与改进
5.1模型的评价
5.1.1模型的优点
(1)采用了较为成熟的数学理论建立模型,可行度比较高;
(2)运用程序显示多个路径,比较直观;
(3)模型的求解运用了强大的MicrosoftVisualC++6.0软件,结果可信度高,便于推广;
(4)通过C++程序,能判断出“当任意个商人﹑任意个仆人﹑船的容量任意时,商人能否安全渡河?
”及解决了“如果能,那么渡河方案又是什么?
”的问题,使得所建模型更加全面。
5.1.2模型的缺点
(1)没有找到商人数﹑仆人数及船的容量之间的数量关系;
(2)没有考虑到实际生活中,在安全渡河的前提下,商人过河的优先级应高于随仆人。
5.2模型的改进
基于以上求解模型用到的方法,我们明显意识到了结果考虑到的不够全面。
为此,我们编写的C++算法程序,通过相应程序求解前面模型得到最短路径的最优解。
但同时当有多个解决方案时,能够将所有符合条件的情况逐一列出。
综合以上的努力,我们与致力于研究出一套方案:
即给出任意个商人与任意个仆人以及船的容量任意的时候,都可以给出安全渡河的方案;
并且在给出商人数、仆人数、船的容量中任意两者,并要使其能够安全渡河情况下的第三者的取值范围,以及得到最优的渡河方案。
由于水平有限,我们只能提出这个美好的想法,用某种方法能把在所有安全状态集合和决策集合中,搜索出所有可能的解,从而从其中找出最优的解。
6模型的推广
“商人渡河”模型适合于解决很多问题,如“传教士与野蛮人渡河”,“印度夫妻渡河”等。
这些问题本质上都是相同或相似的,由此可见这个趣味问题流传的广泛性。
另外还有所谓“人狗鸡米过河”问题,也是颇有趣味的,人、狗、鸡、米均要过河,船需人划,而船上至多还可载一物,但若人不在时,狗会吃鸡,鸡会吃米,问如何设计安全过河方案。
我们完全可以仿照商人渡河问题建立一个多步决策模型,将上述算法稍作修改,就可以得到它的解。
这里就不再赘述了。
另外,用一定容积的若干油瓶倒出一定量的油的问题也属此类问题。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 论文