作者RockLee (Now of all times)
看板Prob_Solve
标题[问题] Google Interview Question (2)
时间Tue Feb 12 09:11:13 2013
原始网址:
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
1F：推 Favonia:这网站描述的显然不是最佳，因为 Round One 第3步两次足矣 02/13 04:58
2F：→ RockLee:不是应该三次吗? Ex. (group 1[5~7], group 5[1~3]), 02/13 07:49
3F：→ RockLee:(group2[5~7], group6[1~3]), (group3[5~7], group7[1~3]) 02/13 07:50
4F：推 pika0923:group 1[5~7] 先跟6比 再跟5或7其中之一比 两次 02/13 08:49
5F：→ RockLee:了解 所以照网站描述的方法 Round Two 应该也只需要两次 02/13 12:36
6F：→ RockLee:总共 16 次即可保证找出 25th 还有办法更少吗? 02/13 12:37