数学研发论坛

 找回密码
 欢迎注册
查看: 667|回复: 33

[讨论] 扔鸡蛋问题

[复制链接]
发表于 2018-3-30 10:32:41 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
你拥有两个鸡蛋,鸡蛋从某一特定楼层及以上的楼层扔下会破粹,从以下的楼层扔下会完好无损。两个鸡蛋完全相同。现在有一个 100 层的大楼,只有两个鸡蛋可以使用,你需要找出让鸡蛋摔碎的临界楼层,问题是你将怎么扔鸡蛋,保证找到临界楼层,所扔次数的期望值最小?    3个鸡蛋以上呢
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-3-30 13:08:42 | 显示全部楼层
楼层和高度成正比,可看做是已经排好序的表的查找问题,一般选择二分搜索法或者黄金分割搜索法,平均次数是 O(log n) 级别。

点评

@zeroieme,我理解成只能丢两次了……  发表于 2018-3-31 18:00
只有两次失败的机会  发表于 2018-3-30 13:24
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-3-30 13:29:18 | 显示全部楼层
本帖最后由 zeroieme 于 2018-3-30 13:38 编辑

100层楼其实是99倍单层楼高,
第一只第11楼起隔10层试验,碎了。用第二只试验第一只碎的下9层开始逐层试验。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-3-30 14:15:43 | 显示全部楼层
1,拥有1个鸡蛋。从第1,2,3,4,5......层依次扔下,直到碎了为止。(从第1层开始逐层往上走)。

2,拥有2个鸡蛋。第1个鸡蛋从第50,75,87...层依次扔下,直到碎了为止。(从第1层开始加半往上走)。
                             第2个鸡蛋从安全层开始逐层往上走。

3,拥有3个鸡蛋。第1个鸡蛋从第1层开始加半往上走。
                             第2个鸡蛋从安全层开始加半往上走。
                             第3个鸡蛋从安全层开始逐层往上走。

4,拥有4个鸡蛋。第1个鸡蛋从第1层开始加半往上走。
                             第2个鸡蛋从安全层开始加半往上走。
                             第3个鸡蛋从安全层开始加半往上走。
                             第4个鸡蛋从安全层开始逐层往上走。

5,拥有5个鸡蛋。第1个鸡蛋从第1层开始加半往上走。
                             第2个鸡蛋从安全层开始加半往上走。
                             第3个鸡蛋从安全层开始加半往上走。
                             第4个鸡蛋从安全层开始加半往上走。   
                             第5个鸡蛋从安全层开始逐层往上走。   
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-3-30 15:07:21 | 显示全部楼层
让题设更严谨些:在1至 100 层的大楼中,临界楼层处于2 ~ 99层,即鸡蛋从100楼层扔下肯定会破碎,鸡蛋从1楼层扔下肯定会完好无损。
由于扔一个鸡蛋后,问题方向是确定的。所以我认为二分法是最佳的寻找临界楼层的方法。
对于只有两个鸡蛋,具体方案如下:
选楼层,[(99+2)/2]=50(取整),从50层往下扔,
如果破碎,从2层开始往下仍,不碎上一层再仍,直到碎为止就可找到临界楼层;
如果不破碎,选楼层,[(99+51)/2]=75,重复上述过程,直到找到临界楼层。

3个鸡蛋(或以上)方法类似,只是如果还有鸡蛋,当仍下碎时,不是从最近不碎层往上一层层仍鸡蛋,而是继续二分法找临界楼层。

注:写的时候没看到楼上帖子,我的方法和楼上的一致。不知这个方法是否是最佳方法(扔次数的期望值最小)?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-3-30 16:44:56 | 显示全部楼层
二分法肯定不是最好的。第一次第50层如果破碎,只有一个鸡蛋可以检测下面的楼层,但是如果没有破碎,有两个鸡蛋可以检测上面的楼层。
这个显然是一个动态规划问题

点评

动态规划,好高档:D  发表于 2018-3-30 19:25
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-3-30 17:11:42 来自手机 | 显示全部楼层
首先我们需要考虑有多少个有效楼层,比如sheng的理解方案下就只有98个有效楼层,1楼和100楼均不需要检测。既然谈到期望,还有先验分布问题,比如按我们先验知识,正常鸡蛋二楼就会破裂,直接到二楼验证即可。所以我们需要在我们的模型上规定,对于n个有效楼层,出现的n+1种情况我们要求等概率
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-3-30 17:13:21 来自手机 | 显示全部楼层
于是一个鸡蛋检测n个有效楼层平均(n+1)/2次
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-3-30 17:15:39 来自手机 | 显示全部楼层
对于两个鸡蛋假设检测n个楼层期望为a(n),那么第一次选第k层,如果碎裂,还需要平均k/2次,没碎,还需要a(n-k)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-3-30 17:25:57 来自手机 | 显示全部楼层
a(0)=0,a(1)=1,a(n)=1+min{k/(n+1)*k/2+(n+1-k)/(n+1)*a(n-k)}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2018-7-18 05:18 , Processed in 0.071643 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表