商人过河问题数学建模c语言

数学建模实验一报告实验题目：研究商人过河问题一、实验目的：编写一个程序（可以是C,C++或Mathlab ）实现商人安全过河问题。

二、实验环境：Turbo c 2.0、Microsoft Visual C++ 6.0、Matlab 6.0以上 三、实验要求：要求该程序不仅能找出一组安全过河的可行方案，还可以得到所有的安全过河可行方案。

并且该程序具有一定的可扩展性，即不仅可以实现3个商人，3个随从的过河问题。

还应能实现 n 个商人，n 个随从的过河问题以及n 个不同对象且每个对象有m 个元素问题(说明：对于3个商人，3个随从问题分别对应于n=2,m=3)的过河问题。

从而给出课后习题5（n=4,m=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|,=<+<v u v u v u ）（|1<u+v<2,u,v=0,1,2},因为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第三步：模型求解。

做业1、2：之阳早格格创做商人过河一、问题沉述问题一：4个商人戴着4个随从过河，过河的工具惟有一艘小船，只可共时载二部分过河，包罗划船的人.随从们稀约, 正在河的任一岸, 一朝随从的人数比商人多, 便杀人越货.乘船渡河的规划由商人决断.商人们何如才搞仄安过河?问题二：假若小船不妨容3人，请问最多不妨有几名商人各戴一名随从仄安过河.二、问题分解问题不妨瞅搞一个多步计划历程.每一步由此岸到此岸或者此岸到此岸船上的人员正在仄安的前提下(二岸的随从数没有比商人多),经有限步使部分人员过河.用状态变量表示某一岸的人员情景，计划变量表示船上的人员情况，不妨找出状态随计划变更的顺序.问题便变换为正在状态的允许变更范畴内（即仄安渡河条件），决定每一步的计划，达到仄安渡河的目标.三．问题假设1. 过河途中没有会出现没有成抗力的自然果素.2. 当随从人数大于商人数时，随从们没有会改变杀人的计划.3．船的品量很佳，正在多次谦载的情况下也能仄常运做.4. 随从会听从商人的调动.四、模型形成x(k)~第k 次渡河前此岸的商人数 x(k),y(k)=0,1,2,3,4; y(k)~第k 次渡河前此岸的随从数 k=1,2,…..s(k)=[ x(k), y(k)]~历程的状态 S~允许状态集中 S={(x,y)|x=0,y=0,1,2,3,4; x=4,y=0,1,2,3,4;x=y=1,2,3} u(k)~第k 次渡船上的商人数 u(k), v(k)=0,1,2;v(k)~ 第k 次渡船上的随从数 k=1,2…..d(k)=( u(k), v(k))~历程的计划 D~允许计划集中 D={u,v|u+v=1,2,u,v=0,1,2}状态果计划而改变s(k+1)=s(k)+(-1)^k*d(k)~状态变化律供d(k)ÎD(k=1,2,….n),使s(k)ÎS 并按变化律s(k+1)=s(k)+(-1)^k*d(k)由（4,4）到达（0,0）数教模型： k+1kS =S +k k D （-1）（1）'4k k x x += （2）'4k k y y +=（3）k.k x y ≥ （4）''k k x y ≥（5）模型分解：由（2）（3）（5）可得化简得概括（4）可得k k x y =战 {}(,)|0,0,1,2,3,4k k k k k S x y x y ===（6） 还要思量{}'(',')|'0,'0,1,2,3,4k k k k k S x y x y === （7）把（2）（3）戴进（7）可得化简得{}(,)|4,0,1,2,3,4k k k k k S x y x y === （8）概括（6）（7）（8）式可得谦脚条件的情况谦脚下式 {}(,)|0,4,0,1,2,3,4;k k k k k k k S x y x y x y ====（9） 所以咱们知讲谦脚条件的面如上图所示：面移动由{}(,)|4,0,1,2,3,4k k k k k S x y x y === （8）到达{}(,)|0,0,1,2,3,4k k k k k S x y x y ===（6）时，不妨认为完毕渡河.果为移动的格数小于等于2，惟有核心面（2，2）到（6）面战（8）面的距离为2，所以核心面（2,2）成为渡河的闭键面.当咱们移动到（2,2）面时，便无法举止下去.故4个商人，4个随从，船容量为2人时，无法仄安渡河. 对付于问题二，咱们不妨修坐模型为：k+1k S =S +k k D （-1）（10）'k k x x M += （11）'k k y y M += （12）k.k x y ≥（13）''k k x y ≥ （14）u(k), v(k)=0,1,2,3; （15）通过类似于问题一的步调不妨知讲：坐标上的闭键面是（3,3），最多不妨五名商人戴五名随从往日.需要决定五名商人戴五名随从的规划可止再决定六名商人戴六名随从的规划没有成止1、五名商人戴五名随从的情况：（1）最先没有成能有三名商人先过河，二名商人一名随从过河，一名商人二名随从过河（2）三个随从先过河（5,2），回去一个随从（5,3），往日二个随从（5,1）回去一个随从（5,2），再往日三个商人（2,2），回去一个商人一个随从（3,3），再往日三个商人（0,3），回去一个随从（0,4），往日三个随从（0,1），回去一个随从（0,2）再往日二个随从（0,0）综上可知：五名商人戴五名随从，小船不妨载三部分不妨过河2、六名商人戴六名随从的情况：（1）最先没有成能有三名商人先过河，二名商人一名随从过河，一名商人二名随从过河（2）三个随从先过河（6,3），回去一个随从（6,4），往日二个随从（6,2）回去一个随从（6,3），往日三个商人（3,3），此时二岸皆是（3,3），由坐标法分解知，那是最交近末面的临界面，然而是如果回去的时间一定是回去一个商人战一个随从，如果那一步可止，后里便举止没有去综上所述，六个商人戴六个随从，小船载三部分的情况下没有克没有及渡河分离1、2知，当小船最多载三部分的时间，最多五名商人各戴一个随从不妨过河.五、模型的考验取评介由少量人的过河问题推广到了更普遍人的过河问题，使得问题变得明白有顺序.六、参照文件[1]章胤，2014年燕山大教世界大教死数教修模竞赛训练ppt，2014年4月17日。

基于商人过河游戏的数学建模1提出问题文献[1]给出一个智力游戏：“三名商人各带一个随从渡河，一只小船只能容纳二人，由他们自己划行。

随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。

但是如何乘船的大权掌握在商人们手中。

商人怎样才能安全渡河呢？”此类智力问题当然可以通过一番思考，拼凑出一个可行的方案来。

文献[1]中通过图解法给出了解答，但是当商人数与随从数发生变化，船能容纳的人数不是二人时，图解法就会变得繁复而难以解决问题。

因此，将上述游戏改为n名商人各带一个随从过河，船每次至多运p个人，至少要有一个人划船，由他们自己划行。

随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。

但是如何乘船的大权掌握在商人们手中。

商人怎样才能安全渡河的问题。

除此之外，考虑了随着船载人数的增多，以及商人与仆人的对数增多到多少时，会影响商人的安全渡河的问题。

2问题分析由于这个虚拟的游戏已经理想化了，所以不必再作假设。

我们希望能找出这类问题的规律性，建立数学模型，并通过计算机编程进行求解。

安全渡河游戏可以看做是一个多步决策过程，分步优化，船由此岸驶向彼岸或由彼岸驶回此岸的每一步，都要对船上的商人和随从做出决策，在保证商人安全的前提下，在无限步内使全部人员过河。

用状态表示某一岸的人员状况，决策表示船上的人员情况，可以找出状态随决策变化的规律。

问题转化为在状态的允许范围内，确定每一步的决策，最后获取一个全局最优方案的决策方案，达到渡河的目标。

除此以外，我们还要找出，随着船载人数的增加，商人与仆人对数达到多少时，会影响到商人不能安全过河。

这里要对船载人数进行限制，因为船载人数过多时，此智力游戏会变得相当繁复，就会失去作为游戏的本来意义。

3模型构成记第k次渡河前此岸的商人数为，随从数为，，，。

将二维向量定义为过程的状态。

安全渡河条件下的状态集合称为允许状态集合，记作S。

当时，；当时，。

记第k次渡船上的商人数为uk，随从数为vk，将二维向量定义为决策。

数学建模题目：商仆过河问题组员：班级：指导老师：目录1.摘要 (3)2.问题的提出 (3)3.问题的分析 (4)4.模型的假设 (5)5.模型的建立与解 (5)6.模型的符号 (6)7.模型的解 (6)8.模型的图解 (8)9.关于C语言的程序算法 (10)10.模型的优缺点 (14)11.参考文献 (15)摘要：本文针对商人安全渡河问题，采用多步决策的过程建立数学模型，求解得到了在随从没杀人越货的情况下的渡河方案。

对于本题而言，在3(15)对商仆、船最大容量为2（8）人的情况下，首先定义了渡河前此岸的状态，并设安全渡河条件下的状态集合定义为允许状态集合，接着得到渡河方案的允许决策集合，然后得到状态随从渡河方案变化的规律。

利用c软件编译运行程序得到了一种商人安全渡河的方案，并输出了允许的状态向量和允许的决策向量。

关键词：船载量、允许状态向量、允许决策向量一．问题的提出仆人们密约，在河的任何一边，只要仆人的数量超过商人的数量，仆人就会联合起来将商人杀死并抢夺其财物，三名商人各带一个随从乘船渡河，一只小船只能容纳两人，由他们自己划行。

在河的任意一岸，一旦随从的人数比商人多，商人就有危险．但是如何乘船渡河的大权掌握在商人们手中。

商人们怎样才能安全渡河呢？同时，推广到十五名商人带十五名随从又如何？二．问题的分析1.安全渡河问题可以看成一个多步决策过程，船由此岸驶向彼岸或从彼岸驶回此岸，都要对船上的人员(商人随从各几人)作出决策。

2.状态向量：用二维坐标向量表示（商，仆）：0<=H<=3(11),0<=S<=3(11)，例如：（3，3，）（5，0）（6，4）等均成立3.允许向量：由题意可知，仆人数少于商人数被选定为允许向量。

4.运载向量：利用二维向量(m,n)表示船只上的商仆数量。

5.可行的运载向量：满足二维向量(m,n)，0<=n<=m<=3(15)。

枚举所有可能的算法：（1，0）（2，0）（3，0）（4，0）（5，0）（6，0）（7，0）（8，0）（1，1）（2，2）（3，3）（4，4）（2，1）（3，2）（4，3）6.可取用状态向量：利用穷举法表示状态，利用递归算法进行模型的建立与运算7.运载向量：使用二维向量进行表示（商，仆）：0<=商<=3(11),0<=仆<=3(11)8.该模型使用逻辑运算法则进行数学模型的建立三．模型的假设(1)每个商人和他的随从均会划船(2)只有一条船，且船只的承载数量为8人(3)船在划行的状况下不受任何的外力干扰(4)不存在任意几人不能同时坐船的情况四．模型的建立与解由题目可知，3(15)对商仆过河，船载量为2(8)人，现记第K次渡河前的商人数为Xk,仆人数为Yk,k=1,2,…,(2)8,再记一组二维向量Ak=(Xk,Yk)，Ak为给定时的状态量，可记做C的表达式为：C=｛(x,y)|x=0,y=0,1,…,(3)15=y=0,1,…,(3)15=y=0,1,…,(3)15再记第K次渡河时船上的商人数为uk,仆人数为vk,记二维向量Bk=(uk,vk),可知小船此时的运载为D，D的表达式为;D ={(u,v)|1<=u+v<=2(8),u,v=0,1,…,2(8)}由上题目中的题意可知第K+1次时的情况为E ：E=Ak+(-1)^k*Dk最终直到3(15)对商仆全部过河时完成问题五．模型的符号A 表示起始状态下商仆所在一岸B 表示末状态商仆所在一岸S 表示商仆的对数K 表示船最多的载人数C 渡河时的一侧岸边的商仆数D 小船运载的商仆数量E 第k次渡河是的商仆数量Ak 河岸一边的商人数Bk 河岸一边的仆人数Ck 河岸另一边的商人数Dk 河岸另一边的仆人数六．模型的解（1）利用程序框图来解决过河问题根据题意状态转移必须满足以下规则;(1). Z从1变0或0变1交替进行。

数学建模论文商仆过河问题摘要本文针对商人安全渡河的问题，采用多步决策的过程建立数学模型，求解得到了在随从没有杀人越货的情况下的渡河方案。

对于本题而言，在11名商人、11名随从、船的最大容量为6人的情况下，首先定义了渡河前此岸的状态，并设安全渡河条件下的状态集定义为允许状态集合，接着得到渡河方案的允许决策集合，然后得到状态随渡河方案变化的规律，利用matlab 7.0，win 7软件，编译运行程序得到了一种商人安全渡河的方案，并输出了允许的状态向量和允许的决策向量。

但是，本文不仅仅是为了拼凑出一个可行方案，而是希望能找到求解这类问题的规律性，并建立数学模型，用以解决更为广泛的问题。

一 .问题的提出当今社会每个人都想当王者，谁都想成为富翁，所以就在这个问题中仆人们也想成为商人。

仆人们密约，在河的任何一边，只要仆人的数量超过商人的数量，仆人就会联合起来将商人杀死并抢夺其财物，十一名商人各带一个随从乘船渡河，一只小船只能容纳六人，由他们自己划行。

在河的任意一岸，一旦随从的人数比商人多，商人就有危险．但是如何乘船渡河的大权掌握在商人们手中。

商人们怎样才能安全渡河呢？同时，推广到M名商人带M名随从又如何？二. 模型假设3 模型假设（1）每个商人和随从都会划船；（2）只有一条船，且每条船上最多只能乘坐六个人；（3）所有商人与随从之间没有矛盾，不会出现有人不愿意同坐一条船的现象；（4）船在渡河的过程中不受外界环境的影响。

三．问题符号说明3符号说明A初始状态下，商人和随从所在的一岸；B初始状态下，商人和随从欲到达的一岸；S 商仆对数K 船最多载人的数目四 .问题分析安全渡河问题可以看成一个多步决策过程。

每一步，即船由此岸驶向彼岸或从彼岸驶回此岸，都要对船上的人员(商人随从各几人)作出决策，在保证安全的前提下(两岸的商人数都不比随从数少)，在有限步内使人员全部过河。

用状态(变量)表示某一岸的人员状况，决策(变量)表示船上的人员状况，可以找出状态随决策变化的规律。

《数学建模实验》课程考试试题----商人安全过河数学建模与求解一．问题提出：4名商人带4名随从乘一条小船过河，小船每次自能承载至多两人。

随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货.乘船渡河的方案由商人决定，商人们如何才能安全渡河呢二．模型假设：商人和随从都会划船，天气很好，无大风大浪，且船的质量很好，可以保证很多次安全的运载商人和随从。

三．问题分析：商随过河问题可以视为一个多步决策过程，通过多次优化，最后获取一个全局最优的决策方案。

对于每一步，即船由此岸驶向彼岸或由彼岸驶向此岸，都要对船上的人员作出决策，在保证两岸的商人数不少于随从数的前提下，在有限步内使全部人员过河。

用状态变量表示某一岸的人员状况，决策变量表示船上的人员状况，可以找出状态随决策变化的规律，问题转化为在状态的允许变化范围内(即安全渡河条件)，确定每一步的决策，达到安全渡河的目标。

四．模型构成：k x ~第k 次渡河前此岸的商人数，k y ~第k 次渡河前此岸的随从数 k x , k y =0,1,2,3,4; k =1,2,… …k S =(k x , k y )~过程的状态,S ~ 允许状态集合，S={(x , y )| x =0, y =0,1,2,3,4; x =4 ,y =0,1,2,3,4; x =y =1,2,3} k u ~第k 次渡船上的商人数k v ~第k 次渡船上的随从数k d =(k u , k v )~决策，D={(u , v )| 21≤+≤v u ,k u , k v =0,1,2} ~允许决策集合 k =1,2,… …因为k 为奇数时船从此岸驶向彼岸，k 为偶数时船从彼岸驶向此岸，所以状态k S 随决策k d 的变化规律是1+k S =k S +k )1(-k d ~状态转移律求k d ∈D(k =1,2, …n), 使k S ∈S, 并按转移律由1S =(4,4)到达状态1+n S =(0,0)。

14对商仆过河问题题目有14名商人各带一名仆人要过河,但船最多能载4人。

商人已获得仆人的阴谋：在河的任意一岸，只要仆人数超过商人数，仆人会将商人杀死并窃取货物。

安排如何乘船的权利权利在商人手上，试为商人制定一个安全的过河方案。

一．摘要n对商仆过河,一只船最多载m人，船上和岸上的仆人数都不能多于商人数,否则商人有危险。

安排合理的渡河方案，保证商人能安全渡河。

（可利用向量，矩阵，图解等方法）。

二．问题提出：有14对商仆乘船过河,一只船最多载4人，由商人和仆人自己划船渡河，在河的任意一岸，一旦仆人数多于商人数，仆人就可将商人杀死,谋取利益，但是乘船渡河的主动权掌握在商人们手中，商人们如何安排渡河方案，才能安全渡河？三．问题分析商仆安全渡河问题可以视为一个多步决策过程，多步决策是指决策过程难以一次完成,而是多步优化，最后获取一个全局最优方案的决策方法。

对于每一步，即船由此岸驶向彼岸，或者船由彼岸驶向此岸的决策，不仅会影响到该过程的效果，而且还会影响到下一步的初始状态,从而对整个过程都会有影响。

所以，在每一次过河时，就不能只从这一次过河本身考虑，还要把它看成是整个过河过程中的一个部分。

在对船上的人员做决策时，要保证两岸的商人数不能少于仆人数,用最少的步伐是人员全部过河.应用状态向量和运载向量，找出状态随运载变化的规律，此问题就转化为状态在允许范围内（即安全渡河条件)，确定每一次该如何过河，从而达到渡河的目标。

现在我们都把它们数量化：即用数学语言来表示。

四．模型假设与符号假设（一）模型假设商人和仆人都会划船，天气很好，无大风大浪，船的质量很好，船桨足够很多次的运载商人和仆人。

（二）符号假设设（x，y）是状态向量，表示任一岸的商人和仆人数,且x，y分别要大于等于0，小于等于M。

1.设(m,n)是运载向量，表示运载的商人数和仆人数，0<=m<=N，0<=n<=N，0〈=m+n〈=N。

2.设用s表示所有的可取状态向量的集合。

数学建模案例作业作业1 商人过河问题三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行（六个人都会划船）。

随从们密谋，无论何时，一旦随从的人数比商人多，就杀人越货。

但是如何乘船渡河的决定权掌握在商人手中。

商人们怎样才能安全渡河？示意图如下： 随从：商人： 一、状态变量一次决策),(k k k y x S = 3,2,1=k 表示第k 次渡河时，此岸的商人数，随从数. 最初 )3,3(0=S 且为整数）3,0(≤≤k k y x)}0,0(),1,0(),2,0(),3,0(),0,1(),1,1(),2,1(),3,1(),0,2(),1,2(),2,2(),3,2(),0,3(),1,3(),2,3(),3,3{(=S要安全过河，需保证彼岸此岸都安全，及随从数不能大于商人数，所以安全的情况有10种，即)}0,0(),1,0(),2,0(),3,0(),1,1(),2,2(),0,3(),1,3(),2,3(),3,3{(=S ② 二、决策变量设),(k k k v u d =2,0(≤≤k k v u 且)21≤+≤k k v u 表示第k 次渡河时，船上的商人数和随从数 )}1,0(),0,1(),2,0(),1,1(),0,2{(=D与状态变量相结合，安全的情况有三种，即 )}1,0(),2,0(),1,1{((=D ③ 三、状态转移方程奇数次（此案到彼岸）k k k d S S -=+1 偶数次（彼岸到此案）k k k d S S +=+1 即k k k k d S S )1(1-+=+ ① 数学建模：由①确定的转移方程下，经过n 次决策，将初始状态转移到最终状态)0,0(=n S . 每次的决策取自③式，每次到达的状态在②中. 图解法：①从右上角移到左下角，每次最多移两步；②奇数次渡河往左下方，偶数次渡河往右下方。

建立平面直角坐标系如图：n S 过河方案：从A 点)3,3(0=S 出发到D 点)0,0(=n S 结束① 小船一次最多能载两人，所以每次最多移动两个格子② 由此岸即彼岸时人员减少，即奇数遍时向左下方行走；有彼岸及此岸时人员增加，即偶数遍时向右上方行走。

#include<stdio.h>#include<conio.h>#include<stdlib.h>struct Node{int x;int y;int state;struct Node *next;};typedef struct Node state;typedef state *link;link pt1=NULL;link pt2=NULL;int a1,b1;int a2,b2;/*栈中每个数据都分为，状态*/void Push(int a,int b,int n){link newNode;newNode=(link)malloc(sizeof(state)); newNode-> x=a;newNode-> y=b;newNode-> state=n;newNode-> next=NULL;if(pt1==NULL){pt1=newNode;pt2=newNode;}else{pt2-> next=newNode;pt2=newNode;}}void Pop() /*弹栈*/{link pointer;if(pt1==pt2){free(pt1);pt1=NULL;pt2=NULL;}pointer=pt1;while(pointer-> next!=pt2)pointer=pointer-> next;free(pt2);pt2=pointer;pt2-> next=NULL;}int origin(int a,int b,int n)/*比较输入的数据和栈中是否有重复的*/ {link pointer;if(pt1==NULL)return 1;else{pointer=pt1;while(pointer!=NULL){if(pointer-> x==a&&pointer-> y==b&&pointer-> state==n) return 0;pointer=pointer-> next;}return 1;}}int judge(int a,int b,int c,int d,int n)/*判断状态是否可行*/{if(origin(a,b,n)==0) return 0;if(a>=0&&b>=0&&a<=3&&b<=3&&c>=0&&d>=0&&c<=3&&d<=3&&a+c==3 &&b+d==3){switch(n){case 1:{if(a==3){Push(a,b,n);return 1;}else if(a==0){Push(a,b,n);return 1;}else if(a==b){Push(a,b,n);return 1;}else return 0;}case 0:{if(a==3){Push(a,b,n);return 1;}else if(a==0){Push(a,b,n);return 1;}else if(a>=b){Push(a,b,n);return 1;}else return 0;}}}else return 0;}int Duhe(int a,int b,int n) /*递归*/ {if(a==0&&b==0) return 1;if(n==0) /*判断状态时，商人和随从状态是否符合要求*/ {if(judge(a-1,b-1,4-a,4-b,1)){if(Duhe(a-1,b-1,1)==1)return 1;}if(judge(a,b-2,3-a,5-b,1)){if(Duhe(a,b-2,1)==1)return 1;}if(judge(a-2,b,5-a,3-b,1)){if(Duhe(a-2,b,1)==1)return 1;}if(judge(a-1,b,4-a,3-b,1)){if(Duhe(a-1,b,1)==1)return 1;}if(judge(a,b-1,3-a,4-b,1)){if(Duhe(a,b-1,1)==1)return 1;}else{Pop();return 0;}if(n==1) /*判断状态时，商人和随从状态是否符合要求*/ {if(judge(a+1,b+1,2-a,2-b,0)){if(Duhe(a+1,b+1,0)==1)return 1;}if(judge(a,b+2,3-a,1-b,0)){if(Duhe(a,b+2,0)==1)return 1;}if(judge(a+2,b,1-a,3-b,0)){if(Duhe(a+2,b,0)==1)return 1;}if(judge(a+1,b,2-a,3-b,0)){if(Duhe(a+1,b,0)==1)return 1;}if(judge(a,b+1,3-a,2-b,0)){if(Duhe(a,b+1,0)==1)return 1;}else{Pop();return 0;}}return 0;}main(){link pointer;Push(3,3,0);Duhe(3,3,0);pointer=pt1;printf("第一个数是此岸商人数量，第二个数是此岸随从数量,0表示船在此岸，代表船在彼岸:\n");while(pointer!=NULL){printf("%d,%d——%d\n",pointer-> x,pointer-> y,pointer-> state);pointer=pointer-> next;}}。

要求该程序不仅能找出一组安全过河的可行方案，还可以得到所有的安全过河可行方案。

并且该程序具有一定的可扩展性，即不仅可以实现3个商人，3个随从的过河问题。

还应能实现n个商人，n个随从的过河问题以及n个不同对象且每个对象有m个元素问题(说明：对于3个商人，3个随从问题分别对应于n=2,m=3)的过河问题。

从而给出课后习题5（n=4,m=1）的全部安全过河方案。

#include"stdio.h"#include"iostream.h"bool PsSet[4][4], turn;//PsSet是允许状态集turn表示由此岸到彼岸或由彼岸到此岸int PdSet[5][2]={{0,1},{0,2},{2,0},{1,0},{1,1}};//PdSet表示允许决策集int Record[12][2],pos=1;//Record记录已走过的状态pos当前位置bool Check[12];//Check记录走过状态的turn值int num=0;//初始化PsSetvoid InitPsSet(){for(int i=0;i<4;i++)for(int j=0;j<4;j++)if(i==0||i==3||i==j);else PsSet[i][j]=true;}//检验该状态是否被用过int IsRepeat(int px,int py,bool turn){ for(int i=0;i<pos;i++)if(px==Record[i][0]&&py==Record[i][1]&&turn==Check[i])return true;return false;}//过河子函数void CrossRiver(int px,int py){ int i;if(px==0&&py==0){ num++;printf("第%d 种方案",num);printf("\n");for(i=0;i<pos;i++){ printf("(%d,%d) 到(%d,%d)",Record[i][0],Record[i][1],3-Record[i][0],3-Record[i][1]);printf("\n");}}else if(turn==false){ for(i=0;i<5;i++){px=px-PdSet[i][0];py=py-PdSet[i][1];if(px<0||py<0||px>3||py>3||PsSet[px][py]||IsRepeat(px,py,turn)) { px=px+PdSet[i][0];py=py+PdSet[i][1];continue;}Record[pos][0]=px;Record[pos][1]=py;Check[pos]=turn;pos++;turn=!turn;CrossRiver(px,py);pos--;turn=!turn;px=px+PdSet[i][0];py=py+PdSet[i][1];}}else {for(i=0;i<5;i++){px=px+PdSet[i][0];py=py+PdSet[i][1];if(px<0||py<0||px>3||py>3||PsSet[px][py]||IsRepeat(px,py,turn)) { px=px-PdSet[i][0];py=py-PdSet[i][1];continue;}Record[pos][0]=px;Record[pos][1]=py;Check[pos]=turn;pos++;turn=!turn;CrossRiver(px,py);pos--;turn=!turn;px=px-PdSet[i][0];py=py-PdSet[i][1];}}}//主函数void main(){int px=3,py=3;InitPsSet();Check[0]=true;Record[0][0]=3;Record[0][1]=3;CrossRiver(px,py);}#include"stdio.h"#include"iostream.h"bool PsSet[2][2][2][2], turn;//PsSet是允许状态集turn表示由此岸到彼岸或由彼岸到此岸int PdSet[4][4]={{1,1,0,0},{1,0,0,0},{1,0,1,0},{1,0,0,1}};//PdSet表示允许决策集int Record[8][4],pos=1;//Record记录已走过的状态pos当前位置bool Check[8];//Check记录走过状态的turn值int num=0;//初始化PsSetvoid InitPsSet(){PsSet[0][1][1][0]=true;PsSet[0][0][1][1]=true;PsSet[0][1][1][1]=true; PsSet[1][0][0][0]=true;PsSet[1][0][0][1]=true;PsSet[1][1][0][0]=true; }//检验该状态是否被用过int IsRepeat(int px,int py,int pu,int pv,bool turn){ for(int i=0;i<pos;i++)if(px==Record[i][0]&&py==Record[i][1]&&pu==Record[i][2]&&pv==Record[i ][3]&&turn==Check[i])return true;return false;}//过河子函数void CrossRiver(int px,int py,int pu,int pv){ int i;if(px==0&&py==0&&pu==0&&pv==0){ num++;printf("第%d 种方案",num);printf("\n");for(i=0;i<pos;i++){ printf("(%d,%d,%d,%d) 到(%d,%d,%d,%d)",Record[i][0],Record[i][1],Record[i][2],Record[i][3],1-Record[i][0],1-Record[i][1],1-Record[i][2],1-Record[i][3]);printf("\n");}}else if(turn==false){ for(i=0;i<4;i++){px=px-PdSet[i][0];py=py-PdSet[i][1];pu=pu-PdSet[i][2];pv=pv-PdSet[i][3];if(px<0||py<0||pu<0||pv<0||px>1||py>1||pu>1||pv>1||PsSet[px][py][pu][ pv]||IsRepeat(px,py,pu,pv,turn)){ px=px+PdSet[i][0];py=py+PdSet[i][1];pu=pu+PdSet[i][2];pv=pv+PdSet[i][3];continue;}Record[pos][0]=px;Record[pos][1]=py;Record[pos][2]=pu;Record[pos][3]=pv;Check[pos]=turn;pos++;turn=!turn;CrossRiver(px,py,pu,pv);pos--;turn=!turn;px=px+PdSet[i][0];py=py+PdSet[i][1];pu=pu+PdSet[i][2];pv=pv+PdSet[i][3];}}else {for(i=0;i<4;i++){ px=px+PdSet[i][0];py=py+PdSet[i][1];pu=pu+PdSet[i][2];pv=pv+PdSet[i][3];if(px<0||py<0||pu<0||pv<0||px>1||py>1||pu>1||pv>1||PsSet[px][py][pu][ pv]||IsRepeat(px,py,pu,pv,turn)){ px=px-PdSet[i][0];py=py-PdSet[i][1];pu=pu-PdSet[i][2];pv=pv-PdSet[i][3];continue;}Record[pos][0]=px; Record[pos][1]=py;Record[pos][2]=pu; Record[pos][3]=pv;Check[pos]=turn; pos++;turn=!turn;CrossRiver(px,py,pu,pv);pos--; turn=!turn; px=px-PdSet[i][0];py=py-PdSet[i][1]; pu=pu-PdSet[i][2]; pv=pv-PdSet[i][3];}}}//主函数void main(){int px=1,py=1,pu=1,pv=1;InitPsSet();Check[0]=true;Record[0][0]=1;Record[0][1]=1;Record[0][2]=1;Record[0][3]=1;CrossRiver(px,py,pu,pv);}#include"stdio.h"#include"iostream.h"bool PsSet[5][5], turn;//PsSet是允许状态集turn表示由此岸到彼岸或由彼岸到此岸int PdSet[5][2]={{0,1},{0,2},{2,0},{1,0},{1,1}};//PdSet表示允许决策集int Record[20][2],pos=1;//Record记录已走过的状态pos当前位置bool Check[20];//Check记录走过状态的turn值int num=0;//初始化PsSetvoid InitPsSet(){for(int i=0;i<5;i++)for(int j=0;j<5;j++)if(i==0||i==4||i==j);else PsSet[i][j]=true;}//检验该状态是否被用过int IsRepeat(int px,int py,bool turn){ for(int i=0;i<pos;i++)if(px==Record[i][0]&&py==Record[i][1]&&turn==Check[i])return true;return false;}//过河子函数void CrossRiver(int px,int py){ int i;if(px==0&&py==0){ num++;printf("第%d 种方案",num);printf("\n");for(i=0;i<pos;i++){ printf("(%d,%d) 到(%d,%d)",Record[i][0],Record[i][1],4-Record[i][0],4-Record[i][1]); printf("\n");}}else if(turn==false){ for(i=0;i<5;i++){px=px-PdSet[i][0];py=py-PdSet[i][1];if(px<0||py<0||px>4||py>4||PsSet[px][py]||IsRepeat(px,py,turn)) { px=px+PdSet[i][0];py=py+PdSet[i][1];continue;}Record[pos][0]=px;Record[pos][1]=py;Check[pos]=turn;pos++;turn=!turn;CrossRiver(px,py);pos--;turn=!turn;px=px+PdSet[i][0];py=py+PdSet[i][1];}}else {for(i=0;i<5;i++){px=px+PdSet[i][0];py=py+PdSet[i][1];if(px<0||py<0||px>4||py>4||PsSet[px][py]||IsRepeat(px,py,turn)) { px=px-PdSet[i][0];py=py-PdSet[i][1];continue;}Record[pos][0]=px;Record[pos][1]=py;Check[pos]=turn;pos++;turn=!turn;CrossRiver(px,py);pos--;turn=!turn;px=px-PdSet[i][0];py=py-PdSet[i][1];}}}//主函数void main(){int px=4,py=4;InitPsSet();Check[0]=true;Record[0][0]=4; Record[0][1]=4;CrossRiver(px,py);}。

数学建模商人过河(hjh)
问题
随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货.
乘船渡河的方案由商人决定.商人们怎样才能安全过河?
分析问题
（1）,数据及其关系？（2）如何存储？（3）过程中数据上的操作？
（4）操作过程中需借助什么结构实现？
解答
（1）数据：河两岸的商人数x∈（0，3）和随从人数y∈（0，3）
关系：线性关系
（2）存储：用二维数组来实现。

（3）操作：前进（过河）、后退（返回）
（4）操作过程中需借助栈结构实现
具体分析
此岸商人数与随从人数为C【x】【y】，彼岸商人数与随从人数为B【3-x】【3-y】，C与B数组中x必须大于等于y。

C与B数组中，各个数组中每相邻两个二维数组|x+y|之差不得超过2。

其中过河途中船上人数用数组A表示A【x1】【y1】，返回途中船上人数A【x2】【y2】。

x1，x2，y1，y2=0，1，2。

x1+y1=1或2；y2+x2=1或2。

从此岸来考察，要从最开始的C【3】【3】变到C【0】【0】。

1，C【3】【3】→C【3】【1】，C【3】【1】→C【3】【2】；
2，C【3】【2】→C【3】【0】，C【3】【0】→C【3】【1】；3，C【3】【1】→C【1】【1】，C【1】【1】→C【2】【2】；4，C【2】【2】→C【0】【2】，C【0】【2】→C【0】【3】；5，C【0】【3】→C【0】【1】，C【0】【1】→C【0】【2】；6，C【0】【2】→C【0】【0】。

操作过程中需借助栈结构实现，具体如下图所示：
此岸人数已经全部转移到彼岸，任务圆满完成，商人们安全过河。

计算机技术基础课程设计C语言设计报告题目：过河问题学院：化学工程学院专业：制药工程班级：050607姓名：孙继楠指导教师:顾煜新设计日期：2007年1月10日一、选题背景：该游戏是我由一个数学建模题——“安全过河问题”而构思的。

有三个商人带者三个随从和货物过河，船每次最多只能载两个人，要求保证在过河期间商人的人数要大于或等于随从的人数，否则随从杀人抢货。

构思:用两个数组来表示两岸的商人和随从,其中'A'表示商人,'B'表示随从,数组a 表示此岸,数组b表示彼岸;通过输入过河的人数,来改变两个数组中的'A'和'B'的个数,在用文本输出两岸的情况.二．设计思路流程本程序主要是文本的输出，及通过键盘。

首先在程序的开始处通过语句头文件开始。

利用window()输出窗口。

通过for语句来实现数据输入，并通过if else语句来判断商人与随从是否安全过河，最后用输出语句输出结果。

三．主要解决问题的方法及技术关键用if else语句判断商人是否成功过河，要求无论在哪岸商人的个数必须大于随丛的个数，否则商人被杀。

四、程序流程图：图1 安全过河流程图五．程序清单#include <stdio.h>#include <conio.h>#include <string.h>void helpf(){clrscr();gotoxy(6,3);printf("gai you xi shi you yi ge shu xue jian mo ti--an quan guo he wen ti er gou \n\n");printf("si de. you san ge shang ren dai zhe san ge sui cong he huo wu guo he,\n");printf("chuan mei ci zui duo zhi neng zai liang ge ren,yao qiu bao zheng zai guo he\n") ;printf("qi jian \n\n shang ren de ren shu yao da yu huo deng yu sui cong de ren shu,\n");printf("fou ze sui cong sha ren qiang huo.\n\n you xi gui ze shi zhe yang si de:\n\n1) shu ru\n");printf("guo he de ren shu ;\n\n2) fei fa shu ru an an le tui chu chu li.\n");printf("zhu jun hao yun!\n");printf("\t\t\t zuo zhe: sun ji nan\n");printf("\t\t\tE-mail: sun ji nan2006@");}char a[6];char b[6];void printcase(char a[],char b[]) {int i,j,xa,xb,x0,ya,yb,y0;xa=xb=x0=ya=yb=y0=0;gotoxy(1,4);printf("ci an\t\t bi an\n"); for(i=0;i<6;i++){if(a[i]=='A')xa++;else if (a[i]=='B')xb++;else if(a[i]=='0')x0++;}for(i=1;i<=xa;i++)printf("shang ren ");printf("\n");for(i=1;i<=xb;i++)printf("sui cong ");printf("\n");for(i=1;i<=x0;i++)printf(" ");printf("\n");for(j=0;j<6;j++){if(b[j]=='A')ya++;else if(b[j]=='B')yb++;else if(b[j]=='0')y0++;}gotoxy(25,5);for(j=1;j<=ya;j++)printf("shang ren ");gotoxy(25,6);for(j=1;j<=yb;j++)printf("sui cong "); . gotoxy(25,7);for(j=1;j<=y0;j++)printf(" ");if(xa==0 && xb==0 && ya==3 && yb==3){printf("\n\n ni yi cheng gong bang zhu shang ren an quan guo he !"); exit(0);}}void main(){int i,x,y,key,ca,cb,j,aA,aB,bA,bB;helpf();getch();clrscr();window(1,1,25,80);textbackground(1);textcolor(14);clrscr();for(i=0;i<3;i++)a[i]='A';for(i=3;i<6;i++)a[i]='B';for(i=0;i<6;i++)b[i]='0';printcase(a,b);while(1){gotoxy(20,10);printf("shu ru qu bi an shang ren de ren shu ："); scanf("%d",&x);gotoxy(22,10);printf("shu ru qu bi an sui cong de ren shu ："); scanf("%d",&y);for(ca=0,cb=0,i=0;i<6;i++){if(a[i]=='A')ca++;else if(a[i]=='B')cb++;}if(x<0 || x>ca || y<0 || y>cb || x+y<1 ||x+y>2){printf("shu ru you wu ！！");exit (0);}for(i=1;i<=x;i++) {for(j=0;j<6;j++)if(a[j]=='A'){a[j]='0';break;}}for(i=1;i<=x;i++){for(j=0;j<6;j++)if(b[j]=='0'){b[j]='A';break;}}for(i=1;i<=y;i++) { for(j=0;j<6;j++)if(a[j]=='B'){a[j]='0';break;}}for(i=1;i<=y;i++){for(j=0;j<6;j++)if(b[j]=='0'){b[j]='B';break;}}for(aA=0,aB=0,i=0;i<6;i++) {if(a[i]=='A')aA++;else if(a[i]=='B')aB++;}for(bA=0,bB=0,i=0;i<6;i++) {if(b[i]=='A')bA++;else if(b[i]=='B')bB++;}if((aA==3) ||(bA==3) || (aA==aB) || (bA==bB)){clrscr();printcase(a,b);}else{clrscr();printf(" shang ren bei sha , zai lai yi ci ba !!!!\n\n\n\n");printcase(a,b);getch();for(i=0;i<3;i++)a[i]='A';for(i=3;i<6;i++)a[i]='B';for(i=0;i<6;i++)b[i]='0';clrscr();printcase(a,b);continue;}gotoxy(20,10);printf("shu ru hui ci an shang ren de ren shu ："); scanf("%d",&x);gotoxy(22,10);printf("shu ru hui ci an sui cong de ren shu ："); scanf("%d",&y);for(ca=0,cb=0,i=0;i<6;i++){if(b[i]=='A')ca++;else if(b[i]=='B')cb++;}if(x<0 || x>ca || y<0 || y>cb || x+y<1 || x+y>2){printf("shu ru you wu ！！");exit (0);}for(i=1;i<=x;i++) {for(j=0;j<6;j++)if(b[j]=='A'){b[j]='0';break;}}for(i=1;i<=x;i++) {for(j=0;j<6;j++)if(a[j]=='0'){a[j]='A';break;}}for(i=1;i<=y;i++){for(j=0;j<6;j++)if(b[j]=='B'){b[j]='0';break;}}for(i=1;i<=y;i++){for(j=0;j<6;j++)if(a[j]=='0'){a[j]='B';break;}}for(aA=0,aB=0,i=0;i<6;i++) {if(a[i]=='A')aA++;else if(a[i]=='B')aB++;}for(bA=0,bB=0,i=0;i<6;i++) {if(b[i]=='A')bA++;else if(b[i]=='B')bB++;}if((aA==3) ||(bA==3) || (aA==aB) || (bA==bB)){clrscr();printcase(a,b);}else{clrscr();printf(" shang ren bei sha ,zai lai yi ci ba !!!!\n\n\n\n");printcase(a,b);getch();for(i=0;i<3;i++)a[i]='A';for(i=3;i<6;i++)a[i]='B';for(i=0;i<6;i++)b[i]='0';clrscr();printcase(a,b);continue;}}}六．设计结果说明程序比较简单，都是比较简单的函数，使用方便，易懂，占用空间小。

编程完成商人过河游戏：有三个商人带着三个随从和货物过河，船每次最多只能载两个人，由他们自己划行，并且如何乘船渡河的大权由商人掌握。

要求保证在过河期间的任一岸上商人的人数要大于或等于随从的人数，否则随从会杀死商人抢走货物。

设计一个符合上述要求的商人过河的游戏#include<stdio.h>#include<stdlib.h>void print() //游戏屏幕{system("cls");printf("****************************************************************\n");printf("* *\n");printf("* ^_^welcome to the game!^_^ *\n");printf("* *\n");printf("* Game rules: *\n");printf("* 3 men and 3 rateiners and goods to pass the river,the boat*\n");printf("* carrys 2 persons each time.In passing the river,at any bank *\n");printf("* number of men must be more than the number the rateiners , *\n");printf("* or the rateiners will kill the men and take the goods. *\n");printf("* Game operations: 1.Input the number of men and rateiners *\n");printf("* in turn. *\n");printf("* 2.Input error keys,the game will restart. *\n");printf("****************************************************************\n");}void began() //游戏开始界面{char ch;printf("\n\n");printf(" Press any key to start the game.(Q key to quit)...");scanf("%c",&ch);if(ch=='Q'||ch=='q')exit(0);}void xianshi(char *a,char *b) // 显示过河的状态{int ax=0,ay=0,bx=0,by=0; //ax，ay,bx,by分别表示岸两边的商人和仆人数int i,j;for(i=0;i<6;i++){if(*(a+i)=='M')ax++;if(*(a+i)=='S')ay++;if(*(b+i)=='M')bx++;if(*(b+i)=='S')by++;}printf("This bank\n");for(i=1;i<=ax;i++)printf("man ");printf("\n");for(i=1;i<=ay;i++)printf("rateiner ");printf("\n\n");printf("That bank\n");for(i=1;i<=bx;i++)printf("man ");printf("\n");for(i=1;i<=by;i++)printf("rateiner ");printf("\n\n");if(ax==0&&ay==0&&bx==3&&by==3){printf("congrarulation! You have finished the game!\n"); // 游戏成功提示exit(0);}}void pan(int ax,int ay,int bx,int by) // 判断过河时，岸两边的商人是否安全，即商人数不少于仆人数{if(ax<ay||bx<by){printf("The men are killed Game Over!\n");exit(0);}}main(){int i,x=0,y=0; //x,y分别表示每次过河时坐船的商人数和仆人数int ax=3,ay=3,bx=0,by=0; // ax，ay,bx,by分别表示岸两边的商人和仆人数char a[6],b[6]; //定义两个数组分别存放岸两边的人数system("color 1E"); //定义背景和字体颜色print();began();print();for(i=0;i<3;i++) //M代表商人，S代表仆人a[i]='M';for(i=3;i<6;i++)a[i]='S';for(i=0;i<6;i++)b[i]='0'; //游戏开始前的状态，即三个商人和三个仆人在等待过河xianshi(a,b); //开始前的状态do //用do-while循环{printf("Please input the number of man to that bank:");scanf("%d",&x);while(x<0||x>2) //判定过河的人数{printf("The wrong number,please input again:");scanf("%d",&x);}print();63xianshi(a,b);printf("Please input the number of rateiner to that bank:");scanf("%d",&y); //判定过河的人数while(y<0||y>2||x+y>2){printf("The wrong number,please input again:");scanf("%d",&y);}ax=ax-x;ay=ay-y;pan(ax,ay,bx,by);bx=bx+x;by=by+y; //一次过河后岸两边商人和仆人的人数print();for(i=0;i<6;i++) //数组设置为空{a[i]='0';b[i]='0';}for(i=0;i<ax;i++)a[i]='M';for(i=3;i<3+ay;i++)a[i]='S';for(i=0;i<bx;i++)b[i]='M';for(i=3;i<3+by;i++)b[i]='S';xianshi(a,b);printf("Please input the number of the man back to this bank:");scanf("%d",&x);while(x<0||x>2){printf("The wrong number,please input again:");scanf("%d",&x);}print();xianshi(a,b);printf("Please input the number of rateiner back to this bank:");scanf("%d",&y);while(y<0||y>2||x+y>2){printf("The wrong number,please input again:");scanf("%d",&y);}bx=bx-x;by=by-y;pan(ax,ay,bx,by);ax=ax+x;ay=ay+y;for(i=0;i<6;i++){a[i]='0';b[i]='0';}for(i=0;i<ax;i++) a[i]='M';for(i=3;i<3+ay;i++) a[i]='S';for(i=0;i<bx;i++) b[i]='M';for(i=3;i<3+by;i++) b[i]='S';print();xianshi(a,b);}while(1);}。

功课1.2：商人过河一、问题重述问题一：4个商人带着4个侍从过河,过河的对象只有一艘划子,只能同时载两小我过河,包含荡舟的人.侍从们密约, 在河的任一岸, 一旦侍从的人数比商人多, 就杀人越货.乘船渡河的筹划由商人决议.商人们如何才干安然过河?问题二：假如划子可以容3人,请问最多可以有几名商人各带一名侍从安然过河.二.问题剖析问题可以看做一个多步决议计划进程.每一步由此岸到此岸或此岸到此岸船上的人员在安然的前提下(两岸的侍从数不比商人多),经有限步使全部人员过河.用状况变量暗示某一岸的人员状况,决议计划变量暗示船上的人员情形,可以找出状况随决议计划变更的纪律.问题就转换为在状况的许可变更规模内（即安然渡河前提）,肯定每一步的决议计划,达到安然渡河的目的.三．问题假设1. 过河途中不会消失不成抗力的天然身分.2. 当侍从人数大于商人数时,侍从们不会转变杀人的筹划.3．船的质量很好,在多次满载的情形下也能正常运作.4. 侍从会服从商人的调剂.四.模子组成x(k)~第k 次渡河前此岸的商人数 x(k),y(k)=0,1,2,3,4; y(k)~第k 次渡河前此岸的侍从数 k=1,2,…..s(k)=[ x(k), y(k)]~进程的状况 S~许可状况聚集 S={(x,y)|x=0,y=0,1,2,3,4; x=4,y=0,1,2,3,4;x=y=1,2,3} u(k)~第k 次渡船上的商人数 u(k), v(k)=0,1,2; v(k)~ 第k 次渡船上的侍从数 k=1,2…..d(k)=( u(k), v(k))~进程的决议计划 D~许可决议计划聚集D={u,v|u+v=1,2,u,v=0,1,2}状况因决议计划而转变s(k+1)=s(k)+(-1)^k*d(k)~状况转移律 求d(k)ÎD(k=1,2,….n),使s(k)ÎS 并按转移律s(k+1)=s(k)+(-1)^k*d(k)由（4,4）到达（0,0）数学模子： k+1k S =S +k k D （-1）（1）'4k k x x += （2）'4k k y y +=（3）k.k x y ≥ （4）''k k x y ≥（5）模子剖析：由（2）（3）（5）可得化简得分解（4）可得k k x y =和 {}(,)|0,0,1,2,3,4k k k k k S x y x y ===（6）还要斟酌{}'(',')|'0,'0,1,2,3,4k k k k k S x y x y === （7）把（2）（3）带入（7）可得化简得{}(,)|4,0,1,2,3,4k k k k k S x y x y === （8）分解（6）（7）（8）式可得知足前提的情形知足下式{}(,)|0,4,0,1,2,3,4;k k k k k k k S x y x y x y ====（9） 所以我们知道知足前提的点如上图所示：点移动由{}(,)|4,0,1,2,3,4k k k k k S x y x y === （8）到达{}(,)|0,0,1,2,3,4k k k k k S x y x y ===（6）时,可以以为完成渡河.因为移动的格数小于等于2,只有中间点（2,2）到（6）点和（8）点的距离为2,所以中间点（2,2）成为渡河的症结点.当我们移动到（2,2）点时,就无法进行下去.故4个商人,4个侍从,船容量为2人时,无法安然渡河. 对于问题二,我们可以树立模子为：k+1k S =S +k k D （-1）（10）'k k x x M+= （11） 'k k y y M += （12）k.k x y ≥（13）''k k x y ≥ （14） u(k), v(k)=0,1,2,3; （15）经由过程相似于问题一的步调可以知道：坐标上的症结点是（3,3）,最多可以五名商人带五名侍从曩昔.须要肯定五名商人带五名侍从的筹划可行再肯定六名商人带六名侍从的筹划不成行1.五名商人带五名侍从的情形：（1）起首不成能有三名商人先过河,两名商人一名侍从过河,一名商人两名侍从过河（2）三个侍从先过河（5,2）,回来一个侍从（5,3）,曩昔两个侍从（5,1）回来一个侍从（5,2）,再曩昔三个商人（2,2）,回来一个商人一个侍从（3,3）,再曩昔三个商人（0,3）,回来一个侍从（0,4）,曩昔三个侍从（0,1）,回来一个侍从（0,2）再曩昔两个侍从（0,0）综上可知：五名商人带五名侍从,划子可以载三小我可以过河 2.六名商人带六名侍从的情形：（1）起首不成能有三名商人先过河,两名商人一名侍从过河,一名商人两名侍从过河（2）三个侍从先过河（6,3）,回来一个侍从（6,4）,曩昔两个侍从（6,2）回来一个侍从（6,3）,曩昔三个商人（3,3）,此时两岸都是（3,3）,由坐标法剖析知,这是最接近终点的临界点,但是假如回来的时刻必定是回来一个商人和一个侍从,假如这一步可行,后面就进行不去综上所述,六个商人带六个侍从,划子载三小我的情形下不克不及渡河联合 1.2知,当划子最多载三小我的时刻,最多五名商人各带一个侍从可以过河.五、模子的磨练与评价由少数人的过河问题推广到了更多半人的过河问题,使得问题变得清楚明了有纪律.六、参考文献[1]章胤,2014年燕山大学全国大学生数学建模比赛培训ppt,2014年4月17日。

作业1、2：商人过河一、问题重述问题一：4个商人带着4个随从过河，过河的工具只有一艘小船，只能同时载两个人过河，包括划船的人。

随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货。

乘船渡河的方案由商人决定。

商人们怎样才能安全过河?问题二：假如小船可以容3人，请问最多可以有几名商人各带一名随从安全过河。

二、问题分析问题可以看做一个多步决策过程。

每一步由此岸到彼岸或彼岸到此岸船上的人员在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河。

用状态变量表示某一岸的人员状况，决策变量表示船上的人员情况，可以找出状态随决策变化的规律。

问题就转换为在状态的允许变化范围内（即安全渡河条件），确定每一步的决策，达到安全渡河的目标。

三．问题假设1. 过河途中不会出现不可抗力的自然因素。

2. 当随从人数大于商人数时，随从们不会改变杀人的计划。

3．船的质量很好，在多次满载的情况下也能正常运作。

4. 随从会听从商人的调度。

四、模型构成x(k)~第k次渡河前此岸的商人数x(k),y(k)=0,1,2,3,4;y(k)~第k次渡河前此岸的随从数k=1,2,…..s(k)=[ x(k), y(k)]~过程的状态S~允许状态集合S={(x,y) x=0,y=0,1,2,3,4; x=4,y=0,1,2,3,4;x=y=1,2,3}u(k)~第k次渡船上的商人数u(k), v(k)=0,1,2;v(k)~ 第k次渡船上的随从数k=1,2…..d(k)=( u(k), v(k))~过程的决策 D~允许决策集合D={u,v |u+v=1,2,u,v=0,1,2}状态因决策而改变s(k+1)=s(k)+(-1)^k*d(k)~状态转移律求d(k) ∈D(k=1,2,….n),使s(k)∈S 并按转移律s(k+1)=s(k)+(-1)^k*d(k)由（4,4）到达（0,0）数学模型：k+1k S =S +k k D （-1） （1）'4k k x x += （2）'4k k y y += （3）k.k x y ≥ （4）''k k x y ≥ （5）模型分析：由（2）（3）（5）可得44kk x y -≥- 化简得k k x y ≤综合（4）可得k k x y = 和 {}(,)|0,0,1,2,3,4k k k k k S x y x y === （6）还要考虑 {}'(',')|'0,'0,1,2,3,4kk k k k S x y x y === （7） 把（2）（3）带入（7）可得{}(4,4)|40,40,1,2,3,4k k k k k S x y x y =---=-=化简得{}(,)|4,0,1,2,3,4k k k k k S x y x y === （8） 综合（6）（7）（8）式可得满足条件的情况满足下式{}(,)|0,4,0,1,2,3,4;k k k k k k k S x y x y x y ==== （9）所以我们知道满足条件的点如上图所示：点移动由{}(,)|4,0,1,2,3,4k k k k k S x y x y === （8） 到达{}(,)|0,0,1,2,3,4k k k k k S x y x y === （6）时，可以认为完成渡河。