var _gaq = _gaq || []; _gaq.push(['_setAccount', 'UA-333696-1']); _gaq.push(['_trackPageview']); _gaq.push(['_trackPageLoadTime']); (function() { var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true; ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s); })();
  • 2009年05月19日

    赛马

    分类:

    赛马

    一共有25匹马,每匹马都以恒速奔跑但速度不同于其它马匹。有一个赛场,赛场仅有5个赛道,也就是说每个赛道最多同时可以有5匹马一起比赛。如果你需要找出跑的最快的3匹马,最少得多少场比赛?

     

    解决方案:这个问题测试你的基本分析技能。为找到最快的3匹马,当然所有的马都需要被测试。于是自然第一步是把马匹划分成5(每组马匹为1-5, 6-10, 11-15, 16-20, 21-25)5次比赛后,我们得到每组的排序,假设排序如下数序(比如在6-10组中6最快而10最慢)。这意味着1, 6, 11, 1621是每组中最快的马匹。

     

    当然每组中最后的两匹被剔除。现在我们把1, 6, 11, 1621放一起进行1次比赛。我们知道每组中,如果最快的马排第5或者第4在所有25匹马中,那么在那组中所有的马不可能排进前3;如果它排第3,在那组中不会有其它马排入前3;如果排第2,在那组中还有一匹马可能排进前3;如果排第一,在那组中可能还有两匹马排进前3。假设 A1>B1>C1>D1>E1,淘汰的用--表示,如下(选出排名前3的马):

    A A1 A2 A3 -- --

    B B1 B2 -- -- --

    C C1 -- -- -- --

    D -- -- -- -- --

    E -- -- -- -- --

    把剩下的A2,A3,B1,B2C1放一起进行1次比赛,即可得出前3,总计7场。

     

    如果需要找出跑的最快的5匹马,则如下(选出排名前5的马):

    A A1 A2 A3 A4 A5

    B B1 B2 B3 B4 --

    C C1 C2 C3 -- --

    D D1 D2 -- -- --

    E E1  -- -- -- --

    此时把A2,B1,A3,B2C1放一起进行1次比赛,得出前3有以下几种可能:

    1.     A1,A2,A3,如下(选出排名前5的马):

    A A1 A2 A3 A4 A5

    B B1 B2 -- -- --

    C C1 -- -- -- --

    D -- -- -- -- --

    E -- -- -- -- --

    把剩下的A4,A5,B1,B2,C1放一起进行1次比赛,即可得出前5,总计8场。

     

    2.     A1,A2,B1,如下(选出排名前5的马):

    A A1 A2 -- -- --

    B B1 B2 B3 -- --

    C C1 C2 -- -- --

    D D1 -- -- -- --

    E -- -- -- -- --

    把剩下的B2,B3,C1,C2,D1放一起进行1次比赛,即可得出前5,总计8场。

     

    3.     A1,B1,B2,如下(选出排名前5的马):

    A A1 -- -- -- --

    B B1 B2 B3 B4 --

    C C1 C2 -- -- --

    D D1 -- -- -- --

    E -- -- -- -- --

    把剩下的B3,B4, C1,C2,D1放一起进行1次比赛,即可得出前5,总计8场。

     

    4.     A1,B1,C1,如下(选出排名前5的马):

    A A1 -- -- -- --

    B B1 -- -- -- --

    C C1 C2 C3 -- --

    D D1 D2 -- -- --

    E E1 -- -- -- --

    把剩下的C2,C3,D1,D2,E1放一起进行1次比赛,即可得出前5,总计8场。

    分享到:

    历史上的今天:

    工作流现状 2006年05月19日