尝试使用 python 计算斐波那契数的最后一位时，我收到错误"RuntimeWarning: overflow encountered in long_scalars"

Question

我正在使用Python来查找斐波那契数的最后一位数字。这是我的代码：

import numpy as np
def calc_fib(n):
if n <= 1:
return n
else:
a=np.arange(n+1,dtype='int64')
for i in range(2,n+1):
a[i]=a[i-1]+a[i-2]
return a[n]%10
n = int(input())
print(calc_fib(n))

该代码适用于 n 的小值，例如当 n = 10 时，它产生 5 的输出，但是当使用较大的 n 值时，它会产生输出：

/Users/amrsulaiman/Desktop/Algorithms_Coursera/W2_2.py:10: RuntimeWarning: overflow encountered in long_scalars a[i]=a[i-1]+a[i-2]
5

值 5 是错误的。应该是9。如何解决此溢出问题并修复我的代码。

Answer 1

您获得 5 而不是n=3319 的原因是，您获得溢出作为第 93 个斐波那契数字，因为它大于 2^64。所以它被存储为负数。第 94 个数字也将不正确，因为它使用不正确的第 93 个数字，这适用于所有数字>92。

这可以通过使用普通的python数组来避免，因为ints在python中没有绑定。试一试：

def calc_fib(n):
if n <= 1:
return n
else:
a=[0,1]
for i in range(2,n+1):
a.append(a[i-1]+a[i-2])
return a[n]%10
n = int(input())
print(calc_fib(n))

Answer 2

十进制加法的一个属性是，总和的最低有效数字仅取决于要相加的两个数字的最低有效数字。因此，您只需一位数即可完成所有计算：

def calcFibonacciLastDigit(n):
if n <= 1:
return n
a=0
b=1
for i in range(2,n+1):
c = a+b
if c >= 10:     #max value for c is 18
c -= 10     #so subtracting 10 will keep c as one digit
a = b
b = c
return c
print(calcFibonacciLastDigit(331))  #prints 9