原题
想必田忌赛马的故事,大家都耳熟能详。但是,大家知道Goolge的童鞋们是怎么赛马的么?不过,首先,大家要先尝试一下:有25匹马,每次只能五匹一起跑,那么最少跑几次,才能确定前三甲呢?
分析
这样的题目,该如何分析呢?没有任何的名次信息,没有秒表,没有相机记录距离(题目中疏忽了:)),我们先简单一点,如何确定第一名呢?6次是可以的,例如可以有如下的方法:
每5匹马比赛一次,找到5个第一名,然后这5匹马进行比赛,得到第一名,6次; 首先5匹马进行比赛,得到第一名,此时剩下20匹马没有参与比赛。每次4匹,分为5组,一次和第一名比较。也是6次得到最终的第一名 ... 我们采用继续第一种方法分析,前三名的情况,如下表:
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 |
上表中A>B>C>D>E,A1>A2>A3>A4>A5。是由前五次得出的结果,因为我们只要前3的名次,排除掉不可能的马匹,变为如下的表格:
A1 | B1 | C1 | ||
A2 | B2 | |||
A3 | ||||
B3为何要排除呢,因为,如果B3不排除,则A1>A2>A3>B3。就是前四的名次了。剩下的6个里面,A1是第一名已经确定,那么剩下的5匹取前两名,即可得到全部前三甲。此时又赛了场。则总共赛了7场。