爱华网IBM公司面试题答案：病狗问题
问题:村子中有50个人，每人有一条狗。在这50条狗中有病狗(这种病不会传染)。于是人们就要找出病狗。每个人可以观察其他的49条狗，以判断它们是否生病，只有自己的狗不能看。观察后得到的结果不得交流，也不能通知病狗的主人。主人一旦推算出自己家的是病狗就要枪毙自己的狗，而且每个人只有权利枪毙自己的狗，没有权利打死其他人的狗。第一天，第二天都没有枪响。到了第三天传来一阵枪声，问有几条病狗，如何推算出？
我承认第一次看到这个题，题目都怀疑了半天，于是我提出了以下一些问题：
①这个方法是否具有可行性？那么首先必须证明这个方案的有效性。这样做是不是一次就可以一次把所有的病狗全部找出来？
这个方法存在的前提是：
⑴ 村中一定有病狗（存在性）
⑵ 村民都很聪明
⑶ 村民能看出哪只是病狗
⑷ 一天看一次其他人的狗，而不能看自己的狗，村民间不允许交流，要推断出病狗。
② 什么情况表示的是一夜?也就是一天的含义到底是什么？
③会不会存在有误杀的情况呢？因为不知道到底有多少条病狗，即使看到了别人的狗可是也无法排除自己的狗是否健康。
④ 开枪有没有顺序，是否有先后，是同时还是次序？
这道题有好几个思考的角度，我自己从一个角度发现了一些问题，但是看别人的做出的结果又找不出问题，以下我搜集了几种角度来分析这道题。
⒈ 按照实际病狗数量角度推（前提是一定有病狗存在）
ⅰ.假设只有一条病狗，那么病狗主人看不到其他病狗，可是又有病狗的存在，那么又听不到别的枪声，此时已经可以判断病狗就是在自己家里了，因此第一天就会开枪，所以就会听到枪声，而这与题意不符。
ⅱ.假设有两条病狗，这两条病狗的主人是a,b.那么a会看到一只病狗，b也会看到一只病狗，对于a来说，如果只有一条病狗，那么b家的狗就必须死。可是第一天没有听到枪声，第二天发现b家的狗没有死，那么说明病狗不止一条，（因为b也看到了病狗，以为只有一条病狗，所以没有开枪）又没看出其他的狗有病，那么病狗只可能在自己家了，因此甲会开枪，同理乙在第二天也会开枪。那么第二天会死两只狗。
可如果是对于正常狗的主人c来说，他第一天看到了两条病狗，可是第一天没有开枪，只能说明不止两条病狗，而其他的狗又是没病的，那么很可能是自己家的狗，不能确定是自己家的狗这里我们看作是不能确定所以就不开枪。（那如果觉得自己家的狗有病，会杀了好狗，同理其他48家狗也会这么认为，所以不会超过两天，如果是直接开枪的话，那么超不过第二天。）
ⅲ.假设有三条病狗，a只会看到两只病狗，而认为自己的狗好的情况下，第一天没有开枪，第二天也没开枪（前提是一天只能看一次，也就是一天指能发现一只是病狗），这时第二天看到了两条病狗了，可是第二天晚上还没有听到枪声，那么第三天会发现没有狗死，那么不止两条狗，而其他的狗又都是好狗，那么只可能病狗是自家的了，同理其他两个人也会这么认为，那么第三天会听到枪声，那么第三天会有三只狗死，满足推论。
ⅳ.假设有四条病狗，按照前面的推理，a在前三天一 共可以看到三只病狗，假设自己的狗是正常的，那么第三天晚上应该听到枪声，而第三天晚上没有听到枪声，
第四天看到狗没有死，那么绝对不止三条狗，那么只可能是自己家的狗是病狗了，那么第四天就会开枪，同理其他三个人也是这个想法，第四天狗都会死了。但是这已经与题意不符了。
原理：第一天看:如果病狗只有1条,即病狗主人没看见其他的有病狗,可以断定自己家的是病狗,可以开抢,没有发生枪响,说明病狗主人看到了其他有病狗,推算病狗大于1,
第二天看:如果病狗只有2条,即其他人可以看都有两条病狗,病狗主人看到的病狗有1条,可以断定自己家的是病狗,可以开抢,既只能看到一条病狗的人可以开抢打死自己狗.而没有开抢,推算病狗数大于2.
第三天看:如果病狗只有3条,即其他人可以看都有三条病狗,病狗主人可以看到外面有2条病狗,可以断定自己家是病狗,可以开抢.如果病狗数大于3,不能开抢.
以上为条件1.
根据条件1.
病狗主人在第一天可根据看到的病狗数和天数来个测算,假如病狗数为1,病狗主人看到的病狗为0,可第1天开抢,病狗数为2,病狗主人看到的病狗为1,可第2天开抢,病狗数为3,病狗主人看到的病狗为2,可第3天开抢,病狗数为为4,病狗主人看到的病狗为3,可第4天开抢,以次类推.....
结论：病狗数为3,病狗主人在第一天看到的病狗数为2,可在第3天开抢。
⒉ 从天数角度进行推论
必要条件：至少有１条病狗，,病狗数＝病狗主人看到的病狗＋１（自己的病狗）
第一天： a,如果病狗主人看到病狗是是０，病狗数肯定为１，可以证明自己的狗是病狗，可以开枪．（第一天就开枪）
b,如果病狗主人看到病狗是是１，病狗数应该为１或者是1 +１＝２，不能证明自己的狗是病狗，不能开抢
c,如果病狗主人看到病狗是是２，病狗数应该为２或者是2＋１＝３，不能证明自己的狗是病狗，不能开抢
其他以次类推d, e, f.............
第二天：因为第一天没有人开抢，(可以排除a）那么考虑b,如果病狗主人看到病狗是１,（其他人看到的病狗数为２），病狗主人可以证明自己的狗是病狗，可以开枪，没有开抢，证明病狗大于２
第三天：因为第二天没有人开抢，（可以排除a和b),那么考虑c,如果病狗主人看到病狗是２，,（其他人看到的病狗数为３），病狗主人可以证明自己的狗是病狗，可以开枪．第三天开枪，证明病狗数为２＋１＝３
原理：假如主人第一天看到的病狗数为n,那么主人第一天就可以确定病狗数是n或者是n+1,那么主人可以在第几天才能断定自己的狗是病狗。
