过河算法

Ⅰ 有10个人要过河，河中有条船一次最多坐5个人，要过几次才可过去

有10个人要过河，河中有条船一次最多坐5个人，要过3次才可过去；

虽然船上每次能坐5个人，但在船返回时，必须有一个人跟着船一起返回；因此，每次只能有5-1=4（个）人过河；

计算如下：

10÷（5-1）=2次……2人

2+1=3次

计算的定义

计算的定义有许多种使用方式，有相当精确的定义，例如使用各种算法进行的“算术”，也有较为抽象的定义，例如在一场竞争中“策略的计算”或是“计算”两人之间关系的成功机率。

将7乘以8（7x8）就是一种简单的算术。数学中的计算有加，减，乘，除，乘方，开方等。其中加减乘除被称为四则运算。

利用布莱克-舒尔斯定价模型（Black-Scholes Model）来算出财务评估中的公平价格（fair price）就是一种复杂的算术。

从投票意向计算评估出的选举结果（民意调查）也包含了某种算术，但是提供的结果是“各种可能性的范围”而不是单一的正确答案。

决定如何在人与人之间建立关系的方式也是一种计算的结果，但是这种计算难以精确、不可预测，甚至无法清楚定义。这种可能性无限的计算定义，和以上提到的数学算术大不相同。

英文中的计算为“Calculation”，来自拉丁文中的“Calculus”，指的是算盘上用来计算的小石头。

Ⅱ 人带着羊狼青菜过河,算法编写

将这个问题转变成一个路径查找问题
起始点（1111）2进制表示起始状态，人 狼 羊 菜在左边，，终点（0000）2进制表示过河成攻
一共有2的4次方，也就是16个点，其中一部分状态不符合要求（可能是在岸左不符合要求，也可能是岸右不符合要求），根据题目要求排除这些点。点间路径可以用 异或 变换来获得，比如1100表示人和狼上船，与起始状态1111异或后变成0011，岸左剩下羊和菜，表示存在从点1111到0011的路径 。这一步要注意判断那些点存在哪些路径，比如：1010状态下就不存在1100这条路径。
路径有三种分别为1100，1010，1001。建立了无向图后，使用深搜广搜都可以。

Ⅲ 关于带钱袋过河的算法。

如果用脑，比较费力，如果用电脑，只不过是一个穷举法而已。

Ⅳ 求船夫渡河问题的算法 急！！！

先运羊到对岸去，然后空船回来，再运狼到对岸去，再将羊装上，载回去，将白菜运过去，现在对岸只有狼和白菜，现在空船回去，将羊再运过河去就行了。谢谢、

Ⅳ 野人过河新问题 算法

野人过河问题算法分析
野人过河问题算法分析

野人过河问题属于人工智能学科中的一个经典问题，问题描述如下： 有三个牧师（也有的翻译为传教士）和三个野人过河，只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有危险. 你能不能找出一种安全的渡河方法呢？
一、算法分析
先来看看问题的初始状态和目标状态，假设和分为甲岸和乙岸：
初始状态：甲岸，3野人，3牧师；
乙岸，0野人，0牧师；
船停在甲岸，船上有0个人；
目标状态：甲岸，0野人，0牧师；
乙岸，3野人，3牧师；
船停在乙岸，船上有0个人；
整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状态的改变是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的算符，根据题目要求，可以得出以下5个算符（按照渡船方向的不同，也可以理解为10个算符）：
渡1野人、渡1牧师、渡1野人1牧师、渡2野人、渡2牧师
算符知道以后，剩下的核心问题就是搜索方法了，本文采用深度优先搜索，通过一个FindNext(…)函数找出下一步可以进行的渡河操作中的最优操作，如果没有找到则返回其父节点，看看是否有其它兄弟节点可以扩展，然后用Process(…)函数递规调用FindNext(…)，一级一级的向后扩展。
搜索中采用的一些规则如下：
1、渡船优先规则：甲岸一次运走的人越多越好（即甲岸运多人优先），同时野人优先运走；
乙岸一次运走的人越少越好（即乙岸运少人优先），同时牧师优先运走；
2、不能重复上次渡船操作（通过链表中前一操作比较），避免进入死循环;
3、任何时候河两边的野人和牧师数均分别大于等于0且小于等于3；
4、由于只是找出最优解，所以当找到某一算符（当前最优先的）满足操作条件后，不再搜索其兄弟节点，而是直接载入链表。
5、若扩展某节点a的时候，没有找到合适的子节点，则从链表中返回节点a的父节点b，从上次已经选择了的算符之后的算符中找最优先的算符继续扩展b。

二、基本数据结构
仔细阅读问题，可以发现有些基本东西我们必须把握，例如：每时刻河两岸野人牧师各自的数目、船的状态、整个问题状态。所以我们定义如下几个数据结构：
typedef struct _riverside // 岸边状态类型
{
int wildMan; // 野人数
int churchMan; // 牧师数
}RIVERSIDE;
typedef struct _boat // 船的状态类型
{
int wildMan; // 野人数
int churchMan; // 牧师数
}BOAT;
typedef struct _question // 整个问题状态
{
RIVERSIDE riverSide1; // 甲岸
RIVERSIDE riverSide2; // 乙岸
int side; // 船的位置, 甲岸为-1, 乙岸为1
BOAT boat; // 船的状态
_question* pPrev; // 指向前一渡船操作
_question* pNext; // 指向后一渡船操作
}QUESTION;
用QUESTION来声明一个最基本的链表。

三、程序流程及具体设计
本文只找出了最优解，据我所知，本问题有三种解。如果真要找出这三种解，^_^，那就得加强对链表的操作了，比如说自己写一个动态链表类，顺便完成一些初始化工作，估计看起来会舒服些。
下面给出部分关键程序：
// 主函数
int main()
{
// 初始化
QUESTION* pHead = new QUESTION;
pHead->riverSide1.wildMan = 3;
pHead->riverSide1.churchMan = 3;
pHead->riverSide2.wildMan = 0;
pHead->riverSide2.churchMan = 0;
pHead->side = -1; // 船在甲岸
pHead->pPrev = NULL;
pHead->pNext = NULL;
pHead->boat.wildMan = 0;
pHead->boat.churchMan = 0;
if (Process(pHead))
{
// ......... 遍历链表输出结果
}
cout<<"成功渡河。";
}
else
cout<<"到底怎样才能渡河呢? 郁闷!"<<endl;
// 回收内存空间
while (pHead)
{
QUESTION* pTemp = pHead->pNext;
delete pHead;
pHead=pTemp;
}
pHead = NULL;
return 0;
}

// 渡船过程, 递规调用函数FindNext(...)

BOOL Process(QUESTION* pQuest)
{
if (FindNext(pQuest))
{
QUESTION* pNew = new QUESTION;
pNew->riverSide1.wildMan = pQuest->riverSide1.wildMan + pQuest->boat.wildMan*(pQuest->side);
pNew->riverSide1.churchMan = pQuest->riverSide1.churchMan + pQuest->boat.churchMan*(pQuest->side);
pNew->riverSide2.wildMan = 3 - pNew->riverSide1.wildMan;
pNew->riverSide2.churchMan = 3 - pNew->riverSide1.churchMan;
pNew->side = (-1)*pQuest->side;
pNew->pPrev = pQuest;
pNew->pNext = NULL;
pNew->boat.wildMan = 0;
pNew->boat.churchMan = 0;
pQuest->pNext = pNew;
if (pNew->riverSide2.wildMan==3 && pNew->riverSide2.churchMan==3)
return TRUE; // 完成
return Process(pNew);
}
else
{
QUESTION* pPrev = pQuest->pPrev;
if (pPrev == NULL)
return FALSE; // 无解
delete pQuest;
pPrev->pNext = NULL;
return Process(pPrev); // 返回其父节点重新再找
}
return TRUE;
}

// 判断有否下一个渡河操作, 即根据比较算符找出可以接近目标节点的操作
// 算符共5个: 1野/ 1牧 / 1野1牧 / 2野 / 2牧
BOOL FindNext(QUESTION* pQuest)
{
// 基本规则
// 渡船的优先顺序: 甲岸运多人优先, 野人优先; 乙岸运少人优先, 牧师优先.
static BOAT boatState[5]; // 5个算符
if (pQuest->side == -1)
{
boatState[0].wildMan = 2;
boatState[0].churchMan = 0;
boatState[1].wildMan = 1;
boatState[1].churchMan = 1;
boatState[2].wildMan = 0;
boatState[2].churchMan = 2;
boatState[3].wildMan = 1;
boatState[3].churchMan = 0;
boatState[4].wildMan = 0;
boatState[4].churchMan = 1;
}
else
{
boatState[0].wildMan = 0;
boatState[0].churchMan = 1;
boatState[1].wildMan = 1;
boatState[1].churchMan = 0;
boatState[2].wildMan = 0;
boatState[2].churchMan = 2;
boatState[3].wildMan = 1;
boatState[3].churchMan = 1;
boatState[4].wildMan = 2;
boatState[4].churchMan = 0;
}
int i; // 用来控制算符
if (pQuest->boat.wildMan == 0 && pQuest->boat.churchMan == 0) // 初始状态, 第一次渡河时
i = 0; // 取算符1
else
{
for (i=0; i<5; i++) // 扩展同一节点时, 已经用过的算符不再用, 按优先级来
if (pQuest->boat.wildMan == boatState[i].wildMan && pQuest->boat.churchMan == boatState[i].churchMan)
break;
i++;
}
if (i < 5)
{
int j;
for (j=i; j<5; j++)
{
int nWildMan1 = pQuest->riverSide1.wildMan + boatState[j].wildMan * pQuest->side;
int nChurchMan1 = pQuest->riverSide1.churchMan + boatState[j].churchMan * pQuest->side;
int nWildMan2 = 3 - nWildMan1;
int nChurchMan2 = 3 - nChurchMan1;
// 判断本次操作的安全性, 即牧师数量>=野人或牧师数为0
if ((nWildMan1 <= nChurchMan1 || nChurchMan1 == 0) &&
(nWildMan2 <= nChurchMan2 || nChurchMan2 == 0) &&
nWildMan1 >=0 && nChurchMan1 >=0 && nWildMan2 >=0 && nChurchMan2 >= 0)
{
// 本操作是否重复上次操作,注意方向不同
if (pQuest->pPrev != NULL)
{
if (pQuest->pPrev->boat.wildMan == boatState[j].wildMan &&
pQuest->pPrev->boat.churchMan == boatState[j].churchMan)
continue;
}
break; // 该操作可行, 推出循环，只找出当前最优节点
}
}
if (j < 5)
{
pQuest->boat.wildMan = boatState[j].wildMan;
pQuest->boat.churchMan = boatState[j].churchMan;
return TRUE;
}
}
return FALSE;

}

Ⅵ 算法“农夫过河”程序 望高手指错修改

v!=1111
能这么用么,这里的1111应该是十进制的1111了吧.
bitset没用过,不知道是不是要用
v.to_ulong()!=0x0F

算法上也有问题,就是当某种走法不成功时,退回上层递归后,没有回复到走之前的状态.应该设个临时变量等于v,对临时变量进行flip和search递归.

另外,采用某种走法前的判断if语句也有问题,比如v[farmer]==v[sheep],我们已经知道正确走法的第一步就是农夫和羊过,但第二步的时候, 农夫和羊都在对岸,值都是1,仍相等,就又都走回来了.

我个人认为,这个问题应该构造树,然后层次遍历,而现在的程序是深度优先遍历.

Ⅶ 高分跪求求过河问题程序算法！

paddy102的专栏

CSDNBlog | 我的首页 | 联系作者 | 聚合 | 登录 5篇文章 :: 0篇收藏:: 0篇评论:: 0个Trackbacks

文章
C++/Visual C++(RSS)
算法设计(RSS)
游戏开发(RSS)
收藏
相册
存档
2004年06月(4)
2004年04月(1)

野人过河问题算法分析
野人过河问题算法分析

野人过河问题属于人工智能学科中的一个经典问题，问题描述如下： 有三个牧师（也有的翻译为传教士）和三个野人过河，只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有危险. 你能不能找出一种安全的渡河方法呢？
一、算法分析
先来看看问题的初始状态和目标状态，假设和分为甲岸和乙岸：
初始状态：甲岸，3野人，3牧师；
乙岸，0野人，0牧师；
船停在甲岸，船上有0个人；
目标状态：甲岸，0野人，0牧师；
乙岸，3野人，3牧师；
船停在乙岸，船上有0个人；
整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状态的改变是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的算符，根据题目要求，可以得出以下5个算符（按照渡船方向的不同，也可以理解为10个算符）：
渡1野人、渡1牧师、渡1野人1牧师、渡2野人、渡2牧师
算符知道以后，剩下的核心问题就是搜索方法了，本文采用深度优先搜索，通过一个FindNext(…)函数找出下一步可以进行的渡河操作中的最优操作，如果没有找到则返回其父节点，看看是否有其它兄弟节点可以扩展，然后用Process(…)函数递规调用FindNext(…)，一级一级的向后扩展。
搜索中采用的一些规则如下：
1、渡船优先规则：甲岸一次运走的人越多越好（即甲岸运多人优先），同时野人优先运走；
乙岸一次运走的人越少越好（即乙岸运少人优先），同时牧师优先运走；
2、不能重复上次渡船操作（通过链表中前一操作比较），避免进入死循环;
3、任何时候河两边的野人和牧师数均分别大于等于0且小于等于3；
4、由于只是找出最优解，所以当找到某一算符（当前最优先的）满足操作条件后，不再搜索其兄弟节点，而是直接载入链表。
5、若扩展某节点a的时候，没有找到合适的子节点，则从链表中返回节点a的父节点b，从上次已经选择了的算符之后的算符中找最优先的算符继续扩展b。

二、基本数据结构
仔细阅读问题，可以发现有些基本东西我们必须把握，例如：每时刻河两岸野人牧师各自的数目、船的状态、整个问题状态。所以我们定义如下几个数据结构：
typedef struct _riverside // 岸边状态类型
{
int wildMan; // 野人数
int churchMan; // 牧师数
}RIVERSIDE;
typedef struct _boat // 船的状态类型
{
int wildMan; // 野人数
int churchMan; // 牧师数
}BOAT;
typedef struct _question // 整个问题状态
{
RIVERSIDE riverSide1; // 甲岸
RIVERSIDE riverSide2; // 乙岸
int side; // 船的位置, 甲岸为-1, 乙岸为1
BOAT boat; // 船的状态
_question* pPrev; // 指向前一渡船操作
_question* pNext; // 指向后一渡船操作
}QUESTION;
用QUESTION来声明一个最基本的链表。

三、程序流程及具体设计
本文只找出了最优解，据我所知，本问题有三种解。如果真要找出这三种解，^_^，那就得加强对链表的操作了，比如说自己写一个动态链表类，顺便完成一些初始化工作，估计看起来会舒服些。
下面给出部分关键程序：
// 主函数
int main()
{
// 初始化
QUESTION* pHead = new QUESTION;
pHead->riverSide1.wildMan = 3;
pHead->riverSide1.churchMan = 3;
pHead->riverSide2.wildMan = 0;
pHead->riverSide2.churchMan = 0;
pHead->side = -1; // 船在甲岸
pHead->pPrev = NULL;
pHead->pNext = NULL;
pHead->boat.wildMan = 0;
pHead->boat.churchMan = 0;
if (Process(pHead))
{
// ......... 遍历链表输出结果
}
cout<<"成功渡河。";
}
else
cout<<"到底怎样才能渡河呢? 郁闷!"<<endl;
// 回收内存空间
while (pHead)
{
QUESTION* pTemp = pHead->pNext;
delete pHead;
pHead=pTemp;
}
pHead = NULL;
return 0;
}

// 渡船过程, 递规调用函数FindNext(...)

BOOL Process(QUESTION* pQuest)
{
if (FindNext(pQuest))
{
QUESTION* pNew = new QUESTION;
pNew->riverSide1.wildMan = pQuest->riverSide1.wildMan + pQuest->boat.wildMan*(pQuest->side);
pNew->riverSide1.churchMan = pQuest->riverSide1.churchMan + pQuest->boat.churchMan*(pQuest->side);
pNew->riverSide2.wildMan = 3 - pNew->riverSide1.wildMan;
pNew->riverSide2.churchMan = 3 - pNew->riverSide1.churchMan;
pNew->side = (-1)*pQuest->side;
pNew->pPrev = pQuest;
pNew->pNext = NULL;
pNew->boat.wildMan = 0;
pNew->boat.churchMan = 0;
pQuest->pNext = pNew;
if (pNew->riverSide2.wildMan==3 && pNew->riverSide2.churchMan==3)
return TRUE; // 完成
return Process(pNew);
}
else
{
QUESTION* pPrev = pQuest->pPrev;
if (pPrev == NULL)
return FALSE; // 无解
delete pQuest;
pPrev->pNext = NULL;
return Process(pPrev); // 返回其父节点重新再找
}
return TRUE;
}

// 判断有否下一个渡河操作, 即根据比较算符找出可以接近目标节点的操作
// 算符共5个: 1野/ 1牧 / 1野1牧 / 2野 / 2牧
BOOL FindNext(QUESTION* pQuest)
{
// 基本规则
// 渡船的优先顺序: 甲岸运多人优先, 野人优先; 乙岸运少人优先, 牧师优先.
static BOAT boatState[5]; // 5个算符
if (pQuest->side == -1)
{
boatState[0].wildMan = 2;
boatState[0].churchMan = 0;
boatState[1].wildMan = 1;
boatState[1].churchMan = 1;
boatState[2].wildMan = 0;
boatState[2].churchMan = 2;
boatState[3].wildMan = 1;
boatState[3].churchMan = 0;
boatState[4].wildMan = 0;
boatState[4].churchMan = 1;
}
else
{
boatState[0].wildMan = 0;
boatState[0].churchMan = 1;
boatState[1].wildMan = 1;
boatState[1].churchMan = 0;
boatState[2].wildMan = 0;
boatState[2].churchMan = 2;
boatState[3].wildMan = 1;
boatState[3].churchMan = 1;
boatState[4].wildMan = 2;
boatState[4].churchMan = 0;
}
int i; // 用来控制算符
if (pQuest->boat.wildMan == 0 && pQuest->boat.churchMan == 0) // 初始状态, 第一次渡河时
i = 0; // 取算符1
else
{
for (i=0; i<5; i++) // 扩展同一节点时, 已经用过的算符不再用, 按优先级来
if (pQuest->boat.wildMan == boatState[i].wildMan && pQuest->boat.churchMan == boatState[i].churchMan)
break;
i++;
}
if (i < 5)
{
int j;
for (j=i; j<5; j++)
{
int nWildMan1 = pQuest->riverSide1.wildMan + boatState[j].wildMan * pQuest->side;
int nChurchMan1 = pQuest->riverSide1.churchMan + boatState[j].churchMan * pQuest->side;
int nWildMan2 = 3 - nWildMan1;
int nChurchMan2 = 3 - nChurchMan1;
// 判断本次操作的安全性, 即牧师数量>=野人或牧师数为0
if ((nWildMan1 <= nChurchMan1 || nChurchMan1 == 0) &&
(nWildMan2 <= nChurchMan2 || nChurchMan2 == 0) &&
nWildMan1 >=0 && nChurchMan1 >=0 && nWildMan2 >=0 && nChurchMan2 >= 0)
{
// 本操作是否重复上次操作,注意方向不同
if (pQuest->pPrev != NULL)
{
if (pQuest->pPrev->boat.wildMan == boatState[j].wildMan &&
pQuest->pPrev->boat.churchMan == boatState[j].churchMan)
continue;
}
break; // 该操作可行, 推出循环，只找出当前最优节点
}
}
if (j < 5)
{
pQuest->boat.wildMan = boatState[j].wildMan;
pQuest->boat.churchMan = boatState[j].churchMan;
return TRUE;
}
}
return FALSE;

}

Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=21630

[点击此处收藏本文] 发表于 2004年04月07日 2:18 PM

没有评论。
发表评论

大名：
请输入尊姓大名
网址：
验证码
评论
请输入评论

记住我？

--------------------------------------------------------------------------------
网站简介－广告服务－网站地图－帮助信息－联系方式－English－问题报告

CSDN北京百联美达美数码科技有限公司 版权所有 京 ICP 证 020026 号 CSDN

&; 2000-04, CSDN.NET, All Rights Reserved

--------------------------------------------------------------------------------

Copyright &; paddy102 Powered By .Text

Ⅷ 猴子过河 java算法

importjava.util.Arrays;
importjava.util.List;
importjava.util.Stack;

publicclassMonkey{
publicString[]monkeys={"a","b","c","A","B","C"};

Rulerule1=newRule1();

Rulerule2=newRule2();

publicintcount=0;

publicStringBuffersuccess=newStringBuffer(2000);

publicvoidboat(){
Stack<String>left=newStack<String>();
Stack<String>right=newStack<String>();
for(inti=0;i<monkeys.length;i++){
left.add(monkeys[i]);
}
go(left,right,"");
System.out.println("***********************共"+count+"种成功方案***********************");
System.out.println(success.toString());
System.out.println("***********************共"+count+"种成功方案***********************");

}

privatevoidgo(Stack<String>left,Stack<String>right,Strings){
for(inti=0;i<left.size();i++){
Stringmonkey1=left.get(i);
for(intj=i+1;j<left.size();j++){
StringBuffersb=newStringBuffer();
Stringmonkey2=left.get(j);
sb.append(s);
sb.append(monkey1);
sb.append(monkey2);
sb.append("->");
sb.append("");
if((rule1.isCanBoat(monkey1,monkey2,sb))&&(rule2.isCanBoat(monkey1,monkey2,sb))){
Stack<String>nextLeft=newStack<String>();
Stack<String>nextRight=newStack<String>();
nextLeft.addAll(left);
nextRight.addAll(right);
nextLeft.remove(monkey1);
nextLeft.remove(monkey2);

nextRight.push(monkey1);
nextRight.push(monkey2);

if(nextLeft.size()==0){
success.append(sb.toString()+nextLeft.toString()+nextRight.toString());
success.append("
");
count++;
continue;
}
back(nextLeft,nextRight,sb.toString());
}
}
}

}

privatevoidback(Stack<String>left,Stack<String>right,Strings){
for(inti=0;i<right.size();i++){
Stringmonkey1=right.get(i);
StringBuffersb=newStringBuffer();
sb.append(s);
sb.append(monkey1);
sb.append("<-");
sb.append("");
if(rule2.isCanBoat(monkey1,monkey1,sb)){
Stack<String>nextLeft=newStack<String>();
Stack<String>nextRight=newStack<String>();
nextLeft.addAll(left);
nextRight.addAll(right);
nextLeft.push(monkey1);
nextRight.remove(monkey1);
go(nextLeft,nextRight,sb.toString());
}
}
}

publicstaticvoidmain(String[]args){
Monkeymonkey=newMonkey();
monkey.boat();
}
}

interfaceRule{
booleanisCanBoat(Stringm1,Stringm2,StringBuffersb);
}

classRule1implementsRule{

String[]childMonkeys={"a","b","c"};

String[]monkeys={"A","B","C"};

publicbooleanisCanBoat(Stringm1,Stringm2,StringBuffersb){

if(m1.toLowerCase().equals(m2.toLowerCase())){
returntrue;
}
List<String>childMonkeysList=Arrays.asList(childMonkeys);
List<String>monkeysList=Arrays.asList(monkeys);
if((monkeysList.contains(m1)&&monkeysList.contains(m2))
||(childMonkeysList.contains(m1)&&childMonkeysList.contains(m2))){
returntrue;
}
sb.append("大猴欺负小猴！");
System.out.println(sb.toString());
returnfalse;
}

}

classRule2implementsRule{

String[]smartMonkeys={"A","B","C","a"};

publicbooleanisCanBoat(Stringm1,Stringm2,StringBuffersb){
List<String>smartMonkeysList=Arrays.asList(smartMonkeys);

if(smartMonkeysList.contains(m1)||smartMonkeysList.contains(m2)){
returntrue;
}
sb.append("没有会划船的猴子！");
System.out.println(sb.toString());
returnfalse;
}

}

Ⅸ 三个强盗三个商人过河 简单的入门级别算法

3个商人和3个强盗要过一条河,如果在河的任意一边商人数目比强盗少,商人就会被抢劫,如何过河?

河边有一只小船，小船上原本无人，小船最多能坐2人，他们都不会去游泳，要保证商人不会被抢劫。

先简化一下商人和强盗：

商人为0 强盗为X 河为-

初始情况：商人和强盗都在河的一边，即000xxx-

操作步骤：

1商人1强盗过去 一商人回000xx-x

2强盗过去 1强盗回 000x-xx

2商人过去 1商人1强盗回 00xx-x0

2商人过去 1强盗回 xxx-000

2强盗过去 1强盗回 xx-000x

2强盗过去 完毕 -xxx000

Ⅹ 人鬼过河 算法 c或java

import java.util.*;

public class RiverGame {
private boolean sf = true;
private final int pairs;
private final String PERSON = "1"; // 人
private final String GHOST = "2"; // 鬼
private List<String> leftCount; // 开始的岸上的人和鬼集合
private List<String> middleCount; // 船上的人和鬼集合
private List<String> rightCount; // 到达的岸上的人和鬼集合

public RiverGame (){
this(0);
}
public RiverGame (int count) {
if(count<3){
pairs = 3;
}else{
pairs = count;
}
leftCount = new ArrayList<String>();
for (int i = 0; i < pairs; i++) {
leftCount.add(PERSON);
leftCount.add(GHOST);
}
middleCount = new ArrayList<String>();
rightCount = new ArrayList<String>();
}

public int getCount(List<String> list, String name) {
int count = 0;
for (String s : list) {
if (name.equals(s)) {
count++;
}
}
return count;
}

public void leftToMiddle(String str1,String str2,int step){
int personCount = 0;
int ghostCount = 0;
if(str1.equals(PERSON)){
personCount++;
}else{
ghostCount++;
}
leftCount.remove(str1);
middleCount.add(str1);
if(str2 != null&&str2.equals(PERSON)){
personCount++;
leftCount.remove(str2);
middleCount.add(str2);
}else if(str2 != null&&str2.equals(GHOST)){
ghostCount++;
leftCount.remove(str2);
middleCount.add(str2);
}
System.out.println("第"+step+"步：");
System.out.print((personCount>0?personCount+"人":"")+(ghostCount>0?ghostCount+"鬼":"")+"上船 ");
printc("过河 ");
}

public void middleToRight(String str1,String str2){
int personCount = 0;
int ghostCount = 0;
if(str1.equals(PERSON)){
personCount++;
}else{
ghostCount++;
}
middleCount.remove(str1);
rightCount.add(str1);
if(str2 != null&&str2.equals(PERSON)){
personCount++;
middleCount.remove(str2);
rightCount.add(str2);
}else if(str2 != null&&str2.equals(GHOST)){
ghostCount++;
middleCount.remove(str2);
rightCount.add(str2);
}
System.out.print((personCount>0?personCount+"人":"")+(ghostCount>0?ghostCount+"鬼":"")+"上岸; ");
}

public void rightToMiddle(String str){
if(str != null){
rightCount.remove(str);
middleCount.add(str);
System.out.print(1+(str.equals(PERSON)?"人":"鬼")+"上船 ");
}
printc("回来 ");
}

public void middleToLeft(String str){
if(str != null){
middleCount.remove(str);
leftCount.add(str);
System.out.print(1+(str.equals(PERSON)?"人":"鬼")+"上岸 ");
}
System.out.println();
}

private void printc(String s){
int personCount = getCount(middleCount, PERSON);
int ghostCount = getCount(middleCount, GHOST);
System.out.print((personCount>0?personCount+"人":"")+(ghostCount>0?ghostCount+"鬼":"")+" "+s);
if(leftCount.contains(PERSON)&&getCount(leftCount, GHOST)>getCount(leftCount, PERSON)){
sf = false;
}else if(rightCount.contains(PERSON)&&getCount(rightCount, GHOST)>getCount(rightCount, PERSON)){
sf = false;
}
}

public void crossRiver() {
int step = 0;
while(leftCount.size() != 0){
step++;
if(leftCount.size()==pairs*2){
leftToMiddle(GHOST, GHOST,step);
middleToRight(GHOST,null);
rightToMiddle(null);
middleToLeft(null);
}else if(getCount(leftCount, PERSON)-2==getCount(leftCount, GHOST)&&middleCount.size()!=0){
leftToMiddle(GHOST, null,step);
middleToRight(GHOST,null);
rightToMiddle(null);
middleToLeft(GHOST);
}else if(getCount(leftCount, PERSON)-2==getCount(leftCount, GHOST)&&middleCount.size()==0){
leftToMiddle(PERSON, PERSON,step);
middleToRight(PERSON,null);
rightToMiddle(GHOST);
middleToLeft(GHOST);
}
else if(getCount(leftCount, PERSON)>getCount(leftCount, GHOST)){
leftToMiddle(PERSON, null,step);
middleToRight(PERSON,null);
rightToMiddle(null);
middleToLeft(null);
}else if(leftCount.contains(PERSON)){
leftToMiddle(PERSON, null, step);
middleToRight(PERSON,PERSON);
rightToMiddle(GHOST);
middleToLeft(null);
}else{
leftToMiddle(GHOST, null, step);
if(leftCount.size()==0){
middleToRight(GHOST,GHOST);
}else{
middleToRight(GHOST,null);
}
rightToMiddle(null);
middleToLeft(null);
}
if(!sf){
System.out.println("过河失败！！！");
return;
}
}
System.out.println("成功过河了！");
}

public static void main(String[] args) {
RiverGame gr = new RiverGame ();
gr.crossRiver();
}
}

第1步：
2鬼上船 2鬼 过河 1鬼上岸; 1鬼 回来
第2步：
1鬼上船 2鬼 过河 1鬼上岸; 1鬼 回来 1鬼上岸
第3步：
2人上船 2人 过河 1人上岸; 1鬼上船 1人1鬼 回来 1鬼上岸
第4步：
1人上船 2人 过河 2人上岸; 1鬼上船 1鬼 回来
第5步：
1鬼上船 2鬼 过河 1鬼上岸; 1鬼 回来
第6步：
1鬼上船 2鬼 过河 2鬼上岸; 回来
成功过河了！