Огромный номер Фибоначчи

Question

Я только начал изучать алгоритмы, и я застрял в проблеме нахождения огромного числа Фибоначчи. Мой пример ввода - 5949. Выход должен быть рассчитан менее чем за 5 секунд.

Вот моя попытка:

def calc_fib(n): 
    if n < 0: 
     print ("Error. Bad input") 
    elif n <= 2: 
     return 1 
    else: 
     F = [] 
    for i in range (2,n): 
     F[i] = F[i-1]+F[i-2] 
    return F[n] 

n = int(input()) 
print(calc_fib(n)) 

Но я получаю ошибку в строке с массивами: IndexError: list index out of range

Answer 1

Вы получаете в IndexError, потому что вы создаете пустой массив, а в следующем шаге попытайтесь получить доступ к последним двум элементам. Вы должны инициализировать его (по крайней мере) двумя элементами.

Answer 2

Вам необходимо инициализировать первые два элемента вашего массива: когда i=2, линия F[i]=F[i-1]+F[i-2] действительно F[2]=F[1]+F[0]. Но F[1] и F[0] не существует: массив пуст!

Answer 3

Вы создали пустой список и указали положение в списке, которого нет. использовать также Append как вы добавляете новые элементы

def calc_fib(n): 
    if n < 0: 
     print ("Error. Bad input") 
    elif n <= 2: 
     return 1 
    else: 
     F = [0,1] # <- change 
    for i in range (2,n): 
     F.append(F[i-1]+F[i-2]) # <- change 
    return F[n] 

n = int(input()) 
print(calc_fib(n)) 

Answer 4

Есть уже некоторые ответы здесь, объясняющие, что случилось с вашим подходом. Однако, если вы ищете альтернативную идею, вот очень быстрый подход, чтобы найти числа фибоначчи. Он использует матричное умножение и завершает время O (log N). Используя этот подход, вы можете найти Фибоначчи 5949 в миллисекундах.

def matrix_mul(A, B): 
    return ([A[0][0] * B[0][0] + A[0][1] * B[1][0], 
     A[0][0] * B[0][1] + A[0][1] * B[1][1]], 
     [A[1][0] * B[0][0] + A[1][1] * B[1][0], 
     A[1][0] * B[0][1] + A[1][1] * B[1][1]]) 

def matrix_exp(A, e): 
    if not e: 
     return [[1,0],[0,1]] 
    elif e % 2: 
     return matrix_mul(A, matrix_exp(A, e-1)) 
    else: 
     sq= matrix_exp(A, e//2) 
     return matrix_mul(sq, sq) 

def fibo(n): 
    M = [[1,1],[1,0]] 
    return matrix_exp(M, n)[0][0] 

Read this для понимания, почему это работает

Answer 5

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

Как я уже упоминал в своем комментарии, здесь нет необходимости создавать список, если вы не хотите хранить таблицу чисел Фибоначчи, к которой можно получить случайный доступ.

Чтобы вычислить одиночные числа Фибоначчи, алгоритм матричного умножения Ибрагима выполняется очень быстро, но это не обязательно для вычисления F (5949). Простая петля for может сделать это менее чем за 0,06 секунды на моей старой машине с частотой 2 ГГц.

from __future__ import print_function 

def fib(n): 
    a, b = 0, 1 
    for i in range(n): 
     a, b = a + b, a 
    return a 

# Test 
for i in range(6): 
    print(i, fib(i))  

выход

0 0 
1 1 
2 1 
3 2 
4 3 
5 5 

Если вы делаете это на Python 2 заменить range в fib на xrange, чтобы сохранить память.