数学模型题目关于商人过河问题的方案..
发布网友
发布时间：2022-04-22 03:21
共3个回答
热心网友
时间：2023-08-15 12:04
以x1代表商人1,x2代表商人2，x3代表商人3，x4代表随从1，x5代表随从2，x6代表随从3。
数组（x1,x2,x3.x4,x5,x6)代表一个顶点，每个顶点都代表一个装袋，比如xi=1表示i在左岸，xi=0代表i不在左岸，比如（1，1，1，1，1，1，1）代表都在左岸，（1,1,1,1,1,0）代表随从3不在左岸。写出所有的顶点数，剔除不合格的顶点数，如（1，0,0,1,1,1）代表一个商人在左岸，三个随从也在左岸，这样随从会杀人越货，显然是不符合要求的。写出所有的顶点后，如果一种状态可以转化为另一种状态，就在代表这两种状态的顶点画上一条线，比如（1,1,1,1,1,1,）代表初试状态，六个人都在左岸，（1,1,0,1,1,0）表示商人3和随从3渡河了不在左岸，从（1,1,1,1,1,1,）六个人都在左岸，商人3和随从3渡河了就能转化成（1,1,0,1,1,0），所以可以在两者之间画上一条线。都画过线后，问题就转化为找出一条从（1,1,1,1,1,1，）到（0,0,0,0,0,0）的路线。
热心网友
时间：2023-08-15 12:05
//约束条件:岸上仆人不能多于商人数
#include <iostream>
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<<" ***********"<<endl;
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<<"此问题无解!"<<endl;
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<<endl;
cout<<" 商人数 仆人数"<<endl;
for(int i = 0; i < ntail; i++)
{
cout<<"第"<<i<<"次 "<<a[i][0]<<" "<<a[i][1]<<endl;
if(i != ntail - 1 && i%2 == 0)
cout<<" --> ("<<abs(a[i + 1][0] - a[i][0])<<","
<<abs(a[i + 1][1] - a[i][1])<<")"<<endl;
else if(i != ntail - 1 && i%2 == 1)
cout<<" <-- ("<<abs(a[i + 1][0] - a[i][0])<<","
<<abs(a[i + 1][1] - a[i][1])<<")"<<endl;
}
cout<<endl;
}
热心网友
时间：2023-08-15 12:05
假设商人和随从分别叫A和B，现在有AAAA+BBBB：
开始只能AB过去或者BB过去：
若是AB过去，只能A回来，BB过去，B回来，只能BB过去或者AA过去：
1.1若是BB过去，只能B回来，对面三个B，A不能过去，无解。
2.2若是AA过去，只能AB回来，重复开始的AB过去，死循环，无解。
若是BB过去，只能B回来，BB过去，B回来，BB过去，无解。
所以，这个破题无解。
