????今天和一個(gè)朋友吃飯亿乳，朋友出了一個(gè)題目讓我想想硝拧，正好最近也在看計(jì)算機(jī)算法方面的書，看看水平有沒有提升葛假。題目大意就是：
有64匹馬障陶，每次最多賽跑8匹馬，想要找出最快的4匹馬聊训，要多少輪?
????最簡單的想法是每一輪比賽都留下前4匹馬抱究，用來進(jìn)行下一場比賽，那么比賽示意圖如下：
11.png
22.png
????上面的方法肯定不是次數(shù)最少的带斑，因?yàn)槔锩嬗泻芏啻伪容^是多余的鼓寺，所以我又花了些時(shí)間考慮怎么去掉這里面無用的比較勋拟，下面是我深思之后的方法，示意圖如下：
33.png
算法的大致思路是：
- 前8輪賽馬照舊妈候，第9輪則是比較前面8輪中每一輪的第1名敢靡，也就是比較A11-A18，比賽后按照排名調(diào)整行的位置州丹，比如未比賽前的A21-A24在比賽后醋安，假設(shè)A21排在第5，所以調(diào)整編碼為A51-A54墓毒。
- 第9輪重新編碼后吓揪，如圖 Figure.1中，實(shí)際需要比較的只剩下橘色的部分了所计，原因可以看做兩個(gè)格子之間的距離超過了3柠辞，這是我的理解。當(dāng)然還可以去掉一些格子主胧，下面繼續(xù)分析叭首。
- 如圖 Figure.2所示，A11是最快的馬踪栋，所以不需要再比較焙格，第2名則要從距離為1的A12和A21中決出，所以第10輪只需要比較A12和A21夷都。
- 無論A12和A21哪個(gè)勝出眷唉，情況其實(shí)是一樣的，如圖 Figure.3和 Figure.4囤官，第3冬阳、4名只需要從綠色部分序號代表的馬中決出，綠色部分正好有8個(gè)格子党饮，一次比賽就可以決出肝陪，所以第11輪就可以判斷出64匹馬中最快的4匹馬。
????得到11這個(gè)答案后感覺應(yīng)該找度娘確認(rèn)一下刑顺，發(fā)現(xiàn)網(wǎng)上有更好的答案：10輪或者11輪比較氯窍。簡單描述一下我與網(wǎng)上答案的差別，A21和A12其實(shí)并不是必須要比較的蹲堂，因?yàn)锳21實(shí)際上和A12不是對稱的荞驴，A21比A22、A23贯城、A31、A32霹娄、A41大能犯，所以跳過我的第10輪比賽鲫骗，直接進(jìn)行 Figure.4，然后判斷A22踩晶、A31是否有進(jìn)前3名执泰，如果進(jìn)了，則只需要將A21插入組成新的排名即完成前4排名渡蜻；如果A22术吝、A31沒有進(jìn)前3名，那么第10輪前3名是A12-A14茸苇，那么再賽一輪A12-A14排苍、A21即可，所以可能是10輪或者11輪学密。
????這是我在簡書上的第一篇文章淘衙，有些小緊張，以后要堅(jiān)持寫下去腻暮，可能會有一些錯(cuò)誤彤守，我會不斷改進(jìn)，希望能夠在算法的路上遠(yuǎn)走越遠(yuǎn)哭靖。
