其中的一个经典节目的面试问题...

One of those classic programming interview questions...

正在提供两个弹子，并告知他们将打破由一定的高度落下时（和presumably苦于没有损害，如果从下高度下降）。你再带到一个100层的大楼（presumably超过一定高度较高），并要求找到最高的楼你可以删除一个大理石不作为有效打破它越好。

You are given two marbles, and told that they will break when dropped from some certain height (and presumably suffer no damage if dropped from below that height). You’re then taken to a 100 story building (presumably higher than the certain height), and asked to find the highest floor your can drop a marble from without breaking it as efficiently as possible.

额外的信息

推荐答案

这里的有趣的事情是如何在最少的下降可能的做到这一点。要去50楼和删除第一将是灾难性的，如果破楼是49，导致我们不得不这样做50滴。我们应该在地板n，其中n是滴所需的最大量下降的第一大理石。如果休息的大理石地板，在N，我们可能不得不作出后N-1下降。如果大理石不破坏我们上去地板2n-1个，如果它打破这里我们必须丢弃第二大理石的n-2次在最坏的情况下。我们继续这样下去直到100层，并尝试在3N-2打破它，4N-3 .... 和n +（N-1）+（N-2）+ ... 1所述; = 100 N = 14，则需要最大滴

The interesting thing here is how you can do it in the least amount of drops possible. Going to the 50th floor and dropping the first would be disastrous if the breaking floor is the 49th, resulting in us having to do 50 drops. We should drop the first marble at floor n, where n is the max amount of drops required. If the marble breaks at floor n, we may have to make n-1 drops after that. If the marble doesn't break we go up to floor 2n-1 and if it breaks here we have to drop the second marble n-2 times in the worst case. We continue like this up to the 100th floor and try to break it at 3n-2, 4n-3.... and n+(n-1)+(n-2)+...1 <=100 n=14 Is the maximum drops required