原始網址:
http://www.careercup.com/question?id=4280852
題目:
49 race cars and no two have the same speed.
Now give you 7 tracks with equal length to find the 25th fastest car.
At least how many races are needed.(no time recorder)
這個題目有兩種可能的解讀,
比較簡單的解讀是一開始幸運選中25th的車,
要進行多少次比賽證明它是25th?
這種解讀答案應該是8次.
因為扣掉選中的車還有48台車,
每次可拿選中的車跟其它6台比,
48/6=8.
我想第二種解讀應該比較符合Google的程度,
最少要比多少次可以保證找出25th的車?
目前我覺得正確的方法中最少的應該是以下網站描述的18次:
http://www.sureinterview.com/shwqst/1062001/154001
該方法的一種 worst case:
1 2 3 4 13 14 XX <- group 1
5 6 7 8 15 16 XX <- group 2
9 10 11 12 17 18 XX <- group 3
19 20 XX 34 35 36 37 <- group 4
XX 28 29 38 39 40 41 <- group 5
XX 30 31 42 43 44 45 <- group 6
XX 32 33 46 47 48 49 <- group 7
(XX: 21 ~ 27)
不知道是否有比18次更少的方法?
或者有辦法證明18次是最少的嗎?

這網站描述的顯然不是最佳，因為 Round One 第3步兩次足矣

不是應該三次嗎? Ex. (group 1[5~7], group 5[1~3]),(group2[5~7], group6[1~3]), (group3[5~7], group7[1~3])

group 1[5~7] 先跟6比 再跟5或7其中之一比 兩次

了解 所以照網站描述的方法 Round Two 應該也只需要兩次總共 16 次即可保證找出 25th 還有辦法更少嗎?