智游城

 找回密码
 注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 6876|回复: 18
打印 上一主题 下一主题

策略问题

[复制链接]
跳转到指定楼层
1#
老陈 发表于 2020-4-10 05:05:51 来自手机 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
本帖最后由 老陈 于 2020-4-9 15:19 编辑

有一家手机生产公司,为了测试手机的抗摔性能,他们选择了一栋100层楼的建筑,把手机从楼上往下扔,目的找到一个临界层,在这层不能摔坏,再高一层就摔坏。你最多只能用2部手机。让你制定一个方案,要求这个方案在最坏的情况下测试次数最少。
分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友 微信微信
收藏收藏
2#
notch 发表于 2020-4-10 09:16:35 | 只看该作者
次数最多的方法就是从第一层开始摔,没坏就往上一层,这样只要一个手机就可以了
现在有两个手机可以摔,那么第一个手机可以用来缩小范围,第二个手机还是要在范围内每层(从低到高)摔一下来得到精确的临界层

假设有一个X (1<=X<=100)可以令挑选次数最少
第一个手机挑X层摔下去
如果坏了,那么从1到X依次摔第二个手机
如果没坏,在剩下的层里挑第X%的层继续摔第一个手机
重复该步骤,可以用有最少的次数挑选到临界层

假设临界层为N (1<=N<=100),为一随机数
当N<X,概率为X%,所需次数是1+N
当X<=N<=X+(100-X)*X%,概率为(100-X)*X%,所需次数是 2+N-X
上述式子可以一直延展下去,然后概率乘以次数就是总预期次数,要求该值最小,然后求得X

这个后面就不会解了,猜测X可能是0.382

3#
ahthwl 发表于 2020-4-10 09:32:57 | 只看该作者
这是数据结构里的动态规划类问题。
设方程f(x,y)为x个鸡蛋测试y层楼,那么f(1,y)=y
f(2,1)=1
f(2,2)=2
从f(2,y),y>2开始就可以从前面的状态进行汇总规划得出当前的次数。数学公式不会打..
4#
qiaoyeluo 发表于 2020-4-10 14:29:16 | 只看该作者
题目可以等同为:x*y=100,求x+y的最小值;

-》面积相同正方形周长最短
-》x=y=10
=》第一个手机扔1层、10层、20层。。。;第二个手机从第一个手机摔坏的前一个点开始扔;最坏情况扔19次。
5#
 楼主| 老陈 发表于 2020-4-11 05:12:16 来自手机 | 只看该作者
本帖最后由 老陈 于 2020-4-10 15:15 编辑
ahthwl 发表于 2020-4-9 19:32
这是数据结构里的动态规划类问题。
设方程f(x,y)为x个鸡蛋测试y层楼,那么f(1,y)=y
f(2,1)=1


这个思路很好,是胜利的开始。不过用鸡蛋测不出手机的抗摔性能。
6#
rahj 发表于 2020-4-11 10:03:35 | 只看该作者
老陈 发表于 2020-4-11 05:12
这个思路很好,是胜利的开始。不过用鸡蛋测不出手机的抗摔性能。

睡原题不就是测试从几楼丢下去鸡蛋能碎吗
7#
rahj 发表于 2020-4-11 10:05:08 | 只看该作者
原题可不就是测试从几楼丢下鸡蛋能碎吗
8#
 楼主| 老陈 发表于 2020-4-11 17:08:02 来自手机 | 只看该作者
rahj 发表于 2020-4-10 20:05
原题可不就是测试从几楼丢下鸡蛋能碎吗

与鸡蛋有啥关系?
9#
rahj 发表于 2020-4-11 17:13:47 | 只看该作者
老陈 发表于 2020-4-11 17:08
与鸡蛋有啥关系?

小学奥数题:有一栋楼共100层,一个鸡蛋从第N层及以上的楼层落下来会摔破, 在第N层以下的楼层落下不会摔破。给你2个鸡蛋,设计方案找出N,并且保证在最坏情况下, 最小化鸡蛋下落的次数。以前做这种题的时候想的很简单,现在看题写最坏情况,会想的比较多
10#
ahthwl 发表于 2020-4-13 17:38:22 | 只看该作者
rahj 发表于 2020-4-11 17:13
小学奥数题:有一栋楼共100层,一个鸡蛋从第N层及以上的楼层落下来会摔破, 在第N层以下的楼层落下不会摔 ...

貌似t题主对于鸡蛋和手机概念转换的过程有点无力……针对这个题目,两个鸡蛋最多13次可以确定出100层楼里具体N是多少。
您需要登录后才可以回帖 登录 | 注册

本版积分规则

手机版|Archiver|智游城论坛

GMT+8, 2024-12-25 22:35 , Processed in 0.074173 second(s), 7 queries , Redis On.

Powered by Discuz! X3.2

© 2001-2012 Comsenz Inc.

返回顶部