查找第100个Lucas号码

Question

我应该编写一个Python函数，它接受一个参数n，并返回Lucas序列的第n次迭代。我已经使用递归来实现这一点，我的问题是代码的效率。函数必须通过的测试用例为lucas(100)，预期值为7920708398483372253127。我不知道有什么更有效的方法来解决这个问题，这样程序就不会在这种情况下永远运行下去

这是我的代码：

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))

请注意，这将很快适用于高达100000的n。 对于较大的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来说也会变慢，大约100万。问题是数字变得非常大，算术运算速度很慢。第一百万个Lucas数字已经是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数：

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

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

Done

但是，由于我们使用IEEE浮点，这在纸面上是100%正确的，而在n值越来越高的计算机上不是100%正确的，因此您可能需要将其移植到您最喜欢的python数学风格（sympy等）