[CS] Career Cup上的一道题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

[CS] Career Cup上的一道题

[CS] Career Cup上的一道题# JobHunting - 待字闺中

G*A2011-10-31 07:10

1 楼

朋友发来问我，说是答案是14 steps maximum. 但是我觉得如果用binary search tree
,最多7 steps就找出来了。请大家看看我是哪里没理解对。谢谢
************
Q: There is a building of 100 floors. If an egg drops from the Nth floor or
above it will break. If it’s dropped from any floor below, it will not
break. You’re given 2 eggs. Find N, while minimizing the number of drops
for the worst case.
************

f*t2011-10-31 07:10

2 楼

你只有两个蛋，怎么binary search..

l*32011-10-31 07:10

3 楼

问题的关键在于你总共只有两个egg,binary search的话容易俩都摔碎了,这样你就没办
法找出具体楼层了

tree
or

【在 G****A 的大作中提到】

: 朋友发来问我，说是答案是14 steps maximum. 但是我觉得如果用binary search tree
: ,最多7 steps就找出来了。请大家看看我是哪里没理解对。谢谢
: ************
: Q: There is a building of 100 floors. If an egg drops from the Nth floor or
: above it will break. If it’s dropped from any floor below, it will not
: break. You’re given 2 eggs. Find N, while minimizing the number of drops
: for the worst case.
: ************

G*A2011-10-31 07:10

4 楼

这个明白，但是任何方法都不可能2蛋保证找到那个n。
刚才网上搜了一下答案，好像是既要minimize the overall steps,又要maximize the
coverage of each step.

【在 f*******t 的大作中提到】

: 你只有两个蛋，怎么binary search..

k*n2011-10-31 07:10

5 楼

为什么不能保证两蛋找到n？

the

【在 G****A 的大作中提到】

: 这个明白，但是任何方法都不可能2蛋保证找到那个n。
: 刚才网上搜了一下答案，好像是既要minimize the overall steps,又要maximize the
: coverage of each step.

d*t2011-10-31 07:10

6 楼

tree
or
Worst case scen.

【在 G****A 的大作中提到】

G*A2011-10-31 07:10

7 楼

说说看啊。

【在 k****n 的大作中提到】

: 为什么不能保证两蛋找到n？
:
: the

d*u2011-10-31 07:10

8 楼

能把题目用中文解释一下吗？没看懂。

tree
or

【在 G****A 的大作中提到】

d*e2011-10-31 07:10

9 楼

drop the first egg in floor 1, 2, 4, 8, 16, 32, 64, 100
if it is broken at some floor, like 64, start from 32, and increment by 1, 2
, ..
7 step is not enough, if it is broken at 100th floor

【在 G****A 的大作中提到】

: 说说看啊。