传教士和野人过河问题

qyxqyxqyx 2012-10-12 10:17:12
加精
M个传教士,C个野人,M>=C,船上能载2人,要求过河时,传教士不能少于野人个数,否则被吃掉。怎么过河?
我看网上说这好像是一个经典问题,请问哪儿有详细的解法和源代码啊
今天360的笔试题~~~~~考这个了,感觉小本好像吃亏不少
...全文
31154 210 打赏 收藏 转发到动态 举报
写回复
用AI写文章
210 条回复
切换为时间正序
请发表友善的回复…
发表回复
Eleve 2014-01-17
  • 打赏
  • 举报
回复
《算法珠玑》里有讲过这个。
tiancai110a 2013-11-27
  • 打赏
  • 举报
回复
引用 71 楼 DelphiGuy 的回复:
[Quote=引用 69 楼 的回复:] M==C时好像无解 [/Quote] 2、3时有解。
M=C=3的时候怎么解啊
tornadomeet 2013-09-25
  • 打赏
  • 举报
回复
引用 76 楼 paces 的回复:
如果 野人也会开船的话那44是可以 的 1.两个野人过河 一个野人返回 2.一个野人一个传教士 一个野人返回 3.重复2 4.重复1 5.重复2 6.重复1 7.野人与传教士 不要返回了
步骤3有问题,那样的话左边的传教士挂了
tornadomeet 2013-09-25
  • 打赏
  • 举报
回复
引用 2 楼 zoeg 的回复:
1、首先由1传教士+1野蛮人过河,船在目的地; 2、此时始发地传教士>野蛮人,目的地传教士=野蛮人; 3、无论后续如何装卸,都必须是1个人回,两个人去,那么可以经过一定的等效转换,也就是一回一去的周期内,只过一个人; 4、由于目的地两种人数相等,因此需要考虑先运传教士; 5、循环运送传教士、野蛮人、传教士、野蛮人,知道始发地只剩下传教士; 6、由一个野蛮人不断将所有传教士运往目的地。 题目本身很简单,非要用代码来表达,似乎没有什么逻辑是需要程序计算的; 如果是强调编程的题目,那就应该是教程序如何来解答这个题目,而不能像人思考那样把所有的特例都利用起来,程序解逻辑应该包含一个变量:船的容量N为各种值时,程序依然工作,否则真不知道程序在这个题目还能写些什么!
引用 2 楼 zoeg 的回复:
1、首先由1传教士+1野蛮人过河,船在目的地; 2、此时始发地传教士>野蛮人,目的地传教士=野蛮人; 3、无论后续如何装卸,都必须是1个人回,两个人去,那么可以经过一定的等效转换,也就是一回一去的周期内,只过一个人; 4、由于目的地两种人数相等,因此需要考虑先运传教士; 5、循环运送传教士、野蛮人、传教士、野蛮人,知道始发地只剩下传教士; 6、由一个野蛮人不断将所有传教士运往目的地。 题目本身很简单,非要用代码来表达,似乎没有什么逻辑是需要程序计算的; 如果是强调编程的题目,那就应该是教程序如何来解答这个题目,而不能像人思考那样把所有的特例都利用起来,程序解逻辑应该包含一个变量:船的容量N为各种值时,程序依然工作,否则真不知道程序在这个题目还能写些什么!
你的条件2不一定成立,可以相等。
healhaha 2012-12-09
  • 打赏
  • 举报
回复
顶一个,学习下!
jyybpd 2012-11-01
  • 打赏
  • 举报
回复
好像很厉害
of123 2012-11-01
  • 打赏
  • 举报
回复
[Quote=引用 100 楼 的回复:]
不是M>C么,一直让一个传教士当船工然后野人传教士不断轮换的运送就完了啊
[/Quote]

不行,假如先渡野人,当传教士船工把第二个野人渡过去返航时,彼岸就是两个野人对一个传教士,把他吃掉了。

如果按你的方法先渡传教士,又假如传教士只比野人多一个,当传教士船工第三船渡传教士的时候,船上加上彼岸的传教士与野人之比是 3 比 1,也就是说,此岸上野人比传教士多了……
KyleWlk 2012-10-31
  • 打赏
  • 举报
回复
好像是一道经典的算法题
LAONINGA098 2012-10-31
  • 打赏
  • 举报
回复
好像很厉害
zgy_adapter 2012-10-31
  • 打赏
  • 举报
回复
在上下船的过程不发生吃人的事件那就M=C=4就有解了~~好纠结的问题啊!!!
仲翰藻8 2012-10-31
  • 打赏
  • 举报
回复
1、首先由1传教士+1野蛮人过河,船在目的地;
2、此时始发地传教士>野蛮人,目的地传教士=野蛮人;
3、无论后续如何装卸,都必须是1个人回,两个人去,那么可以经过一定的等效转换,也就是一回一去的周期内,只过一个人;
4、由于目的地两种人数相等,因此需要考虑先运传教士;
5、循环运送传教士、野蛮人、传教士、野蛮人,知道始发地只剩下传教士;
6、由一个野蛮人不断将所有传教士运往目的地。

题目本身很简单,非要用代码来表达,似乎没有什么逻辑是需要程序计算的;
如果是强调编程的题目,那就应该是教程序如何来解答这个题目,而不能像人思考那样把所有的特例都利用起来,程序解逻辑应该包含一个变量:船的容量N为各种值时,程序依然工作,否则真不知道程序在这个题目还能写些什么!
Ahh_Freshmeat 2012-10-30
  • 打赏
  • 举报
回复
牛啊

[Quote=引用 6 楼 的回复:]

很基础的人工智能例题,定义出状态与转换规则,就可以等价变换为一道搜索题

比如可以用2维坐标(传教士,狼)来表示数量,那刚开始的时候,出发地就是S=(M,C),目的地是T=(0,0),船上的人是B=(b1,b2)。所以这道题就变成了:遍历所有T=T+B, T-B的情况,最终让T变为(M,C),相应的S=(0,0)

还有些限制条件,“船上能载2人”:b1+b2<=2

“过河时,传……
[/Quote]
qqy28 2012-10-29
  • 打赏
  • 举报
回复
这个是个老问题了,不难啊!
china_clear 2012-10-29
  • 打赏
  • 举报
回复
这只能算是个数学问题,用计算机实现其实已经是用数学解决好了,只是按步骤一步一步执行而已
_DennisYu 2012-10-29
  • 打赏
  • 举报
回复
a*算法吧
comeandgo201205 2012-10-29
  • 打赏
  • 举报
回复
很经典,顶一下。
zhireide 2012-10-29
  • 打赏
  • 举报
回复
小时候听过一个一农夫带一只羊和一只狼和一棵白菜过河的比这个简单。
bjliuzg 2012-10-29
  • 打赏
  • 举报
回复
楼上的不对吧,要是传教士只比野人多一人,把一个传教士当船夫,始终会出现一岸野人多余传教士的。
hg2980986 2012-10-27
  • 打赏
  • 举报
回复
s8520789 2012-10-27
  • 打赏
  • 举报
回复
太复杂
加载更多回复(164)

33,006

社区成员

发帖
与我相关
我的任务
社区描述
数据结构与算法相关内容讨论专区
社区管理员
  • 数据结构与算法社区
加入社区
  • 近7日
  • 近30日
  • 至今
社区公告
暂无公告

试试用AI创作助手写篇文章吧