相关疑难解决方法(0)

其中一个经典的编程面试问题......

给你两个大理石,并告诉他们从某个高度下降时会破裂(如果从那个高度以下掉落,可能不会受到伤害).然后你被带到一座100层高的建筑物(大概高于一定的高度),并要求找到最高的楼层,你可以尽可能高效地将大理石从大地上掉下来.

额外信息

• 你必须找到正确的楼层(不是可能的范围)
• 大理石都保证在同一层楼打破
• 假设您需要零时间更换地板 - 只计算大理石滴的数量
• 假设正确的楼层随机分布在建筑物中

这个问题(为了确定这样一只猫能活下来的最大楼层,你需要抛出多少只猫才能生存下来.实际上相当残忍),O(n ^ 3)复杂度已经得到了答案.这个问题等同于这个Google Code Jam,它应该可以解决N = 2000000000.

似乎O(n ^ 3)解决方案不足以解决它.从查看解决方案页面,jdmetz的解决方案(#2)似乎是O(n log n).我不太了解算法.有人可以解释一下吗？

编辑

这是问题描述:

假设我们想知道N层建筑中的哪些故事可以安全地从中掉落鸡蛋,哪些会导致鸡蛋在着陆时破裂.我们做了一些假设:可以再次使用在摔倒后存活的鸡蛋.

• 必须丢弃破蛋.
• 所有鸡蛋的跌倒效果都是一样的.
• 如果鸡蛋在掉落时断裂,那么如果从较高的窗口掉落则会破裂.
• 如果一个鸡蛋在摔倒后存活,那么它会在较短的摔倒后存活.
• 不排除一楼的窗户打破鸡蛋,也不排除N楼的窗户不会导致鸡蛋破裂.

给定一个N层建筑和一个鸡蛋供应,找到最小化(在最坏的情况下)确定断裂所需的实验滴数的策略.

我已经看到并解决了2个鸡蛋的问题,其中答案是14 = N = 100.我尝试使用DP了解wiki的通用解决方案,但无法理解他们想要做什么.请告诉他们他们是如何到达DP以及它是如何工作的？

编辑:

本条中给出的最高流量可用d滴和e蛋测试的复发如下:

f[d,e] = f[d-1,e] + f[d-1,e-1] + 1

复发很好,但我无法理解它是如何衍生出来的？

这个解释对我来说并不清楚....我只是希望有人用更清晰的话语向我解释这种情况.

我正在阅读Robert Sedgewick的算法第4版,他有以下任务:

假设你有一个N层建筑和2个鸡蛋.假设如果鸡蛋被扔掉F楼或更高楼层,鸡蛋就会被打破,否则就会破裂.您的成本模型是投掷次数.设计一个策略来确定F,使某些常数c的投掷数量为~c√F.

任务的第一部分是在2√N步骤中找到F,这是一个解决方案:

第1部分的解决方案:

• 要达到2*sqrt(N),请在楼层sqrt(N),2*sqrt(N),3*sqrt(N),...,sqrt(N)*sqrt(N)下降鸡蛋.(为简单起见,我们假设sqrt(N)是一个整数.)
• 假设蛋在k*sqrt(N)水平处破裂.
• 然后使用第二个蛋,您应该在区间(k-1)*sqrt(N)到k*sqrt(N)中执行线性搜索.
• 总共可以在最多2*sqrt(N)的试验中找到F楼.

他还提供了~c√F部分的提示(第2部分):

第2部分的提示:1 + 2 + 3 + ... k~1/2 k ^ 2.

那么~c√F步骤的算法是什么？