Выпадение яйца в худшем случае

Question

Я пытался написать алгоритм для вычисления максимального количества или испытаний, требуемых в худшем случае, в проблеме сбрасывания яйца. Вот мой питон код

def eggDrop(n,k): 
    eggFloor=[ [0 for i in range(k+1) ] ]* (n+1) 
for i in range(1, n+1): 
    eggFloor[i][1] = 1 
    eggFloor[i][0] = 0 
for j in range(1, k+1): 
    eggFloor[1][j] = j 
for i in range (2, n+1): 
    for j in range (2, k+1): 
     eggFloor[i][j] = 'infinity' 
     for x in range (1, j + 1): 
      res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x]) 
      if res < eggFloor[i][j]: 
       eggFloor[i][j] = res 

return eggFloor[n][k]print eggDrop(2, 100) 

`` `

код выводит значение 7 для 2eggs и 100floors, но ответ должен быть 14, я не знаю, что ошибка я сделал в код. В чем проблема?

Answer 1

Проблема заключается в этой строке:

eggFloor=[ [0 for i in range(k+1) ] ]* (n+1) 

Вы хотите, чтобы это создать список, содержащий (п + 1) списки (к + 1) нулей. То, что делает * (n+1), несколько отличается - оно создает список, содержащий (n + 1) копии того же списка.

Это важное различие - потому что, когда вы начинаете изменять записи в списке - скажем,

eggFloor[i][1] = 1 

это фактически изменяет элемент [1]из всех списков, а не только i го один.

Чтобы вместо этого создать отдельные списки, которые могут быть изменены независимо друг от друга, вы хотите что-то вроде:

eggFloor=[ [0 for i in range(k+1) ] for j in range(n+1) ] 

С этой модификацией, программа возвращает 14, как и ожидалось.

(Чтобы отладить это, было бы неплохо написать функцию для выделения массива eggFloor и отобразить ее в разных точках вашей программы, чтобы вы могли сравнить ее с тем, что вы ожидали. скоро станет довольно ясно, что происходит!)