如何计算第10000000项斐波那契数

当n比较小的时候，无非就是什么递归，递推，但是当n大了呢，比如2000项，20000？200000？递归可能就解不出来了，而递推也比较耗时间

我简单的查了下网上并没有类似的问题和解答

我这里就简单的讲讲我的做法

以python为例，首先是建立一个长度为n+1（0到n）的数组，把第n项标为特殊值，然后用公式去寻找需要的值：

公式：

当n为偶数；
f(n)=f(n/2)*f(n/2)+f(n/2+1)*f(n/2+1)
当n为奇数：
f(n)=f((n+1)/2)*f((n+1)/2+1)+f((n+1)/2)*f((n+1)/2-1)

思路：

要算n项，就要去找对应的一些项，类似递归，但是递归肯定不行，所以把递归改成循环，用标记大法

这里就是用的数组（列表），用递推公式，把未知的记录下来，如果公式里没有未知，就计算其值，直到相关的所有子公式都没有未知数，即可得到结果

这样可以忽略掉所有与结果无关的数，只取感兴趣的数，用最快的速度找到答案

代码：

下面是python代码，（其他语言类似，不过py支持很大的整数计算，像c语言之类的就要用到大整数加法了)

n = int(input('n：'))+1
if n <= 4:
    d = [None]*4
else:
    d = [None]*n
d[n-1] = -1
d[n-2] = -1
d[0],d[1],d[2],d[3] = 0,1,1,2
while -1 in d:
    while True:
        n = d.index(-1)+1
        if n%2 == 0:
            a = int(n/2)
            b = a+1
            if not d[a-1]:
                d[a-1] = -1
                break
            if not d[b-1]:
                d[b-1] = -1
                break
            d[n-1] = d[a-1]**2+d[b-1]**2
            break
        else:
            a = int((n+1)/2)
            if not d[a-1]:
                d[a-1] = -1
                break
            if not d[a-2]:
                d[a-2] = -1
                break
            if not d[a]:
                d[a] = -1
                break
            d[n-1] = d[a-1]*d[a]+d[a-1]*d[a-2]
            break
print(d[n-1])

在少量的数据时可能不如其他算法，但是当数据极大，例如几千几万，都是很快就出结果的，其他常规算法肯定不行

注：

（亲测千万以下时长都是在可忍受的范围内的（大概一分钟以内，百万以下都是秒出））

如果觉得这篇文章对您有帮助，请点个赞吧！