Блог

Главная - Вопросы по программированию - Проблема при попытке реализовать итеративное решение для рядов Фибоначчи с использованием списков

Проблема при попытке реализовать итеративное решение для рядов Фибоначчи с использованием списков

#python #list

Вопрос:

  def fibo(m):
  dp = []
  for i in range(m 1):
    dp.append(0)
  dp[0] = 1
  dp[1] = 1
  if(m>1):
    for i in range(2,m 1):
      dp[i] = dp[i-1]   dp[i -1]
  return dp[m]

Я получаю сообщение об ошибке, в котором говорится, что индекс списка не привязан, может ли он решить эту проблему и может опубликовать правильный код . Спасибо.

 ---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-92-ea67e751dd0e> in <module>()
     12   return dp[m]
     13 
---> 14 fibo(0)

<ipython-input-92-ea67e751dd0e> in fibo(m)
      6     dp.append(0)
      7   dp[0] = 1
----> 8   dp[1] = 1
      9   if(m>1):
     10     for i in range(2,m 1):

IndexError: list assignment index out of range

Комментарии:

1. Ваш код отображается range(m 1) , но обратная связь range(m) .

2. range(0 1) это справедливо 0 . Поэтому вы не создаете dp[1] , когда звоните fibo(0)

Ответ №1:

Когда m == 0 начальный for цикл только добавляется dp[0] , поэтому при назначении на dp[1] появляется ошибка.

Вместо назначения после цикла добавьте 1 в цикл. Элементы после dp[1] этого будут перезаписаны вторым циклом, поэтому не имеет значения, каковы их исходные значения.

 def fibo(m):
    dp = []
    for i in range(m 1):
        dp.append(1)
    if(m>1):
        for i in range(2,m 1):
            dp[i] = dp[i-1]   dp[i-2]
    return dp[m]

Другой способ сделать это-инициализировать dp первые два элемента, а затем добавить к ним в цикле, который вычисляет каждый элемент ряда.

 def fibo(m):
    dp = [1, 1]
    if(m>1):
        for i in range(2,m 1):
            dp.append(dp[i-1]   dp[i-2])
    return dp[m]

Ответ №2:

Зачем добавлять нули в свой список перед присвоением значений ? Когда вы пройдете m = 0 , у вас будет ошибка при попытке доступа dp[1] .

Кроме того, в нем есть опечатка dp[i] = dp[i-1] dp[i -1] . Фибоначчи-это сумма (n-1) th и (n-2) th элементов, подобных этому dp[i] = dp[i-1] dp[i -2]

Я бы сделал что-то вроде :

 def fibo(m):
  dp = []
  dp.append(0)
  dp.append(1)
  if(m>1):
    for i in range(2,m 1):
      dp.append(dp[i-1]   dp[i -2])
  return dp[m]

Ответ №3:

Вы также можете инициализировать dp список в начале до длины числа, а затем просто сохранить ответ в соответствующем индексе.

 def fib(n):
    if n<=1:
        return n
    dp=[0]*(n 1)
    dp[1]=1
    for i in range(2,n 1):
        dp[i]=dp[i-2] dp[i-1]
    return dp[n]

>>> print(fib(5))
5
>>> print(fib(9))
34

Ответ №4:

Ошибка индекса, которую вы видите, возникает, когда вы передаете m как 0. В этом случае список содержит только один элемент( dp = [0] ), но ваш код пытается получить доступ ко второму элементу по индексу: т. е. dp[1] = 1 (отсюда ошибка индекса)

Простой способ обойти это-вообще не инициализировать список, а сразу начать добавлять в него номера рядов Фибоначчи.

 def fibo(m):
   dp = []
   dp.append(1)
   dp.append(1)
   # Use a loop for the remainder of the numbers. Will only execute if m > 1
   for i in range(2,m 1):
       dp.append(dp[i-1]   dp[i-2])
   return dp[m]

Альтернативным решением было бы вообще не использовать список (поскольку вас интересует только n-й элемент серии). Решение довольно лаконичное:

 def fibo(m):
    a, b = 1, 1
    while (m > 0):
         a, b = b, a b   # At every iteration, "a" takes the value of the next element in the fibo series.
         m -= 1
    return a
Метки: