雁过无痕

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::


问题:
 

一共有25匹马,有一个赛场,赛场有5个赛道,就是说最多同时可以有5匹马一起比赛。假设每匹马都跑的很稳定,不用任何其他工具,只通过马与马之间的比赛,试问最少得比多少场才能知道跑得最快的5匹马?

 

思路:

先将25匹马分成五组,进行五场比赛。第六场比赛可以考虑都取各个小组的第一名(或第二名)。假设都取各小组的第一名,根据这场比赛的排名,将原来的小组分别编号为abcde,并将原来的25匹马分别编号为:

a1  b1  c1  d1  e1

a2  b2  c2  d2  e2

a3  b3  c3  d3  e3

a4  b4  c4  d4  e4

a5  b5  c5  d5  e5

其中XiX表示组的编号,i为在该组的排名,则有:
 a1 > b1 > c1 > d1 > e1
 
a1 > a2 > a3 > a4 > a5
 b1 > b2 > b3 > b4 > b5
         .......
 e1 > e2 > e3 > e4 > e5
  

注意到:跑得比a3b2c1这三匹马都快的只可能是a1a2b1,因而a3b2c1三匹马中跑得最快的必然是前四之一因此,第七场比赛,这三匹马必然参加,剩下两个名额待定。先考虑这三匹马的排名:

(下面用[]集合表示已确定是前五的马,用{}集合表示剩下的马中所有有可能是前五的马。)

  a3 b2 c1 a3 c1 b2:  [a1, a2, a3]  +  {a4,a5,b1,b2,c1}

  b2 a3 c1:  [a1,b1,b2]  +  { a2,a3, b3,b4}

  b2 c1 a3:  [a1,b1,b2]  +  {a2,b3,b4,c1,c2,d1}

  c1 a3 b2:  [a1,b1,c1]  +  {a2,c2,c3,d1,d2,e1 }

为了能在第八场确定前五,必须将上面的{a2,b3,b4,c1,c2,d1} {a2,c2,c3,d1,d2,e1} 的候选马匹数减少到五匹,因而剩下的两个名额必须是这两个集合的重复元素,即是{a2, c2, d1}中的两个。由于a2跑得比a3快,若选择a2的话,不能利用前面的分析,因而剩下两匹马选择 c2 d1

 

第七场比赛:a3b2c1c2d1 的前两名是:

  a3   :  [a1, a2, a3]  +   {a4, a5, b1, b2, c1}的前二名(由第八场比赛决定)

b2 a3:  [a1, b1, b2]  +   {a2,a3, b3,b4}的前二名

b2 c1:  [a1, b1, b2]  +   {a2, b3, b4, c1, max(c2, d1)} 的前二名

c1 a3:  [a1,a2,a3,b1,c1]  (第七场就可确定前五)

c1 b2:  [a1,b1,c1]  +    {a2,b2,b3,c2,d1}的前二名

c1 c2:  [a1,b1,c1,c2]  +  {a2,b2,c3,d1}的第一名

c1 d1:  [a1,b1,c1,d1]  +  {a2,b2,c2,d2,e1}的第一名

 

因而,最少七场比赛,最多八场比赛就可确定跑得最快的5匹马。

 

posted on 2010-12-03 20:51 flyinghearts 阅读(3288) 评论(14)  编辑 收藏 引用 所属分类: 算法

评论

# re: 25匹马取前5[未登录] 2010-12-03 22:28 清正
没看明白 为什么说 a3、b2、c1三匹马中跑得最快的必然是前四之一?
比如 a5 b5 也可能占据 后2位啊 即使 a1 b1 a2 占据前三的话?  回复  更多评论
  

# re: 25匹马取前5 2010-12-03 22:30 dwtsteven
其实就是使用归并排序。

博主的话不明白。  回复  更多评论
  

# re: 25匹马取前5 2010-12-09 13:29 flyinghearts
@清正
你误解了,在a组内,一定有 a1 > a2 > a3 > a4 > a5  回复  更多评论
  

# re: 25匹马取前5 2010-12-09 13:31 flyinghearts
@dwtsteven
这道题,根本就不能用归并排序。
  回复  更多评论
  

# re: 25匹马取前5 2011-07-07 13:39 (与狼共舞)
要用排除法.

分A,B,C,D,E 共5组.

第一轮分5组, 比5场. 每场最后两名淘汰, 因为不可能进前三.

A1,A2,A3, ... E1,E2,E3 进入后面的比赛.



第6场, 前面每组的第2名比, 本场得第一名的组的第2和第3名进入后面比赛.

例如A2 得第1名. 举例 C2 的前面有 C1, A2, A1, 所以 C2, C3 都被淘汰.

共有 A1, A2, A3, B1, C1, D1, E1 共7人进入后面的比赛.



第7场: A1, B1, C1, D1, E1 比赛, 分两种情况:

第1种: A1 得第3名或之后的名次, 比赛结束. 胜利者是本场比赛前三名.

第2种: A1 得 第1或第2名, 需第8场比赛. 最后两名被淘汰.



第8场: 去掉第7场的最后两名, 补充 A2, A3 进行比赛. 胜利者是本场比赛前三名.



第6场不用每场的第1名比容易理解一些, 认为第1名所在组的第2名比其他组的第2名快是错误的假设.

  回复  更多评论
  

# re: 25匹马取前5 2011-07-07 22:32 flyinghearts
@(与狼共舞)
是25取前5, 不是取前3。你的做法,第一步就错了。
  回复  更多评论
  

# re: 25匹马取前5 2011-09-14 18:23 657844136
300轮才是对的  回复  更多评论
  

# re: 25匹马取前5 2011-09-14 18:27 657844136
博主写了一大串东东其实都是错的,禁不起推敲,最科学的是300轮。  回复  更多评论
  

# re: 25匹马取前5[未登录] 2011-09-21 18:23 Jeff
分析非常漂亮,赞一个!  回复  更多评论
  

# re: 25匹马取前5 2012-02-04 05:26 random
我个人觉得有可以修改的地方:
引用:
① a3 b2 c1 或 a3 c1 b2: 则 [a1, a2, a3] + {a4,a5,b1,b2,c1}
② b2 a3 c1: [a1,b1,b2] + { a2,a3, b3,b4}
③ b2 c1 a3: [a1,b1,b2] + {a2,b3,b4,c1,c2,d1}
④ c1 a3 b2: [a1,b1,c1] + {a2,c2,c3,d1,d2,e1 }

问题一:
一共有6种可能,这里只讨论了5种,遗漏了:
c1 b2 a3

问题二:
④ c1 a3 b2: [a1,b1,c1] + {a2,c2,c3,d1,d2,e1 } 中,
{}内遗漏a3: 可能发生[a1,b1,c1,a2,a3]的组合


  回复  更多评论
  

# re: 25匹马取前5 2012-02-28 20:25 flyinghearts
@random
确实是遗漏了a3。看得真认真。
这段话只是一个思考过程,通过分析,从其中发现可能解决问题的做法,再去进一步验证这种做法是否正确。这个思考过程,不一定要求完全正确、全面,只要在思考中有了灵感,可以随时中断思考。因此,进一步对c1 b2 a3的讨论并不是必要的。
  回复  更多评论
  

# re: 25匹马取前5 2012-10-11 16:18 chow
分析应该再简明一点  回复  更多评论
  

# re: 25匹马取前5 2013-01-15 20:37 Jack47

注意到:跑得比a3、b2、c1这三匹马都快的只可能是a1、a2、b1,因而a3、b2、c1三匹马中跑得最快的必然是前四之一。

这段话有问题吧?
如果是以下这种情况呢:
A1>A2>A3>A4
A3>B1>B2
B1>C1
第四名可能是A4,也可能是B1
  回复  更多评论
  

# re: 25匹马取前5 2013-03-21 20:48 flyinghearts
@Jack47
没问题,就是按你这个条件, 若第四名可能是A4或B1,那么 A3 > A4,A3 > B1,可知, A3排在A4、B1前,也进了前四。  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理