python - 尝试使用 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

n=331 得到 5 而不是 9 的原因是第 93 个 fib 数大于 2^64 时溢出。所以它被存储为负数。第 94 个数字也将是不正确的，因为它使用了不正确的第 93 个数字，这对所有 >92 的数字都是如此。

这可以通过使用普通的 python 数组来避免，因为 int 在 python 中没有绑定(bind)。试一试:

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