IBM公司面試題答案：病狗問(wèn)題

　　問(wèn)題:村子中有50個(gè)人，每人有一條狗。在這50條狗中有病狗(這種病不會(huì)傳染)。于是人們就要找出病狗。每個(gè)人可以觀察其他的49條狗，以判斷它們是否生病，只有自己的狗不能看。觀察后得到的結(jié)果不得交流，也不能通知病狗的主人。主人一旦推算出自己家的是病狗就要槍斃自己的狗，而且每個(gè)人只有權(quán)利槍斃自己的狗，沒(méi)有權(quán)利打死其他人的狗。第一天，第二天都沒(méi)有槍響。到了第三天傳來(lái)一陣槍聲，問(wèn)有幾條病狗，如何推算出？

我承認(rèn)第一次看到這個(gè)題，題目都懷疑了半天，于是我提出了以下一些問(wèn)題：

①這個(gè)方法是否具有可行性？那么首先必須證明這個(gè)方案的有效性。這樣做是不是一次就可以一次把所有的病狗全部找出來(lái)？

這個(gè)方法存在的前提是：

⑴ 村中一定有病狗（存在性）

⑵ 村民都很聰明

⑶ 村民能看出哪只是病狗

⑷ 一天看一次其他人的狗，而不能看自己的狗，村民間不允許交流，要推斷出病狗。

② 什么情況表示的是一夜?也就是一天的含義到底是什么？

③會(huì)不會(huì)存在有誤殺的情況呢？因?yàn)椴恢赖降子卸嗌贄l病狗，即使看到了別人的狗可是也無(wú)法排除自己的狗是否健康。

④ 開(kāi)槍有沒(méi)有順序，是否有先后，是同時(shí)還是次序？

這道題有好幾個(gè)思考的角度，我自己從一個(gè)角度發(fā)現(xiàn)了一些問(wèn)題，但是看別人的做出的結(jié)果又找不出問(wèn)題，以下我搜集了幾種角度來(lái)分析這道題。

⒈ 按照實(shí)際病狗數(shù)量角度推（前提是一定有病狗存在）

ⅰ.假設(shè)只有一條病狗，那么病狗主人看不到其他病狗，可是又有病狗的存在，那么又聽(tīng)不到別的槍聲，此時(shí)已經(jīng)可以判斷病狗就是在自己家里了，因此第一天就會(huì)開(kāi)槍?zhuān)跃蜁?huì)聽(tīng)到槍聲，而這與題意不符。

ⅱ.假設(shè)有兩條病狗，這兩條病狗的主人是a,b.那么a會(huì)看到一只病狗，b也會(huì)看到一只病狗，對(duì)于a來(lái)說(shuō)，如果只有一條病狗，那么b家的狗就必須死。可是第一天沒(méi)有聽(tīng)到槍聲，第二天發(fā)現(xiàn)b家的狗沒(méi)有死，那么說(shuō)明病狗不止一條，（因?yàn)閎也看到了病狗，以為只有一條病狗，所以沒(méi)有開(kāi)槍?zhuān)┯譀](méi)看出其他的狗有病，那么病狗只可能在自己家了，因此甲會(huì)開(kāi)槍?zhuān)硪以诘诙煲矔?huì)開(kāi)槍。那么第二天會(huì)死兩只狗。

可如果是對(duì)于正常狗的主人c來(lái)說(shuō)，他第一天看到了兩條病狗，可是第一天沒(méi)有開(kāi)槍?zhuān)荒苷f(shuō)明不止兩條病狗，而其他的狗又是沒(méi)病的，那么很可能是自己家的狗，不能確定是自己家的狗這里我們看作是不能確定所以就不開(kāi)槍。（那如果覺(jué)得自己家的狗有病，會(huì)殺了好狗，同理其他48家狗也會(huì)這么認(rèn)為，所以不會(huì)超過(guò)兩天，如果是直接開(kāi)槍的話，那么超不過(guò)第二天。）

ⅲ.假設(shè)有三條病狗，a只會(huì)看到兩只病狗，而認(rèn)為自己的狗好的情況下，第一天沒(méi)有開(kāi)槍?zhuān)诙煲矝](méi)開(kāi)槍?zhuān)?b>前提是一天只能看一次，也就是一天指能發(fā)現(xiàn)一只是病狗），這時(shí)第二天看到了兩條病狗了，可是第二天晚上還沒(méi)有聽(tīng)到槍聲，那么第三天會(huì)發(fā)現(xiàn)沒(méi)有狗死，那么不止兩條狗，而其他的狗又都是好狗，那么只可能病狗是自家的了，同理其他兩個(gè)人也會(huì)這么認(rèn)為，那么第三天會(huì)聽(tīng)到槍聲，那么第三天會(huì)有三只狗死，滿(mǎn)足推論。

ⅳ.假設(shè)有四條病狗，按照前面的推理，a在前三天一 共可以看到三只病狗，假設(shè)自己的狗是正常的，那么第三天晚上應(yīng)該聽(tīng)到槍聲，而第三天晚上沒(méi)有聽(tīng)到槍聲，

第四天看到狗沒(méi)有死，那么絕對(duì)不止三條狗，那么只可能是自己家的狗是病狗了，那么第四天就會(huì)開(kāi)槍?zhuān)砥渌齻€(gè)人也是這個(gè)想法，第四天狗都會(huì)死了。但是這已經(jīng)與題意不符了。

原理：第一天看:如果病狗只有1條,即病狗主人沒(méi)看見(jiàn)其他的有病狗,可以斷定自己家的是病狗,可以開(kāi)搶,沒(méi)有發(fā)生槍響,說(shuō)明病狗主人看到了其他有病狗,推算病狗大于1,

　　第二天看:如果病狗只有2條,即其他人可以看都有兩條病狗,病狗主人看到的病狗有1條,可以斷定自己家的是病狗,可以開(kāi)搶,既只能看到一條病狗的人可以開(kāi)搶打死自己狗.而沒(méi)有開(kāi)搶,推算病狗數(shù)大于2.

　　第三天看:如果病狗只有3條,即其他人可以看都有三條病狗,病狗主人可以看到外面有2條病狗,可以斷定自己家是病狗,可以開(kāi)搶.如果病狗數(shù)大于3,不能開(kāi)搶.

　　以上為條件1.

　　根據(jù)條件1.

　　病狗主人在第一天可根據(jù)看到的病狗數(shù)和天數(shù)來(lái)個(gè)測(cè)算,假如病狗數(shù)為1,病狗主人看到的病狗為0,可第1天開(kāi)搶,病狗數(shù)為2,病狗主人看到的病狗為1,可第2天開(kāi)搶,病狗數(shù)為3,病狗主人看到的病狗為2,可第3天開(kāi)搶,病狗數(shù)為為4,病狗主人看到的病狗為3,可第4天開(kāi)搶,以次類(lèi)推.....

結(jié)論：病狗數(shù)為3,病狗主人在第一天看到的病狗數(shù)為2,可在第3天開(kāi)搶。

⒉ 從天數(shù)角度進(jìn)行推論

　必要條件：至少有１條病狗，,病狗數(shù)＝病狗主人看到的病狗＋１（自己的病狗）

　　第一天： a,如果病狗主人看到病狗是是０，病狗數(shù)肯定為１，可以證明自己的狗是病狗，可以開(kāi)槍?zhuān)ǖ谝惶炀烷_(kāi)槍?zhuān)?br />
　　　　　　b,如果病狗主人看到病狗是是１，病狗數(shù)應(yīng)該為１或者是1 +１＝２，不能證明自己的狗是病狗，不能開(kāi)搶

　　　　　c,如果病狗主人看到病狗是是２，病狗數(shù)應(yīng)該為２或者是2＋１＝３，不能證明自己的狗是病狗，不能開(kāi)搶

　　　　　其他以次類(lèi)推d, e, f.............

　　第二天：因?yàn)榈谝惶鞗](méi)有人開(kāi)搶?zhuān)?可以排除a）那么考慮b,如果病狗主人看到病狗是１,（其他人看到的病狗數(shù)為２），病狗主人可以證明自己的狗是病狗，可以開(kāi)槍?zhuān)瑳](méi)有開(kāi)搶?zhuān)C明病狗大于２

　

　　第三天：因?yàn)榈诙鞗](méi)有人開(kāi)搶?zhuān)梢耘懦齛和b),那么考慮c,如果病狗主人看到病狗是２，,（其他人看到的病狗數(shù)為３），病狗主人可以證明自己的狗是病狗，可以開(kāi)槍?zhuān)谌扉_(kāi)槍?zhuān)C明病狗數(shù)為２＋１＝３

原理：假如主人第一天看到的病狗數(shù)為n,那么主人第一天就可以確定病狗數(shù)是n或者是n+1,那么主人可以在第幾天才能斷定自己的狗是病狗。

愛(ài)華網(wǎng)本文地址 » http://www.klfzs.com/a/25101016/294058.html