数学建模实验一报告
实验题目:研究商人过河问题
一、实验目的:编写一个程序（可以是C,C+＋或Mathlab ）实现商人安全过河问题。
二、实验环境:Tur ｂo c 2．0、M ｉcro ｓo ｆt Ｖisual C ＋+ 6。0、Ma ｔla ｂ 6.0以上
三、实验要求：要求该程序不仅能找出一组安全过河的可行方案，还可以得到所有的安全过河可行方案。并且该程序具有一定的可扩展性，即不仅可以实现3个商人,3个随从的过河问题.还应能实现
n 个商人,ｎ个随从的过河问题以及n 个不同对象且每个对象有m 个元素问题(说明：对于3个商人，3个随从问题分别对应于n=2，m=3)的过河问题。从而给出课后习题5（n=4,ｍ=1)的全部安全过河方案。
四、实验步骤：
第一步：问题分析。这是一个多步决策过程，涉及到每一次船上的人员以及要考虑此岸和彼岸上剩余的商人数和随从数，在安全的条件下(两岸的随从数不比商人多）,经有限步使全体人员过河.
第二步：分析模型的构成.记第k 次渡河前此岸的商人数为k x ，随从数为k y , 2,1=k ,n y x k k 2,1,=,(具有可扩展性），将）（k k y x ,定义为状态,状态集合
成为允许状态集合（S ）。S=｛2,1;3,2,1,0,3;3,2,1,0,0|,======y x y x y x y x ）（｝记第k 次渡船的商人数为k u ，随从数为k v ，决策为),(k k v u ，安全渡河条件下，决策的集合为允许决策集合。允许决策集合记作D,所以D={2,1,0,,21|,=<+ ，因为k 为奇数时船从此岸驶向彼岸，k 为偶数时船由彼岸驶向此岸，所以状态k s 随决策k d 变化的规律是k k k k d s s )1(1-+=-，此式为状态转移律。制定安全渡河方案归结为如下的多步决策模型：求决策)2,1(n k D d k =∈，使状态S s k ∈按照转移律，由初始状态)3,3(1=s 经有限n 步到达)0,0(1=+n s 第三步：模型求解。 #incluｄe "ｓｔｄio.ｈ” #iｎcluｄe ”string．h＂ ＃inｃｌuｄe 〈memoｒy> ＃ｉｎclｕdｅ #iｎｃludｅ〈iostream〉 uｓing ｎａmｅｓｐace sｔｄ; #inｃlude "conio.h" FILE ＊fp;/*设立文件指针,以便将它用于其他函数中＊/ struct a{ lonｇ m，ｓ; ｓtruct a ＊ｎｅxｔ; }；/＊数组类型a:记录各种情况下船上的商人和仆人数，m:代表商人数 s：代表仆人数*／sｔrｕcｔ a *jj,head;/＊heａd为头指针的链表单元（船上的人数的各种情况的链表）＊／ int n，totａl=０,ｊs=0;/*ｔoｔal表示船上各种情况总数*/ stｒｕcｔ aim ｛ loｎg m1，s1,m２，s2； iｎt n； ｓtｒuct ａim *bａｃk，*ｎexｔ；};/*用于建立双向的指针链表,记入符合的情况，m1，s1表示要过岸的商人数和仆人数;ｍ2，s2表示过岸了的商人数和仆人数，n表示来回的次数＊/ ｉnt k1，ｋ2; vｏid freeit(struct aim *ｐ)｛ strucｔ aim ＊ｐ１＝p； p１=p-＞ｂack； free（p); if(p1!=NULL) p1－>next＝NULL; reｔｕrｎ； ｝/*释放该单元格，并将其上的单元格的nｅxt指针还原＊/ inｔ deterｍ(strucｔａiｍ＊p) { sｔrucｔａim *ｐ1＝p； iｆ（p－>s1〉k２）returｎ—1;/＊仆人数不能超过总仆人数＊/ if(p—>m1＞ｋ１)ｒｅtｕｒn -１；/*商人数不能超过总商人数＊/ iｆ（ｐ—＞s2＞k2）retｕrn －1；/＊对岸,同上＊／ if(ｐ—〉m2＞k1)reｔurｎ-1;/*对岸,同上＊/ ｉｆ（p-＞s1〈0)rｅturn —１;/＊仆人数不能为负*／ ｉｆ(p—〉s２<0)ｒeturn －1;/＊商人数不能为负＊/ iｆ(p—>ｍ1<0）retｕｒn -1；/＊对岸，同上＊/ if（ｐ-＞m2＜0）reｔｕrｎ－1；/＊对岸,同上＊/ if（p-〉ｍ1!＝０） if(p－>s1〉p—>m１)return -1; iｆ（p—＞m2!=0） if（p—>s２〉p->ｍ2）retuｒn -1；／＊两岸商人数均不能小于仆人数*／ whｉlｅ(p1!=NULL){ p1=p1－〉back; if(p1!=NＵLＬ） if(p1->n％2＝=p－>ｎ%２) if（ｐ1－>s1＝＝p->s1） if(p１—〉s2==p->s2） ｉｆ（p1—＞m1=＝p->m1） if（p1->m２=＝p-＞m2) retｕrn -1；｝/*用于解决重复，算法思想:即将每次算出的链表单元与以前的相比较，若重复,则表示出现循环＊/ iｆ（ｐ－〉s1=＝0＆＆p—>m1==0) if(p—＞ｎ%2==0)rｅtｕrn 1; elｓe return －1；/＊显然如果达到条件就说明ok了*/ returｎ０;｝/*判断函数＊/ ｉnｔ sｉgn(iｎt n)｛ if(n%2==0）ｒeturn -1； ｒeturn 1;｝/＊符号函数*/ void copyit(struct aim ＊ｐ3，struct ａiｍ＊p)｛ p3—>s1＝p-〉s1; ｐ3－>s2＝ｐ—>s2； p3—>m１＝p-〉m1; ｐ3—＞m2=ｐ-〉m2； p3—〉n=p-＞n+1； p3—>bacｋ＝ｐ； p３->next=ＮULL； p->neｘt=p３； }／*复制内容函数，将p中的内容写入p3所指向的链表单元中*/ vｏiｄｐrint（sｔｒuct aim ＊p３）{ strucｔａim ＊ｐ=ｐ３； ｊs++； while（p－>ｂacｋ){p=p—＞ｂack;} priｎtf（”\n第%d种方法:＼n"，js）; fpｒｉnｔｆ（fp，"\n第%d种方法：\n＂,jｓ）; int count＝0； ｗhiｌe(ｐ）{ printf(＂％lｄ,％ld:：%ld，％lｄ\ｔ＂，p-＞m1，p—＞ｓ1,p—〉ｍ2,ｐ－>s2）； fpriｎtf（ｆp,"％ld，％ｌd：：％lｄ,％ｌd＼ｔ”，p—〉m1,p—>s１，ｐ—>m2，ｐ—>ｓ2）； p=p－〉next； ｃｏuｎt＋+; ｝
