过河问题-数学建模C++实现
发布网友
发布时间：2022-12-28 08:42
共1个回答
热心网友
时间：2023-10-09 19:14
（注：若是VS2010开发工具源码复制可直接运行，若是其他开发工具，可能要小部分修改，源码核心算法不用改动。具体实现请查看相应注释！此文仅供学习参考！）
程序源码：
// CrossRiver.cpp :定义控制台应用程序的入口点。
//开发工具：VS2010旗舰版
//系统环境：window7旗舰版
//实现语言：C语言
//班级：计算机XXX班
//学号：20XXXXXXXXXX
#include"stdafx.h"
#include
boolisEnd(int [],int );//判断是否结束
int_tmain(int argc, _TCHAR* argv[])
{
intA[4]={0,0,0,0};//定义人、狗、鸡、米的初始状态，此时四者都在此岸
//定义过渡状态，包括：人自己过河，人载狗过河，人载鸡过河，人载米过河，四种状态。
//注：其中最后的一维用来标记该向量是否已被使用，使用记为1，未使用记为0，在数组中即是a[x][4]存放的变量。
inta[4][5]={{1,0,0,0,0},{1,1,0,0,0},{1,0,1,0,0},{1,0,0,1,0}};
//保存输出的对应步骤的字符串
char* str[4]={"人划船过河","人划船载狗过河","人划船载鸡过河","人划船载米过河"};
//问题描述
printf(">>>>>>>>某日，路人甲在河边遇到了一个难题:\n");
printf("\t他带了三件物品：一只狗、一只鸡、一袋米要到河的对岸去，然而河边的\n");
printf("\t小船载重太小，每次只允许载三件物品里的一件过河。但是，人不在的\n");
printf("\t时候，鸡和米或狗和鸡在一边时，鸡会去吃米，狗会去咬鸡。\n");
printf(">>>>>>>>那么他该如何过河才能保证三件物品完好无损呢？\n");
printf("\n---解---过河步骤如下：\n");
//记录步骤
int n=1;
//开始进行状态转移
while(!isEnd(A,4)){
for(int i=0;i<4;i++){
//当过渡状态向量未被使用时
if(!a[i][4]){
//保存转换中间态
int B[4];
//异或运算，求转换态
for(int k=0;k<4;k++){
B[k]=A[k]^a[i][k] ;
}
//状态（1,0,0,x）是不允许的，此时人在河的彼岸，有没有载米过去，狗和鸡都会出现问题。
//状态（0,1,1,x）是不允许的，此时人在河的此岸，有没有载米回来，狗和鸡都会出现问题。
if((!B[1]&&!B[2]&&B[0])||(B[1]&&B[2]&&!B[0]))continue;
//状态（1,x,0,0）是不允许的，此时人在河的彼岸，有没有载狗过去，鸡和米都会出现问题。
//状态（0,x,1,1）是不允许的，此时人在河的此岸，有没有载狗回来，鸡和米都会出现问题。
elseif((!B[2]&&!B[3]&&B[0])||(B[2]&&B[3]&&!B[0]))continue;
//其它状态允许
else {
//改变状态
for(int j=0;j<4;j++){
A[j]=B[j];
}
//表示该状态已被使用
a[i][4]=1;
//输出对应的步骤描述
printf("\n-%d-%s\n",n,str[i]);//输出相应步骤
//步骤加一
n++;
}
}
//当过渡向量已被使用时，修改其使用状态值，以便于下一次使用。
else a[i][4]=0;
}
}
printf("\n----------------------此时，人、狗、鸡、米已全部过河！\n");
system("pause");
//结束
return 0;
}
boolisEnd(int L[],int n){//判断是否结束，只要状态向量有一个为零，即还未结束。
for(int i=0;i
//判断状态向量的各个值，为零即停止循环，返回false
if(!L[i])return false;
}
//状态向量的各个值都为1，这表示四者都已在彼岸。过河完成！
return true;
}
运行结果：
