1. 首頁
  2. 面試

微軟面試題病狗

微軟面試題病狗

一個住宅區內有100戶人家,每戶人家養一條狗,每天傍晚大家都在同一個地方遛狗。已知這些狗中有一部分病狗,由於某種原因,狗的主人無法判斷自己的狗是否是病狗,卻能夠分辨其他的狗是否有病,現在,上級傳來通知,要求住戶處決這些病狗,並且不允許指認他人的.狗是病狗(就是隻能判斷自己的),過了7天之後,所有的病狗都被處決了,問,一共有幾隻病狗?為什麼?

7只(數學歸納法證明)

1)若只有1只病狗,因為病狗主人看不到有其他病狗,必然會知道自己的狗是病狗(前提是一定存在病狗),所以他會在第一天把病狗處決。

2)設有k只病狗的話,會在第k天被處決,那麼,如果有k+1只,病狗的主人只會看到k只病狗,而第k天沒有人處決病狗,病狗主人就會在第k+1天知道自己的狗是病狗,於是病狗在第k+1天被處決

3)由1)2)得,若有n只病狗,必然在第n天被處決