【C++】算法集锦(12):高楼扔鸡蛋
发布日期:2021-06-30 19:47:35
浏览次数:2
分类:技术文章
本文共 1340 字,大约阅读时间需要 4 分钟。
文章目录
题目描述
我有一箩筐的鸡蛋,我可以给你两个。
我有一栋一百层的楼,我想让你站在第一百层,以最少的次数帮我测出来鸡蛋最多扔到哪一层不会碎。 你放心扔,如果没碎,不用去捡,我直接补给你一个。 事成之后,这张支票你随便填。_佰_拾_圆
题目分析(我的想法)
咋样,有什么想法吗?
我说说我的想法,首先,第二个鸡蛋肯定一层一层扔啊(不是两层两层扔)。
那第一个鸡蛋呢?我是这么想的啊,土是土了点,但我觉得很有效。
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次波动。嗯嗯,不错。
转载地址:https://lion-wu.blog.csdn.net/article/details/114106903 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月09日 21时39分29秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
synchronized和CAS锁的区别【图文教程】
2019-04-30
配置nginx只允许域名访问,禁止ip访问【图文教程】
2019-04-30
Java代理【图文教程】_第1章_静态代理
2019-04-30
Java代理【图文教程】_第2章_jdk动态代理
2019-04-30
AOP面向切面编程【图文教程】_第1章
2019-04-30
AOP面向切面编程【图文教程】_第2章
2019-04-30
二叉树之前序、中序、后序和层次遍历【图文教程】
2019-04-30
java类的构成
2019-04-30
创建安装linux:centOS
2019-04-30
Xshell连接CentOS及安装hadoop的准备
2019-04-30
在linux上配置jdk和hadoop
2019-04-30
HDFS配置及常见命令
2019-04-30
xshell连接linux速度很慢或者连接一段时间后会自动断
2019-04-30
Hadoop Windows插件配置
2019-04-30
存储 HDFS内部运行原理
2019-04-30
二丶存储+分析处理信息MapReduce内部原理
2019-04-30