鸡蛋问题，完全不懂算法 - 编程论坛

#2

rjsp2013-03-30 14:17

什么数据都没有，你自己觉得这种问题有解吗？
类似的问题我见过，比如两只鸡蛋，一百层楼，求最佳策略

#3

azzbcc2013-03-30 14:18

假设有 N层楼，第一次肯定在 N/2测试，失败就在 N/4测试，成功就在 3*N/4测试、、、、、、

所以最多测试 [logN + 1] 次

只是我的想法，算法很菜

[ 本帖最后由 azzbcc 于 2013-3-30 14:19 编辑 ]

#4

rjsp2013-03-30 14:35

以下是引用azzbcc在2013-3-30 14:18:05的发言：

假设有 N层楼，第一次肯定在 N/2测试，失败就在 N/4测试，成功就在 3*N/4测试、、、、、、

所以最多测试 [logN + 1] 次

只是我的想法，算法很菜

如果鸡蛋有无限多，你的这个二分法是对的。
如果楼高100层，只有两只鸡蛋可用，那么当依次在 9 22 34 45 55 64 72 79 85 90 94 97 99 100 层抛鸡蛋

#5

azzbcc2013-03-30 15:06

确实，鸡蛋数量会影响结果。

如果鸡蛋个数大于 [logN + 1]，那肯定是用二分法，小于的话，我搞不来

貌似这个页面可以帮到你

http://blog.

#6

gfchen18192013-03-30 17:24

我顶3楼

#7

叶子一哥2013-03-30 18:48

顶5楼

#8

关关0022013-03-30 21:06

我顶5楼

#9

不要脸的猫2013-03-30 21:22

同上……

#10

fanpengpeng2013-03-30 22:46

5楼中给的页面中提出的分析方法，想了一下，可以推广到大于两个鸡蛋的情况（用类似的思路分析，在摔碎鸡蛋的时候用鸡蛋数减一来递归）
这样的话在楼主提出的问题不确定规格的情况下可以给出对于楼层数为N 鸡蛋个数为k(>=2)的情况的通用算法
当鸡蛋个数大于1个时，按照公式算出最佳抛鸡蛋的楼层抛出鸡蛋根据结果修改鸡蛋数量和新的楼层区间
当鸡蛋个数等于1个时，从楼层区间最底层逐层抛出鸡蛋

那个页面中提到的分析方法是对的，不过后面的递推过程我还没完全理清楚不保证他最后给出的公式是正确的
关键是学习人家的方法楼主可以试着去实现这样的算法成功了你就可以理直气壮的要求留下来了

#11

王小言2013-03-31 15:27

回复 5楼 azzbcc

谢谢前辈，没想到的，根本没有想到有这么多的前辈给我回答，真的谢谢了哈~~

#12

azzbcc2013-03-31 19:34

我一个学生，算不得前辈。

那两位才是真正的大牛

#13

shangsharon2013-04-05 02:50

0.628

#14

holy__shit2013-08-25 18:23

听说过,好像记得是10