Индекс вне диапазона в Фибоначчи с использованием динамического программирования - PullRequest
Новая
       24

Индекс вне диапазона в Фибоначчи с использованием динамического программирования

0 голосов
/ 31 октября 2019

Недавно динамическое программирование заинтересовало меня. Итак, я написал код для ряда Фибоначчи, используя концепцию динамического программирования, но каждый раз при выполнении меня встречают с массивом вне индекса вне диапазона. Я изо всех сил пытался понять это, но не мог это исправить. Из-за ошибки я думаю, что индекс выходит за рамки последней итерации. Вот мой код: 

def fibo(n) :

# len(mem) being shorter than n will indicate that the position is not filled(memoized)
# if it is equal then is has the required value it wont have to calculate res = fibo(n-1)+ fibo(n-2)
    if len(mem) == n :
        return mem[n]

#General cases
    if n == 1 or n == 2 :
        res = 1
    elif n == 0 :
        res = 0
    else :
        res = fibo(n-1)+ fibo(n-2)

#Here the len(m) should be n-1 and thus we append the value of 'res'so at one point we can return it instead of calculating
    mem.append(res)
    return res

#Start of Program
n = int(input("Enter the position :"))

#Defining mem as a list
mem = []

print(fibo(n))

Ответы [ 2 ]

0 голосов
/ 03 ноября 2019

но правильна ли реализация?

Нет. Даже если вы включите исправление @ ExplodingGayFish, оно скрывает тот факт, что ваша логика запоминания нарушена. Например: 

...
#Defining mem as a list
mem = [1]

print(fibo(5))
print(mem)

print(fibo(4))
print(mem)

Вы получаете правильный ответ, но выполняете всю работу снова: 

> python3 test.py
5
[1, 1, 1, 2, 1, 3, 1, 1, 2, 5]
3
[1, 1, 1, 2, 1, 3, 1, 1, 2, 5, 1, 1, 2, 1, 3]
>

Это связано с неправильным обращением с массивом mem, включаяэтот тест: 

if len(mem) == n :

, который действительно должен быть больше , а не равно . Решение на самом деле проще, чем ваш неработающий код: 

def fibo(n, memory=[0]):  # intentional dangerous default

    if len(memory) > n:
        return memory[n]

    if n == 1:
        res = 1
    else:
        res = fibo(n - 1) + fibo(n - 2)

    memory.append(res)

    return res

Однако, даже при множественных вызовах fibo(900), хороший рекурсивный алгоритм , подобный следующему: 

def fibo(n, res=0, nxt=1):
    if n == 0:
        return res

    return fibo(n - 1, nxt, res + nxt)

будет соответствовать скорости моей исправленной версии вашего кода даже без напоминания! И ни один не достигнет fibo(1000) без расширения стека Python из-за глубины рекурсии. (Вот почему было бы лучше запоминать итеративное решение.)

0 голосов
/ 31 октября 2019

Сначала вам нужно добавить 1 к вашему списку: 

mem = [1]
for i in range(1,10):
    print(fibo(i))

1
1
2
3
5
8
13
21
34
...