- 相關(guān)推薦
微軟面試題病狗
一個(gè)住宅區(qū)內(nèi)有100戶(hù)人家，每戶(hù)人家養(yǎng)一條狗，每天傍晚大家都在同一個(gè)地方遛狗。已知這些狗中有一部分病狗，由于某種原因，狗的主人無(wú)法判斷自己的狗是否是病狗，卻能夠分辨其他的狗是否有病，現(xiàn)在，上級(jí)傳來(lái)通知，要求住戶(hù)處決這些病狗，并且不允許指認(rèn)他人的狗是病狗(就是只能判斷自己的)，過(guò)了7天之后，所有的病狗都被處決了，問(wèn)，一共有幾只病狗?為什么?
7只(數(shù)學(xué)歸納法證明)
1)若只有1只病狗，因?yàn)椴」分魅丝床坏接衅渌」罚厝粫?huì)知道自己的狗是病狗(前提是一定存在病狗)，所以他會(huì)在第一天把病狗處決。
2)設(shè)有k只病狗的話(huà)，會(huì)在第k天被處決，那么，如果有k+1只，病狗的主人只會(huì)看到k只病狗，而第k天沒(méi)有人處決病狗，病狗主人就會(huì)在第k+1天知道自己的狗是病狗，于是病狗在第k+1天被處決
3)由1)2)得，若有n只病狗，必然在第n天被處決