来一个支付宝SA的面试题

前几天支付宝来我们学校校招SA了,我太小了木有参加.然后打听到一个题目:

一个村子里有50户人家,每户人家养一条狗,不幸的是村子里的有狗感染了疯狗病,现在要杀死疯狗。
杀狗规则如下:
(1)必须确定是疯狗才能杀
(2)杀狗用猎枪,开枪杀狗人人都听的见,没聋子.
(3)只能观察其他人家的狗是否得了疯狗病,不能观察自己的狗是否有疯狗病
(4)只能杀自己家的狗,别人家的狗你就是知道有疯狗病也不能杀.
(5)任何观察到了其他人家的狗有疯狗病都不能告诉任何人.
每人每天去观察一遍其他人家的狗是否疯狗
现在现象是:第一天没有枪声,第二天没有枪声,第三天响起一片枪声.

问:第三天杀了多少条疯狗?

面试算法

阅读 12.2k

6 个回答

事实：镇上至少有一条疯狗

1.假设镇上有一条疯狗。推论第一天一定有枪响。
原因：49人看到的景象是A有一条疯狗，其他48人狗不疯，自己的不知道。A看到的是所有人的狗都正常，根据事实推断，自己的狗肯定是疯的，枪响。

2.假设镇上有两条疯狗。推论第二天一定有枪响。
第一天没有枪响，原因：48人看到的景象是AB各有一条疯狗，其他47人狗不疯，自己的不知道。A看到B有疯狗，B看到A有疯狗，其他48人的狗正常。A不能推断自己的狗是否为疯，因为他观察到镇上已经有一条疯狗了，B同理。第一天没有人能推断自己的狗是否正常，观察完毕。
第二天AB同时枪毙狗，原因：A推断B昨天没有枪毙狗的唯一原因就是镇上还有第二条疯狗（只有一条的情况下第一天一定有枪响）。但是除了B以外其他48人的狗有都不疯，所以自己的狗是疯的，B同理。

3.假设镇上有3条疯狗。推论第三天会有枪响。
第二天没有枪响的原因见上面两段。
第三天枪响的原因：ABC各有一条疯狗，A观察到BC各有一条疯狗，但是第二天没有枪响（如果只有两只疯狗第二天必然枪响），也就是说镇上有另外一条疯狗，也就是自己的狗。BC同理，第三天枪响。

答案，第三天枪毙了三只疯狗。

joyqi

16.2k3894100

发布于
2011-04-27

这个问题很有趣，我在思考的时候首先要解决一个人在什么情况下会杀死自己的狗，因为他是不知道自己的狗是否有病的，但是有以下一个条件保证了

不幸的是村子里的有狗感染了疯狗病

这是一个不起眼的条件，但它却是我们所有假设的重要基础，也就是必然有狗染病，但不是全部染病，那么我们来假设只有一只疯狗的时候，第一天所有人都去看了，大部分人发现有一只疯狗，只有一个人发现没有疯狗，这个时候他基于上面的假设就会自己杀狗，也就是说如果只有一只疯狗，第一天就会有枪声

那么实际情况是疯狗数肯定会比一只多，那么在什么情况下，第一天会没有枪声呢？那就是所有人都看到了不止一只疯狗，也就是说至少有两只狗染病。

后面的情况大家可以继续...

binbox

= = 这个是完整的题目

1.假设50条狗全是疯狗，那么，第一天，任何一个村民观察到的所有狗都是疯狗，但是不能确定自己的狗是不是，所以不杀，过了一晚，发现没人杀狗，以为其他人观察错误，于是继续等，第三天，发现还没人杀，以为自己判断错误，其实自己的狗是疯狗，杀狗。
-------------
好吧这个题目很大一部分受的主观想法的影响啊..