来一个支付宝SA的面试题


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

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

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

面试 面试题 算法

Surufel 10 years, 11 months ago

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

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同理,第三天枪响。

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

bladelo answered 10 years, 11 months ago

Your Answer