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

数学建模实验一报告实验题目：研究商人过河问题一、实验目的：编写一个程序（可以是C,C++或Mathlab）实现商人安全过河问题。二、实验环境：Turboc2.0、MicrosoftVisualC++6.0、Matlab6.0以上三、实验要求：要求该程序不仅能找出一组安全过河的可行方案，还可以得到所有的安全过河可行方案。并且该程序具有一定的可扩展性，即不仅可以实现3个商人，3个随从的过河问题。还应能实现n个商人，n个随从的过河问题以及n个不同对象且每个对象有m个元素问题(说明：对于3个商人，3个随从问题分别对应于n=2,m=3)的过河问题。从而给出课后习题5（n=4,m=1）的全部安全过河方案。四、实验步骤：第一步：问题分析。这是一个多步决策过程，涉及到每一次船上的人员以及要考虑此岸和彼岸上剩余的商人数和随从数，在安全的条件下（两岸的随从数不比商人多），经有限步使全体人员过河。第二步：分析模型的构成。记第k次渡河前此岸的商人数为kx，随从数为ky，2,1k，nyxkk2,1,，（具有可扩展性），将）（kkyx,定义为状态，状态集合成为允许状态集合（S）。S={2,1;3,2,1,0,3;3,2,1,0,0|,yxyxyxyx）（}记第k次渡船的商人数为ku，随从数为kv，决策为),(kkvu，安全渡河条件下，决策的集合为允许决策集合。允许决策集合记作D，所以D={2,1,0,,21|,vuvuvu）（|1u+v2,u,v=0,1,2},因为k为奇数时船从此岸驶向彼岸，k为偶数时船由彼岸驶向此岸，所以状态ks随决策kd变化的规律是kkkkdss)1(1，此式为状态转移律。制定安全渡河方案归结为如下的多步决策模型：求决策)2,1(nkDdk，使状态Ssk按照转移律，由初始状态)3,3(1s经有限n步到达)0,0(1ns第三步：模型求解。#includestdio.h#includestring.h#includememory#includestdlib.h#includeiostreamusingnamespacestd;#includeconio.hFILE*fp;/*设立文件指针，以便将它用于其他函数中*/structa{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表示来回的次数*/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-s1k2)return-1;/*仆人数不能超过总仆人数*/if(p-m1k1)return-1;/*商人数不能超过总商人数*/if(p-s2k2)return-1;/*对岸，同上*/if(p-m2k1)return-1;/*对岸，同上*/if(p-s10)return-1;/*仆人数不能为负*/if(p-s20)return-1;/*商人数不能为负*/if(p-m10)return-1;/*对岸，同上*/if(p-m20)return-1;/*对岸，同上*/if(p-m1!=0)if(p-s1p-m1)return-1;if(p-m2!=0)if(p-s2p-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)return1;elsereturn-1;/*显然如果达到条件就说明ok了*/return0;}/*判断函数*/intsign(intn){if(n%2==0)return-1;return1;}/*符号函数*/voidcopyit(structaim*p3,structaim*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所指向的链表单元中*/voidprint(structaim*p3){structaim*p=p3;js++;while(p-back){p=p-back;}printf(\n第%d种方法:\n,js);fprintf(fp,\n第%d种方法:\n,js);intcount=0;while(p){printf(%ld,%ld::%ld,%ld\t,p-m1,p-s1,p-m2,p-s2);fprintf(fp,%ld,%ld::%ld,%ld\t,p-m1,p-s1,p-m2,p-s2);p=p-next;count++;}cout一共有count步完成endl;}/*打印函数，将p3所指的内容打印出来*/voidtrans(structaim*p){structaim*p3;/*p3为申请的结构体指针*/structa*fla;inti,j,f;fla=&head;p3=(structaim*)malloc(sizeof(structaim));f=sign(p-n);for(i=0;itotal;i++){fla=fla-next;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记录判断结果*/if(j==-1){if(itotal-1){continue;}else{freeit(p3);break;}}intcount1=0;if(j==1){if(itotal-1){print(p3);count1++;continue;}else{print(p3);freeit(p3);break;}//coutcout1endl;printf(%d,count1);printf(\n);}if(j==0)trans(p3);}return;}/*转移函数，即将人转移过河*//*n=0*/voidmain(){structaim*p,*p1;intj,a,e,f;structa*flag;/*flag是用与记录头指针*/FILE*fpt;if((fpt=fopen(c:result.dat,w+))==0){printf(can'tcreatit\n);exit(0);}fp=fpt;system(cls);printf(问题描述：三个商人各带一个随从乘船过河，一只小船只能容纳X人，由他们自己划船。三个商人窃听到随从们密谋，在河的任意一岸上，只要随从的人数比上人多，就杀掉商人。但是如何乘船渡河的决策权在商人手里，商人们如何安排渡河计划确保自身安全？\n);printf(\n);p=(structaim*)malloc(sizeof(structaim));p-back=NULL;p-next=NULL;p-s2=0;p-m2=0;p-n=1;/*设立初始头指针*/printf(pleaseinputthetotalofpeopleontheboard\n);fprintf(fp,\n请输入船上的人数\n);scanf(%d,&n);fprintf(fp,\n%d\n,n);flag=&head;for(e=0;e=n;e++)for(f=0;f=n;f++)if(e+f0&&e+f=n){total++;jj=(structa*)malloc(sizeof(structa));jj-m=e;jj-s=f;flag-next=jj;jj-next=NULL;flag=jj;}/*********************************/printf(pleaseinputthetotalofmerchantandsalventasfollow:mechant,salvent;\n);fprintf(fp,\npleaseinputthetotalofmerchantandsalventasfollow:mechant,salvent;\n);scanf(%ld,%ld,&p-m1,&p-s1);fprintf(fp,\n%ld,%ld\n,p-m1,p-s1);/**********************************/k1=p-m1;k2=p-s1;trans(p);fclose(fpt);getch();}第一步：三个商人，三个随从的模型求解答案为：运行后的结果为：第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,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)到(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)第二步：四个商人三个随从，其结果为：第1种方法:4,3::0,03,2::1,14,2::0,12,2::2,13,2::1,12,1::2,22,2::2,10,2::4,10,3::4,00,1::4,21,1::3,20,0::4,3一共有12步完成第2种方法:4,3::0,03,2::1,14,2::0,12,2::2,13,2::1,12,1::2,22,2::2,10,2::4,10,3::4,00,1::4,22,1::2,21,0::3,31,1::3,20,0::4,3一共有14步完成第3种方法:4,3::0,03,2