Найти сотый номер Лукаса

Question

Я должен написать функцию Python, которая принимает аргумент n и возвращает n-ю итерацию последовательности Лукаса. Я использовал рекурсию для выполнения sh этого, и моя проблема связана с эффективностью кода. Тестовый пример, который должна пройти функция: lucas(100), с ожидаемым значением 792070839848372253127. Я не знаю более эффективного способа решить эту проблему, чтобы программа не продолжала работать вечно, когда доходит до этого случая.

Это мой код:

def lucas(n):
"""Returns the nth Lucas number.
  Lucas numbers form a series similar to Fibonacci:
  2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843,...

>>> lucas(0)
2
>>> lucas(1)
1
>>> lucas(2)
3
>>> lucas(3)
4
>>> lucas(11)
199
>>> lucas(100)
792070839848372253127
"""
"*** YOUR CODE HERE ***"



    if n == 0:
      return 2
    elif n == 1:
      return 1
    else:
      return lucas(n-1) + lucas(n-2)

Если кто-то может оказать какую-либо помощь, я был бы очень признателен!

Редактировать: Спасибо всем, кто предоставил помощь и другие решения !!! Я новичок в использовании StackOverflow, поэтому я действительно ценю это! В итоге я использовал следующий код, чтобы найти гораздо более быстрое и эффективное решение:

list = [2,1]

for i in range(2,n+1):
    list.append(list[i-2] + list[i-1])

return list[n]

Answer 1

Вы постоянно вычисляете одни и те же значения, поэтому кешируйте их:

@functools.lru_cache
def lucas(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    else:
        return lucas(n-1) + lucas(n-2)

Или просто оставьте последние два рядом для следующего:

def lucas(n):
    a, b = 2, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Рекурсивная версия:

def lucas(n, a=2, b=1):
    return lucas(n - 1, b, a + b) if n else a

Answer 2

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

def lucas(n):
    a, b = 2, 1
    for _ in range(n):
        a, b = b, a + b
    return a

for i in range(101):
    print(i, lucas(i))

Обратите внимание, что это будет работать быстро для n до примерно 100 000. Для больших n мы можем использовать формулы удвоения для чисел Фибоначчи и соотношение между числами Лукаса и числами Фибоначчи : lucas(n) = fibonacci(n-1)+fibonacci(n+1).

def fibonacci(n):
    return fibonacci_pairs(n)[0]

# returns the tuple (fib(n), fib(n+1)).
def fibonacci_pairs(n):
    if n == 0:
        return (0, 1)
    else:
        a, b = fibonacci_pairs(n // 2)
        c = a * (b * 2 - a)
        d = a * a + b * b
        if n % 2 == 0:
            return (c, d)
        else:
            return (d, c + d)

def lucas(n):
    if n == 0:
        return 2
    else:
        return fibonacci(n+1) + fibonacci(n-1)

for i in range(101):
    print(i, lucas(i))
for i in range(7):
    print(10**i, lucas(10**i))

Это также замедляется примерно на 1 миллион. Проблема в том, что числа становятся очень большими, для которых арифметические операции c являются медленными. Миллионный номер Лукаса уже 208988 цифр.

Answer 3

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

Для тех люди: вообще не пишите рекурсивную функцию, вы можете напрямую вычислить любое число Лукаса с тривиальным битом математики:

golden_ratio = (1 + 5 ** 0.5) / 2

def lucas(n):
    if n == 0:
        return 2
    return round(golden_ratio ** n)

Готово .

Однако, поскольку мы работаем с плавающими IEEE, это на 100% правильно на бумаге, а не на 100% правильно на компьютерах с более высокими и высокими значениями n, поэтому вам может потребоваться перенести это на ваш любимый вид математика python (sympy, et c)