【C++】算法集锦(12):高楼扔鸡蛋
发布日期:2021-06-30 19:47:35
浏览次数:3
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
逛到本站,mark一下
[***.202.152.39]2024年04月27日 03时31分36秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
邹传伟:作为信息互联网的区块链 | 云图思潮
2019-04-30
【图学院】区块链与密码学全民课堂第2-1讲:理解区块链竟如此简单?
2019-04-30
TensorRT使用过程中的问题记录1
2019-04-30
python-opencv将图片合成视频
2019-04-30
Background-Matting背景替换模型
2019-04-30
OKHttp基本用法
2019-04-30
Android之项目命名规则
2019-04-30
Android之AsyncTask机制篇
2019-04-30
retrofit+MVP开发
2019-04-30
Android SQLite基本用法
2019-04-30
xUtils框架之DB模块
2019-04-30
语言国际化
2019-04-30
WebView下载文件并显示进度
2019-04-30
最新Android框架排行榜
2019-04-30
Android studio常用快捷键
2019-04-30
自定义MyOkHttp封装和调用
2019-04-30
Android四大组件、六大布局、五大存储
2019-04-30
Android之Activity篇
2019-04-30
Android之Broadcast篇
2019-04-30
Android之ContentProvider篇
2019-04-30