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次,找出来这些马中 跑得快的 前三名
如果马跑的时间未知,那怎么能7次?你怎么确定每组的第二名不比每组的第一名快?我意思是没有马跑的时间下,假设第一组的第一名最快,而第一组的第二名,只差第一名一个马鼻,用楼上的方法不就有错吗?因为第一组的第二名的时间很可能比二,三,四,五组的第一名快啊
 
有错请指教,新手小白
这个错误的答案既然还有三人点赞.根本不需要比赛七次.最多5次,甚至更少.
一.25匹马分为5组,进行5次赛跑;
二.5组第一比赛.选出第一的马.剩下有资格竞争第二名跟第三名的剩12匹马.
三.12匹马选出前两名就是第二三名了.而12匹马打乱重新去比赛只需要三次就能出结果.所以最多5次.
**之前答案错了.第二条.5组第一比赛完后..选出了第一名..**
**然后第一名的那组第一次比赛的2,3名(这组第一名,所以前三还有两个名额可以竞争),**
**第二名那组的1,2名.(因为第二名这组最好的那个也才是第二名.所以你这组前三只剩两个名额)**
**第三名那组的第1名.(第三名这组只有这组的第一名有资格竞争,因为你这组最好的成绩是才第三,你最多只能竞争一下第三名的,你那组中输给你的马已经失去前三的资格.)**
**(同理,第四名和第五名已经失去了竞争前三的资格,那么作为原先区域第一.原先区域的马就排除了前三的可能)**
**所以只有这5只马有资格竞争最快的第二名和第三名.**
**所以只需要再多一次.总共三次比赛.**

要回复问题请先登录注册