引言：
之前去西安某游戲公司面試前端開發崗位，考了我一道賽馬題，當場沒想出來，面試也就順理成章的涼涼，
回家之后，我仔細研究了一下，結合網路上的一些思路，梳理出來一個目前個人認為的最優解，但不知道會不會存在更少的情況，
本文就結合這道題目，分享一下我個人解此題的一個詳細思路，用圖文的形式去呈現，
題目要求：
現有64匹馬，賽場上有8條跑道（一場最多賽8匹），問，在不用計時器的情況下，最少情況下，賽多少場能夠找到最快的4匹，如圖：
分析：
根據題意，我們可以很輕松想到，64匹馬能夠排成8*8的方陣（一共8組，每組8匹），
剛好每組8匹剛好占滿8個跑道，不構成浪費，
無論怎樣，至少每匹馬都得參加比賽，有參考依據，才有可能得出結論，
1.第一步：（8場）
如上述分析，將64匹馬隨機分成8組，每組8匹，讓它們跑去吧，
這樣我們至少可以得出每一組的排名，這里為了不混淆，組統一用ABCDEFGH表示，名次用12345678表示，
現在我們知道每一組的排名，但不能輕易下結論，極端情況下，A組的8匹有可能是最快的8匹，B組的第1也許很快，但比起A組第8，仍然是難以望其項背，
這樣我們還不能確定具體名次，我們可以讓每一組的第1名加賽一場，得出每組按第一升序排列的矩陣，
2.第二步：（1場）
如上述，每組第1加賽一場，我們可以按名次排列出一個8*8的矩陣，
如下表所示，A為第1名所在組，B為第2名所在組，以此類推，
這樣下來，A1一定是64匹中的大哥，最快的那匹，我們用土豪金標注，（因為是每組第1中的第1）
而且，E1作為每組第1中的第5，已經不可能在整體前4了，因為A1，B1，C1，D1都比它快，所以EFGH組全部淘汰，（用白色標注）
對于D1而言，是每組第1中的第4，是可能入圍的，而且最好名次也是第4，那么D2~D8作為D1的小弟肯定沒戲了，
同理，對C1而言，最好名次也是第3，C2作為C1小弟可以勉強爭一下第4，所以C3~C8淘汰，
那么B4~B8以及A5~A8全部淘汰，現在場上只剩下了A1~A4，B1~B3，C1~C2，D1，總共10匹馬，用紅色標記，如圖：
3.第三步：（1場，最多2場）
還剩下10匹馬，但我們已知A1一定是全場最佳，所以剩下9匹馬需要再比一場，
現在只有8個賽道，卻有9匹馬，看樣子是需要讓其中一匹馬在場下看熱鬧了，
而這匹馬最好選擇“邊緣人”，也就是在淘汰邊緣的，相比較而言D1的位置最為尷尬，ABC組里邊的非第1，隨時有可能擠掉它成功上位，
所以，選擇D1看熱鬧是最合適不過的了，（因為D1最多拿第4，否則淘汰）
接下來，我們就讓A2，A3，A4，B1，B2，B3，C1，C2去跑，
跑完之后，這樣我們可以參照C1的名次來判斷接下來需要怎么賽，
若C1是本組第4~7名，則整體2~4名和本組前3一一對應，加上A1的第1名，構成前4，（結束）
若C1是本組第3名，則讓C2和D1加賽一場，搶第4名，（加賽一場，結束）
若C1是本組第2名，則前4就是A1，C1，C2及D1，C2和D1不必進行季軍爭奪，怎么爭奪都是一個第3一個第4，（結束）
4.第四步：（總結）
結合上述分析，看C1最后一場如果不跑第3就是最少情況，最少需要10場，（8+1+1），
這僅僅是目前本人認為最少的場次，如果有更犀利的思路，我會積極采納！
原創地址：https://www.cnblogs.com/ElemSN/p/13528080.html，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/593.html
標籤：其他
上一篇：程式員應該如何找作業呢？