【引导性,看到图片请思考,不要着急下滑哦】
64/8 = 8
32/8 = 4
16/8 = 2
8/8 = 1
8 + 4 + 2 + 1 = 15 次
再思考一下呀?
找出前4名。
第一步:前面的8次是必不可少的,分成8组,赛8次
第二步:拿出第一名的8只马再比1次,这时候第一名就已经知道了,最后的3只马,肯定在前4只第一名马所在的队伍里,可以舍弃一半,剩下32只马。
因为找Top4,那么选中的这4组,可以只保留每组的前4名,此时有16只马(去掉第一名,15只马),再进一步简化,可简化为以下9只马。
第三步就是:9只里面找前3只。
1 | 2 | 3 | 4 | |
---|---|---|---|---|
A组 | 第一名已定,排除 | √ | √ | √ |
B组 | √ | √ | √ | |
C组 | √ | √ | ||
D组 | √ |
选9只马中的任意8只比较几次呢?
不选B1,选剩下8只。
1、如果C1D1第一第二,那么A1B1C1D1为top4。
2、如果C1C2第一第二,那么A1B1C1C2为top4。
3、如果B2能排到前三,那么A1B1为top4中一员,也可推导出剩下2只。
所以至少8+1+1=10次。
4、如果…(剩下情况依此类推)
其他情况呢?都是10次可推吗?
需要多比1次的情况,是存在的。
比如?
比如A2A3C1第一,那么C1肯定被B1挤掉了,但是不知道B1、A2、A3的排序,需要再比一次。这种情况下需要11次。
如果不选A2,选剩下8只是什么情况呢?
此时如果A3是第一名,那么肯定A1A2A3前三名,A3后的是第四名。
否则其他情况都需要再比一次。
如果不选A3,选剩下8只是什么情况呢?
除了上面2种情况(去掉A2,B1),其他情况都没办法10次推出结果,必须11次。