作者lingpxs (跟我認真你就輸了XD)
看板logic
標題Re: [討論] IBM面試問題
時間Sun Mar 2 21:15:52 2008
如果只有一隻
會有49人看到一隻病狗
A村民看不到
所以A村民第一天晚上會殺了自己的狗
如果有兩隻
會有48人看到2隻病狗
2人看到一隻病狗
那兩人會跟一隻情況的49人一樣
等看看有病狗的主人會不會殺自己的狗
如果沒殺自己的狗
表示對方也看到一隻病狗
但自己又看不到其他病狗
表示自己的也是病狗
所以第二天晚上兩人會殺了自己的狗
而其他48人即可確定自己的狗沒問題
要是有三隻
如假設二 47人中有人看到3隻病狗
3人看到兩隻病狗
這三人的想法會跟假設二中的48人想法一樣
等過第二天晚上看看那兩人會不會殺自己的狗
如果沒有 就是對方也看到兩隻病狗
也就是說自己的狗也是生病的
所以第三天晚上三個人會殺了自己的狗
※ 引述《wanga (bright eyes)》之銘言：
: 請問這題該如何著手?
: ----------------------------------
: 村子中有50個人 每人有一條狗
: 在這50條狗中有病狗（這種病不會傳染）。于是人們就要找出病狗。
: 每個人可以觀察其他的49條狗，以判斷它們是否生病，只有自己的狗不能看。
: 觀察後得到的結果不得交流，也不能通知病狗的主人。
: 主人一旦推算出自己家的是病狗就要槍斃自己的狗，
: 而且每個人只有權利槍斃自己的狗，沒有權利打死其他人的狗。
: 第一天，第二天都沒有槍響。到了第三天傳來一陣槍聲，
: 問有幾條病狗?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.118.155.180
1F：推 come:村民又不知道有幾隻病狗 怎麼判斷自己的狗有沒有生病 03/14 13:42
2F：推 blatta:樓上，所以才會傳來「一陣」槍聲，而不是三聲XD 04/21 12:05
3F：推 josa9616:簡單來說 第一天 可能有發現病狗 但 知道不是自己的 04/23 00:04
4F：推 theknight:TO COME 如果在不知道自己狗有沒有生病的情形下 06/17 13:10
5F：→ theknight:當然選擇不開槍 06/17 13:10
6F：→ theknight:關鍵點在於 "至少有一隻病狗" + "類似骨牌效應" 06/17 13:11