數(shù)學(xué)建模：研究商人過河問題

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=|1u+v2,u,v=0,1,2,因為k為奇數(shù)時船從此岸駛向彼岸，k為偶數(shù)時船由彼岸駛向此岸，所以狀態(tài)隨決策變化的規(guī)律是，此式為狀態(tài)轉(zhuǎn)移律。制定安全渡河

3、方案歸結(jié)為如下的多步?jīng)Q策模型：求決策，使狀態(tài)按照轉(zhuǎn)移律，由初始狀態(tài)經(jīng)有限n步到達第三步：模型求解。#include stdio.h#include string.h#include #include #include using namespace std;#include conio.hFILE *fp;/*設(shè)立文件指針，以便將它用于其他函數(shù)中*/struct along m,s;struct a *next;/*數(shù)組類型a：記錄各種情況下船上的商人和仆人數(shù)，m：代表商人數(shù) s：代表仆人數(shù)*/struct a *jj,head;/*head為頭指針的鏈表單元（船上的人數(shù)的各種情況的鏈表）*/

4、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)struct aim *p1=p; p1=p-back;free(p);if(p1!=NULL)p1-next=NULL;return;/*釋放該單元格，并將其上的單元格的next指針還原*/int

5、 determ(struct aim *p) struct aim *p1=p;if(p-s1k2)return -1;/*仆人數(shù)不能超過總仆人數(shù)*/if(p-m1k1)return -1;/*商人數(shù)不能超過總商人數(shù)*/if(p-s2k2)return -1;/*對岸，同上*/if(p-m2k1)return -1;/*對岸，同上*/if(p-s1s2m1m2m1!=0)if(p-s1p-m1)return -1;if(p-m2!=0)if(p-s2p-m2)return -1;/*兩岸商人數(shù)均不能小于仆人數(shù)*/while(p1!=NULL)p1=p1-back;if(p1!=NULL)if(

6、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ù)，則表示出現(xiàn)循環(huán)*/if(p-s1=0&p-m1=0)if(p-n%2=0)return 1;else return -1;/*顯然如果達到條件就說明ok了*/return 0;/*判斷函數(shù)*/int sign(int n)if(n%2=0)return -1;return 1;/*符號函數(shù)*/void copyit(struct aim *p3,struct aim

7、 *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-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-s

8、2);fprintf(fp,%ld,%ld:%ld,%ldt,p-m1,p-s1,p-m2,p-s2);p=p-next;count+;cout一共有count步完成n);for(i=0;inext;copyit(p3,p);p3-s1-=fla-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(itotal-1)continue;elsefreeit(p3);break;int count1=0;if(j=1)if(itotal-1)prin

9、t(p3);count1+;continue;elseprint(p3);freeit(p3);break;/coutcout1back=NULL;p-next=NULL;p-s2=0;p-m2=0;p-n=1;/*設(shè)立初始頭指針*/printf(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;f0&e+fm=e; jj-s=f; flag-next=jj; jj-ne

10、xt=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,&p-s1);fprintf(fp,n%ld,%ldn,p-m1,p-s1);/*/k1=p-m1;k2=p-s1;trans(p);fclose(fpt);getch()

11、;第一步：三個商人，三個隨從的模型求解答案為：運行后的結(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,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

12、,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) 到 (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) 到

13、(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: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,

14、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 一共有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種方

15、法: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,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

16、: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 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

17、,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 一共有12步完成第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種方

18、法: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 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

19、,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: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

20、,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 一共有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

21、,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: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

22、,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 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

23、,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: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 一共有1

24、6步完成第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 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,0

25、2,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: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

26、: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,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

27、 一共有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,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

28、: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: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步完成第41種方法: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