Abo

关于赛马问题(horse-racing problem)

腾讯面试题:赛马🐴问题


wallhaven-j5erl5

原来还有另一种赛马算法题,这里不提及,所谓的“田忌赛马”算法题,大概也是带记忆的广搜或者深搜吧,估摸着~

64马8道选top4

有64匹赛马,有8个跑道可以利用,赛马的速度是恒定的,不计时但记录每次比赛的名词,请问赛几次可以取得速度排名前四的赛马?

具体做法:

  1. 首先把64匹马随机分成8组,分别进行8次比赛,记录成绩。

  2. 再将每组第一名集合起来进行一次比赛。这是第九次比赛。

  3. 留下第九次比赛前四名的马所在的组。因为对于后四名的马所在的组来说根据判断原则没有一匹有机会进入前四的。

  4. 剩下的四组按照每组第一名在第九次比赛的成绩排序,这样按照判断原则,只剩下10匹马(如下)可能进入前4,而第一组的第一名肯定是跑最快的马。

第一组: 1 2 3 4
第二组: 1 2 3
第三组: 1 2
第四组: 1

我的理解

  • 找top3:2+2+1
  • 找top4:3+3+2+1
  • 找top5:4+4+3+2+1
  • 找top6:5+5+4+3+2+1

或许可以用动态规划来解决赛马问题,但是代码的时间复杂度为平方阶,所以先不编写

这样问题就变成9匹马找出前三快的。情况好的话跑一次可以得到,不行的话两次。

所以结果是10或者11

30马5道容1马选top3

问题:已知有30匹马,5个跑道,每个跑道只能容一匹马,没有计时器,至少需要比赛多少次,可以找出最快的前三匹马?

此题跟上面唯一不同的时候,这里要求每个赛道只能容得下一匹马,那也就是说,30= 5 x 6中,我们需要6次的赛马,能得到6只相对快的马,其实就是把上题的解法逻辑纵向化,接下来是6只马在5赛道上决绝出top3,这里需要两次,因为6 > 5,然后同理根据规律:找top3:2+2+1,只是在5匹马里面找出前两快的,1次即可

最终答案即使:6+2+1=9次,因此需要看清楚题意,即跑道一次性所能容得下的马量

25马5道选各个top马至少需要的比赛次数

有25匹马,有一个5个赛道的马场,每场比赛可以决出5匹马的排名,假设每匹马发挥稳定,且不会出现名次相同的情况。问:如果要知道25匹马中跑得最快的马,需要几场比赛?如果需要知道跑得第二快的马,需要几场比赛?第三快的呢?

转化成top1,top2,top3问题即可

口算易得:

  • top1:6

  • top2:6+1 // 在1+1匹马里面选出最快的一匹

  • top3:6+1 // 在2+2+1匹马里面选出最快的两匹

所以答案是6、7、7