今天和一个朋友吃饭，朋友出了一个题目让我想想，正好最近也在看计算机算法方面的书，看看水平有没有提升。题目大意就是：
有64匹马，每次最多赛跑8匹马，想要找出最快的4匹马，要多少轮?
最简单的想法是每一轮比赛都留下前4匹马，用来进行下一场比赛，那么比赛示意图如下：
11.png
22.png
上面的方法肯定不是次数最少的，因为里面有很多次比较是多余的，所以我又花了些时间考虑怎么去掉这里面无用的比较，下面是我深思之后的方法，示意图如下：
33.png
算法的大致思路是：
- 前8轮赛马照旧，第9轮则是比较前面8轮中每一轮的第1名，也就是比较A11-A18，比赛后按照排名调整行的位置，比如未比赛前的A21-A24在比赛后，假设A21排在第5，所以调整编码为A51-A54。
- 第9轮重新编码后，如图 Figure.1中，实际需要比较的只剩下橘色的部分了，原因可以看做两个格子之间的距离超过了3，这是我的理解。当然还可以去掉一些格子，下面继续分析。
- 如图 Figure.2所示，A11是最快的马，所以不需要再比较，第2名则要从距离为1的A12和A21中决出，所以第10轮只需要比较A12和A21。
- 无论A12和A21哪个胜出，情况其实是一样的，如图 Figure.3和 Figure.4，第3、4名只需要从绿色部分序号代表的马中决出，绿色部分正好有8个格子，一次比赛就可以决出，所以第11轮就可以判断出64匹马中最快的4匹马。
得到11这个答案后感觉应该找度娘确认一下，发现网上有更好的答案：10轮或者11轮比较。简单描述一下我与网上答案的差别，A21和A12其实并不是必须要比较的，因为A21实际上和A12不是对称的，A21比A22、A23、A31、A32、A41大，所以跳过我的第10轮比赛，直接进行 Figure.4，然后判断A22、A31是否有进前3名，如果进了，则只需要将A21插入组成新的排名即完成前4排名；如果A22、A31没有进前3名，那么第10轮前3名是A12-A14，那么再赛一轮A12-A14、A21即可，所以可能是10轮或者11轮。
这是我在简书上的第一篇文章，有些小紧张，以后要坚持写下去，可能会有一些错误，我会不断改进，希望能够在算法的路上远走越远。
网友评论