两个丢鸡蛋的谜题变体:未知/无限底数 [英] Two egg dropping puzzle variation: unknown/infinite floors

问题描述

序言

这个问题是由上周关于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:

定义

您将获得两个蛋，并进入一个 k 层的建筑物.两个鸡蛋都是一样的目的是找出最高楼层 f * ，从中当鸡蛋从该楼层的窗户掉下来时，鸡蛋不会破裂.如果鸡蛋掉落并且不会破裂，它没有损坏并且可以掉落再次.但是，一旦鸡蛋破损，就是鸡蛋了.找到 f * 的斋戒方式(最少滴)是什么?

You are given two eggs, and access to a k-storey building. Both eggs are identical. The aim is to find out the highest floor f* from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg. What is the fastes (least amount of drops) way to find f*?

解决方案

这个想法是要从地板上放下第一个鸡蛋 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.

这篇关于两个丢鸡蛋的谜题变体:未知/无限底数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！