<p>这里有一个更快的方法。只需使用最后两个值,即可逐步建立序列</p>
<pre class="lang-py prettyprint-override"><code>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))
</code></pre>
<p>请注意,这将很快适用于高达100000的n。
对于较大的n,我们可以使用<a href="https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form" rel="nofollow noreferrer">doubling formulas for Fibonacci</a>和<a href="https://en.wikipedia.org/wiki/Lucas_number#Relationship_to_Fibonacci_numbers" rel="nofollow noreferrer">relationship between Lucas numbers and Fibonacci numbers</a>:<code>lucas(n) = fibonacci(n-1)+fibonacci(n+1)</code></p>
<pre><code>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))
</code></pre>
<p>这对n来说也会变慢,大约100万。问题是数字变得非常大,算术运算速度很慢。第一百万个Lucas数字已经是208988位了</p>