o****e
发帖数: 80 | 1 【 以下文字转载自 BrainTeaser 讨论区 】
发信人: ogtree (好好努力), 信区: BrainTeaser
标 题: Re: 还是扔鸡蛋，N层楼M个鸡蛋咋办啊
发信站: BBS 未名空间站 (Thu Jul 8 16:19:07 2010, 美东)
i think for the case of 3 eggs, should be like this
start from n-th floor, then try middle floor of n/2-th , then use the 3rd
egg to try either upper half section
or lower half section,
so for the n-th floor, the max try will be (n+2)/2;
then go to the n-2 th floor, the max try will be n/2
and so on
so the sequence will be like this
n, n-2, n-4, n-6, ......... | s*******u
发帖数: 35 | 2 Let f_1(n) be the number of floors we can test with 1 egg and n throws.
f_2(n) be the number of floors we can test with 2 eggs and n throws.
f_3(n) be the number of floors we can test with 3 eggs and n throws.
Clearly, f_1(n)=n; Consider two eggs. Clearly the first throw has to be at
floor n because otherwise if the
egg breaks at n, we would not be able to test the floors below. Now if the
first egg does not break, we can
test f_2(n-1) more floors. So f_2(n)=n+f_2(n-1); Hence f_2(n)=(n+1
【在 o****e 的大作中提到】
: 【 以下文字转载自 BrainTeaser 讨论区 】
: 发信人: ogtree (好好努力), 信区: BrainTeaser
: 标 题: Re: 还是扔鸡蛋，N层楼M个鸡蛋咋办啊
: 发信站: BBS 未名空间站 (Thu Jul 8 16:19:07 2010, 美东)
: i think for the case of 3 eggs, should be like this
: start from n-th floor, then try middle floor of n/2-th , then use the 3rd
: egg to try either upper half section
: or lower half section,
: so for the n-th floor, the max try will be (n+2)/2;
: then go to the n-2 th floor, the max try will be n/2
| p*****k
发帖数: 318 | |
|
