查看: 126575|回复: 18

过河问题，听过吗？ [复制链接]

刚吃完

白魔

Rank: 1

积分: 109
帖子: 98
精华: 0
UID: 41408
性别: 保密

电梯直达

1^#

发表于 2008-8-26 17:24:39 |只看该作者 |倒序浏览

三个野人三个牧师过一条河，
只有一条船，船只能坐两个人。
所有人都会划船。
在任何情况下野人的数量不能超过牧师，
否则野人会吃掉牧师。
问怎样过河？
(请忽略种族歧视的含义)

收藏0

使用道具举报

溪风

铜魔

批发零售加团购

Rank: 8 Rank: 8

积分: 9635
帖子: 5813
精华: 10
UID: 32603
性别: 男
居住地: 沈阳市
WCA ID: 扯
兴趣爱好: 其它

2^#

发表于 2008-8-26 17:26:19 |只看该作者

先抢了再看看是什么，呵

教好魔方，办好比赛，做好推广。全天，全年，全力。
飞速店：沈阳太原街中山路新华购收中4楼1330817281
魔方飞速叠杯批发零售团购；专业少儿魔方培训Q：4995657
对社会各界开展魔方相关活动合作！欢迎洽谈！

使用道具举报

独树

蓝魔

Rank: 2

积分: 368
帖子: 343
精华: 0
UID: 26153
性别: 保密

3^#

发表于 2008-8-26 17:27:29 |只看该作者

抢个沙发请问楼主你给发的更简单的方法是什么意思？？

用自身的缺点去撞别人的优点以此砥砺自我

使用道具举报

kexin_xiao

银魔

小欣然的爸爸

Rank: 7 Rank: 7 Rank: 7

积分: 37843
帖子: 34374
精华: 15
UID: 16477
性别: 保密

4^#

发表于 2008-8-26 17:32:48 |只看该作者

1、一野人一牧师过，野人上岸 
2、牧师回，上岸，两野人过去，一野人上岸一野人回 
3、野人上岸，两牧师上船，一牧师上岸，一野人一牧师回，一野人上岸两牧师上船 
4、两牧师上岸，野人上船去接其他野人

[ 本帖最后由 kexin_xiao 于 2008-8-26 17:38 编辑 ]

天津1群11471969，2群5834223
3群62462688，4群62462702
5群70735234，6群33712046
7群12240584，8群29198783
9群62974165，欢迎加入！

使用道具举报

刚吃完

白魔

Rank: 1

积分: 109
帖子: 98
精华: 0
UID: 41408
性别: 保密

5^#

发表于 2008-8-26 17:38:43 |只看该作者

我见过回答最快的。

厉害，你以前没看过的话，你简直是天才。
我见过回答最快的。

使用道具举报

qinguaidang

蓝魔

Rank: 2

积分: 549
帖子: 488
精华: 0
UID: 38067
性别: 男

6^#

发表于 2008-8-26 17:39:34 |只看该作者

4#的解法差不多，有道理
以前见过这种问题
就是想不起来了
欣然说得貌似是最佳的

使用道具举报

kexin_xiao

银魔

小欣然的爸爸

Rank: 7 Rank: 7 Rank: 7

积分: 37843
帖子: 34374
精华: 15
UID: 16477
性别: 保密

7^#

发表于 2008-8-26 17:47:17 |只看该作者

我也修改了一下，最后一步刚开始写错了，忘了写野人划船回来了，呵呵，船自己回来多好啊，可以省一步，呵呵

天津1群11471969，2群5834223
3群62462688，4群62462702
5群70735234，6群33712046
7群12240584，8群29198783
9群62974165，欢迎加入！

使用道具举报

金眼睛

蓝魔

Rank: 2

积分: 421
帖子: 233
精华: 2
UID: 25681
性别: 保密

8^#

发表于 2008-8-26 18:04:21 |只看该作者

前面已经有类似的题了，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/lol.gif" border=0 smilieid="12"> 
思路：(Ctrl+A可见)
过河问题有一个中间对称状态，即A(原来)，B(到达)两岸对等。对于这道题，一定是两岸以及船上各一个野人和牧师。
假设当船在B岸，且B岸上有两个野人和牧师为上一状态。
再往前推，一定是两个牧师将船划过来的，也就是说A岸上原来有三个牧师，一个野人。
再往前就很简单了，A岸上有三个牧师，肯定不会数量不占优，野人们自己去随便渡吧，呵呵！
最后将如何实现中间对称状态的步骤反向操作，就可以全部渡到B岸了。
 
假设当船在A岸，且A岸上有两个野人和牧师为上一状态。
再往前推，一定是B岸上原来有三个牧师，一个野人。可见两岸状态反了。

使用道具举报