【动态规划问题】求算法:n个鸡蛋,用最少的个数求出从多高扔下去刚好摔碎

【动态规划问题】求算法:n个鸡蛋,用最少的个数求出从多高扔下去刚好摔碎
如题,有一个未知高度m米(m为整数),鸡蛋从m米扔下不会碎,但是从m+1米扔下去就会碎,m就是鸡蛋的碎点(breaking point).我有n个鸡蛋去测试这个刚好摔碎的高度,每次从不同高度扔下去观察是否摔碎,可以把所有n个鸡蛋都用了.
求一个动态规划的算法(dynamic programming algorithm)来用最少的次数算出那个高度.
两个假设如下:
所有的鸡蛋完全一样的硬度(碎点都是一样的)
如果一个鸡蛋从某高度掉下没有摔碎,那个这个鸡蛋任然完好无损,可以和其他鸡蛋一样继续试验.


求大神写一个java或者c++ program 来执行这个算法,这其实是我的作业,我现在基本上没有头绪怎么开始,有好的建议也好,如果有不清楚的请告诉我,

图片只是原题,题意是我补充问题里写的,
不用帮我写代码,给我点思路如何解决这个问题也可以得分,
心回路转 1年前 已收到1个回答 举报

玻璃780 幼苗

共回答了17个问题采纳率:94.1% 举报

这题应有个上限,就是鸡蛋扔多少米一定会坏,设为h米


设T(i,j)为用i个鸡蛋,上限为j米,最坏情况下最少次数.


i从1到n,j从1到h
T(1,j)=j-1 即只有一个鸡蛋,需要从一米开始一直到j-1米,要j-1次
T(i,1)=0 即当1米一定摔坏,则碎点是0,不需要扔即可知道


当i>1且j>1时

其中
k表示扔一个鸡蛋在k米
T(i,j-k)+1 是指鸡蛋扔在k层没摔坏,则等于i个鸡蛋,最坏j-k米需要次数+1
T(i-1,k)+1 是指鸡蛋扔在k层摔坏,则等于i个鸡蛋,最坏k米需要次数+1
max 是指两种情况下最坏需要的次数
min 在1到j-1米中选择最坏情况下最小次数的米数

1年前

4
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 16 q. 0.027 s. - webmaster@yulucn.com