策略问题

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

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

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

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

与鸡蛋有啥关系？

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

我们用
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 00:52
找到个M层楼N个鸡蛋的试验次数的解答,对付着看看
我觉得手算的难度在于递归嵌套,有空我也出个抽屉原理的 ...

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