商人过河的数学模型及编程解决
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表示所有的可取状态向量的集合。
3.设用d表示所有运载向量的集合。
4.设用表示从此岸到彼岸，作减；用表示从彼岸到此岸，作加。S k：表示第k步可取状态向量（S k属于s）；d k：表示第k步可取转移向量（d k属于d）；
五．模型的建立
我们以3名商人为例。
设第k次渡河前此岸的商人数为x k，随从数为y k，k=1，2，…，x k，y k=0，1，2，3，将二维向量S k=（x k，y k）定义为状态。安全渡河条件下的状态集合称为允许状态集合，记为S，则允许状态集合为：S={（x，y）|x = 0或3，y = 0，1，2，3，x = y = 1，2} （1）又设第k次渡船上的商人数为u k，随从数为v k，将二维向量
d k=（u k+ v k）定义为决策。则允许决策集合为：
D={（u，v）| u + v = 1，2} （2）
因为k为奇数时船从此岸驶向彼岸，k为偶数时船由彼岸驶向此岸，所以状态S k随着决策d k变化的规律即状态转移规律是：
S k+1 = S k +（- 1）k d k （3）
这样，制定安全渡河方案归结为如下的多步决策问题：
求决策d k ∈ D（k = 1，2，…，n），使状态S k ∈ S按照规律（3），由初始状态S1=（3，3）经有限步（设为n）到达状态S n+1=（0，0）。
六．模型的简化与求解
下面通过程序给出这个多步决策问题的一个解：
a[1]={0，0}；a[2]={0，1}；a[3]={0，2}；a[4]={0，3}；
a[5]={3，0}；a[6]={3，1}；a[7]={3，2}；a[8]={3，3}；
a[9]={1，1}；a[10]={2，2}；
（*以上给出10个允许的状态*）
d[1]={0，2}；d[2]={2，0}；d[3]={1，1}；d[4]={0，1}；
d[5]={1，0}；
（*以上表示给出5个允许的决策*）
i=1；j=1；k=1；s[0]=s[1]={3，3}；
Print[″此岸————船上————对岸″]；
Do[
Do[s[i+1]=s[i]+（-1）^i d[j]；
t=0；
Do[If[s[i+1]= =a[k]，t=1]，{k，1，10}]；
If[t= =0，Continue[ ]]；
（*以上是保证状态属于允许的状态*）
l=Mod[i+1，2]；m=l；u=0；
If[i+1> =3，
Do[If[s[i+1]= =s[m]，u=1，Break[ ]]，{m，l，i -1，2}] ]；
If[u= =0，c[i+1]=d[j]；Break[ ]]
，{j，1，5}]；
If[t= =0，Print[No，Result]；Break[ ]]；
b[i+1]={3，3}-s[i+1]；
Print[s[i]，″- - - -″，c[i+1]，″- - - -″，b[i+1]]； If[s[i+1]= ={0，0}，Break[ ]]
，{i，1，12}]
程序运行结果如下：
此岸——————船上——————对岸
{3，3}——————{0，2}——————{0，2}
{3，1}——————{0，1}——————{0，1}
{3，2}——————{0，2}——————{0，3}
{3，0}——————{0，1}——————{0，2}
{3，1}——————{2，0}——————{2，2}
{1，1}——————{1，1}——————{1，1}
{2，2}——————{2，0}——————{3，1}
{0，2}——————{0，1}——————{3，0}
{0，3}——————{0，2}——————{3，2}
{0，1}——————{0，1}——————{3，1}
{0，2}——————{0，2}——————{3，3} 可以得出经过11步的渡河就能达到安全渡河的目标及满足渡河的次数尽量少的条件。这11步的渡河方案就是上面程序运行结果中船上下面的一列。渡河的整个过程如下所示：
去2随从回1随从
（3商人3随从）—————→（3商人1随从）—————→去2随从回1随从
（3商人2随从）—————→（3商人0随从）—————→去2商人回1商人1随从
（3商人1随从）—————→（1商人1随从）—————→去2商人回1随从
（2商人2随从）—————→（0商人2随从）—————→去2随从回1随从
（0商人3随从）—————→（0商人1随从）—————→去2随从
（0商人2随从）—————→（渡河成功）
七、结果分析与检验
八、模型的优缺点与改进方向
九、参考文献
【1】茆诗松等 , 概率论与数理统计教程，北京：高等教育出版社,2004年。【2】赵静，但琦，数学建模与数学实验[3]，北京：高等教育出版社，2008年。
十、附录
（一）程序
//约束条件:岸上仆人不能多于商人数
#include
using namespace std;
struct Node
{
int nMer;
int nSer;
int length;
};
class A
{
public:
A();
~A();
void Tspt(); //过河的动作
void doLeft(int nhead,int ntail,int nlength);
private:
bool islegal(int nm,int ns); //判断是否满足约束条件，满足为true Node *funTspt(int nm,int ns,bool flag);//添加STEP[head]可以向后延伸的节点
bool noRepeat(int nm,int ns);//没有重复返回TRUE
void funshow(int a[][2],int ntail);
bool funLeft(Node nd,int b1,int b2,int n);
void show(int s[],int p[][2],int &top,int &count,int a[]);
int head;
int tail;
int n; //商仆的对数
int nB; //船最多的载人数目
Node *STEP;
};
A::~A()
{
free(STEP);
}
A::A()
{
cout<<"请输入商仆的对数:";
cin>>n;
cout<<"请输入船最多载人的数目:";
cin>>nB;
STEP = (Node *)malloc(sizeof(Node)*10000);
memset(STEP,0,sizeof(Node)*10000);
head = tail = 0;
STEP[0].nMer = STEP[0].nSer = n;
}
int main()
{
A a;
a.Tspt();
return 0;
}
void A::show(int s[],int p[][2],int &top,int &count,int a[])
{
if(top == -1)
return ;
//已找到目标状态需，输出数据
if(top == STEP[head].length)
{
cout<<"*********** "<<++count<<" ***********"< funshow(p,top + 1); B: top--; if(top == -1) return ; C: s[top]--; if(STEP[(s[top])].length != top)//退过了 { s[top] = a[top]; goto B; } if(funLeft(STEP[(s[top])],p[top - 1][0],p[top - 1][1],top - 1) == false) goto C; p[top][0] = STEP[(s[top])].nMer; p[top][1] = STEP[(s[top])].nSer; show(s,p,top,count,a); return ; } //在中间加入节点STEP[(s[top + 1])] if(funLeft(STEP[(s[top + 1])],p[top][0],p[top][1],top) == true)// 符合条件 { top++; p[top][0] = STEP[(s[top])].nMer; p[top][1] = STEP[(s[top])].nSer; show(s,p,top,count,a); return ; } else //不符合条件 { E: s[top + 1]--; if(STEP[(s[top + 1])].length == top)//退过了，到了下一层 { s[top + 1] = a[top + 1]; D: s[top]--; if(STEP[(s[top])].length != top)//退过了，到了下一层 { for(int i = top; i <= STEP[head].length; i++) s[i] = a[i]; top--; if(top == -1) return ; goto D; } if(top == 0) return ; if(funLeft(STEP[(s[top])],p[top - 1][0],p[top - 1][1],top - 1) == false) goto D; p[top][0] = STEP[(s[top])].nMer; p[top][1] = STEP[(s[top])].nSer; show(s,p,top,count,a); return ; } if(funLeft(STEP[(s[top + 1])],p[top][0],p[top][1],top) == false) goto E; top++; p[top][0] = STEP[(s[top])].nMer; p[top][1] = STEP[(s[top])].nSer; show(s,p,top,count,a); } } void A::doLeft(int nhead,int ntail,int nlength) { int a[1000]; int a1[1000]; int sp[1000][2]; bool flag = false; memset(a,0xff,4000); memset(a1,0xff,4000); memset(sp,0xff,8000); if(STEP[head].length%2 == 0) flag = true; while(STEP[head].length == nlength - 1) { funTspt(STEP[head].nMer,STEP[head].nSer,flag); head++; } for(int i = 0; i < head + 1; i++) { a[(STEP[i].length)] = i; a1[(STEP[i].length)] = i; } sp[0][0] = sp[0][1] = n; STEP[head].nMer = STEP[head].nSer = 0; int top = 0; int count = 0; show(a1,sp,top,count,a); } bool A::funLeft(Node nd,int b1,int b2,int n) { bool flag = abs(nd.nMer - b1) + abs(nd.nSer - b2) < nB + 1 && abs(nd.nMer - b1) + abs(nd.nSer - b2) > 0; if(flag == false) return false; if(n%2 == 0 && b1 >= nd.nMer && b2 >= nd.nSer) return true; if(n%2 == 1 && b1 <= nd.nMer && b2 <= nd.nSer) return true; return false; } void A::Tspt() { Node *temp = new Node; temp = NULL; bool flag = false; while(head <= tail) { if(STEP[head].length%2 == 0) flag = true; else flag = false; temp = funTspt(STEP[head].nMer,STEP[head].nSer,flag); if(NULL != temp) break; head++; } if(head > tail) { cout<<"此问题无解!"< exit(1); } doLeft(temp->nMer,temp->nSer,temp->length);//temp->nMer表示head delete temp; } Node* A::funTspt(int nm,int ns,bool flag) {//flag == true 向对岸运输 Node *nd = NULL; int temp = 1; int tM = STEP[head].nMer; //可供运输的商人数 int tS = STEP[head].nSer; //可供运输的仆人数 if(flag == false) //向此岸运输 { tM = n - STEP[head].nMer; tS = n - STEP[head].nSer; temp = -1; } for(int i = 0; i < tM + 1 && i < nB + 1; i++)//i表示运输的商人数{ for(int j = 0; j < tS + 1 && j < nB - i + 1; j++)//j表示运输的仆人数 { if(i + j == 0) continue; int p = STEP[head].nMer - temp*i; int q = STEP[head].nSer - temp*j; if(islegal(p,q) == true && noRepeat(p,q) == true) { if(p == 0 && q == 0) { tail++; STEP[tail].length = STEP[head].length + 1; STEP[tail].nMer = p; STEP[tail].nSer = q; nd = (Node*)malloc(sizeof(Node)); nd->length = STEP[head].length + 1; nd->nMer = head; nd->nSer = tail; return nd; } tail++; STEP[tail].length = STEP[head].length + 1; STEP[tail].nMer = p; STEP[tail].nSer = q; } } } return nd; } bool A::noRepeat(int nm,int ns) { int j1 = 0; if(STEP[head].length%2 == 0) j1 = 1; for(int i = j1; i < tail + 1; i++) { if(STEP[i].length%2 == j1 && nm == STEP[i].nMer && ns == STEP[i].nSer) return false; } return true; } bool A::islegal(int nm,int ns) { //商人数少于仆人数或者商人数为0 if((nm == 0) || (nm == n) || (nm == ns)) return true; return false; } void A::funshow(int a[][2],int ntail) { cout< cout<<" 商人数仆人数"< for(int i = 0; i < ntail; i++) { cout<<"第"< if(i != ntail - 1 && i%2 == 0) cout<<" --> ("< a[i][0])<<"," < else if(i != ntail - 1 && i%2 == 1) cout<<" <-- ("< a[i][0])<<"," < } cout< } 商人过河 一、问题重述和分析 随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货。现有4名商人各带一个随从一起渡河一只船只能容纳两个人，但如何乘船渡河的大权掌握在商人的手里，商人怎样安排才能在有限步内安全渡河？ 二、模型假设 1、在商人人数多于随从时乘船渡河的大权掌握在商人的手里； 2、商人和随从都会划船； 三．符号说明 x表示商人人数； y表示随从人数； z表示划船到河的此岸与彼岸。 四、模型的建立与求解 本题为多步决策模型，每一次过河都是状态量的转移过程。 此岸四个商人用x=0、1、2、3、4表示，此岸四个随从用y=0、1、2、3、4表示，z=0时表示划船到河的此岸时，z=1时表示划船到河的彼岸时，用有序数对（x，y，z）表示每次转移的状态量。解决此问题就是状态量（4,4,0）转移至（0,0,1），以下就是状态量转移的全部情况（其中“！”表示不能再转移下去或与前面步骤重复）： （4,4，0）→（3,3,1） ↓↓ （4,2,1）→（4,3,0）→（4,1,1）→（4,2,0）→（4,0,1）→（4,1,0）→！ ↓ （2,2,1） ↓ ！ 由以上关系可知，一只船只能容纳两个人的情况下，四名商人各带一个随从无法过河。 此外，如果船的容量增加到3人，那么商人就能以几种方式安全过河，以下 是其中一种方案： （4,4,0）→（4,2,1）→（4,3,0）→（4,1,1,）→（4,2,0）→（2,2,1） ↓ （0,1,1）←（0,3,0）←（0,2,1）←（0,4,0）←（0,3,1）←（3,3,0）↓ （0,2,0）→（0,0,1） 五、模型推广 通过以上模型的建立，若商人和随从人数增加或小船容量加大，考虑n名商人各带一随从的情况。 商人过河问题数学建模 WEIHUA system office room 【WEIHUA 16H-WEIHUA WEIHUA8Q8- 作业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,vu+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） 商人过河问题 /*************************************************** *M个商人与每人各带的一个仆人过河问题 *船每次至多运N个人，至少要有一人划船 *在任一岸，当商人数<仆人数时,仆人就杀人越货 *过河由商人安排运送人员及数目 *找出安全渡河的全部方法并打印(原问题中M=3，N=2) *2010-10-10 20时许（纪念伟大的双十） * LYP ***************************************************/ /****************************************************************** *本题为多步决策 *若考虑只针对人数为 M = 3 对，每次过河人数最多 N = 2 *可以证明路径中必须经坐标中(3,1)过至(1,1)点(过诃时)， *后返回至(2,2)点，再过诃至(0,2)点(只剩2个仆人) *可以先考虑(3,3)到(3,1)点 *再经(0,2)至(0,0),完成过诃(由图形的对称性关系,可以直接将(3,1)至(3,1)路径翻转,更改对应标号即可) *当然也可以用动态规划求解 *本代码不限定M,N值,可通过修改宏M,N的值,求其他商人(仆人)数与最大过河人数的全部路径 *******************************************************************/ /********************************************************************* * *商人数x < 仆人数y时遭杀人越货，过河失败 *对应可行域为: *x = 0, y = 0…M; elements[]中编号0…M *0 < x < M, y = x; elements[]中编号M+1…2M-1 *x = M, y = 0…M； elements[]中编号2M…3M *图像上表示如下:(共 3*M+1 个点),过河即从3M点到0点 *过河为左下方1/4圆区域 *返回为右上方1/4圆区域 1、问题描述（问题与假设） 随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货.乘船渡河的方案由商人决定.商人们怎样才能安全过河? 假设：1. 过河途中不会出现不可抗力的自然因素。 2. 当随从人数大于商人数时，随从们不会改变杀人的计划。 3.船的质量很好，在多次满载的情况下也能正常运作。 4. 随从会听从商人的调度。 2、问题模型与求解（公式、图、表、算法或代码等） 模型的建立： 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~允许状态集合 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） 数学模型： 模型分析： 由（2）（3）（5）可得 Yk Xk -≥-44 化简得 Yk k ≤X 关键代码： clear clc n=3;m=3;h=2; m0=0;n0=0; tic LS=0; LD=0; for i=0:n for j=0:m if i>=j&n-i>=m-j|i==n|i==0 LS=LS+1; S(LS,:)=[i j]; end if i+j>0&i+j<=h&(i>=j|i==0) LD=LD+1; D(LD,:)=[i j]; end end end N=15; Q1=inf*ones(2*N,2*N); Q2=inf*ones(2*N,2*N); t=1; le=1; q=[m n]; f0=0; while f0~=1&t 基于商人过河游戏的数学建模 1提出问题 文献[1]给出一个智力游戏：“三名商人各带一个随从渡河，一只小船只能容纳二人，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。但是如何乘船的大权掌握在商人们手中。商人怎样才能安全渡河呢？”此类智力问题当然可以通过一番思考，拼凑出一个可行的方案来。文献[1]中通过图解法给出了解答，但是当商人数与随从数发生变化，船能容纳的人数不是二人时，图解法就会变得繁复而难以解决问题。 因此，将上述游戏改为n名商人各带一个随从过河，船每次至多运p个人，至少要有一个人划船，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。 但是如何乘船的大权掌握在商人们手中。商人怎样才能安全渡河的问题。 除此之外，考虑了随着船载人数的增多，以及商人与仆人的对数增多到多少时，会影响商人的安全渡河的问题。 2问题分析 由于这个虚拟的游戏已经理想化了，所以不必再作假设。我们希望能找出这类问题的规律性，建立数学模型，并通过计算机编程进行求解。安全渡河游戏可以看做是一个多步决策过程，分步优化，船由此岸驶向彼岸或由彼岸驶回此岸的每一步，都要对船上的商人和随从做出决策，在保证商人安全的前提下，在无限步内使全部人员过河。用状态表示某一岸的人员状况，决策表示船上的人员情况，可以找出状态随决策变化的规律。问题转化为在状态的允许范围内，确定每一步的决策，最后获取一个全局最优方案的决策方案，达到渡河的目标。 除此以外，我们还要找出，随着船载人数的增加，商人与仆人对数达到多少时，会影响到商人不能安全过河。这里要对船载人数进行限制，因为船载人数过多时，此智力游戏会变得相当繁复，就会失去作为游戏的本来意义。 3模型构成 商人过河functionjueche=guohe %程序开始需要知道商人和仆人数； n=input（' 输入商人数目:'）; nn=input（' 输入仆人数目:'）; nnn=input（' 输入船的最大容量:'）; ifnn>n n=input（'' 输入商人数目:'）; nn=input（' 输入仆人数目:'）; nnn=input（' 输入船的最大容量:'）; end %决策生成 jc=1;% 决策向量放在矩阵 d 中，jc 为插入新元素的行标初始为 1 ； for i=0:nnn for j=0:nnn if（i+j<=nnn）&（i+j>0）% 满足条D={（u,v） |1<=u+v<=nnn,u,v=0,1,2} d（ jc,1:3）=[i,j ，1] ；%生成一个决策向量立刻扩充为三维； d（ jc+1,1:3）=[-i,-j,-1];% 同时生成他的负向量； jc=jc+2;% 由于生成两个决策向量，则jc 要向下移动两个；end end j=0; end% 状态数组生成 kx=1;% 状态向量放在 A 矩阵中，生成方法同矩阵生成； for i=n:-1:0 for j=nn:-1:0 if((i>=j)&((n-i)>=(nn-j)))|((i==0)|(i==n))%(i>=j)&((n-i)>=(nn-j)))|((i==0)|(i==n ))为可以存在状态的约束条件 A(kx,1:3)=[i,j,1];% 生成状态数组集合D' A(kx+1,1:3)=[i,j,0]; kx=kx+2; end end j=nn; end; % 将状态向量生成抽象矩阵 k=(1/2)*size(A,1); CX=zeros(2*k,2*k); a=size(d,1); for i=1:2*k for j=1:a c=A(i,:)+d( j,:); x=find((A(:,1)==c(1))&(A(:,2)==c(2))&(A(:,3)==c(3))); 作业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）可得 44k k x y -≥- 化简得 k k x y ≤ 数学建模作业——实验1 学院：软件学院 姓名： 学号： 班级：软件工程2015级 GCT班 邮箱： 电话： 日期：2016年5月10日 基本实验 1.椅子放平问题 依照1.2.1节中的“椅子问题”的方法，将假设中的“四腿长相同并且四脚连线呈正方形”，改为“四腿长相同并且四脚连线呈长方形”，其余假设不变，问椅子还能放平吗？如果能，请证明；如果不能，请举出相应的例子。 答：能放平，证明如下： 如上图，以椅子的中心点建立坐标，O为原点，A、B、C、D为椅子四脚的初始位置，通过旋转椅子到A’、B’、C’、D’，旋转的角度为α，记A、B两脚，C、D两脚距离地面的距离为f(α)和g(α)，由于椅子的四脚在任何位置至少有3脚着地，且f(α)、g(α)是α的连续函数，则f(α)和g(α)至少有一个的值为0，即f(α)g(α)=0，f(α)≥ 0，g(α)≥0，若f(0)＞0，g(0)=0， 则一定存在α’∈（0，π），使得 f(α’)=g(α’)=0 令α=π（即椅子旋转180°,AB 边与CD 边互换），则 f(π)=0，g(π)＞0 定义h(α)=f(α)-g(α)，得到 h(0)=f(0)-g(0)＞0 h(π)=f(π)-g(π)＜0 根据连续函数的零点定理，则存在α’∈（0，π），使得 h(α’)=f(α’)-g(α’)=0 结合条件f(α’)g(α’)=0,从而得到 f(α’)=g(α’)=0，即四脚着地，椅子放平。 2. 过河问题 依照1.2.2节中的“商人安全过河”的方法，完成下面的智力游戏：人带着猫、鸡、米过河，船除需要人划之外，至多能载猫、鸡、米之一，而当人不在场时，猫要吃鸡、鸡要吃米，试设计一个安全过河的方案，并使渡河的次数尽量的少。 答：用i =1,2,3,4分别代表人，猫，鸡，米。1=i x 在此岸，0=i x 在对岸，()4321,,,x x x x s =此岸状态，()43211,1,1,1x x x x D ----=对岸状态。安全状态集合为 : 数学建模课程作业 论文题目： 对商人过河问题的研究 指导教师：黄光辉 小组成员：黄志宇（20156260）车辆工程04班 牛凯春（20151927）电气工程05班 文逸楚（20150382）工商管理02 班 一、问题重述 3名商人带3名随从乘一条小船过河，小船每次只能承载至多两人。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。乘船渡河的方案由商人决定，商人们如何才能安全渡河呢？ 二、问题分析 本题针对商人们能否安全过河问题，需要选择一种合理的过河方案。对该问题可视为一个多步决策模型，通过对每一次过河的方案的筛选优化，最终得到商人们全部安全过到河对岸的最优决策方案。对于每一次的过河过程都看成一个随机决策状态量，商人们能够安全到达彼岸或此岸我们可以看成目标决策允许的状态量，通过对允许的状态量的层层筛选，从而得到过河的目标。 三、模型假设 1.过河途中不会出现不可抗力的自然因素。 2.当随从人数大于商人数时，随从们不会改变杀人的计划。 3．船的质量很好，在多次满载的情况下也能正常运作。 4.随从会听从商人的调度，所有人都到达河对岸。 四、符号说明 第k次渡河前此岸的商人数 第k次渡河前此岸的随从数 过程的状态向量 允许状态集合 第k次渡船上的商人数 第k次渡船上的随从数 决策向量 允许决策集合 x y 3322110s 1s n +1d 1d 11五、模型建立 本题为多步决策模型，每一次过河都是状态量的转移过程。 用二维向量表示过程的状态，其中分别表示对应时刻此岸的商人，仆人数以及船的行进方向，其中则允许状态集合: = 又将二维向量定义为决策，则允许的决策合集为: 因为k 为奇数时船从此岸驶向彼岸，k 为偶数时船从彼岸驶向此岸，所以状态随决策的变化规律是 该式称为状态转移律。 求决策，使,并按照转移律，由经过有限步n 到达状态 六、模型求解 本模型使用MATLAB 软件编程，通过穷举法获得决策方案如下(完整matlab 程序详见附录): 初始状态： 可用图片表示为：X0= 3 3状态为: S = 3 13 23 03 11 12 20 20 30 10 20 0决策为: D = 02 组长：王鹏道110714 组员：任利伟110713、孙祎110706 小组成员负责情况： 王鹏道：选择论文题目、设计论文版面字体、分配成员任务、总结任利伟：一、问题提出、关键、分析。二、模型假设、三、模型建立孙祎：四、模型求解、五、模型的检验、拓展及延伸 2014年11月24日 摘要 为了求解3个商人和3个随从的过河问题，用数学分析方法，建立数学模型，并且加以求解，展示动态规划思想的应用步骤。最后利用计算机蝙程进行求解，获得过河问题的完整求解过程；有效地求解类似多步决策问题的作用。 关键词：多步决策计算机求解状态转移律图解法 一、 问题的提出 随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货，但是乘船渡河的方案由商人决定.商人们怎样才能安全过河? 二、 问题的关键 解决的关键集中在商人和随从的数量上，以及小船的容量上，该问题就是考虑过河步骤的安排和数量上。各个步骤对应的状态及决策的表示法也是关键。 三、 问题的分析 在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河。由于船上人数限制，这需要多步决策过程，必须考虑每一步船上的人员。动态规划法正是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解的子问题为止。分解成所有子问题按层次关系构成一棵子问题树．树根是原问题。原问题的解依赖于子问题树中所有子问题的解。 四、 模型假设 记第k 次过河前A 岸的商人数为X K ， 随从数为Y K k=1，2，? X K ,Y K =0，1，2，3，将二维向量S K =(X K ，Y K )定义为状态．把满足安全渡河条件下的状态集合称为允许状态集合。记作S 。则 S={(X K ,Y K )|(X K =0,Y K =0,1,2,3),(X K =3,Y K =0,1,2,3),(X K =Y K =1)(X K =Y K =2)} 记第k 次过河船上的商人数为U K 随从数为V K 将二维向量D K =(U K ,V K )定义为决策．由小船的容量可知允许决策集合（记作D)为 D={(U K ,V K )|U K +V K =l,2}={(O,1);(O,2);(1,O);(1,1);(2,O)} 五、 模型建立： 动态规划法正是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解的子问题为止。分解成所有子问题按层次关系构成一棵子问题树．树根是原问题。原问题的解依赖于子问题树中所有子问题的解。 P59 4.学校共1002名学生，237人住在A 宿舍，333人住在B 宿舍，432人住在C 宿舍。学生要组织一个10人的委员会，使用Q 值法分配各宿舍的委员数。 解:设P 表示人数，N 表示要分配的总席位数。i 表示各个宿舍（分别取A,B,C ），i p 表示i 宿舍现有住宿人数，i n 表示i 宿舍分配到的委员席位。 首先，我们先按比例分配委员席位。 A 宿舍为:A n = 365.21002 10237=? B 宿舍为:B n =323.31002 10333=? C 宿舍为:C n =311.4100210432=? 现已分完9人，剩1人用Q 值法分配。 5.93613 22372 =?=A Q 7.92404 33332 =?=B Q 2.93315 44322 =?=C Q 经比较可得，最后一席位应分给A 宿舍。 所以，总的席位分配应为：A 宿舍3个席位，B 宿舍3个席位，C 宿舍4个席位。 商人们怎样安全过河 由上题可求：4个商人，4个随从安全过河的方案。 解：用最多乘两人的船，无法安全过河。所以需要改乘最多三人乘坐的船。 如图所示，图中实线表示为从开始的岸边到河对岸，虚线表示从河对岸回来。商人只需要按照图中的步骤走，即可安全渡河。总共需要9步。 P60 液体在水平等直径的管内流动，设两点的压强差ΔP 与下列变量有关：管径d,ρ,v,l,μ,管壁粗糙度Δ，试求ΔP 的表达式 解：物理量之间的关系写为为()?=?,,,,,μρ?l v d p 。 各个物理量的量纲分别为 []32-=?MT L p ，[]L d =，[]M L 3-=ρ，[]1-=LT v ，[]L l =，[]11--=MT L μ，Δ是一个无量纲量。 ???? ??????-----=?0310100011110010021113173A 其中0=Ay 解得 ()T y 00012111---=， ()T y 00101102--=， ()T y 01003103--=， ()T y 10000004= 所以 l v d 2111---=ρπ，μρπ112--=v ，p v ?=--313ρπ，?=4π 因为()0,,,,,,=??p l v d f μρ与()0,,,4321=ππππF 是等价的，所以ΔP 的表达式为： ()213,ππψρv p =? 讨论资金积累、国民收入与人口增长的关系 班级：2009级数学与应用数学 黄全（组长）: P092314746 邱亚彪: P091712712 谢志成:P091712679 央金:P091715381 罗国庭:P091712739 讨论资金积累、国民收入与人口增长的关系 摘要 如何保证人口增长对国民收入影响的正效应和国民平均收入持续性增长，一直是全国人民所共同关注的问题。本文对资金积累、国民收入和人口增长三者之间的关系进行讨论，通过导数结合三者之间存在的基本规律，建立相应的微分方程，利用微分方程法给出方程，由matlab解得资金积累、国民收入与人口增长的关系。通过掌握该关系，确定资金积累的增长率大于人口增长率时国民收入才会增长，从而更好地调整人口出身率、控制人口的数量和人口质量，保证我国人口增长与国民收入增长之间的适当的比例关系，使得国民平均持续性增长，促进社会经济的迅速发展，提高人民的生活质量，为整个社会的长远战略需求做贡献。 关键字：资金积累状态转移律图解法微分方程决策 一、 问题重述 讨论资金积累、国民收入与人口增长的关系 （1）若国民平均收入x 与按人口平均资金积累y 成正比，说明仅当总资金积累 的相对增长率k 大于人口的相对增长率r 时，国民平均收入才是增长的. （2）作出k(x)和r(x)的示意图，说明二曲线交点是平衡点，讨论它的稳定性。 （3）分析人口激增会引起什么后果 二、符号说明 1x : t 时刻总资金累积量，2x ：t 时刻人口数量， 3x ：国民平均收入量 ，k ：总资金的相对增长率 r ：人口的相对增长率 三 、模型的假设 在一定时期后,增长的人口数量为:：22x rx '=； 总资金的增长量为：11x kx '= ； 四、问题的分析 在社会主义发展的初级阶段，国民收入是指一定时期（通常为1年）内，物质生产部门劳动者新创造的价值,它是物质资料生产进一步发展和人口再生产条件改善的物质基础。在其他条件已定的情况下,国民收入总量愈多,人均消费基金和积累基金也越多，从而有利于人们生活的改善和技术装备水平的提高，也有利于人口数量的控制和人口质量的提高。人口增长从 3个方面影响国民收入的增减： ① 人口或劳动者数量的多少； ② 每个劳动者技术装备水平的高低； ③ 劳动者节省消耗和管理才能的大小。 国民收入又分为资金的累积和消费，累积资金=国民收入错误！未找到引用源。消费资金，而消费资金=基本消费资金错误！未找到引用源。人口发展速度。因此， 为增加人均国民收入，增强一国的经济实力和提高人民生活水平，要在大力发展经济、增加生产的基础上合理地调节人口增长。 数学建模作业 班级：数学131 姓名：丁延辉 学号：13190122 （二）商人过河Matlab代码 三个商人三个随从 z=zeros(30,3); %z为由(a,b,c)的列向量组成的3行30列数组，初始化为0矩阵，a,b,c代表此刻此岸的商人，仆人数量以及船的运行状态，c=1表示即将向彼岸运行 m=zeros(1,20); %m为一维行向量，初始化为1矩阵，用于在后面的程序中判断第k次选择的乘船方案 d=[0,1,1;0,2,1;1,0,1;1,1,1;2,0,1]; %共有5种可以选择的乘船方案，最后面一列全为1，即用于在后面表示使得z(k,3)的取值保持随着k的奇偶性保持着0-1变换. z(1,:)=[3,3,1]; %初始状态为[3,3,1] k=1; m(k)=1; %第一次默认的乘船方案为决策1——d(1) flag=1; %用于在后面判断是否成功找到方案 answer=0; %用于在后面判断是否找到 答案 while k>0 %保持k>0 if m(k)>5 flag=0; break; end p=0; z(k+1,:)=z(k,:)+(-1)^k*d(m(k),:); %每一次的运算规则都是z(k+1)=z(k)-(-1)^k*d(m(k),:),d(m(k),:)表示决策方案 a=z(k+1,1); %将当前情况的矩阵数值复制给a商人,b仆人 b=z(k+1,2); c=z(k+1,3); if (a==3&&(b==0||b==1||b==2||b==3))||(a==1&&b==1)||(a==2&&b==2 )||(a==0&&(b==0||b==1||b==2||b==3)) %判断(a,b)是否符合限定情况 for j=1:k %判断是否此岸a,b,c与之前有重复，如果是，结束此次循环，重新选择乘船方案 if a==z(j,1)&&b==z(j,2)&&c==z(j,3) if m(k)~=5 %决策方案只有5种，所以m(k)<=5， 2011高教社杯全国大学生数学建模竞赛 承诺书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）：西京学院 参赛队员(打印并签名) ：1. 邹高永 2. 张大伟 3. 钱晓东 指导教师或指导教师组负责人(打印并签名)： 日期：年月日赛区评阅编号（由赛区组委会评阅前进行编号）： 2011高教社杯全国大学生数学建模竞赛 编号专用页 赛区评阅编号（由赛区组委会评阅前进行编号）： 赛区评阅记录（可供赛区评阅时使用）： 评 阅 人 评 分 备 注 全国统一编号（由赛区组委会送交全国前编号）： 全国评阅编号（由全国组委会评阅前进行编号）： 商人过河 摘要 本文针对商人安全渡河的问题，采用多步决策的过程建立数学模型，求解得到了在随从没有杀人越货的情况下的渡河方案。 对于本题而言，在3名商人、3名随从、船的最大容量为2的情况下，首先定义了渡河前此岸的状态，并设安全渡河条件下的状态集定义为允许状态集合，接着得到渡河方案的允许决策集合，然后得到状态随渡河方案变化的规律，最后利用平面坐标分析法，并利用计算机进行了仿真，得到了一种商人安全渡河的方案。 但是，本文不仅仅是为了拼凑出一个可行方案，而是希望能找到求解这类问题的规律性，并建立数学模型，用以解决更为广泛的问题。基于此目的，利用了dijkstra算法，得到最短路径的最优解。但同时由于该算法遍历计算的节点很多，所以效率低，而且当有多个最短距离时，不能够将所有符合条件的情况逐一列出。 最后，从这类问题解得趣味性、合理性进行了深入讨论，得到了“传教士与野蛮人渡河”，“印度夫妻渡河”等问题通用的模型，并将其进行了推广。这也是本文的一大特色。 关键词渡河问题状态集合决策集合平面坐标dijkstra算法 《数学模型实验》实验报告 姓名：王佳蕾学院：数学与信息科 学学院 地点：主楼402 学号：055专业：数学类时间：2017年4 月16日 实验名称： 商人和仆人安全渡河问题的matlab实现 实验目的： 1.熟悉matlab基础知识，初步了解matlab程序设计； 2.研究多步决策过程的程序设计方法； 3.（允许）状态集合、（允许）决策集合以及状态转移公式的matlab表示；实验任务： 只有一艘船，三个商人三个仆人过河，每一次船仅且能坐1-2个人，而且任何一边河岸上仆人比商人多的时候，仆人会杀人越货。怎么在保证商人安全的情况下，六个人都到河对岸去，建模并matlab实现。 要求：代码运行流畅，结果正确，为关键语句加详细注释。 实验步骤： 1.模型构成 2.求决策 3.设计程序 4.得出结论（最佳解决方案） 实验内容： （一）构造模型并求决策 设第k次渡河前此岸的商人数为xk，随从数为yk，k=1,2,...，xk，yk=0,1,2,3.将二维向量sk=（xk，yk）定义为状态，安全渡河条件下的状态集合称为允许状态集合，记作S，S 对此岸和彼岸都是安全的。 S={(x,y)|x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2} 设第k次渡船上的商人数为uk，随从数vk，将二维变量dk=（uk，vk）定义为决策，允许决策集合记为D,由小船的容量可知， D={(u,v)|1<=u+v<=2,u,v=0,1,2} k为奇数时，船从此岸驶向彼岸，k为偶数时，船从彼岸驶向此岸，状态sk随决策变量dk的变化规律为sk+1=sk+(-1)^k*dk（状态转移律） 这样制定安全渡河方案归结为如下的多步决策模型： 求决策dk∈D(k=1,2,...,n)，使状态sk∈S，按照转移律，由初始状态s1=（3,3）经有限步n到达状态sn+1=（0,0）。 （二）程序设计 商人过河的数学模型及编程解决 摘要：M对商仆过河，一只船最多载N人，船上和岸上的仆人数都不能多于商人数，否则商人有危险。安排合理的渡河方案，保证商人能安全渡河。（可利用向量，矩阵，图解等方法） 一．问题提出： 有M对商仆乘船过河，一只船最多载N人，由商人和仆人自己划船渡河，在河的任意一岸，一旦仆人数多于商人数，仆人就可将商人杀死，谋取利益，但是乘船渡河的主动权掌握在商人们手中，商人们如何安排渡河方案，才能安全渡河？ 二．假设： 商人和仆人都会划船，天气很好，无大风大浪，船的质量很好，船桨足够很多次的运载商人和仆人。 三．参数： 1．设（x，y）是状态向量，表示任一岸的商人和仆人数，并且x，y分别要大于等于0，小于等于M。 2．设（m，n）是运载向量，表示运载的商人数和仆人数，0<=m<=N，0<=n<=N，0<=m+n<=N。 3．设用s表示所有的可取状态向量的集合。 4．设用d表示所有运载向量的集合。 5．设用表示从此岸到彼岸，作减；用表示从彼岸到此岸，作加。Sk：表示第k步可取状态向量（sk 属于s）；dk：表示第k步可取转移向量（dk属于 d）； 四．问题分析： 商仆安全渡河问题可以视为一个多步决策过程，多步决策是指决策过程难以一次完成，而是多步优化，最后获取一个全局最优方案的决策方法。对于每一步，即船由此岸驶向彼岸，或者船由彼岸驶向此岸的决策，不仅会影响到该过程的效果，而且还会影响到下一步的初始状态，从而对整个过程都会有影响。所以，在每一次过河时，就不能只从这一次过河本身考虑，还要把它看成是整个过河过程中的一个部分。在对船上的人员做决策时，要保证两岸的商人数不能少于仆人数，用最少的步伐是人员全部过河。应用状态向量和运载向量，找出状态随运载变化的规律，此问题就转化为状态在允许范围内（即安全渡河条件），确定每一次该如何过河，从而达到渡河的目标。现在我们都把它们数量化：即用数学语言来表示。 我们以3名商人为例 设第k次渡河前此岸的商人数为x k，随从数为y k，k=1，2，…，x k，y k =0，1，2，3，将二维向量S k = （x k，y k）定义为状态。安全渡河条件下的状态集合称为允许状态集合，记为S，则允许状态集合为： 商人过河问题 一、三名商人各带一名随从的情况 1．问题（略） 2．模型假设 ①当一边岸满足随从数大于商人数，但商人数为0时仍为一种安全状 态； ②小船至多可容纳2人，且渡河时由随从（或者商人）来划船。 3．分析与建模 商人过河需要一步一步实现，比如第一步：两个仆人过河，第二步：一个仆人驾船回来，第三步：又是两个仆人过河，第四步：…… 其中每一步都使当前状态发生变化，而且是从一种安全状态变为另一种安全状态。如果我们把每一种安全状态看成一个点，又如果存在某种过河方式使状态a变到状态b，则在点a和点b之间连一条边，这样我们把商人过河问题和图联系起来，有可能用图论方法来解决商人过河问题。 建模步骤：⑴首先要确定过河过程中的所有安全状态，我们用二元数组(,) x y 表示一个安全状态（不管此岸还是彼岸），其中x表示留在此岸的主人数，y表示留在此岸的随从数。两岸各有十种安全状态： (0,0),(0,1),(0,2),(0,3),(2,2),(1,1),(3,0),(3,1),(3,2),(3,3) ⑵在两岸的安全状态之间，如存在一种渡河方法能使一种状态变为另一种 安全状态，则在这两种状态之间连一条边。这样，得到如下一个二部图（图1），其中下方顶点表示此岸状态，上方顶点表示彼岸状态。我们的目的是要找出一条从此岸(3,3)到彼岸(0,0)的最短路。 ⑶观察发现此岸的状态(0,0)，(3,0)和彼岸的状态(0,3)，(3,3)都是孤立点，在求最短路的过程中不涉及这些点，把它们删去。两岸的点用1,2, (16) 新标号。 （3,3）（3,2）（3,1）（3,0）（1,1）（2,2）（0,3）（0,2）（0,3）（0,0） ○②④⑥⑧⑩○○12○14○16 ①③⑤○⑦⑨○11○13○15○ （3,3）（3,2）（3,1）（3,0）（1,1）（2,2）（0,3）（0,2）（0,3）（0,0） 数学建模作业（四）——商人过河问题 一．问题描述 有四名商人各带一名仆人过河，但船最多能载二人，商人已获得仆人的阴谋：在河的任一岸，只要仆人数超过商人数，仆人会将商人杀死并窃取财物且安排如何乘船的权力掌握在商人手中。试为商人制定一个安全过河的方案。 二．解决方案 用递归的源程序如下： 开始时商人，强盗所在的河的这边设为0状态，另一边设为1状态（也就是船开始时的一边设为0，当船驶到对岸是设为1状态，在这两个状态时，都必须符合条件） #include PPointer1=newnode; PPointer2=newnode; } else { PPointer2-> next=newnode; PPointer2=newnode; } } void Pop() /*弹栈*/ { link pointer; if(PPointer1==PPointer2) { free(PPointer1); PPointer1=NULL; PPointer2=NULL; } pointer=PPointer1; while(pointer-> next!=PPointer2) pointer=pointer-> next; free(PPointer2); PPointer2=pointer; PPointer2-> next=NULL; } int history(int a,int b,int n) /*比较输入的数据和栈中是否有重复的*/ { link pointer; if(PPointer1==NULL) return 1; else { pointer=PPointer1; while(pointer!=NULL) { if(pointer-> x==a&&pointer-> y==b&&pointer-> state==n) return 0; 商人过河问题的Java编程解决 转自：“电脑编程技巧与维护”https://www.sodocs.net/doc/c516127801.html,/摘要为商人过河问题建立数学模型，归结为路径搜索问题，并给出一个通用的Jav程序来解决此类问题。 关键词商人过河，二元组，链表，集合 一、描述 商人过河问题是一个传统的智力问题。其描述如下：三名商人各带一名随从乘船渡河，—只小船只能容纳二人，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。但是如何乘船渡河的大权掌握在商人们手中，商人们怎样才能安全渡河呢？ 商人过河问题可以看作一个多步决策过程，通过一系列决策步骤逼近决策目标，并最终达到决策目标。对于该问题的每一步决策，就是要对船由此岸驶向彼岸或由彼岸驶回此岸的人员（包括商人和随从）作出规划，在保证商人安全的前提下，通过有限的步骤，实现人员全部过河的目标。 二、分析 针对这一具体问题，可以经过一番精心安排，找到一个解决方案。不过，本文希望对这一问题进行发展和延伸，建立起数学模型，发现其中蕴含的规律，并借助计算机的运算能力，找到一个通用的一般解法。 在商人过河问题中，用一个二元组来表示岸上商人和随从的组成(m，s)，其中m表示商人人数，s表示随从人数，每个组合可以视为一种状态。所有可能的状态可以表示为集合： S0={(m, s)|0≤m≤3; 0≤s≤3} 安全状态要求商人人数为0，或者大于等于随从人数，因此，所有的安全状态可以表示为集合： S1={(m, s)| m=0, s=0,1,2,3; m=3, s=0,1,2,3; m=s=1,2} 二元组(m，s)也可以表示一次渡河方案，其中m表示船载的商人人数，s表示船载的随从人数。则所有的渡河方案可以表示为集合： S2={(m , s)|0≤m；0≤s；0≤m+s≤2 } 一次渡河决策可以表示为： (m, s)K+1 = (m , s)K - (-1)K(u, v)K K = 0,1,2,3… (m , s)K为第K次渡河时，岸上的商人和随从的组成，(u, v)K为第K次渡河方案，K从0开始。 整个决策方案就是要找到有限步渡河决策，使商人和随从的人数组成从原始状态（3，3），经由一系列中间的安全状态，迁移到最终状态（0，0）的过程。 三、编程 建立前面的数学模型后，即找到一条从状态（3，3）到（0，0）的路径，可以编写程序，利用计算机的计算能力，通过穷举法找到一条状态迁移路径。 1．类二元组 类Dual实现问题分析中提到的二元组，其主要代码如下： class Dual { int m, s;商人过河问题
商人过河问题数学建模修订稿
商人过河问题
数学建模题型
基于商人过河游戏的数学建模-最新教育文档
商人过河问题matlab程序
商人过河问题数学建模
数学建模作业——实验1
数学建模 商人过河
数学建模商人过河__论文
数学建模与数学实验课后习题答案
商人安全过河问题
商人过河matlab程序以及解析
商人过河优化模型
数学模型实验商人过河
最新商人过河的数学模型及编程解决
商人过河问题
数学建模作业(商人过河问题)
商人过河问题的Java编程解决