[問題] Google Interview Question (2)

[RockLee (Now of all times)]

原始網址:
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次是最少的嗎?

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 111.252.88.12
推 Favonia:這網站描述的顯然不是最佳，因為 Round One 第3步兩次足矣
→ RockLee:不是應該三次嗎? Ex. (group 1[5~7], group 5[1~3]),
→ RockLee:(group2[5~7], group6[1~3]), (group3[5~7], group7[1~3])
推 pika0923:group 1[5~7] 先跟6比 再跟5或7其中之一比  兩次
→ RockLee:了解 所以照網站描述的方法 Round Two 應該也只需要兩次
→ RockLee:總共 16 次即可保證找出 25th 還有辦法更少嗎?