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

《数学建模：研究商人过河问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数学建模实验一报告实验题目：研究商人过河问题一、实验目的：编写一个程序（可以是C,C++或Mathlab）实现商人安全过河问题。二、实验环境：Turboc2.0、MicrosoftVisualC++6.0、Matlab6.0以上三、实验要求：要求该程序不仅能找出一组安全过河的可行方案，还可以得到所有的安全过河可行方案。并且该程序具有一定的可扩展性，即不仅可以实现3个商人，3个随从的过河问题。还应能实现n个商人，n个随从的过河问题以及n个不同对象且每个对象有m个元素问题(说明：对于3个商人，3个随从问题分别对应于n=2,m=3)的过河

2、问题。从而给出课后习题5（n=4,m=1）的全部安全过河方案。四、实验步骤：第一步：问题分析。这是一个多步决策过程，涉及到每一次船上的人员以及要考虑此岸和彼岸上剩余的商人数和随从数，在安全的条件下（两岸的随从数不比商人多），经有限步使全体人员过河。第二步：分析模型的构成。记第k次渡河前此岸的商人数为，随从数为，，，（具有可扩展性），将定义为状态，状态集合成为允许状态集合（S）。S={}记第k次渡船的商人数为，随从数为，决策为，安全渡河条件下，决策的集合为允许决策集合。允许决策集合记作D，所以D={

3、1

4、},因为k为奇数时船从此岸驶向彼岸，k为偶数时船由彼岸驶向此岸，所以状态随决策变化的规律是，此式为状态转移律。制定安全渡河方案归结为如下的多步决策模型：求决策，使状态按照转移律，由初始状态经有限n步到达第三步：模型求解。#include"stdio.h"#include"string.h"#include#include#includeusingnamespacestd;#include"conio.h"FILE*fp;/*设立文件指针，以便将它用于其他函数中*/structa

5、{longm,s;structa*next;};/*数组类型a：记录各种情况下船上的商人和仆人数，m：代表商人数s：代表仆人数*/structa*jj,head;/*head为头指针的链表单元（船上的人数的各种情况的链表）*/intn,total=0,js=0;/*total表示船上各种情况总数*/structaim{longm1,s1,m2,s2;intn;structaim*back,*next;};/*用于建立双向的指针链表，记入符合的情况，m1，s1表示要过岸的商人数和仆人数；m2，s2表示过岸了的商人数和仆人数，n表示来回

6、的次数*/intk1,k2;voidfreeit(structaim*p){structaim*p1=p;p1=p->back;free(p);if(p1!=NULL)p1->next=NULL;return;}/*释放该单元格，并将其上的单元格的next指针还原*/intdeterm(structaim*p){structaim*p1=p;if(p->s1>k2)return-1;/*仆人数不能超过总仆人数*/if(p->m1>k1)return-1;/*商人数不能超过总商人数*/if(p->s2>k2)return-1;/*对岸

7、，同上*/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->ba

8、ck;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)return1;elsereturn-1;/*显然如果达到条件就说明ok了*/return0;}/*判断函数*/intsign(intn){if(n%2

9、==0)return-1;return1;}/*符号函数*/voidcopyit(structaim*p3,structaim*p){p3->s1=p->s1;p3->s2=p->s2;p3->m1=p->m1;p3->m2=p->m