PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] Google Interview Question (2)

看板Prob_Solve (計算數學 Problem Solving)作者 (Now of all times)時間11年前 (2013/02/12 09:11), 編輯推噓2(2推 0噓 4→)
留言6則, 3人參與, 最新討論串1/9 (看更多)
原始網址: 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
推
02/13 04:58, , 1F
這網站描述的顯然不是最佳，因為 Round One 第3步兩次足矣
02/13 04:58, 1F
→
02/13 07:49, , 2F
不是應該三次嗎? Ex. (group 1[5~7], group 5[1~3]),
02/13 07:49, 2F
→
02/13 07:50, , 3F
(group2[5~7], group6[1~3]), (group3[5~7], group7[1~3])
02/13 07:50, 3F
推
02/13 08:49, , 4F
group 1[5~7] 先跟6比 再跟5或7其中之一比 兩次
02/13 08:49, 4F
→
02/13 12:36, , 5F
了解 所以照網站描述的方法 Round Two 應該也只需要兩次
02/13 12:36, 5F
→
02/13 12:37, , 6F
總共 16 次即可保證找出 25th 還有辦法更少嗎?
02/13 12:37, 6F
‣ 更多 RockLee 的文章
文章代碼(AID): #1H6PQrIL (Prob_Solve)
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 9 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共9篇)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 RockLee 的文章
文章代碼(AID): #1H6PQrIL (Prob_Solve)