青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

雁過無痕

  C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理 ::


問題:
 

一共有25匹馬,有一個賽場,賽場有5個賽道,就是說最多同時可以有5匹馬一起比賽。假設每匹馬都跑的很穩定,不用任何其他工具,只通過馬與馬之間的比賽,試問最少得比多少場才能知道跑得最快的5匹馬?

 

思路:

先將25匹馬分成五組,進行五場比賽。第六場比賽可以考慮都取各個小組的第一名(或第二名)。假設都取各小組的第一名,根據這場比賽的排名,將原來的小組分別編號為a、bc、d、e,并將原來的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
  

注意到:跑得比a3、b2c1這三匹馬都快的只可能是a1、a2、b1,因而a3b2、c1三匹馬中跑得最快的必然是前四之一。因此,第七場比賽,這三匹馬必然參加,剩下兩個名額待定。先考慮這三匹馬的排名:

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

  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。

 

第七場比賽:a3、b2c1c2、d1 的前兩名是:

  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 閱讀(3528) 評論(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??吹谜嬲J真。
這段話只是一個思考過程,通過分析,從其中發現可能解決問題的做法,再去進一步驗證這種做法是否正確。這個思考過程,不一定要求完全正確、全面,只要在思考中有了靈感,可以隨時中斷思考。因此,進一步對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前,也進了前四。  回復  更多評論
  

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            在线午夜精品| 国产精品网站视频| 一本久久综合亚洲鲁鲁| 亚洲高清在线精品| 亚洲黄色在线| 亚洲天堂av图片| 午夜视频一区| 久久久噜噜噜久噜久久| 欧美成人午夜| 亚洲精品国精品久久99热一| 99成人在线| 亚洲一区二区三区在线| 欧美在线二区| 欧美电影在线观看完整版| 欧美日韩国产另类不卡| 国产欧美va欧美不卡在线| 在线看片日韩| 亚洲欧美日韩中文播放| 免费亚洲一区| 亚洲狼人综合| 久久久久久久综合狠狠综合| 欧美日韩免费网站| 韩国一区电影| 亚洲专区一区| 欧美国产日韩一区二区| 亚洲一区免费视频| 欧美高清视频免费观看| 国产欧美一区在线| 夜夜嗨av一区二区三区网页| 老**午夜毛片一区二区三区| 一本色道久久88精品综合| 久久久无码精品亚洲日韩按摩| 欧美日韩伦理在线免费| 亚洲国产你懂的| 久久精品夜色噜噜亚洲a∨ | av成人免费在线| 欧美在线1区| 欧美午夜宅男影院| 亚洲精品乱码久久久久久按摩观| 欧美在线中文字幕| 日韩视频一区二区三区在线播放| 欧美资源在线观看| 国产精品一区二区黑丝| 亚洲视频精选在线| 亚洲国产欧美另类丝袜| 久久综合亚州| 怡红院精品视频在线观看极品| 午夜视频在线观看一区二区| 一区二区三区国产精品| 欧美日韩不卡在线| 亚洲精品自在在线观看| 欧美mv日韩mv国产网站app| 欧美在线一级va免费观看| 国产精品日韩欧美一区| 亚洲一区二区三区四区五区黄| 亚洲国产精品va在看黑人| 免费成人黄色| 狠狠色丁香婷婷综合| 99精品视频免费全部在线| 蜜臀av国产精品久久久久| 午夜精品视频| 国产日韩在线视频| 久久久久国产成人精品亚洲午夜| 亚洲免费小视频| 国产精品自拍视频| 欧美一区永久视频免费观看| 亚洲视频在线观看一区| 欧美日一区二区三区在线观看国产免| 99精品视频免费| 99成人在线| 国产精品久99| 久久国产视频网| 久久久久久亚洲精品不卡4k岛国| 伊人久久大香线| 亚洲第一天堂无码专区| 欧美久久在线| 亚洲欧美日韩专区| 亚洲欧美国产一区二区三区| 国产一区二区成人久久免费影院| 久久精品一区二区三区四区| 久久免费观看视频| 亚洲肉体裸体xxxx137| 亚洲免费电影在线| 国产九区一区在线| 麻豆乱码国产一区二区三区| 欧美激情中文字幕乱码免费| 亚洲欧美亚洲| 久久综合狠狠综合久久激情| 日韩亚洲国产精品| 小黄鸭精品aⅴ导航网站入口| 在线观看国产一区二区| 一本到12不卡视频在线dvd| 国产亚洲人成a一在线v站 | 亚洲国产成人久久综合一区| 欧美精品aa| 久久精品国产久精国产爱| 欧美成在线视频| 久久精品视频免费播放| 欧美国产综合视频| 欧美一区二区视频在线| 免费不卡在线观看| 午夜精品久久久久影视| 欧美www视频| 久久国产主播精品| 欧美日韩视频在线第一区| 老司机午夜免费精品视频| 欧美日韩一二三区| 免费成人激情视频| 国产精品欧美久久| 亚洲人成77777在线观看网| 国内精品模特av私拍在线观看| 日韩视频第一页| 亚洲区一区二区三区| 久久久精品五月天| 欧美一级专区| 欧美日韩在线高清| 亚洲国产成人久久综合| 欧美阿v一级看视频| 宅男精品视频| 麻豆成人综合网| 久久精品一二三| 国产精品久久久久久av福利软件 | 欧美一区2区视频在线观看| 欧美激情一区二区三区全黄| 性欧美精品高清| 欧美1级日本1级| 国产精品福利在线观看网址| 亚洲大胆视频| 136国产福利精品导航网址应用| 午夜精品久久久久久久久| 午夜精品福利在线| 国产精品啊v在线| 夜夜爽夜夜爽精品视频| 这里只有精品视频| 欧美日韩系列| 一本高清dvd不卡在线观看| 夜夜爽www精品| 欧美日韩视频在线第一区| 亚洲精选在线| 亚洲在线播放电影| 国产精品日韩精品| 欧美一区二区三区日韩视频| 久久成人免费网| 国产在线欧美日韩| 久久久久久久久久久成人| 免费观看在线综合色| 亚洲国产精品一区二区尤物区| 另类春色校园亚洲| 亚洲国产日韩欧美综合久久| 日韩视频一区二区三区在线播放 | 久久aⅴ国产紧身牛仔裤| 久久九九热免费视频| 黄色精品一区二区| 美女诱惑一区| 夜夜嗨av一区二区三区网页| 香蕉免费一区二区三区在线观看 | 韩国欧美一区| 免费中文字幕日韩欧美| av成人毛片| 久久久久久夜| 亚洲人成网站在线播| 欧美视频免费在线观看| 午夜精品免费在线| 亚洲国产你懂的| 欧美一区二区免费观在线| 在线精品视频一区二区三四| 欧美日韩一区二区三区四区五区| 亚洲欧美视频在线观看| 亚洲国产影院| 久久av在线| 99www免费人成精品| 国产一区二区三区四区老人| 欧美激情视频一区二区三区免费 | 久久aⅴ国产紧身牛仔裤| 欧美一区二区三区视频免费播放| 国产三级欧美三级日产三级99| 久久久久久亚洲精品杨幂换脸| 亚洲美女91| 免费亚洲视频| 香蕉久久夜色精品国产使用方法| 在线观看亚洲视频| 国产精品美女999| 欧美国产精品中文字幕| 欧美专区在线观看一区| aa级大片欧美三级| 欧美高清成人| 久久国产精品久久久| 夜夜嗨一区二区| 亚洲国产一区二区三区高清| 国产欧美日韩综合一区在线播放| 欧美人与性禽动交情品| 老巨人导航500精品| 西瓜成人精品人成网站| 这里只有精品在线播放| 亚洲精品久久久一区二区三区| 免费中文字幕日韩欧美| 久久精品国产一区二区三区免费看 | 亚洲高清视频在线| 国产日韩欧美综合精品| 国产精品日日摸夜夜添夜夜av|