快捷搜索:  as

这是一个田径比赛中的算法问题

  

这是一个田径比赛中的算法问题

  假定有二十五名短跑选手比赛竞争金银铜牌,赛场上有五条赛道,因此一次可以有五个人同时参赛。比赛不计时,只看相应的名次。假如选手的发挥是稳定的,也就是说如果张三比李四跑得快,李四比王五跑的快,那张三一定比王五跑的快。问最少需要几组比赛才能决出前三名?

  A1,B1,C1,D1,E1为各个组的第一名,且A1到E1顺序为冠军组的第一名到第五名;

  题目开头说只有五条跑道,而且不让用表来计时,那说明同一组最多只能有5个人来跑,而且每个人跑步的速度是无法量化的。

  Step2.找出第二名。冠军组的第二名会不会就是全部人中的第二名?那可不一定!我们假设冠军组的第一名来自A组,那冠军组的第二名不一定要比A组的第二名跑得快。所以A组的第二名需要和冠军组剩余了四个人得再跑一场才能决出银牌,等等,我们可别忘了题目中只需要我们找出25个人中跑的最快的前三名,那显然冠军组最后两名的存在就没有意义,果断out~

  最后,我们来找找问题中可能隐藏的答案,那就是最后一段对于“发挥稳定”的说明,既然快是“可传递的”,那似乎是节省赛跑次数的途径之一。

  可以看出季军的候选人中也是包含亚军的候选人的,刚好五个人一组,只需要再跑一次就找出了亚军和季军了!

  Step1.找出第一名。25个人分成5(A,B,C,D,E)组,每组5个人,跑5组,然后让每一组的第一名再跑一组,我们把这一组称为冠军组,冠军组的第一名就是所有人中的第一名。所以为了决出金牌,我们总共跑了6组。

  这个问题的解题过程带给我最大的启发就是在遇到问题时,最大化挖掘题目信息,去除信息中的噪音,我们就能得到一个相对最优的解,同样的思想也贯穿于我们的日常工作中。

  那这空出的两个位置要怎么安排才能更有利于减少比赛次数呢?那肯定是把第季军的候选人加进去才划算啊。

  平时工作之余,也常琢磨一些有趣的算法来打发时间,不过这里说的“算法”和算法工程师们搞的机器学习算法还是不太一样,为了好理解一点,我定义其为用计算机思维解决日常实际问题的方法或策略,今天要跟大家聊的这个经典算法其实是我们之前用于招聘算法相关岗位的笔试题之一,名曰“锦标赛排序问题”,相应解决这个问题的方法我们称之为锦标赛排序算法。

  其次,这个问题对效率是有要求的。意味着我们不止要决出前三名,还得找出效率最高的跑法,作为一枚优秀的算法,保证结果对的同时还得保证高效。

  截止目前,我遇到的真正解出该问题的人还是个位数,有兴趣的同学可以先不着急往下看,自己可以先推演一下

您可能还会对下面的文章感兴趣: