智游城

标题: 策略问题 [打印本页]

作者: 老陈 时间: 2020-4-10 05:05
标题: 策略问题
本帖最后由老陈于 2020-4-9 15:19 编辑

有一家手机生产公司，为了测试手机的抗摔性能，他们选择了一栋100层楼的建筑，把手机从楼上往下扔，目的找到一个临界层，在这层不能摔坏，再高一层就摔坏。你最多只能用2部手机。让你制定一个方案，要求这个方案在最坏的情况下测试次数最少。

作者: notch 时间: 2020-4-10 09:16
次数最多的方法就是从第一层开始摔，没坏就往上一层，这样只要一个手机就可以了
现在有两个手机可以摔，那么第一个手机可以用来缩小范围，第二个手机还是要在范围内每层（从低到高）摔一下来得到精确的临界层

假设有一个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

作者: ahthwl 时间: 2020-4-10 09:32
这是数据结构里的动态规划类问题。
设方程f(x,y)为x个鸡蛋测试y层楼，那么f(1,y)=y
f(2,1)=1
f(2,2)=2
从f(2,y),y>2开始就可以从前面的状态进行汇总规划得出当前的次数。数学公式不会打..

作者: qiaoyeluo 时间: 2020-4-10 14:29
题目可以等同为：x*y=100，求x+y的最小值；

-》面积相同正方形周长最短
-》x=y=10
=》第一个手机扔1层、10层、20层。。。；第二个手机从第一个手机摔坏的前一个点开始扔；最坏情况扔19次。

作者: 老陈 时间: 2020-4-11 05:12
本帖最后由老陈于 2020-4-10 15:15 编辑

ahthwl 发表于 2020-4-9 19:32
这是数据结构里的动态规划类问题。
设方程f(x,y)为x个鸡蛋测试y层楼，那么f(1,y)=y
f(2,1)=1

这个思路很好，是胜利的开始。不过用鸡蛋测不出手机的抗摔性能。

作者: rahj 时间: 2020-4-11 10:03

老陈发表于 2020-4-11 05:12
这个思路很好，是胜利的开始。不过用鸡蛋测不出手机的抗摔性能。

睡原题不就是测试从几楼丢下去鸡蛋能碎吗

作者: rahj 时间: 2020-4-11 10:05
原题可不就是测试从几楼丢下鸡蛋能碎吗

作者: 老陈 时间: 2020-4-11 17:08

rahj 发表于 2020-4-10 20:05
原题可不就是测试从几楼丢下鸡蛋能碎吗

与鸡蛋有啥关系？

作者: rahj 时间: 2020-4-11 17:13

老陈发表于 2020-4-11 17:08
与鸡蛋有啥关系？

小学奥数题:有一栋楼共100层，一个鸡蛋从第N层及以上的楼层落下来会摔破，在第N层以下的楼层落下不会摔破。给你2个鸡蛋，设计方案找出N，并且保证在最坏情况下，最小化鸡蛋下落的次数。以前做这种题的时候想的很简单,现在看题写最坏情况,会想的比较多

作者: ahthwl 时间: 2020-4-13 17:38

rahj 发表于 2020-4-11 17:13
小学奥数题:有一栋楼共100层，一个鸡蛋从第N层及以上的楼层落下来会摔破，在第N层以下的楼层落下不会摔 ...

貌似t题主对于鸡蛋和手机概念转换的过程有点无力……针对这个题目，两个鸡蛋最多13次可以确定出100层楼里具体N是多少。

作者: rahj 时间: 2020-4-13 17:47

ahthwl 发表于 2020-4-13 17:38
貌似t题主对于鸡蛋和手机概念转换的过程有点无力……针对这个题目，两个鸡蛋最多13次可以确定出100层楼里 ...

你这么一说我恍然大悟，原来是这个原因
我算出是14，另外这题很看天意的，题里面写的是最坏情况，要是100层的时候还碎不了，那临界点其实是无法确定的
不如假定没有超过100层的楼房比较好

作者: notch 时间: 2020-4-14 10:00

rahj 发表于 2020-4-11 17:13
小学奥数题:有一栋楼共100层，一个鸡蛋从第N层及以上的楼层落下来会摔破，在第N层以下的楼层落下不会摔 ...

说一下解题的过程吧

作者: rahj 时间: 2020-4-14 12:54

notch 发表于 2020-4-14 10:00
说一下解题的过程吧

和楼上说的差不多,通过动态规划来解
最坏情况下,摔x次,第一个鸡蛋手机从x层摔,最坏情况之一是碎了,那么接下来倒推第二个鸡蛋(手机)要摔x-1次
之二是没碎,那么还是那个鸡蛋(手机),接下来从x+(x-1)层摔,因为还是两个情况,碎了还是第二个摔x-1次,没碎继续上高层x+(x-1)+(x-2)摔
最后高斯一下,解出x(x+1)/2 >= 100,x=14
这里是100是因为题目没说100层会碎,按照题意和天意,很可能100层也不会碎,或者13层就会碎,因此最小14次

作者: ahthwl 时间: 2020-4-15 17:57

rahj 发表于 2020-4-14 12:54
和楼上说的差不多,通过动态规划来解
最坏情况下,摔x次,第一个鸡蛋手机从x层摔,最坏情况之一是碎了,那么接 ...

14是对的，我很久以前做的，记错了。

作者: 老陈 时间: 2020-4-18 08:23
本帖最后由老陈于 2020-4-17 18:31 编辑

这是我在微信朋友圈里看到的一道题，由于对我来说原题难度太大，当时我没做出来，所以我简化后发到这里。原题如下：
有一家手机生产公司，为了测试手机的抗摔性能，他们选择了一栋N层楼的建筑，把手机从楼上往下扔，目的找到一个临界层，在这层不能摔坏，再高一层就摔坏。你最多只能用M部手机。让你制定一个方案，要求这个方案在最坏的情况下测试次数最少。

作者: 老陈 时间: 2020-4-27 09:06
本帖最后由老陈于 2020-4-28 18:15 编辑

我们用
F(M,N)
表示N层楼M部手机的试验次数。
我们选择第一部手机从第K层扔下，
如果手机摔坏，试验次数为：
F(M-1,K-1)+1
如果手机没有摔坏，试验次数为：
F(M,N-K)+1
我们取其中较大的那个。
我们取K从1到N，得到N个数，取最小的数。就得到了
F(M,N)
有的城友会问
F(M-1,K-1)和F(M,N-K)是未知的啊？
不用担心，两个参数至少有一个比M或N小，我们可以先求参数小的。一直到(1,2),(2,1),(1,1)，显然：
F(1,K)=K
F(K,1)=1

作者: rahj 时间: 2020-4-29 14:52

老陈发表于 2020-4-27 09:06
我们用
F(M,N)
表示N层楼M部手机的试验次数。

找到个M层楼N个鸡蛋的试验次数的解答,对付着看看
我觉得手算的难度在于递归嵌套,有空我也出个抽屉原理的题,我上本科自个出的
__________________________分隔______________________________
此题还有一个扩展，就是为N个鸡蛋从M层摔找出最小值。
　　那就不是很好手解了，所以写了代码，使用动态规划原理。动态规划式子如下：

f[n][m] = 1+max(f[n-1][k-1],f[n][m-k]) k属于[1,m-1]
解释下原理：
1、当手里有n个的时候，鸡蛋从k层往下摔，如果破了，那么手里只有n-1鸡蛋了，那么就需要测试f[n-1][k-1]楼层。或者更通俗好理解点的，我们运用2个鸡蛋100楼层的题目举例子。以上式子变为：f[2][m] = 1+max(f[1][k-1],f[2][m-k])
　　那么当手里有2个鸡蛋的时候，在k层摔，碎了。那么现在手里也就只有一个鸡蛋了，此时我们必须遍历1~k-1找出第一次碎的楼层。所以为1+f[1][m-k]，前面的1代表在k层的操作。
2、没破，那么手里还有n个鸡蛋，那么需要测试k+1~m这些楼层。

此时我想问下，当手里有2个鸡蛋测试1~m-k层和手里有2个鸡蛋测试k+1~m有什么区别？
有人说有，因为楼层越高越容易碎，那其实是你个人的想法罢了。其实并没有区别，所以第一个公式可以写为f[n][m-k]。
————————————————
版权声明：本文为CSDN博主「林子木」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/wolinxuebin/java/article/details/47057707

作者: 老陈 时间: 2020-4-30 11:25

rahj 发表于 2020-4-29 00:52
找到个M层楼N个鸡蛋的试验次数的解答,对付着看看
我觉得手算的难度在于递归嵌套,有空我也出个抽屉原理的 ...

摔鸡蛋很简单，1层楼摔下，鸡蛋肯定坏。
如果摔手机，手算也没有任何难度，就是计算量大。
具体做法：
比如1000层楼30部手机。
画一张30行，1000列的大表格。
把第一行和第一列填进数字，第1行都是列号，第1列都是1。
然后逐个由小到大填写F(M,N)到M行N列。

作者: rahj 时间: 2020-5-2 10:25
老陈上道了，知道鸡蛋也是能摔坏的

欢迎光临智游城 (http://zhiyoucheng.co/)