25匹马的角逐

简介:

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

注意: "假设每匹马都跑的很稳定" 的意思是在上一场比赛中A马比B马快,则下一场比赛中A马依然比B马快。

稍微想一下,可以采用一种 竞标赛排序(Tournament Sort)的思路。

(1) 首先将25匹马分成5组,并分别进行5场比赛之后得到的名次排列如下:

              A组:  [A1  A2  A3   A4  A5]

              B组:  [B1  B2  B3   B4  B5]

              C组:  [C1  C2  C3  C4  C5]

              D组:  [D1  D2  D3  D4  D5]

              E组:  [E1  E2  E3   E4  E5]

      其中,每个小组最快的马为[A1、B1、C1、D1、E1]。

(2) 将[A1、B1、C1、D1、E1]进行第6场,选出第1名的马,不妨设 A1>B1>C1>D1>E1. 此时第1名的马为A1。

(3) 将[A2、B1、C1、D1、E1]进行第7场,此时选择出来的必定是第2名的马,不妨假设为B1。因为这5匹马是除去A1之外每个小组当前最快的马。

(3) 进行第8场,选择[A2、B2、C1、D1、E1]角逐出第3名的马。

(4) 依次类推,第9,10场可以分别决出第4,5名的吗。

因此,依照这种竞标赛排序思想,需要10场比赛是一定可以取出前5名的。

 

仔细想一下,如果需要减少比赛场次,就一定需要在某一次比赛中同时决出2个名次,而且每一场比赛之后,有一些不可能进入前5名的马可以提前出局。 当然要做到这一点,就必须小心选择每一场比赛的马匹。我们在上面的方法基础上进一步思考这个问题,希望能够得到解决。

(1) 首先利用5场比赛角逐出每个小组的排名次序是绝对必要的。

(2) 第6场比赛选出第1名的马也是必不可少的。假如仍然是A1马(A1>B1>C1>D1>E1)。那么此时我们可以得到一个重要的结论:有一些马在前6场比赛之后就决定出局的命运了(下面绿色字体标志出局)。

       A组:  [A1  A2  A3   A4  A5]

       B组:  [B1  B2  B3   B4  B5 ]

       C组:  [C1  C2  C3  C4  C5 ]

       D组:  [D1  D2 D3  D4  D5 ]

       E组:  [E1  E2  E3   E4  E5 ]

(3) 第7场比赛是关键,能否同时决出第2,3名的马呢?我们首先做下分析:

     在上面的方法中,第7场比赛[A2、B1、C1、D1、E1]是为了决定第2名的马。但是在第6场比赛中我们已经得到(B1>C1>D1>E1),试问?有B1在的比赛,C1、D1、E1还有可能争夺第2名吗? 当然不可能,也就是说第2名只能在A2、B1中出现。实际上只需要2条跑道就可以决出第2名,剩下C1、D1、E1的3条跑道都只能用来凑热闹的吗?

能够优化的关键出来了,我们是否能够通过剩下的3个跑道来决出第3名呢?当然可以,我们来进一步分析第3名的情况?

     ● 如果A2>B1(即第2名为A2),那么根据第6场比赛中的(B1>C1>D1>E1)。 可以断定第3名只能在A3和B1中产生。

     ● 如果B1>A2(即第2名为B1),那么可以断定的第3名只能在A2, B2,C1 中产生。

     好了,结论也出来了,只要我们把[A2、B1、A3、B2、C1]作为第7场比赛的马,那么这场比赛的第2,3名一定是整个25匹马中的第2,3名。

     我们在这里列举出第7场的2,3名次的所有可能情况:

     ①  第2名=A2,第3名=A3

     ②  第2名=A2,第3名=B1

     ③  第2名=B1,第3名=A2

     ④  第2名=B1,第3名=B2

     ⑤  第2名=B1,第3名=C1

(4)  第8场比赛很复杂,我们要根据第7场的所有可能的比赛情况进行分析。

      ①  第2名=A2,第3名=A3。那么此种情况下第4名只能在A4和B1中产生。

           ● 如果第4名=A4,那么第5名只能在A5、B1中产生。

           ● 如果第4名=B1,那么第5名只能在A4、B2、C1中产生。

不管结果如何,此种情况下,第4、5名都可以在第8场比赛中决出。其中比赛马匹为[A4、A5、B1、B2、C1]

      ②  第2名=A2,第3名=B1。那么此种情况下第4名只能在A3、B2、C1中产生。

           ● 如果第4名=A3,那么第5名只能在A4、B2、C1中产生。

           ● 如果第4名=B2,那么第5名只能在A3、B3、C1中产生。

           ● 如果第4名=C1,那么第5名只能在A3、B2、C2、D1中产生。

那么,第4、5名需要在马匹[A3、B2、B3、C1、A4、C2、D1]七匹马中产生,则必须比赛两场才行,也就是到第9场角逐出全部的前5名。

      ③  第2名=B1,第3名=A2。那么此种情况下第4名只能在A3、B2、C1中产生。

           情况和②一样,必须角逐第9场

      ④  第2名=B1,第3名=B2。 那么此种情况下第4名只能在A2、B3、C1中产生。

           ● 如果第4名=A2,那么第5名只能在A3、B3、C1中产生。

           ● 如果第4名=B3,那么第5名只能在A2、B4、C1中产生。

           ● 如果第4名=C1,那么第5名只能在A2、B3、C2、D1中产生。

那么,第4、5名需要在马匹[A2、B3、B4、C1、A3、C2、D1]七匹马中产生,则必须比赛两场才行,也就是到第9场角逐出全部的前5名。

        ⑤  第2名=B1,第3名=C1。那么此种情况下第4名只能在A2、B2、C2、D1中产生。

            ● 如果第4名=A2,那么第5名只能在A3、B2、C2、D1中产生。

            ● 如果第4名=B2,那么第5名只能在A2、B3、C2、D1中产生。

            ● 如果第4名=C2,那么第5名只能在A2、B2、C3、D1中产生。

            ● 如果第4名=D1,那么第5名只能在A2、B2、C2、D2、E2中产生。

那么,第4、5名需要在马匹[A2、B2、C2、D1、A3、B3、C3、D2、E1]九匹马中 产 生,因此也必须比赛两场,也就是到第9长决出胜负。

总结:最好情况可以在第8场角逐出前5名,最差也可以在第9场搞定。




本文转自我爱物联网博客园博客,原文链接:http://www.cnblogs.com/yydcdut/p/3906128.html,如需转载请自行联系原作者

相关文章
看见专精特新“小巨人”|专访北大英华赵晓海:法律信息化,道阻且长行则将至
2021年北大英华取得“北京市‘专精特新’中小企业”称号,2022年5月又荣获了“北京市‘专精特新’小巨人企业”称号。赵晓海说,北大英华还会积极争取成为国家级“专精特新”小巨人。未来,北大英华将面向全国法律用户提供更丰富的法律知识服务,公司在数据安全、服务器稳定性及性能上有更高的需求。
看见专精特新“小巨人”|专访北大英华赵晓海:法律信息化,道阻且长行则将至
民营火箭陆续上天,噱头还是突破?
近日,智能相对论(aixdlun)的一篇《中国民营火箭准备好了吗》被虎嗅、钛媒体、36kr、创业邦等创投媒体相继推荐,引发了网友热议。文章中表示,民营火箭的赛程已经过半,中国民营航天也正是进入了冲刺阶段。5月17日,零壹空间宣布,自主研发商业火箭“重庆两江之星”发射成功,而在今年4月,星际荣耀也发射了名为“双曲线一号S”的同类火箭,两家企业争相发射,标志着民营火箭赛局下半场的哨声被正式吹响,中国民营火箭的好戏这才正式拉开了帷幕。
民营火箭陆续上天,噱头还是突破?
PennApps 属于学生的黑客马拉松
Pando Daily的 Erin Griffith 待在校园的大礼堂里,350 多个学生面对着主席台,他们中很多人蜷缩在折叠椅里,打瞌睡,坐在他身边的家伙甚至微微打鼾。
199 0
PennApps 属于学生的黑客马拉松
黑客马拉松
厨房里堆满方便食品和提神饮料,工作台上有人在挑灯夜战,有人因为累极而进入梦乡……不同团队连续48小时的编程鏖战,目标是各自交出能够正常使用的Android应用程序——此情此景所呈现的是某一场黑客马拉松大赛(hackathon)的 “执行概念”阶段。
286 0
黑客马拉松
“黑客马拉松”让我们学到了什么?
黑客马拉松是一种开发软件的活动形式:开发者们在一定期间内协同开发软件。黑客马拉松为开发者和团体提供学习机会和场地,并把活动发布到网络上。开发者在这里玩得很开心。
290 0
启迪之星刘博:优秀的创业者=家国情怀+学者智慧+商业思维+江湖行动
实际上每个投资人真的不一样。每个机构的资金、投资范围,都是由他的背景、经验、习惯和他所见到的东西决定的,所以每个机构都不一样。大家不要以为这个机构这样,那个机构那样,但是有普遍规律,不代表一切,因为投资的事情,相对来说慎重、偶然的。
1890 0
区块链:2018年的第一场火还是第一场泡沫?听听大咖们怎么说
2018年的第一场火还是第一场泡沫?听听大咖们怎么说
1624 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等