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

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

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

3、律。制定安全渡河方案歸結(jié)為如下的多步?jīng)Q策模型：求決策，使?fàn)顟B(tài)按照轉(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 *next;/*

4、數(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表示來(lái)回的次數(shù)*/int k1,k2;void freeit(struct aim *p)struct ai

5、m *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;/*對(duì)岸，同上*/if(p->m2>k1)return -1;/*對(duì)岸，同上*/if

6、(p->s1<0)return -1;/*仆人數(shù)不能為負(fù)*/if(p->s2<0)return -1;/*商人數(shù)不能為負(fù)*/if(p->m1<0)return -1;/*對(duì)岸，同上*/if(p->m2<0)return -1;/*對(duì)岸，同上*/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!=NU

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

8、=0)return -1;return 1;/*符號(hào)函數(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)容打印出來(lái)*/void trans(struct aim *p)struct aim *p3;/*p3為申請(qǐng)的結(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->m

11、*f;p3->m1-=fla->s*f;p3->s2+=fla->m*f;p3->m2+=fla->s*f;/*運(yùn)算過程，即過河過程*/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;printf(&

12、quot;%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("cls

13、"); printf("問題描述：三個(gè)商人各帶一個(gè)隨從乘船過河，一只小船只能容納X人，由他們自己劃船。三個(gè)商人竊聽到隨從們密謀，在河的任意一岸上，只要隨從的人數(shù)比上人多，就殺掉商人。但是如何乘船渡河的決策權(quán)在商人手里，商人們?nèi)绾伟才哦珊佑?jì)劃確保自身安全？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("

14、please input the total of people on the boardn");fprintf(fp,"n請(qǐng)輸入船上的人數(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; jj-&g

15、t;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,&p-&

16、gt;s1);fprintf(fp,"n%ld,%ldn",p->m1,p->s1);/*/k1=p->m1;k2=p->s1;trans(p);fclose(fpt);getch();第一步：三個(gè)商人，三個(gè)隨從的模型求解答案為：運(yùn)行后的結(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) 到

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

18、、(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)第二步：四個(gè)商人三個(gè)隨從，其結(jié)果為：第1種方法:4,3:0,0 3,2:1,1 4,2:0,1 2,2:2,1

19、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 一共有12步

20、完成第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,0:3

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

22、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 一共有12步完成

23、第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 1,1:

24、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:1,1

25、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 一共有1

26、2步完成第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:0,2

27、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 0,1:

28、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:1,1

29、 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 3,2

30、: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:4,0

31、 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,0 4,

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

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