Google面试题求解:25匹马赛跑,5个跑道,怎么以最少的比赛次数来决出最快的3匹,马跑的时间未知,只知道马的先后顺序.

木舟

赞同来自: 数美招聘 jinxiu2216 staticor

  思路:  (1)25匹马分为5组,进行5次赛跑;  (2)由5组第一再跑一次,这样可以选出所有马最快的那匹;  (3)由最快的那匹的分组中的第二匹、第三匹和步骤(2)中的第一匹,第二匹,以及步骤(2)中的第三快,共五批马再跑一次  总共比赛7次

借个火

赞同来自:

先说一下对题目的理解:25匹马,5个跑道 跑的时间未知。也就是每次最多跑5匹,相同起点,相同终点,只能通过先后到达的顺序判断快慢。   我的答案也是7次。然后纠正下一楼的答案。   步骤(2)之后,这5匹中的第一名,就是这25匹中最快的一个。然后去找第2名和第3名   首先步骤(2)中最快的那一组的5匹马中的第2和第3 名,有可能比 步骤(2)中的第1名跑得还快   其次步骤(2)中第二名的5匹马中的第二名,有可能比步骤(3)中的第1名跑得还快   然后其他的马肯定不是前三名。   那么现在只有5匹马有可能是第2 或 第3名。所以这5匹马再跑一次,第1名和第2名就是25匹马中的第2第3名。   最后总结 7次,找出来这些马中 跑得快的 前三名

yuching93

赞同来自:

如果马跑的时间未知,那怎么能7次?你怎么确定每组的第二名不比每组的第一名快?我意思是没有马跑的时间下,假设第一组的第一名最快,而第一组的第二名,只差第一名一个马鼻,用楼上的方法不就有错吗?因为第一组的第二名的时间很可能比二,三,四,五组的第一名快啊   有错请指教,新手小白

wangmy03

赞同来自:

这个错误的答案既然还有三人点赞.根本不需要比赛七次.最多5次,甚至更少. 一.25匹马分为5组,进行5次赛跑; 二.5组第一比赛.选出第一的马.剩下有资格竞争第二名跟第三名的剩12匹马. 三.12匹马选出前两名就是第二三名了.而12匹马打乱重新去比赛只需要三次就能出结果.所以最多5次.

wangmy03

赞同来自:

之前答案错了.第二条.5组第一比赛完后..选出了第一名.. 然后第一名的那组第一次比赛的2,3名(这组第一名,所以前三还有两个名额可以竞争), 第二名那组的1,2名.(因为第二名这组最好的那个也才是第二名.所以你这组前三只剩两个名额) 第三名那组的第1名.(第三名这组只有这组的第一名有资格竞争,因为你这组最好的成绩是才第三,你最多只能竞争一下第三名的,你那组中输给你的马已经失去前三的资格.) (同理,第四名和第五名已经失去了竞争前三的资格,那么作为原先区域第一.原先区域的马就排除了前三的可能) 所以只有这5只马有资格竞争最快的第二名和第三名. 所以只需要再多一次.总共三次比赛.

要回复问题请先登录注册