Найти первое число Фибоначчи выше 1 миллиона

Question

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

Я думаю, вы бы отключилиfor-с циклом while, но не понял, как заставить все это работать.

Заранее спасибо :)

def fib_seq(n):
    if n <= 2:
       return 1
    return fib_seq(n-1) + fib_seq(n-2)


lst = []
for i in range(1, 20):
    lst.append(i)
    print(fib_seq(i), lst)

Answer 1

Если вам нужно сделать это с некоторой находкой рекурсии, вы должны стараться не вызывать рекурсии дважды с каждой итерацией.Это классический пример, где сложность взрывается.Один из способов сделать это - запомнить уже рассчитанные результаты.Другое - поддерживать состояние с помощью аргументов функции.Например, это даст ответ и вызовет функцию только 32 раза:

def findIndex(v, prev = 0, current = 1, index = 0):
    if v < prev:
        return (prev, index)
    return findIndex(v, current, prev+current, index + 1 )


findIndex(1000000)  # (1346269, 31)

Answer 2

Некоторые баллы:

• Вам не нужно составлять список.Вас только просят вернуть индекс и соответствующее число Фибоначчи.

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

Вот как это может выглядеть:

def fib(atleast):
    a = 0
    b = 1
    i = 1
    while b < atleast:
        a, b = b, a+b
        i += 1
    return i, b


print(fib(1000000)) # (31, 1346269)