數(shù)學(xué)建模:研究商人過河問題_第1頁
數(shù)學(xué)建模:研究商人過河問題_第2頁
數(shù)學(xué)建模:研究商人過河問題_第3頁
數(shù)學(xué)建模:研究商人過河問題_第4頁
數(shù)學(xué)建模:研究商人過河問題_第5頁
已閱讀5頁,還剩5頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、精選文檔 數(shù)學(xué)建模試驗一報告試驗題目:爭辯商人過河問題一、試驗?zāi)康模壕帉懸粋€程序(可以是C,C+或Mathlab)實現(xiàn)商人平安過河問題。二、試驗環(huán)境:Turbo c 2.0、Microsoft Visual C+ 6.0、Matlab 6.0以上 三、試驗要求:要求該程序不僅能找出一組平安過河的可行方案,還可以得到全部的平安過河可行方案。并且該程序具有肯定的可擴展性,即不僅可以實現(xiàn)3個商人,3個隨從的過河問題。還應(yīng)能實現(xiàn)n個商人,n個隨從的過河問題以及n個不同對象且每個對象有m個元素問題(說明:對于3個商人,3個隨從問題分別對應(yīng)于n=2,m=3)的過河問題。從而給出課后習(xí)題5(n=4,m=1)

2、的全部平安過河方案。 四、試驗步驟: 第一步:問題分析。這是一個多步?jīng)Q策過程,涉及到每一次船上的人員以及要考慮此岸和彼岸上剩余的商人數(shù)和隨從數(shù),在平安的條件下(兩岸的隨從數(shù)不比商人多),經(jīng)有限步使全體人員過河。 其次步:分析模型的構(gòu)成。記第k次渡河前此岸的商人數(shù)為,隨從數(shù)為,(具有可擴展性),將定義為狀態(tài),狀態(tài)集合成為允許狀態(tài)集合(S)。S=記第k次渡船的商人數(shù)為,隨從數(shù)為,決策為,平安渡河條件下,決策的集合為允許決策集合。允許決策集合記作D,所以D=|1<u+v<2,u,v=0,1,2,由于k為奇數(shù)時船從今岸駛向彼岸,k為偶數(shù)時船由彼岸駛向此岸,所以狀態(tài)隨決策變化的規(guī)律是,此式為

3、狀態(tài)轉(zhuǎn)移律。制定平安渡河方案歸結(jié)為如下的多步?jīng)Q策模型:求決策,使?fàn)顟B(tài)依據(jù)轉(zhuǎn)移律,由初始狀態(tài)經(jīng)有限n步到達(dá)第三步:模型求解。#include "stdio.h"#include "string.h"#include <memory>#include <stdlib.h>#include <iostream>using namespace std;#include "conio.h"FILE *fp;/*設(shè)立文件指針,以便將它用于其他函數(shù)中*/struct along m,s;struct a *nex

4、t;/*數(shù)組類型a:記錄各種狀況下船上的商人和仆人數(shù),m:代表商人數(shù) s:代表仆人數(shù)*/struct a *jj,head;/*head為頭指針的鏈表單元(船上的人數(shù)的各種狀況的鏈表)*/int n,total=0,js=0;/*total表示船上各種狀況總數(shù)*/struct aim long m1,s1,m2,s2;int n;struct aim *back,*next;/*用于建立雙向的指針鏈表,記入符合的狀況,m1,s1表示要過岸的商人數(shù)和仆人數(shù);m2,s2表示過岸了的商人數(shù)和仆人數(shù),n表示來回的次數(shù)*/int k1,k2;void freeit(struct aim *p)struc

5、t 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;/*仆人數(shù)不能超過總仆人數(shù)*/if(p->m1>k1)return -1;/*商人數(shù)不能超過總商人數(shù)*/if(p->s2>k2)return -1;/*對岸,同上*/if(p->m2>k1)return -1;/*對岸,同上

6、*/if(p->s1<0)return -1;/*仆人數(shù)不能為負(fù)*/if(p->s2<0)return -1;/*商人數(shù)不能為負(fù)*/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;/*兩岸商人數(shù)均不能小于仆人數(shù)*/while(p1!=NULL)p1=p1->back;if(p1

7、!=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;/*用于解決重復(fù),算法思想:即將每次算出的鏈表單元與以前的相比較,若重復(fù),則表示消滅循環(huán)*/if(p->s1=0&&p->m1=0)if(p->n%2=0)return 1;else return -1;/*明顯假如達(dá)到條件就說明ok了*/return 0;/*推斷函數(shù)*/int sign(int n)if

8、(n%2=0)return -1;return 1;/*符號函數(shù)*/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;/*復(fù)制內(nèi)容函數(shù),將p中的內(nèi)容寫入p3所指向的鏈表單元中*/void print(struct aim *p3)struct aim *p=p3;js+;while(p-

9、>back)p=p->back;printf("n第%d種方法:n",js);fprintf(fp,"n第%d種方法:n",js);int count=0;while(p) printf("%ld,%ld:%ld,%ldt",p->m1,p->s1,p->m2,p->s2);fprintf(fp,"%ld,%ld:%ld,%ldt",p->m1,p->s1,p->m2,p->s2);p=p->next;count+;cout<<"

10、;一共有"<<count<<"步完成"<<endl;/*打印函數(shù),將p3所指的內(nèi)容打印出來*/void trans(struct aim *p)struct aim *p3;/*p3為申請的結(jié)構(gòu)體指針*/struct a *fla;int i,j,f;fla=&head;p3=(struct aim *)malloc(sizeof(struct aim);f=sign(p->n);for(i=0;i<total;i+)fla=fla->next;copyit(p3,p);p3->s1-=fla-&

11、gt;m*f;p3->m1-=fla->s*f;p3->s2+=fla->m*f;p3->m2+=fla->s*f;/*運算過程,即過河過程*/j=determ(p3);/*推斷,j記錄推斷結(jié)果*/if(j=-1)if(i<total-1)continue;elsefreeit(p3);break;int count1=0;if(j=1)if(i<total-1)print(p3);count1+;continue;elseprint(p3);freeit(p3);break;/cout<<cout1<<endl;prin

12、tf("%d",count1);printf("n");if(j=0)trans(p3);return;/*轉(zhuǎn)移函數(shù),即將人轉(zhuǎn)移過河*/*n=0*/void main() struct aim *p,*p1;int j,a,e,f;struct a *flag;/*flag是用與記錄頭指針*/FILE*fpt;if(fpt=fopen("c:result.dat","w+")=0)printf("can't creat itn");exit(0);fp=fpt; system("

13、;cls"); printf("問題描述:三個商人各帶一個隨從乘船過河,一只小船只能容納X人,由他們自己劃船。三個商人竊聽到隨從們密謀,在河的任意一岸上,只要隨從的人數(shù)比上人多,就殺掉商人。但是如何乘船渡河的決策權(quán)在商人手里,商人們?nèi)绾沃涠珊臃桨复_保自身平安?n"); printf("n"); p=(struct aim *)malloc(sizeof(struct aim);p->back=NULL;p->next=NULL;p->s2=0;p->m2=0;p->n=1;/*設(shè)立初始頭指針*/printf(&q

14、uot;please input the total of people on the boardn");fprintf(fp,"n請輸入船上的人數(shù)n");scanf("%d",&n);fprintf(fp,"n%dn",n);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; j

15、j->s=f; flag->next=jj; jj->next=NULL; flag=jj; /*/printf("please input the total of merchant and salvent as follow: mechant,salvent;n");fprintf(fp,"nplease input the total of merchant and salvent as follow: mechant,salvent;n");scanf("%ld,%ld",&p->m1,&

16、;p->s1);fprintf(fp,"n%ld,%ldn",p->m1,p->s1);/*/k1=p->m1;k2=p->s1;trans(p);fclose(fpt);getch();第一步:三個商人,三個隨從的模型求解答案為:運行后的結(jié)果為:第 1 種方案:(3,3) 到 (0,0)、(3,1) 到 (0,2)、(3,2) 到 (0,1)、(3,0) 到 (0,3)、(3,1) 到 (0,2)、(1,1) 到 (2,2)、(2,2) 到 (1,1)、(0,2) 到 (3,1)、(0,3) 到 (3,0)、(0,1) 到 (3,2)、(0,

17、2) 到 (3,1)、(0,0) 到 (3,3)第 2 種方案:(3,3) 到 (0,0)、(3,1) 到 (0,2)、(3,2) 到 (0,1)、(3,0) 到 (0,3)、(3,1) 到 (0,2)、(1,1) 到 (2,2)、(2,2) 到 (1,1)、(0,2) 到 (3,1)、(0,3) 到 (3,0)、(0,1) 到 (3,2)、(1,1) 到 (2,2)、(0,0) 到 (3,3)第 3 種方案:(3,3) 到 (0,0)、(2,2) 到 (1,1)、(3,2) 到 (0,1)、(3,0) 到 (0,3)、(3,1) 到 (0,2)、(1,1) 到 (2,2)、(2,2) 到 (

18、1,1)、(0,2) 到 (3,1)、(0,3) 到 (3,0)、(0,1) 到 (3,2)(、0,2) 到 (3,1)、(0,0) 到 (3,3)第 4 種方案:(3,3) 到 (0,0)、(2,2) 到 (1,1)、(3,2) 到 (0,1)、(3,0) 到 (0,3)、(3,1) 到 (0,2)、(1,1) 到 (2,2)、(2,2) 到 (1,1)、(0,2) 到 (3,1)、(0,3) 到 (3,0)、(0,1) 到 (3,2)、(1,1) 到 (2,2)(0,0) 到 (3,3)其次步:四個商人三個隨從,其結(jié)果為:第1種方法:4,3:0,0 3,2:1,1 4,2:0,1 2,2:

19、2,1 3,2:1,12,1:2,2 2,2:2,1 0,2:4,1 0,3:4,0 0,1:4,21,1:3,2 0,0:4,3 一共有12步完成第2種方法:4,3:0,0 3,2:1,1 4,2:0,1 2,2:2,1 3,2:1,12,1:2,2 2,2:2,1 0,2:4,1 0,3:4,0 0,1:4,22,1:2,2 1,0:3,3 1,1:3,2 0,0:4,3 一共有14步完成第3種方法:4,3:0,0 3,2:1,1 4,2:0,1 2,2:2,1 3,2:1,12,1:2,2 2,2:2,1 0,2:4,1 0,3:4,0 0,1:4,20,2:4,1 0,0:4,3 一共

20、有12步完成第4種方法:4,3:0,0 3,2:1,1 4,2:0,1 2,2:2,1 3,2:1,12,1:2,2 2,2:2,1 1,1:3,2 2,1:2,2 0,1:4,21,1:3,2 0,0:4,3 一共有12步完成第5種方法:4,3:0,0 3,2:1,1 4,2:0,1 2,2:2,1 3,2:1,12,1:2,2 2,2:2,1 1,1:3,2 2,1:2,2 0,1:4,20,2:4,1 0,0:4,3 一共有12步完成第6種方法:4,3:0,0 3,2:1,1 4,2:0,1 2,2:2,1 3,2:1,12,1:2,2 2,2:2,1 1,1:3,2 2,1:2,2 1

21、,0:3,31,1:3,2 0,1:4,2 0,2:4,1 0,0:4,3 一共有14步完成第7種方法:4,3:0,0 3,2:1,1 4,2:0,1 2,2:2,1 3,2:1,12,1:2,2 2,2:2,1 1,1:3,2 2,1:2,2 1,0:3,31,1:3,2 0,0:4,3 一共有12步完成第8種方法:4,3:0,0 3,2:1,1 4,2:0,1 4,0:0,3 4,1:0,22,1:2,2 2,2:2,1 0,2:4,1 0,3:4,0 0,1:4,21,1:3,2 0,0:4,3 一共有12步完成第9種方法:4,3:0,0 3,2:1,1 4,2:0,1 4,0:0,3

22、4,1:0,22,1:2,2 2,2:2,1 0,2:4,1 0,3:4,0 0,1:4,22,1:2,2 1,0:3,3 1,1:3,2 0,0:4,3 一共有14步完成第10種方法:4,3:0,0 3,2:1,1 4,2:0,1 4,0:0,3 4,1:0,22,1:2,2 2,2:2,1 0,2:4,1 0,3:4,0 0,1:4,20,2:4,1 0,0:4,3 一共有12步完成第11種方法:4,3:0,0 3,2:1,1 4,2:0,1 4,0:0,3 4,1:0,22,1:2,2 2,2:2,1 1,1:3,2 2,1:2,2 0,1:4,21,1:3,2 0,0:4,3 一共有1

23、2步完成第12種方法:4,3:0,0 3,2:1,1 4,2:0,1 4,0:0,3 4,1:0,22,1:2,2 2,2:2,1 1,1:3,2 2,1:2,2 0,1:4,20,2:4,1 0,0:4,3 一共有12步完成第13種方法:4,3:0,0 3,2:1,1 4,2:0,1 4,0:0,3 4,1:0,22,1:2,2 2,2:2,1 1,1:3,2 2,1:2,2 1,0:3,31,1:3,2 0,1:4,2 0,2:4,1 0,0:4,3 一共有14步完成第14種方法:4,3:0,0 3,2:1,1 4,2:0,1 4,0:0,3 4,1:0,22,1:2,2 2,2:2,1

24、1,1:3,2 2,1:2,2 1,0:3,31,1:3,2 0,0:4,3 一共有12步完成第15種方法:4,3:0,0 3,2:1,1 3,3:1,0 2,2:2,1 3,2:1,12,1:2,2 2,2:2,1 0,2:4,1 0,3:4,0 0,1:4,21,1:3,2 0,0:4,3 一共有12步完成第16種方法:4,3:0,0 3,2:1,1 3,3:1,0 2,2:2,1 3,2:1,12,1:2,2 2,2:2,1 0,2:4,1 0,3:4,0 0,1:4,22,1:2,2 1,0:3,3 1,1:3,2 0,0:4,3 一共有14步完成第17種方法:4,3:0,0 3,2:

25、1,1 3,3:1,0 2,2:2,1 3,2:1,12,1:2,2 2,2:2,1 0,2:4,1 0,3:4,0 0,1:4,20,2:4,1 0,0:4,3 一共有12步完成第18種方法:4,3:0,0 3,2:1,1 3,3:1,0 2,2:2,1 3,2:1,12,1:2,2 2,2:2,1 1,1:3,2 2,1:2,2 0,1:4,21,1:3,2 0,0:4,3 一共有12步完成第19種方法:4,3:0,0 3,2:1,1 3,3:1,0 2,2:2,1 3,2:1,12,1:2,2 2,2:2,1 1,1:3,2 2,1:2,2 0,1:4,20,2:4,1 0,0:4,3

26、一共有12步完成第20種方法:4,3:0,0 3,2:1,1 3,3:1,0 2,2:2,1 3,2:1,12,1:2,2 2,2:2,1 1,1:3,2 2,1:2,2 1,0:3,31,1:3,2 0,1:4,2 0,2:4,1 0,0:4,3 一共有14步完成第21種方法:4,3:0,0 3,2:1,1 3,3:1,0 2,2:2,1 3,2:1,12,1:2,2 2,2:2,1 1,1:3,2 2,1:2,2 1,0:3,31,1:3,2 0,0:4,3 一共有12步完成第22種方法:4,3:0,0 3,2:1,1 3,3:1,0 2,2:2,1 4,2:0,14,0:0,3 4,1:

27、0,2 2,1:2,2 2,2:2,1 0,2:4,10,3:4,0 0,1:4,2 1,1:3,2 0,0:4,3 一共有14步完成第23種方法:4,3:0,0 3,2:1,1 3,3:1,0 2,2:2,1 4,2:0,14,0:0,3 4,1:0,2 2,1:2,2 2,2:2,1 0,2:4,10,3:4,0 0,1:4,2 2,1:2,2 1,0:3,3 1,1:3,20,0:4,3 一共有16步完成第24種方法:4,3:0,0 3,2:1,1 3,3:1,0 2,2:2,1 4,2:0,14,0:0,3 4,1:0,2 2,1:2,2 2,2:2,1 0,2:4,10,3:4,0

28、0,1:4,2 0,2:4,1 0,0:4,3 一共有14步完成第25種方法:4,3:0,0 3,2:1,1 3,3:1,0 2,2:2,1 4,2:0,14,0:0,3 4,1:0,2 2,1:2,2 2,2:2,1 1,1:3,22,1:2,2 0,1:4,2 1,1:3,2 0,0:4,3 一共有14步完成第26種方法:4,3:0,0 3,2:1,1 3,3:1,0 2,2:2,1 4,2:0,14,0:0,3 4,1:0,2 2,1:2,2 2,2:2,1 1,1:3,22,1:2,2 0,1:4,2 0,2:4,1 0,0:4,3 一共有14步完成第27種方法:4,3:0,0 3,2

29、:1,1 3,3:1,0 2,2:2,1 4,2:0,14,0:0,3 4,1:0,2 2,1:2,2 2,2:2,1 1,1:3,22,1:2,2 1,0:3,3 1,1:3,2 0,1:4,2 0,2:4,10,0:4,3 一共有16步完成第28種方法:4,3:0,0 3,2:1,1 3,3:1,0 2,2:2,1 4,2:0,14,0:0,3 4,1:0,2 2,1:2,2 2,2:2,1 1,1:3,22,1:2,2 1,0:3,3 1,1:3,2 0,0:4,3 一共有14步完成第29種方法:4,3:0,0 4,1:0,2 4,2:0,1 3,2:1,1 3,3:1,02,2:2,1

30、 3,2:1,1 2,1:2,2 2,2:2,1 0,2:4,10,3:4,0 0,1:4,2 1,1:3,2 0,0:4,3 一共有14步完成第30種方法:4,3:0,0 4,1:0,2 4,2:0,1 3,2:1,1 3,3:1,02,2:2,1 3,2:1,1 2,1:2,2 2,2:2,1 0,2:4,10,3:4,0 0,1:4,2 2,1:2,2 1,0:3,3 1,1:3,20,0:4,3 一共有16步完成第31種方法:4,3:0,0 4,1:0,2 4,2:0,1 3,2:1,1 3,3:1,02,2:2,1 3,2:1,1 2,1:2,2 2,2:2,1 0,2:4,10,3

31、:4,0 0,1:4,2 0,2:4,1 0,0:4,3 一共有14步完成第32種方法:4,3:0,0 4,1:0,2 4,2:0,1 3,2:1,1 3,3:1,02,2:2,1 3,2:1,1 2,1:2,2 2,2:2,1 1,1:3,22,1:2,2 0,1:4,2 1,1:3,2 0,0:4,3 一共有14步完成第33種方法:4,3:0,0 4,1:0,2 4,2:0,1 3,2:1,1 3,3:1,02,2:2,1 3,2:1,1 2,1:2,2 2,2:2,1 1,1:3,22,1:2,2 0,1:4,2 0,2:4,1 0,0:4,3 一共有14步完成第34種方法:4,3:0,

32、0 4,1:0,2 4,2:0,1 3,2:1,1 3,3:1,02,2:2,1 3,2:1,1 2,1:2,2 2,2:2,1 1,1:3,22,1:2,2 1,0:3,3 1,1:3,2 0,1:4,2 0,2:4,10,0:4,3 一共有16步完成第35種方法:4,3:0,0 4,1:0,2 4,2:0,1 3,2:1,1 3,3:1,02,2:2,1 3,2:1,1 2,1:2,2 2,2:2,1 1,1:3,22,1:2,2 1,0:3,3 1,1:3,2 0,0:4,3 一共有14步完成第36種方法:4,3:0,0 4,1:0,2 4,2:0,1 2,2:2,1 3,2:1,12,

33、1:2,2 2,2:2,1 0,2:4,1 0,3:4,0 0,1:4,21,1:3,2 0,0:4,3 一共有12步完成第37種方法:4,3:0,0 4,1:0,2 4,2:0,1 2,2:2,1 3,2:1,12,1:2,2 2,2:2,1 0,2:4,1 0,3:4,0 0,1:4,22,1:2,2 1,0:3,3 1,1:3,2 0,0:4,3 一共有14步完成第38種方法:4,3:0,0 4,1:0,2 4,2:0,1 2,2:2,1 3,2:1,12,1:2,2 2,2:2,1 0,2:4,1 0,3:4,0 0,1:4,20,2:4,1 0,0:4,3 一共有12步完成第39種方法:4,3:0,0 4,1:0,2 4,2:0,1 2,2:2,1 3,2:1,12,1:2,2 2,2:2,1 1,1:3,2 2,1:2,2 0,1:4,21,1:3,2 0,0:4,3 一共有12步完成第40種方法:4,3:0,0 4,1:0,2 4,2

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論