题目一(网易笔试题):25匹马5个跑道,怎样选出最快的5匹来?最少的次数

题目二(2016美团校招笔试题):30个马赛跑,5个跑道,找出前五名,至少找几次

题目三:64匹马,8条跑道,分几次可以选出最快的4匹?

********** ********** ********** ********** ********** **********

题目一:最多10次

题目二:最多12次

题目三:最多13次

********** ********** ********** ********** ********** **********

以题目一为例:

Step1:

先将25匹马按5条跑道分组:

1 24 22 2 16

6 19 3 9 7

11 8 10 14 15

12 17 18 13 20

21 5 23 4 25

将以上5组马分别进行比赛并排序。【比赛总次数:5】

24 22 16 2 1

19 9 7 6 3

15 14 11 10 8

20 18 17 13 12

25 23 21 5 4

Step2:

将最快马匹数(TopCount)除以赛道数(TrackCount)取整得到GroupCompIndex,即每组马匹中第几名应该进行第6场比赛。

GroupCompIndex = TopCount/TrackCount=5/5=1 (取每组的第二名进行比赛)

22 9 14 18 23

比赛结果为【23 22 18 14 9】 【比赛总次数:5+1=6】

依据第六场比赛结果Step1中的5组比赛进行排名:

第1组:25 23 21 5 4

第2组:24 22 16 2 1

第3组:20 18 17 13 12

第4组:15 14 11 10 8

第5组:19 9 7 6 3

依据上表分析:

第1组的第GroupCompIndex名肯定是前6名,因为比第1组的第【GroupCompIndex】名快的只有每组的第一名。【最重要的依据,遇到TopCount > GroupCompIndex * TrackCount第GroupCompIndex名肯定也是Topn】

第1组的第0..GroupCompIndex名(不包含GroupCompIndex)肯定是前5名,因为比第1组的第【GroupCompIndex】名大的只有最多5名。【获得Top5数据:25】

查找剩余的可能是Top4的成员列表

针对第n组,存在(【GroupCompIndex】+ 1)* (n - 1) 匹马比当前组的第【GroupCompIndex】匹马快。

也就是当前组有 TopCount - (【GroupCompIndex】+ 1)* (n - 1) 匹马是Top5或者比第【GroupCompIndex】名快的未进行比赛赛马可能是Top5

例如:

第1组TopCount - (【GroupCompIndex】+ 1)* (1 - 1) = 5-2*0 = 5;所以所有成员都有可能是Top4:【2321 5 4】

第2组TopCount - (【GroupCompIndex】+ 1)* (2 - 1) = 5-2*1 = 3;所以成员【2422 16】都有可能是Top4

第3组TopCount - (【GroupCompIndex】+ 1)* (3 - 1) = 5-2*2 = 1;所以成员【20】都有可能是Top4

第4组TopCount - (【GroupCompIndex】+ 1)* (4 - 1) = 5-2*3 = -1,小于0取本组第【GroupCompIndex】之前的马;所以成员【15】都有可能是Top4

第5组TopCount - (【GroupCompIndex】+ 1)* (5 - 1) = 5-2*4 = -3,小于0取本组第【GroupCompIndex】之前的马;所以成员【15】都有可能是Top4

由此得到Top4的列表:

23 21 5 424 22 16 20 15 19

再按照Step1,Step2进行递归运算,直到只存在一组时,直接取钱Topn。

Top4分组:

23 21 5 4 24

22 16 20 15 19

Top4分组排序: 【比赛总次数:6+2=8】

24 23 21 5 4

22 20 19 16 15

按照GroupCompIndex:2进行比较【21,19】 排序两组 【比赛总次数:8+1=9】【获得Top5数据:25,24,23】

24 23 21 5 4

22 20 19 16 15

Top2分组:

21 5 4 22 20

Top2分组排序:

22  21  20  5 4      【比赛总次数:9+1=10】【获得Top5数据:25,24,23,22,21】

赛马比赛--25匹马5个跑道,怎样选出最快的5匹来相关推荐

  1. 25匹马5个跑道,选出最快的5匹马?

    回顾之前问题:25匹马5个跑道,怎样选出最快的3匹? 答:先分成5组比赛并组内排序(从1到5速度减慢),再让每组第一名比赛,按照每组第一名的比赛结果从快到慢对每组排序(从A到E速度减慢),此时共计比赛 ...

  2. 腾讯面试题:64匹马,8个跑道,选出最快的四匹马

    题目描述 64匹马,8个跑道,需要赛多少场,选出最快的四匹马? 题目分析 题目本身是含义不清楚的,但是既然是程序员面试题,隐含条件是: 1.不能计时: 2.在最坏的情况下,至少多少轮比赛,必然能选择出 ...

  3. 程序员求助:腾讯面试题,64匹马8个跑道,多少轮选出最快的四匹

    昨天,有网友私信我,说去阿里面试,彻底的被打击到了.问了为什么网上大量使用ThreadLocal的源码都会加上private static?他被难住了,因为他从来都没有考虑过这个问题.无独有偶,今天笔 ...

  4. 25匹马,5个跑道,每次只能跑5匹,用最少的次数选出最快的前3匹

    跑马智力题 25匹马 5个跑道,每次只能跑5匹,至少需要多少次才能选出最快的前3匹? 分五组ABCDE,每组5匹: 先每组马pk,找出每组中的最快的马,标记为A1B1C1D1E1;----需比赛5场: ...

  5. 【字节跳动面试题】赛马问题 64匹马8个跑道最少几次赛出最快的4匹马

    2020年1月 字节跳动研发岗实习面试题 文章目录 赛马问题 一. 64匹马8个跑道 二. 36匹马6赛道 赛马问题 一. 64匹马8个跑道 64匹马8个跑道(不计时),问最少要比多少次,才能知道最快 ...

  6. 64匹马8个跑道需要多少轮才能挑选出最快的4匹马?

    64匹马8个跑道需要多少轮才能挑选出最快的四匹马? 第一步 把64匹马分成8组,每组各比赛一次,按照快慢进行排序,出现以下结果: 第二步 淘汰每一组的最后四匹,因为只需要跑的最快的四匹,即使出现一个组 ...

  7. 智力题:64匹马8个跑道,至少需要多少轮才能挑选出最快的4匹马

    题意: 64匹马8个跑道需要多少轮才能挑选出最快的四匹马? 解法: 1.分成八组,每组8匹马. 2.八组内部分别比赛,总共比八场,对每组的马排序. 每组的后四匹显然不是答案,直接淘汰. 现在只剩下八组 ...

  8. 有36匹马,六个跑道,用最少的次数选出最快的前3匹马

    有36匹马,六个跑道,用最少的次数选出最快的前3匹马 问题描述 分析 结论 问题描述 现有36匹马,6个赛道,没有计时器.现在要在36匹马中选出前三名,请问最少需要多少次比赛? 分析 根据问题我们可以 ...

  9. 智力题:36匹马,6条跑道,没有计时器,至少需要多少次选出最快的三匹马

    智力题:36匹马,6条跑道,没有计时器,至少需要多少次选出最快的三匹马 1.将马分成六组进行比赛,比赛六次,六组马分别都是有序的. 2.分别将六组马中跑得最快的马挑出来,让这六匹马再进行第七次比赛,将 ...

  10. 64匹马8条跑道找最快的4匹马

    假设跑道一样,马体力无限,速度均衡.有64匹马只有8条跑道,找最快的4匹马,至少要跑多少次? 答案:10-11次. 这类题,都是根据已知条件用尽量少的成本推导出尽量多的已知条件来进行最尽筛选 1.分8 ...

最新文章

  1. python学生管理系统界面-Python实现GUI学生信息管理系统
  2. JVM 参数及各部分含义(转)
  3. [C#]关于override和new在重写方法时的区别
  4. C++内联 inline的用法
  5. Linux学习-01-安装虚拟机与linux系统
  6. GIT入门笔记(18)- 标签创建和管理
  7. 使用Zipkin和Sleuth进行SpringBoot微服务跟踪
  8. main.js中的Vue.config.productionTip = false
  9. 因未能提交年度报告 瑞幸咖啡收到纳斯达克退市通知
  10. smtplib,发送邮件时的bug
  11. win7 更新android sdk,大神为你详解win7系统android sdk manager无法更新的处理对策
  12. 取消UltraEdit提示“文件可能不是DOS格式”
  13. c语言图书管理系统登录系统,C语言图书管理系统设计代码.doc
  14. 三菱a系列motion软体_三菱MDSDMSPV3系列连接接口说明
  15. rk3288 android7.1.2 4g模块调试(四)
  16. AudioRecord的用法
  17. 【Games104】 如果构建游戏世界
  18. getLocation需要在app.json中声明permission字段
  19. 多重继承时的虚函数表
  20. 每天一个npm包 之 qs

热门文章

  1. max的标准库头文件 c语言,float.h - C语言标准库
  2. python MyQR制作动态二维码
  3. 金仓数据库KingbaseES服务启动失败原因
  4. 下行法求最小割集案例_故障树分析方法(FTA)
  5. Beta 多样性排序分析方法与比较
  6. Java 2实用教程(第5版)实验指导与习题解答 第4章-类与对象
  7. 手机开热点但是电脑一直连接不上_电脑连接手机热点无法上网的三种解决方法...
  8. ConfigUtil.class.getResource
  9. 广数工业机器人五点法_盘点:国产工业机器人“四小龙”新业绩经营情况
  10. 运营的新手先简单认识一下ASO