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