記得這是在大四上半年晚上開(kāi)臥談會(huì)的時(shí)候我們宿舍一個(gè)大能人給我們出的題，今天突然想起來(lái)：
從前有一個(gè)村莊，村莊里有若干個(gè)村民，村民都非常的聰明，對(duì)于各種復(fù)雜的問(wèn)題他們都能夠仔細(xì)的觀(guān)察，并能做出你所能做的一切分析和判斷，他們每個(gè)人都養(yǎng)且僅養(yǎng)一條狗。有一天，所有的村民接到了一條確切的消息：村里的狗中有若干條得了一種?。ㄟ@種病不會(huì)傳染）。要求由且僅由這些村民自己找出這些病狗，他們每天上午要檢查除了自己的狗以外所有的狗。村民之間不許交談，如果一個(gè)村民通過(guò)觀(guān)察分析，判斷出了自己的狗是病狗，那他就開(kāi)槍打死這只狗，但任何人不許打死別人的狗。排查工作就這樣開(kāi)始了，第一天沒(méi)有槍響，第二天也沒(méi)有槍響，第三天的正午，所有人都聽(tīng)到了“砰……”的一陣槍響。請(qǐng)問(wèn)：村子里共有多少條病狗？
后來(lái)知道了這個(gè)問(wèn)題是
IBM
公司的一道面試題。答案是
3
條。解決的方法如下，按假設(shè)病狗數(shù)量不斷推論：
假設(shè)病狗數(shù)為
1
，那么在第一天這條病狗的主人就會(huì)發(fā)現(xiàn)：除了他自己的狗以外所有的狗都沒(méi)有病，然而病狗確實(shí)是存在的，因此這個(gè)村民就會(huì)做出推斷，自己的狗就是病狗。他就會(huì)開(kāi)槍打死它。然而第一天沒(méi)有槍響，我們要繼續(xù)假設(shè)。
假設(shè)病狗數(shù)為
2
，大多數(shù)人都會(huì)發(fā)現(xiàn)這
2
條病狗，但會(huì)有且僅會(huì)有兩個(gè)村民只看到了
1
條病狗（因?yàn)樗麄冏约旱墓芬彩遣」罚@然地，他們所看到的病狗是彼此對(duì)方的）。我們考慮這兩個(gè)村民中的一個(gè)人，在第一天，他暫時(shí)還不能斷定自己的狗是否有病，但他可以假設(shè)：他所看到的這條病狗就是村里唯一的病狗；然后就此做出上一自然段（假設(shè)病狗數(shù)為
1
）中的分析：如果真的是這樣，那這個(gè)病狗的主人也會(huì)發(fā)現(xiàn)自己的狗是病狗（因?yàn)椴」返闹魅瞬粫?huì)看到其他的狗生?。Ｔ诮裢?，病狗的主人就會(huì)把它處死。然而，在他第二天出去檢查的時(shí)候，發(fā)現(xiàn)所有的狗都活得好好的。他會(huì)做出判斷：先前的假設(shè)是錯(cuò)誤的，村子里的病狗不僅僅是一條，但是第一天在他去檢查時(shí)的確僅發(fā)現(xiàn)了
1
條病狗，因此很明顯地，自己的狗一定就是病狗。這條可憐的狗也會(huì)被處決。但是第二天仍沒(méi)有槍響。需要繼續(xù)假設(shè)。
假設(shè)病狗數(shù)為
3
，大多數(shù)人會(huì)看到
3
條病狗，有
3
位村民只看到
2
條。在你做出分析的同時(shí)，村民也在進(jìn)行著同樣縝密的推理。這
3
位村民會(huì)做出上一自然段（假設(shè)病狗數(shù)為
2
）中的分析，他們一定知道，如果第二天有狗被處決的話(huà)，那么他們的假設(shè)就成立。然而等到了第三天去檢查的時(shí)候，發(fā)現(xiàn)沒(méi)有狗被處死，那足以證明自己的狗也是病狗。他們會(huì)在第三天開(kāi)槍。假設(shè)成立，原題得解。
你也許能夠發(fā)現(xiàn)，上述三段分析中，后一段都會(huì)借助前邊的那一段來(lái)分析。這儼然是一個(gè)遞歸問(wèn)題。假設(shè)病狗數(shù)為
n
，如果
n==0
則執(zhí)行操作，跳出遞歸，如果
n>0
則遞歸
(n-1)
的情況。把當(dāng)前的狀況用一個(gè)三元組來(lái)表示
(
第
d
天
,
總共看到
t
條狗
,
其中有
s
條有病
)
，下面是偽代碼：
bool assume(day, total, sick) {
? if ( sick == 0 ) { shoot(hisDog); return true; }
? else {
if( assume(day+1, total-1, sick-1) ) return false;
else { shoot(hisDog); return true; }
}
今天早上起來(lái)發(fā)現(xiàn)新買(mǎi)的
n73
不見(jiàn)了，可把我給急壞了，我拿來(lái)笤帚用笤帚把在床底下不斷地掃，最后只掃出了幾個(gè)玻璃球、一只襪子、幾張涂滿(mǎn)鴉的破紙，一大堆土。后來(lái)發(fā)現(xiàn)桌上躺著那個(gè)
old pal
：
2610
，我才恍然大悟，原來(lái)是個(gè)夢(mèng)啊。哼哼，太有意思了。
都說(shuō)有錢(qián)人，尤其是實(shí)打?qū)嵉馗沙鰜?lái)的有錢(qián)人從來(lái)不亂花錢(qián)，他們的錢(qián)都是血汗，哪舍得花啊，哪有時(shí)間花啊。亂花錢(qián)，那是紈绔子弟，是暴發(fā)戶(hù)。北京月入
10k
的大牛還有擠公交車(chē)的，人家
手機(jī)之父
馬丁
?
庫(kù)貝先生還會(huì)用幾百塊錢(qián)（折合成人民幣）的破手機(jī)呢。
我還是個(gè)并且在未來(lái)的很長(zhǎng)時(shí)間以?xún)?nèi)都將是個(gè)對(duì)當(dāng)前的不好不壞的日子很滿(mǎn)足但是對(duì)未來(lái)的美好生活充滿(mǎn)期待的窮光蛋……
