如何从建筑物中扔2个鸡蛋并找到地板F与~c*sqrt(F)投掷？

Question

我正在阅读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步骤的算法是什么？

Answer 1

从地板1,3,6,......(部分总和为1,2,3,......)中丢弃第一个蛋.然后在最后两层之间进行线性搜索.