囚犯过河问题-逻辑题

某日，某公司，遇到一面试题：
有三个看守和三个囚犯要过河，有一条船，船上一次只能载2个人。船上和岸上都不能出现囚犯多于看守的情况，否则看守会被干掉。问用什么方法可以让大家安全过河。

我推了十来分钟，结论是无解。问了面试官，他说有解，让我上网查查。但是确实无解。
不管怎么运，都有囚犯单独呆的机会，那么他就会逃跑。所以是无解。
如有高人认为有解，请出来证明。面试官要在javaeye上，也想看看他的解。

评论

13 楼 jxygjzh 2011-03-03  

没说警察必须看着罪犯  只能这样考虑：

3警察3罪犯  0警察0罪犯   2个罪犯过去 1个罪犯返回 -->

3警察2罪犯  0警察1罪犯   2个罪犯过去 1个罪犯返回 -->

3警察1罪犯  0警察2罪犯   2个警察过去 1警察1罪犯返回 -->

2警察2罪犯  1警察1罪犯   2个警察过去 1个罪犯返回 -->

0警察3罪犯  3警察0罪犯  ...

然后 就是罪犯上去罪犯回去了..

12 楼 败家小孩 2011-03-03  

diferent 写道

败家小孩 写道

一囚一看守过河不成，不正好一对一对吗

那得有三条船...

他也没说不能空船再回来，一看守一囚犯过了河再空船回来，呵呵，如果不行，好像真误解

11 楼 guozq518 2011-03-03  

应该是船上可以载三人吧

10 楼 interjc 2011-03-03  

最好的办法是用绳子，把囚犯绑起来

9 楼 diferent 2011-03-03  

败家小孩 写道

一囚一看守过河不成，不正好一对一对吗

那得有三条船...

8 楼 interjc 2011-03-03  

mengdboy 写道

2囚 船过岸-->一囚回-->再一囚一看守船过河-->那一囚回-->此时对岸一看守一囚  这边两看守两囚
再一囚一看守船过河-->一囚回-->再两囚过河-->一囚回-->最后一囚一 看守过河-->完成过河!

1囚回去的时候，那边就是3囚对2警了，警会被干掉

7 楼 败家小孩 2011-03-03  

一囚一看守过河不成，不正好一对一对吗

6 楼 diferent 2011-03-03  

mengdboy 写道

fastbo 写道

mengdboy 写道

2囚 船过岸-->一囚回-->再一囚一看守船过河-->那一囚回-->此时对岸一看守一囚  这边两看守两囚
再一囚一看守船过河-->一囚回-->再两囚过河-->一囚回-->最后一囚一 看守过河-->完成过河!

2囚过岸，人都跑了，船也弃了。其它人游过来了吧。

照这样想的话根本就过不了河,看守只要不要干掉就可以拉,囚犯肯定不敢跑的 直接有瞄准器监视撒?

就算两囚不跑~
一囚一看守到对岸(船第二次到对岸的时候)~
看守也被弄死了啊.
这个题~ 很差劲~ 和 农夫 那个差好多.
设计题目的人~思想就很不正常吧~
"岸上船上都不能出现囚犯多于看守的情况"~船上只能两个人,怎么可能出现囚犯多于看守的情况,楼主记错了题 ? 还是出题的人 脑子秀了

5 楼 zpl3001 2011-03-03  

无解，不解释
          

4 楼 greenpower 2011-03-03  

很简单的状态机问题，至少10年前的老题目了

3 楼 mengdboy 2011-03-03  

fastbo 写道

mengdboy 写道

2囚 船过岸-->一囚回-->再一囚一看守船过河-->那一囚回-->此时对岸一看守一囚  这边两看守两囚
再一囚一看守船过河-->一囚回-->再两囚过河-->一囚回-->最后一囚一 看守过河-->完成过河!

2囚过岸，人都跑了，船也弃了。其它人游过来了吧。

照这样想的话根本就过不了河,看守只要不要干掉就可以拉,囚犯肯定不敢跑的 直接有瞄准器监视撒?

2 楼 fastbo 2011-03-03  

mengdboy 写道

2囚 船过岸-->一囚回-->再一囚一看守船过河-->那一囚回-->此时对岸一看守一囚  这边两看守两囚
再一囚一看守船过河-->一囚回-->再两囚过河-->一囚回-->最后一囚一 看守过河-->完成过河!

2囚过岸，人都跑了，船也弃了。其它人游过来了吧。

1 楼 mengdboy 2011-03-03  

2囚 船过岸-->一囚回-->再一囚一看守船过河-->那一囚回-->此时对岸一看守一囚  这边两看守两囚
再一囚一看守船过河-->一囚回-->再两囚过河-->一囚回-->最后一囚一 看守过河-->完成过河!