Algorithm (1 piece)

Egg problem

Description: There are two eggs, dropped from 100 layers, to test the hardness of the egg, assuming that the egg does not break at the 9th layer, and broken at the 10th layer, then the critical point of the egg will not break at the 9th layer. Q: How to use the minimum number of attempts to test the number of eggs will not break the critical point.

If the problem has an optimal solution, and the interpretation of the optimal solution is an upper limit on the number of worst attempts, then if the optimal solution is x, then the position of the first attempt should be x. Because if we break this, we’re left with one egg and we can only go from level 1 to x minus 1. If this position is not broken, then the problem becomes a subproblem, at the height of n minus x, assuming that the optimal solution is X minus 1(tried once before), where is the position of the first attempt.

F (x) = min(Max (I, f(x-i)+1)) (1<= I <=x) Max expresses the worst result after I, and the lowest worst result is the optimal solution

It can be roughly described as the optimal solution of f(x) is that the maximum of I and f(x- I)+1 minimizes for some value of I.

So this is essentially a problem of dynamic programming:

record_dict = {}

def f(n):
    if n == 1:
        return 1
    min = n+1
    for i in range(2, n):
        if n-i in record_dict:
            compare_right = record_dict[n-i]
        else:
            compare_right = f(n-i)
            record_dict[n-i] = compare_right
        max_v = max(i, compare_right+1)
        if min > max_v:
            min = max_v
    return min
Copy the code