楼层扔鸡蛋问题

[Changsheng Jiang]

在看群里历史中问题, 可惜以前不曾加入. 这里抛一个问题, 权作引玉.

2 个鸡蛋, 确定在 100 层楼的临界破碎层数, 最少需要扔几次? 3 个鸡蛋?

[const]

2个要14次，3个鸡蛋要得次数应该是求[n*(n+1)+(n-1)*n+(n-2)*(n-1)+ ... + 2*1]/2= n*(n
+1)*(2*n+4)/12 >=100的n的最小值(8)。不知道是不是？
-----------------------------------------------------
初来乍道，多多指教！

[Changsheng Jiang]

应该是对的

Yours sincerely,
Changsheng Jiang

2008/10/12 const <zhongli...@gmail.com>

[樊帆]

我连问题都没看懂，汗自己一个先

2008/10/12 Changsheng Jiang <jiang...@gmail.com>:

[鋆邓]

这题我曾在ICPC比赛中做过，解法是：

求解N个鸡蛋，k次投掷最多可以测到多少层楼，这个用DP解：

第一次砸砸破了是测出其下F(N-1,k-1)种（不包括该楼，因为该楼必破），没破时可以测出其上F(N, k-1)搂以内的，

所以F(N,k) = F(N-1,k-1) + 1 + F(N,k-1)

然后N固定时，k越大显然能测的楼也越多，是递增的

在F(N)表里，根据楼数二分查找需要的次数。

2008/10/12 樊帆 <fanfan1...@gmail.com>

[Patrol Sun]

这个鸡蛋是什么意思呀？今天EMC笔试有这个题目，可惜我不会 真后悔没有好好看咱maillist里的帖子呀

2008/10/11 Changsheng Jiang <jiang...@gmail.com>

[Peng Du]

yes
这个题目就用动态规划做就好了

On 10月14日, 下午12时47分, "鋆邓" <tdzl2...@gmail.com> wrote:
> 这题我曾在ICPC比赛中做过，解法是：
> 求解N个鸡蛋，k次投掷最多可以测到多少层楼，这个用DP解：
> 第一次砸砸破了是测出其下F(N-1,k-1)种（不包括该楼，因为该楼必破），没破时可以测出其上F(N, k-1)搂以内的，
> 所以F(N,k) = F(N-1,k-1) + 1 + F(N,k-1)
> 然后N固定时，k越大显然能测的楼也越多，是递增的
> 在F(N)表里，根据楼数二分查找需要的次数。
>

> 2008/10/12 樊帆 <fanfan19830...@gmail.com>
>
>
>
> > 我连问题都没看懂，汗自己一个先
>
> > 2008/10/12 Changsheng Jiang <jiangzuo...@gmail.com>:

> > > 应该是对的
>
> > > Yours sincerely,
> > > Changsheng Jiang
>

> > > 2008/10/12 const <zhongliangk...@gmail.com>

>
> > >> 2个要14次，3个鸡蛋要得次数应该是求[n*(n+1)+(n-1)*n+(n-2)*(n-1)+ ... + 2*1]/2= n*(n
> > >> +1)*(2*n+4)/12 >=100的n的最小值(8)。不知道是不是？
> > >> -----------------------------------------------------
> > >> 初来乍道，多多指教！
>
> > >> On 10月11日, 下午11时28分, "Changsheng Jiang" <jiangzuo...@gmail.com> wrote:
> > >> > 在看群里历史中问题, 可惜以前不曾加入. 这里抛一个问题, 权作引玉.
>

> > >> > 2 个鸡蛋, 确定在 100 层楼的临界破碎层数, 最少需要扔几次? 3 个鸡蛋?- 隐藏被引用文字 -
>
> - 显示引用的文字 -