找到第100个Lucas数

Question

我应该编写一个Python函数，该函数接受参数n，并返回Lucas序列的第n次迭代。我使用了递归来实现这一点，我的问题是代码的效率。函数必须通过的测试用例是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

这里有一个更快的方法。仅使用最后两个值，就可以逐步建立序列。

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，我们可以使用doubling formulas for Fibonacci和relationship between Lucas numbers and Fibonacci numbers：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))

对于大约一百万的n，这也会变慢。问题是数字变得非常大，因此算术运算很慢。第一百万个卢卡斯数字已经有208988位数了。

Answer 2

您正在重复计算相同的值，因此请缓存它们：

@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 3

有些人会找到这个问题，因为他们有相同的家庭作业，但有些人会找到它，因为他们希望找到一种真正有效的方法来计算Lucas数。

对于那些家伙:根本不要写递归函数，你可以用一点微不足道的数学直接计算任何Lucas数：

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

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

Done。

然而，因为我们使用的是IEEE floats，所以这在纸上是100%正确的，而在n值越来越高的计算机上不是100%正确，所以你可能需要将它移植到你最喜欢的数学(符号等)中。