斐波那契数列第N项

如何计算第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])

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

注:

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

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

本文作者: 小世炎
本文链接: https://blog.xiaoshiyan.top/archives/202
版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议 转载请注明出处!
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇