洛译小筑

别来无恙,我的老友…
随笔 - 45, 文章 - 0, 评论 - 172, 引用 - 0
数据加载中……

神秘的村庄,聪明的村民,得病的狗,正午的枪声

记得这是在大四上半年晚上开卧谈会的时候我们宿舍一个大能人给我们出的题,今天突然想起来:

从前有一个村庄,村庄里有若干个村民,村民都非常的聪明,对于各种复杂的问题他们都能够仔细的观察,并能做出你所能做的一切分析和判断,他们每个人都养且仅养一条狗。有一天,所有的村民接到了一条确切的消息:村里的狗中有若干条得了一种病(这种病不会传染)。要求由且仅由这些村民自己找出这些病狗,他们每天上午要检查除了自己的狗以外所有的狗。村民之间不许交谈,如果一个村民通过观察分析,判断出了自己的狗是病狗,那他就开枪打死这只狗,但任何人不许打死别人的狗。排查工作就这样开始了,第一天没有枪响,第二天也没有枪响,第三天的正午,所有人都听到了“砰……”的一阵枪响。请问:村子里共有多少条病狗?

后来知道了这个问题是 IBM 公司的一道面试题。答案是 3 条。解决的方法如下,按假设病狗数量不断推论:

假设病狗数为 1 ,那么在第一天这条病狗的主人就会发现:除了他自己的狗以外所有的狗都没有病,然而病狗确实是存在的,因此这个村民就会做出推断,自己的狗就是病狗。他就会开枪打死它。然而第一天没有枪响,我们要继续假设。

假设病狗数为 2 ,大多数人都会发现这 2 条病狗,但会有且仅会有两个村民只看到了 1 条病狗(因为他们自己的狗也是病狗,显然地,他们所看到的病狗是彼此对方的)。我们考虑这两个村民中的一个人,在第一天,他暂时还不能断定自己的狗是否有病,但他可以假设:他所看到的这条病狗就是村里唯一的病狗;然后就此做出上一自然段(假设病狗数为 1 )中的分析:如果真的是这样,那这个病狗的主人也会发现自己的狗是病狗(因为病狗的主人不会看到其他的狗生病)。在今晚,病狗的主人就会把它处死。然而,在他第二天出去检查的时候,发现所有的狗都活得好好的。他会做出判断:先前的假设是错误的,村子里的病狗不仅仅是一条,但是第一天在他去检查时的确仅发现了 1 条病狗,因此很明显地,自己的狗一定就是病狗。这条可怜的狗也会被处决。但是第二天仍没有枪响。需要继续假设。

假设病狗数为 3 ,大多数人会看到 3 条病狗,有 3 位村民只看到 2 条。在你做出分析的同时,村民也在进行着同样缜密的推理。这 3 位村民会做出上一自然段(假设病狗数为 2 )中的分析,他们一定知道,如果第二天有狗被处决的话,那么他们的假设就成立。然而等到了第三天去检查的时候,发现没有狗被处死,那足以证明自己的狗也是病狗。他们会在第三天开枪。假设成立,原题得解。

你也许能够发现,上述三段分析中,后一段都会借助前边的那一段来分析。这俨然是一个递归问题。假设病狗数为 n ,如果 n==0 则执行操作,跳出递归,如果 n>0 则递归 (n-1) 的情况。把当前的状况用一个三元组来表示 ( d , 总共看到 t 条狗 , 其中有 s 条有病 ) ,下面是伪代码:

bool assume(day, total, sick) {

  if ( sick == 0 ) { shoot(hisDog); return true; }

  else {

if( assume(day+1, total-1, sick-1) ) return false;

else { shoot(hisDog); return true; }

}

今天早上起来发现新买的 n73 不见了,可把我给急坏了,我拿来笤帚用笤帚把在床底下不断地扫,最后只扫出了几个玻璃球、一只袜子、几张涂满鸦的破纸,一大堆土。后来发现桌上躺着那个 old pal 2610 ,我才恍然大悟,原来是个梦啊。哼哼,太有意思了。

都说有钱人,尤其是实打实地干出来的有钱人从来不乱花钱,他们的钱都是血汗,哪舍得花啊,哪有时间花啊。乱花钱,那是纨绔子弟,是暴发户。北京月入 10k 的大牛还有挤公交车的,人家 手机之父 马丁 库贝先生还会用几百块钱(折合成人民币)的破手机呢。

我还是个并且在未来的很长时间以内都将是个对当前的不好不坏的日子很满足但是对未来的美好生活充满期待的穷光蛋……

posted on 2007-04-21 18:15 ★ROY★ 阅读(1109) 评论(9)  编辑 收藏 引用 所属分类: 饭后茶余

评论

# re: 神秘的村庄,聪明的村民,得病的狗,正午的枪声  回复  更多评论   

这道题有异曲同工之妙:
一群人开舞会,每人头上都戴着一顶帽子。帽子只有黑白两种,黑的至少有一顶。每个人都能看到其它人帽子的颜色,却看不到自己的。主持人先让大家看看别人头上戴的是什幺帽子,然后关灯,如果有人认为自己戴的是黑帽子,就打自己一个耳光。第一次关灯,没有声音。于是再开灯,大家再看一遍,关灯时仍然鸦雀无声。一直到第三次关灯,才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子?
2007-04-22 07:52 | pengkuny

# re: 神秘的村庄,聪明的村民,得病的狗,正午的枪声  回复  更多评论   

嘿嘿这个好,耳光抽得辟了啪啦的。
杀狗那个让人感觉怪怪的,莫名其妙的恐怖感。听了以后晚上都不敢上厕所。我听完僵尸故事都敢上。
2007-04-22 08:40 | ★田德健★

# re: 神秘的村庄,聪明的村民,得病的狗,正午的枪声  回复  更多评论   

动物保护组织对此表示谴责,^_^
2007-05-12 13:07 | 天衣有缝

# re: 神秘的村庄,聪明的村民,得病的狗,正午的枪声  回复  更多评论   

在假设2时,其中的一个村民怎么会只看到一条病狗呢?如果它判断另一个村民的狗时病狗,那他一定也可以判断自己的狗和另一个村民一样。那他的假设只能应该是:他们俩的狗是病狗,或者其他人的狗是病狗...我始终想不通你的假设,就是他们只看到了1条病狗。
2007-05-14 20:20 | Aug

# re: 神秘的村庄,聪明的村民,得病的狗,正午的枪声  回复  更多评论   

错了,不好意思,我忘记看一个条件,他们不能检查自己的狗...抱歉了!
2007-05-14 20:21 | Aug

# re: 神秘的村庄,聪明的村民,得病的狗,正午的枪声  回复  更多评论   

呵呵。。
2007-05-14 22:08 | ★ROY★

# re: 神秘的村庄,聪明的村民,得病的狗,正午的枪声  回复  更多评论   

晕啊晕........
2008-09-21 22:19 | 王晶

# re: 神秘的村庄,聪明的村民,得病的狗,正午的枪声  回复  更多评论   

实在话:我没看这文章.看见"杀狗"俩字就浑身冒冷汗了
2008-09-21 22:22 | 王晶

# re: 神秘的村庄,聪明的村民,得病的狗,正午的枪声  回复  更多评论   

博主你好!我对你文中给出的代码有点疑问,按照这个函数assume()的执行流程来看,它最终会递归到shoot his dog,所以这个函数只能描述病狗主人的行为。能否提供一个普遍描述所有村民行为的函数?
2008-10-13 11:29 | Shinelion

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理