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

.

数学建模实验一报告

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

一、实验目的:编写一个程序(可以是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 \#include \#include #include #include using namespace std; #include \

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(\第%d种方法:\\n\fprintf(fp,\第%d种方法:\\n\

.

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4