我有一箩筐的鸡蛋,我可以给你两个。 我有一栋一百层的楼,我想让你站在第一百层,以最少的次数帮我测出来鸡蛋最多扔到哪一层不会碎。 你放心扔,如果没碎,不用去捡,我直接补给你一个。 事成之后,这张支票你随便填。
_佰_拾_圆
咋样,有什么想法吗?
我说说我的想法,首先,第二个鸡蛋肯定一层一层扔啊(不是两层两层扔)。 那第一个鸡蛋呢?
我是这么想的啊,土是土了点,但我觉得很有效。
1、肯定不能·一层一层扔
2、如果两层两层扔,最多扔100/2+(2-1) = 51次即可(去尾法)。
3、如果三层一扔,最多扔100/3+(3-1) = 35次
4、···
5、如果八层一扔,最多扔100/8+(8-1) = 19次
6、如果九层一扔,最多扔100/9+(9-1) = 19次
7、十层一扔也是19次(7层一扔是20次)
8、十一层一扔,也是19次
9、十二层一扔,19次
10、十三层,19次
此后再无低于或等于19次的机会了(以十九层(当前最低次数)为限)
那么,这么多种扔法的最坏情况都是一样的情况下,我们该选哪种? 这就涉及概率论了。 我献丑了,不喜欢看的小伙伴可以直接滑下去了。
对第一个鸡蛋而言
扔的层数/砸碎概率 | 一次 | 两次 | 三次 | 四次 | 五次 | 六次 | 七次 | 八次 | 九次 | 十次 | 十一次 | 十二次 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
八层 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 |
九层 | 0.09 | 0.09 | 0.09 | 0.09 | 0.09 | 0.09 | 0.09 | 0.09 | 0.09 | 0.09 | 0.09 | |
十层 | 0.10 | 0.10 | 0.10 | 0.10 | 0.10 | 0.10 | 0.10 | 0.10 | 0.10 | 0.10 | ||
十一层 | 0.11 | 0.11 | 0.11 | 0.11 | 0.11 | 0.11 | 0.11 | 0.11 | 0.11 | |||
十二层 | 0.12 | 0.12 | 0.12 | 0.12 | 0.12 | 0.12 | 0.12 | 0.12 | ||||
十三层 | 0.13 | 0.13 | 0.13 | 0.13 | 0.13 | 0.13 | 0.13 |
对于第二个鸡蛋而言:(记扔的层数为n) 如果在中间层数碎了,概率都是:1/(n-1),如果是最后一次扔都没碎的话,概率是:1/(100%n-1),如果n是10的话,直接不用算了。
接下来就会发现这个期望实在是太难算了。
同时,也有了一个新的问题: 如果我选了扔十层,我第一次扔十层,第二次一定要扔十层吗?我不能扔九层?不能扔十一层?我一定要每次都是十层? 还好我还没去算期望,不然白算了。 还好我事先分析的透彻,不然就浪费半个小时了。
后来,我看到了这么一种解法: 说是一直以同样的层数匹配下去,会对高层鸡蛋不公平。 但是呢,考虑到上面的情况,给出了一种优化,即每次扔的层数递减。 为什么不是迪迦呢?对高层的鸡蛋更不公平了。
所以,要扔到一百层,第一次扔多少呢?我们算一下啊: 1+2+3+4+···+14>100 1+2+3+4+···+13<100 所以第一次扔14层,第二次13层····最后会多5是吧,那就看你心情愿意放哪儿去了。比如我就···5层,3层,2层这样了。 这样就能基本保证投蛋次数普遍在14次波动。
嗯嗯,不错。