作者kiedveian (極地之星光)
看板Inference
標題Re: [問題] 一題關於賽馬的題目
時間Sun Nov 27 09:10:20 2011
※ 引述《ds0319 (撲撲撲)》之銘言：
: 其實是面試的題目
: 只是我好想知道答案...
: 就是說今天有100隻馬，要找出最快的前三隻
: 但是跑道只有三個，也就是說一次最多三隻馬下去跑分出勝負
: 快的馬永遠都會跑的比慢的馬快
: 請問最少要跑幾輪比賽
我的方法同前推文所寫
(33+11+4+1+1) + 2 + 2 = 54次
詳細一點為
(33+11+4+1+1) +(1+1)+(1+1)
使用方法為
1.先選出第一名
2.從輸給第一名中選第二名
3.從輸給第二名中選第三名
使用這個方法必須依序選出一二三名
否則不確定第一名，可能輸給第一名的會非常的多
定義a與b ，a為輸給第1名的，b為輸給第2名的
找出第一名共5個階段
其中第一階段的餘數併入第3階段比
100
33....1 a b
11....0 a b
4.....0 a b
1.....1 a
b
1.....0 a
共33+11+4+1+1輪
第5階段操作的正確的話，可省去第4階段的b
可想成45階段選出第一名與第四名，第四名除去、二三名為a
---------------------第5階段說明分隔線-------------------
情況為第4階段 勝出1+剩餘1
因此還有一個名額
假設當時名次為 123 x ，x為剩餘的，3應為第4階段的b
選出1、3、x當做第5階段的比賽
名次 1 2 3
i. 1 3 x 名次為123x
j. 1 x 3 名次為1x23 或 12x3
k. x 1 3 名次為x123
i狀況下，3會變成第5階段的 a，因此第4階段的b可忽略
j或k的狀況下，3不可能是第3名，第4階段的b也可忽略
--------------------說明結束分隔線-----------------------
找出第二名，同等於簡化後的原題
由剛產生的5個a下去比
第2階段與第1階段的餘數比
1.....2 b
1.....0 b
共1+1輪
第三名則為前面產生的b(4-1)+2=5個
比較方法同上
1.....2
1.....0
共1+1輪
(33+11+4+1+1) + 2 + 2 = 54次
以上，歡迎討論
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.117.117.13
※ 編輯: kiedveian 來自: 59.117.117.13 (11/27 10:10)
→ puzzlez:第二名在其他輪中 不是也有可能是第一名？ 11/27 13:09
是的，但在只要沒遇到第一名，會前進到四強
推 closetou:請問你的第二階段為什麼不是11...1而是11...0 11/27 13:22
因為是33下去分隊，第一階段的餘數不包含在內
※ 編輯: kiedveian 來自: 59.117.117.13 (11/27 13:27)
→ puzzlez:終於看懂了0.0....這題出在面試還滿過分的 11/27 14:52
→ puzzlez:這個有考慮到 第3名不小心與第1名在一起時被淘汰的情形嗎? 11/27 14:56
如果123名同組，取第1名時會將第3名分至b組
如果第1、3名同組而第2名不同組
取第1名時會將第3名分至a組
取第2名時會將第3名分至b組
※ 編輯: kiedveian 來自: 59.117.117.13 (11/27 15:12)
推 closetou:我的方法跟原po略有不同 11/27 15:29
→ closetou:恕小弟無能，研究很久還是看不太懂 11/27 15:29
→ closetou:我的方法po在Tech_Job版，有不一樣的地方煩請指正 11/27 15:30
推 puzzlez:哦...原來如此...我沒問題了 謝謝 :-) 11/27 16:40