问题描述
序言
这个问题是由上周关于SO的类似问题启发而来的，在清楚真正的问题是什么之前，该问题已被删除.我认为这种变化带来了一个我想分享的不错的问题.
This problem was inspired by a similar question last week on SO, that got deleted before it was clear what the real question was. I think this variation makes a nice problem that I wanted to share.
两个蛋的问题
A detailed definition and solution can be found here, but I will add a quick summary:
定义
解决方案
这个想法是要从地板上放下第一个鸡蛋 sqrt(k)，2 * sqrt(k)，3 * sqrt(k)... k .如果鸡蛋在地板 i * sqrt(k)处破裂，请使用第二个鸡蛋测试(i-1)* sqrt(k)和之间的其余地板i * sqrt(k)-1 .总体而言，这最多将导致 2 * sqrt(k)下降，因此复杂度将为 O(sqrt(k)).
The idea is to drop the first egg from floors sqrt(k), 2*sqrt(k), 3*sqrt(k)... k. If the egg breaks at floor i*sqrt(k) use the second egg to test the remaining floors between (i-1)*sqrt(k) and i*sqrt(k)-1. Overall this will result in at most 2*sqrt(k) drops so the complexity will be O(sqrt(k)).
仅出于完整性考虑:在最坏的情况下，有一种方法可以减少丢弃次数(可以在此处)，但是其复杂度与 O(sqrt(k))
Just for completeness: there is a method with less drops in the worst-case (details can be found here), which however has the same complexity of O(sqrt(k))
问题:层数无限/未知的两个鸡蛋问题
现在假设您没有关于 k 或 k 的楼层数是无限的信息.是否有可能发现 f * 比仅在 O(f *)中测试每个楼层更有效?
Now imagine that you have no information about the number of floors k or k is infinite. Is it possible to find f* more efficient than just testing each floor in O(f*)?
换句话说:是否有一种 efficiency 方法来删除两个运行时复杂度与 k 独立但仅取决于答案的 f * ?
In other words: Is there an efficient method to drop the two eggs whose runtime complexity is independent from k but only depends on the answer f*?
推荐答案
有一个简单的方法具有O(sqrt(f *))复杂性.将第n步设置为n楼，即检查第1、3(1 + 2)，6(1 + 2 + 3)楼等.这样，在第n步中，您将位于n *(n +1)/2楼，您将以n = O(sqrt(f *))的步长达到f *.
There is a simple method that has O(sqrt(f*)) complexity. Make your nth step to be n floors up, that is, check floors 1, 3 (1 + 2), 6 (1 + 2 + 3), etc. This way at the nth step you will be on n*(n+1)/2 floor, and you will reach f* in n = O(sqrt(f*)) steps.
然后，对于第二个鸡蛋，您将需要在第1阶段的最后一步中进行n步操作，这将增加另一个O(sqrt(f *)).
Then for the second egg you will need to go n single steps over your last step in stage 1, which will add another O(sqrt(f*)).
如果O(sqrt(k))对于已知k最佳，则此方法在复杂性方面也必须是最佳.
If O(sqrt(k)) was optimal for known k, this method has to be optimal in terms of complexity, too.
这篇关于两个丢鸡蛋的谜题变体:未知/无限底数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！