當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

BAT 面试题：25匹马，5个跑道，每个跑道最多能有1匹马进行比赛，最少比多少次能比出前3名？前5名？

發布時間：2024/1/8 编程问答 43 豆豆

生活随笔收集整理的這篇文章主要介紹了 BAT 面试题：25匹马，5个跑道，每个跑道最多能有1匹马进行比赛，最少比多少次能比出前3名？前5名？小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

寫在前面：最近在刷面試題的過程中遇到這么一道題，感覺解讀題目的角度很多，這里介紹自己的做法。注意：本文并不是參考答案，只是為大家在面試的時候多提供一條思路，或許可以獲得面試官的青睞。

25匹馬，5個跑道，每個跑道最多能有 1 匹馬進行比賽，最少比多少次能比出前 3 名？前 5名？

1 - 一些假設

同一馬匹在任意場次的速度都能保持一致。

2 - 前 3 名分析

將 25 匹馬分為 5 個小組，每個小組跑一場，共 5 場比賽。假設決出的順序如下圖：

組A組B組C組D組E

A1	B1	C1	D1	E1
A2	B2	C2	D2	E2
A3	B3	C3	D3	E3
A4	B4	C4	D4	E4
A5	B5	C5	D5	E5

取每個小組的第一名跑一場，假設決出的順序為 A1 > B1 > C1 > D1 > E1，則 A1 是第一名，剔除掉沒有希望進入前 3 的馬匹后，排序表變為：

組A組B組C組D組E

-	B1	C1	-	-
A2	B2	-	-	-
A3	-	-	-	-
-	-	-	-	-
-	-	-	-	-

容易發現，剛好只剩下 5 匹馬，可以在一場比賽跑完。

結果就是 5 + 1 + 1 = 7 場。

3 - 前 5 名分析

和前 3 名的分析類似，分成 5 個小組，5 個小組的第一名再跑一場，決出第一名后剔除沒有機會進入前 5 的馬匹，排序表如下：

組A組B組C組D組E

-	B1	C1	D1	E1
A2	B2	C2	D2	-
A3	B3	C3	-	-
A4	B4	-	-	-
A5	-	-	-	-

注意到 B1 是 BCDE 四組中最快的馬，但是 B1 和 A 組剩下的馬的快慢暫不得知。B1 與 A 組馬的順序將會直接影響接下來需要跑的場次。

讓 A 組剩下的 4 匹馬和 B1 跑一場，則可能出現如下結果：

結果 1結果 2結果 3結果 4結果 5

A2	A2	A2	A2	B1
A3	A3	A3	B1	A2
A4	A4	B1	A3	A3
A5	B1	A4	A4	A4
B1	A5	A5	A5	A5

容易發現，由于 B1 的特殊性，結果 1 和結果 2 其實已經決出了前 5 的馬匹（包括 A1），結果 3 決出了前 4 的馬匹，結果 4 決出了前 3 的馬匹，結果 5 決出了前 2 的馬匹。

所以最少需要 5 + 1 + 1 = 7 場。（題目到這里就可以結束了）

結果 1 和結果 2 具有偶然性，出現其他結果時的情況比較復雜，但是考慮到每場都會至少確定 1 個名次，那么實際上最多 5 + 5 =10 場就能確定前 5 。

4 - 拓展

64匹馬，8條跑道，決出前4名？

分 8 組，決出第一名之后剔除不能進入前 4 的馬匹，如下：組A組B組C組D組E…

-	B1	C1	D1	-	-
A2	B2	C2	-	-	-
A3	B3	-	-	-	-
A4	-	-	-	-	-

還剩 9 匹馬，一次跑不完。

筆者的考慮是第 10 場先不安排A4、B3、C2、D1中的某一匹，因為這 4 匹馬相對較慢，很大幾率不會入選前 4，根據結果來確認是否需要第 11 場。比如，第 10 場 D1 沒有上場，如果（速度比 D1 快的）B1 或者 C1 不在前 3，那么 D1 就沒有再上場的必要了。反之，若 B1、C1分別是第 2 、第 3 名，那么 D1 還是有機會爭一爭第 4 的。

所以按這個思路，最多 11 場，最少 10 場就能確認前 4。