数学研发论坛

 找回密码
 欢迎注册
查看: 1321|回复: 32

[讨论] 扔鸡蛋问题

[复制链接]
发表于 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 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)}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-3-30 17:31:59 来自手机 | 显示全部楼层
发现一个例外,第一次选择第一层破裂时,还需要0次而不是1/2次
计算结果应该第一次在第14层抛下(使用sheng的模型而且假设均匀分布)
下面是计算的概率a[n]
[1, 5/3, 2, 23/10, 31/12, 39/14, 3, 19/6, 67/20, 7/2, 11/3, 99/26, 55/14, 61/15, 67/16, 147/34, 40/9, 173/38, 93/20, 100/21, 107/22, 229/46, 61/12, 259/50, 137/26, 289/54, 305/56, 321/58, 169/30, 355/62, 93/16, 389/66, 203/34, 423/70, 49/8, 459/74, 239/38, 497/78, 129/20, 535/82, 277/42, 573/86, 74/11, 34/5, 158/23, 653/94, 337/48, 695/98, 179/25, 737/102, 379/52, 779/106, 200/27, 411/55, 211/28, 289/38, 445/58, 913/118, 39/5, 959/122, 491/62, 335/42, 257/32, 1051/130, 1075/132, 1099/134, 281/34, 383/46, 587/70, 1199/142, 17/2, 1249/146, 637/74, 433/50, 331/38, 1349/154, 1375/156, 1401/158, 357/40, 485/54, 741/82, 1509/166, 64/7, 1563/170, 795/86, 539/58, 411/44, 1671/178, 283/30, 863/91, 877/92, 1783/186, 453/47, 1841/190, 935/96, 1899/194, 482/49, 1957/198, 993/100, 2015/202]
而对于k个有效楼层,我们第一次应该选择的楼层b(k)为
[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13]
比如上面给出b(98)=13,所以对于100层(98个有效楼层),应该选择第14层
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-3-23 12:34 , Processed in 0.057225 second(s), 21 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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