商仆过河问题——数学建模.doc

商仆过河问题——数学建模
数学建模论文
- 2 -
商仆过河问题
数学建模论文
- 3 -
选择一种可行方案，进行过河或返回，得到新的状态
否
判断是不是允许状态集合中的状态，并且还没在已经考虑的状态中
是否还有其他状态
否
结束
是
是
是
主程序流程图
数学建模论文
- 7 -
图解法：状态s=(x,y) 16个格点
允许状态 10个●点
允许决策 移动1或2格; k奇,左下移;
k偶,右上移.
x
y
3
3
2
2
1
1
0
S1
sn+1
d1
d11
总共需要11步
可以得出经过11步的渡河就能达到安全渡河的目标及满足渡河的次数尽量少的条件。这11步的渡河方案就是上面程序运行结果中船上下面的一列。
八、 模型的检验
用2名商人和2名随从的过河问题的解决思路，检验3名商人和3名随从的过河问题。
数学建模论文
- 8 -
九、 模型的拓展和延伸
通过三名商人和三名随从的过河问题的解决方案，可以进一步计算四名商人和四名随从的过河问题，通过计算机编程可以设计m名商人和n名随从的过河问题。
十、总结
这是通过数学分析的方法解决实用问题，经过问题提出、问题假设、问题分析、模型建立、模型求解、模型检验的过程，解决商人过河问题。然后扩展延伸到n个商人的问题。
学习数学建模以来，重新认识了学习数学的乐趣，也重新认识了数学，本以为数学是单调的，枯燥的，学习了之后，发现数学是普遍存在我们生活之中的。解决现实中的问题，很多都需要数学。沉浸在数学的世界里，发现学习是有趣的；相比于机械的认识各个组织器官，建立一个数学模型解决问题是十分有趣的。
参考文献：
（1）傅清祥．《数据结构与算法》．王晓东．北京：电子工业出版社 1998．
（2）姜启瑟．《数学建模》(第二版)．北京：高等教育出版社，2000．
（3）运筹学教材编写组．《运筹学》(修订版)．北京：清华大学出版社。2001．
附：商仆过河的C程序及运行截屏:
#include <iostream>
using namespace std;
struct Node
{ int nMer;
数学建模论文
- 9 -
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;
数学建模论文
- 10 -
int tail;
int n; //商仆的对数
int nB; //船最多的载人数目
Node *STEP;
};
A::~A()
{
free(STEP);
}
A::A()
{
cout<<"请输入商仆的对数S=";
F: cin>>n;
if(n==1)
{
nB=2;
cout<<"船最多载人的数目K="<<nB;
}
else if(n==2)
{
cout<<"船最多载人的数目可以取:";
for(int x=n;x<=2*n;x++)
数学建模论文
- 11 -
{
cout<<x<<"、";
}
cout<<endl;
cout<<"请输入船最多载人的数目K=";
cin>>nB;
}
else if(n==3)
{