112
一道麵試題：賽馬問題
一共有25匹馬，有一個賽場，賽場有5個賽道，就是說最多同時可以有5匹馬一起比賽。假設每匹馬都跑的很穩定，不用任何其他工具，隻通過馬與馬之間的比賽，試問，最少得比多少場才能知道跑得最快的5匹馬？（不能使用撞大運的算法）
很明顯這是一個算法題，網上有很多貼子在討論這個問題，不過都沒有給出一個明確的答案。我想了想，想到下麵的一個算法：
1）分成5組A，B，C，D，E，比五場。然後根據每場結果分別給這五組內的五匹馬排序（從快到慢）。
2）每組的頭名再賽一場，取走第一名，然後該組第二名頂上。
3）重複第二步，直到選出前5名。
這個算法是比較笨的算法，總計需要賽10次，這個算法應該是萬無一失的。現在的問題的就，如何優化這個算法，想了想，的確是有優化的空間的。也就是說，是可以少於10次的。
想了一想，上麵的那個算法自從第6次開始就使用5個排序數組的頭名做“冒泡法”，總是挑一個最優秀的出來，其實，在第6次以後除了挑出最優秀的，我們還可以在每次比賽後淘汰一些速度不行的，淘汰的馬匹數自然會比選出的更多，所以，一方麵在找，另一方麵在淘汰，找出前5名的速度應該會更快。
比如：我們假設比賽完第六場後，我們得到下麵的排序：（每組排序是——快馬從左到右，各組頭名的排序是——快馬從上到下）
A組 A1 A2 A3 A4 A5
B組 B1 B2 B3 B4 B5
C組 C1 C2 C3 C4 C5
D組 D1 D2 D3 D4 D5
E組 E1 E2 E3 E4 E5
這樣，我們不但知道，A1是25匹馬裏最快的馬，而且我們可以淘汰近一半的馬，比如E2，E3，E4，E5就可以全部淘汰了，為什麼呢，因為比E2快的馬有A1,B1,C1,D1,E1這五匹馬，所以，E2後麵的馬是無法進入前五名了；同理，D3和其後麵的也進入不了前5；同理，C4，C5，B5都可以淘汰。
於是，在第六輪後我們可以得知，除了A1外的Top 4必然在下麵這些馬中：
A組 A2 A3 A4 A5
B組 B1 B2 B3 B4
C組 C1 C2 C3
D組 D1 D2
E組 E1
接下來的過程應該不必我多說了。重複前麵的方法，盡可能淘汰無法進前N名的馬，於是後麵的馬就越來越少，你所需要的比賽也會越來越少。
那麼，對於這個題，聰明的你知道最少要比賽幾場了嗎？
舉一反三，如果有64匹馬，8個賽道呢？不失一般性，如果有N匹馬，M個賽道呢？N = M*M，那麼公式是什麼呢？
期待你的答案！
最後更新：2017-04-03 18:51:55