w********h
发帖数: 12367 | 1 Yes. You are right.
f(x)=100/x + (x-1),
x is the gap as you called.
The minimum f(x)=10+(10-1)=19.
i.e.
First you try one on the 10th floor,
if the sample is broken,
you just need to try another one from 2nd to 9th.
The total number of trying is 8+1=9.
But this is not the worst case.
The worst case is you try 11th-20th,
21st-30th,...,91st-100th.
At last the first sample is broken on the 100th floor.
You need 100/10=10 for the tests of the first sample.
As to the second one,
you still need 9 time | s******a
发帖数: 38 | 2 Well, for this problem, I don't think this is the optimal solution.
I can surely beat the number 19.
Consider the following gap sequence:
14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 3, you will get at most 14.
【在 w********h 的大作中提到】
: Yes. You are right.
: f(x)=100/x + (x-1),
: x is the gap as you called.
: The minimum f(x)=10+(10-1)=19.
: i.e.
: First you try one on the 10th floor,
: if the sample is broken,
: you just need to try another one from 2nd to 9th.
: The total number of trying is 8+1=9.
: But this is not the worst case.
| s******a
发帖数: 38 | 3 The version I heard is, you should minimize the total number of floors you
climb up and down. Say, you drop one sample at 10th floor, it didn't break.
You can go down to get the sample, or you can climb to 20th floor and
continue your experiment with the second sample. Then you have to go
downstairs to get them. Of course, if it's broken, there is no need to
pick it up. But then you are stuck with the only sample left. This is
a tricky problem. I haven't got the answer yet. Maybe you guys can ba | x**e
发帖数: 315 | 4 这种方法的一个问题是为什么gap要每次是一样的
我的solution是18。
第一次试验第100-9^2=19层floor
第二次 100-8^2=36层
。。。
第九次 100-1^2=99层
第十次 100层
按最坏情况，试验次数分别是
1+Num{2,...,18}=18
2+Num{20,...,35}=18
3+Num{37,...,50}=17
。。。
9+Num{97,98}=11
结果比下面好。
ps:不是动脑筋问题，是数学问题。是etude的数据结构作业？
可以转到Science版，那儿有好多大牛。 | x**e
发帖数: 315 | 5 定义A(N)为对楼层总数为N的最佳方案的试验次数。
A(N)性质，不减函数，自然数映到自然数。
假设第一次在n层floor试验，两种情况
a:瓶碎，最坏情况从二楼到n-1楼重新试验。Num{2,...,n-1}=n-2
b:瓶不碎，则把第n层当作第一层，重新试验。
楼层数变为N-n+1。
所以A(N)<=1+Max{A(N-n+1),n-2} (1)
A(N)=Min{ Max{1+A(N-n+1),n-1} } 对所有1
A(N)=Min{ Max{1+A(m), N-m} } 对所有1
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
递推公式
从n=1楼层开始做归纳 |
|
