两个鸡蛋问题混乱

Question

两个鸡蛋问题:

• 给你2个鸡蛋.
• 您可以使用100层高的建筑.
• 鸡蛋可能非常坚硬或非常脆弱意味着如果从一楼掉落可能会破裂,或者如果从100楼掉落则可能甚至不会破裂.两个鸡蛋都是相同的.
• 您需要弄清楚100层高的建筑物的最高楼层,鸡蛋可以在不破坏的情况下掉落.
• 现在的问题是你需要做多少滴.你可以在这个过程中打破2个鸡蛋

我确信已经充分讨论了两个鸡蛋问题(如上所述).但是有人可以帮助我理解为什么以下解决方案不是最佳的.

假设我使用段大小的分段和扫描算法s.所以,

d ( 100 / s   + (s-1) ) = 0    [ this should give the minima,  I need '(s-1)' scans per segment and there are '100/s' segments]
-
ds

=> -100 / s^2 + 1 = 0
=> s^2 = 100
=> s = 10

所以根据这个,我需要最多19滴.但最佳解决方案可以做到14滴.

那么问题出在哪里呢？

Answer 1

你似乎在假设大小相等的片段.对于最佳解决方案,如果第一个段的大小为N,则第二个段的大小为N-1,依此类推(因为当您开始测试第二个段时,您已经为第一个段丢弃了一个分割).

Answer 2

所以,你需要解决n+(n-1)+(n-2)+...+1<=100,从那里(n)(n+1)/2<=100(这个函数变换与做等差数列的等差数列的求和又名),现在如果你解决N(WolframAlpha的:Reduce[Floor[n + n^2] >= 200, n])你14.现在你知道你需要到一楼下降是14楼,接下来是(14 + 14-1)楼和整个序列:

14; 27; 39; 50; 60; 69; 77; 84; 90; 95; 99; 100 

如果你打破第一个鸡蛋,你会回到最后一个鸡蛋并线性检查所有选项,直到你打破第二个鸡蛋,当你这样做时,你得到了答案.没有魔力.

http://mathworld.wolfram.com/ArithmeticSeries.html

Answer 3

正确和最佳的解决方案是13, 25, 36, 46, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100,假设鸡蛋断裂的地板随机选择,其中找到鸡蛋休息的楼层的平均试验次数最少.

基于这些信息,我们可以编写一个递归函数来最小化平均试验,从而得到解决方案

13, 25, 36, 46, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100

每个楼层步骤都有以下最大试验

13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14

这显然比通过假设从14开始并减少的差距而得到的天真解决方案要好得多.在这种情况下,55%的时间你只需要13次试验.它非常接近于得到的最优解n (n+1) / 2 >= 100,n = 13.651并且我们的最优解是(13*5+14*9)/14即13.643

这是一个快速实现:

import sys

def get_max_trials(floors):
    pf = 0
    trials = []
    for i, f in enumerate(floors):
        trials.append(i+f-pf)
        pf = f
    return trials

def get_trials_per_floor(floors):
    # return list of trials if egg is assumed at each floor
    pf = 0
    trials = []
    for i, f in enumerate(floors):
        for mid_f in range(pf+1,f+1):
            trial = (i+1) + f - mid_f + 1
            if mid_f == pf+1:
                trial -= 1
            trials.append(trial)
        pf = f
    return trials

def get_average(floors):
    trials = get_trials_per_floor(floors)
    score = sum(trials)
    return score*1.0/floors[-1], max(trials)

floors_map = {}
def get_floors(N, level=0):
    if N == 1:
        return [1]
    if N in floors_map:
        return floors_map[N]
    best_floors = None
    best_score = None
    for i in range(1,N):
        base_floors = [f+i for f in get_floors(N-i, level+1)]
        for floors in [base_floors, [i] + base_floors]:
            score = get_average(floors)
            if best_score is None or score < best_score:
                best_score = score
                best_floors = floors

    if N not in floors_map:
        floors_map[N] = best_floors
    return best_floors

floors = get_floors(100)
print "Solution:",floors
print "max trials",get_max_trials(floors)
print "avg.",get_average(floors)

naive_floors = [14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100]
print "naive_solution",naive_floors 
print "max trials",get_max_trials(naive_floors)
print "avg.",get_average(naive_floors)

输出:

Solution: [13, 25, 36, 46, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100]
max trials [13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14]
avg. (10.31, 14)
naive_solution [14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100]
max trials [14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 12]
avg. (10.35, 14)