抛9次: 从9楼起抛,如果碎了,从1楼开始向上抛;没碎,转化为一个2个鸡蛋抛8次的问题(上面这问题),所以抛9次可以测出9 + 36 = 45层。 抛10次: 从10楼起抛,如果碎了,从1楼开始向上抛;没碎,转化为一个2个鸡蛋抛9次的问题(上面这问题),所以抛10次可以测出10 + 45 = 55层。 抛11次: 从11楼起抛...
在刚才的情况中,每次扔鸡蛋的楼层都是等间隔的,B每次要扔的次数都是一样的,如果临界楼层比较靠后,A扔的次数就多了,如果让间隔变得不等,A每多扔一次,B的范围就缩小一次,这样总次数就可以平均下,也许会更好,我们尝试下 第一次在第n层扔,第二次加n-1层,第三次加n-2层……,也就是A每次扔的间隔都会缩小...
你知道存在楼层 F ,满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎,从 F 楼层或比它低的楼层落下的鸡蛋都不会破。 每次移动,你可以取一个鸡蛋(如果你有完整的鸡蛋)并把它从任一楼层 X 扔下(满足 1 <= X <= N)。 你的目标是确切地知道 F 的值是多少。 无论F 的初始值如何,你确...
我们不妨先把问题具体化,比如给你2个鸡蛋100层楼。 我们首先想到的是第一个鸡蛋从中间的第50楼开始扔,划分楼层更快,剩余测试楼层减半,但是最坏情况是鸡蛋碎了,第二个鸡蛋只能从1楼逐层到49楼扔,总共50次。最糟糕的想法是第一个鸡蛋就从1楼开始扔,最坏需要扔100次,第一次在第一层扔不碎的情况和第一次在...
解析 答案:我们可以使用二分法来找到鸡蛋破裂的临界楼层。首先将一个鸡蛋从50层扔下,如果鸡蛋破裂,则下一步从1层到49层中进行尝试;如果鸡蛋没有破裂,则下一步从51层到100层中进行尝试。以此类推,每一次将楼层范围缩小一半,直到确定鸡蛋破裂的临界楼层。
题目:扔鸡蛋问题 有2个鸡蛋,从100层楼上往下扔,以此来测试鸡蛋的硬度。比如鸡蛋在第9层没有摔碎,在第10层摔碎了,那么鸡蛋不会摔碎的临界点就是9层。 问:如何用最少的尝试次数,测试出鸡蛋不会摔碎的临界点? 举个栗子,最笨的测试方法是什么样呢?
题目:扔鸡蛋问题 有2个鸡蛋,从100层楼上往下扔,以此来测试鸡蛋的硬度。比如鸡蛋在第9层没有摔碎,在第10层摔碎了,那么鸡蛋不会摔碎的临界点就是9层。 问:如何用最少的尝试次数,测试出鸡蛋不会摔碎的临界点? 举个栗子,最笨的测试方法是什么样呢?
利用 动态规划JAVA实现 扔鸡蛋问题: public class Solution { /* * @param eggs: the number of eggs * @param floors: the number of floors * @return: the number of drops in the worst case */ public int dropEggs2(int eggs, int floors) { // write your code here //第一步永远是创建动态...
1、 一个100层的楼,扔下一个鸡蛋(花瓶),怎么判断在N层不碎,N + 1层碎,思路是什么? 因为就一个鸡蛋,所以,我们很容易就可以想到从第一层开始扔就可以了,直到碎,说明这是N + 1层。 2、一个100层的楼,给你两个一模一样的鸡蛋(花瓶),判断这个鸡蛋的硬度,即N层不碎,N + 1层碎,最少需要多少次?