w**********9
发帖数: 20 | 1 49 辆赛车. Assume for each one, it travels the track in the same amount
of time every time. Also assume no two finish the track in the same
amount of time. Suppose you have 7 tracks, but no timer. Design races to
find the 25-th fastest with minimal number of races.
mitbbs 曾经讨论过这个题，当时没有注意，现在已经搜索不到了。 欢迎大家讨论讨论
想了一个解法，不清楚还有没有更优解，特来请教
7次， 跑出 A1, A2, .... A7
B1, B2, ... B7
..
..
G1, G2, .....G7
第8次， 取 A4, B4, C4, .....G4
不失一般性，设A4为第一，B4为第二....
这样， A1, A2, A3, A4, B1, B2, 肯定在前24名（包括第24名）
再跑19次得到第25名
共需要 7 + 1 + 19 = 27次 | a***c
发帖数: 2443 | 2 the problem doesn't look like it's set up right. needs more constraints to
make a meaningful problem.
Does the original question say you can't race 49 cars all at once? | j*****4
发帖数: 292 | 3 use median finding algorithm
【在 w**********9 的大作中提到】
: 49 辆赛车. Assume for each one, it travels the track in the same amount
: of time every time. Also assume no two finish the track in the same
: amount of time. Suppose you have 7 tracks, but no timer. Design races to
: find the 25-th fastest with minimal number of races.
: mitbbs 曾经讨论过这个题，当时没有注意，现在已经搜索不到了。 欢迎大家讨论讨论
: 想了一个解法，不清楚还有没有更优解，特来请教
: 7次， 跑出 A1, A2, .... A7
: B1, B2, ... B7
: ..
: ..
| a***c
发帖数: 2443 | 4 best case 10 races with 1/19 chance.
don't know about worst case, 19? there's probably room for improvement here. | w**********9
发帖数: 20 | 5
【在 j*****4 的大作中提到】
: use median finding algorithm
| w**********9
发帖数: 20 | 6 不知道能不能说得详细点呢？我的这个方法第8步是median finding， 但第9步后，感
觉不太好弄。
【在 j*****4 的大作中提到】
: use median finding algorithm
|
|
