64匹马8个跑道需要多少轮才能挑选出最快的4匹马?
64匹馬8個跑道需要多少輪才能挑選出最快的四匹馬?
第一步
把64匹馬分成8組,每組各比賽一次,按照快慢進行排序,出現以下結果:
第二步
淘汰每一組的最后四匹,因為只需要跑的最快的四匹,即使出現一個組的第五名比另一個組的第一名還快的話,那么這兩組在挑選的時候也是第五名之前的前四名最快。類比到所有組,所有組的后四名都會被淘汰。
舉例:如果A組的第五名比B組的第一名也快的話,那么A,B兩組中選最快的四匹也是A組中的前四匹。類比到所有組,所有組的后四匹都淘汰。
我們先根據第一步給出每一組的按照快慢給出的順序:
然后淘汰每一組的后4名:
綠色標出來的區域就是淘汰的部分。
第三步
讓剛才8個組的第一名進行比較,就可以找出來64匹中跑的最快的一批。然后把第五名及比第五名跑得慢的馬全部淘汰。
這次淘汰的是黃色的部分。可以確定E1,F1,G1,H1比A1,B2,C1,D1跑的慢,那么E1,F1,G1,H1是所在組的第一名,所以所在組直接淘汰。粉色的標記出來的是64匹馬中跑的最快的。
我們現在可以確定:A1>B1>C1>D1 A1>A2>A3>A4
第四步
剩下的16匹馬中右下角的6匹馬直接淘汰:
因為A1是最快的,接下倆組合必然是A2或者B2開始,那么只挑選4匹的話,所以右下加的6匹是絕對選不上的。
第五步
讓B1不參加的情況下剩下的8匹直接比賽:
如果C1,D1是第一第二,那么最快的4匹就是A1,B1,C1,D1。
如果C1, C2是第一第二,那么最快的4匹就是A1,B1,C1,C2.。
如果B2, B3是第一第二,那么最快的4匹就是A1,B1,B2,B3.。
如果B2, C1是第一第二,那么最快的4匹就是A1,B1,B2,C1。
如果出現以上情況的話。那么4匹最快的馬已經挑選出來直接結束。
那么就需要:8+1+1 = 10輪
如果B2,C1都沒有在第一第二出現過,那么前兩名必然是A2,A3。
那么這個是時候前4名里面到底有沒有B1是不確定,因為有兩種情況
要么是:A1,A2,A3,A4
要么是:A1,B1,A2,A4
所有A2,A3,A4,B1還需要比賽一次,在4匹里面挑選3匹和A1組成最快的4匹馬
那么就需要:8+1+1+1 = 11輪
到這里問題已經解決!!!
以上就是完整的解法
分析一下爭議比較大的方法
有一種思路前四步一樣,在第五步的時候:青色標記的9匹任意選擇選8匹進行比賽,選出前3名和剛才沒有選到的那一匹馬再次比賽,4匹馬中選前三名和A1就組成了最快的4匹馬。
這種方法需要:8+1+1+1 = 11輪
最后爭議的方法必然需要11輪,但是我們在使用上面的讓B1不參加比賽剩下的8匹馬直接比賽的時候,我們可以通過分析結果決定是否有必要進行第11輪,所以我們給出第五步的方法更好。
總結
以上是生活随笔為你收集整理的64匹马8个跑道需要多少轮才能挑选出最快的4匹马?的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 最高效的回文数(C语言实现)
- 下一篇: C++Primer Plus (第六版)