1樓:引力微子球
這個回答只適用於直接求第n項的情況,且可能需要一些線性代數和快速冪相關的知識。
首先我們把求斐波那契數列的通項寫成以下形式:
那麼我們可以推出:
之所以繞到矩陣,是因為我們可以藉著快速冪演算法來快速的計算這個等號左邊的矩陣(時間複雜度從 降至 )。
deffib(n
):def
mul(a,
b):# 為對稱矩陣輕度優化的版本,矩陣中相等的兩項只求一次x=a[0][
0]*b
[0][0
]+a[
0][1]
*b[1
][0]y
=a[0
][0]*
b[0][
1]+a
[0][1
]*b[
1][1]
z=a[
1][0]
*b[0
][1]+
a[1][
1]*b
[1][1
]return((x
,y),(
y,z))
storage=((
0,1),
(1,1
))# 快速指數冪用的矩陣
result=((
1,0),
(0,1
))# 單位矩陣i=
0while(1
<
<=(n
-1):# result根據需要乘上storageif(n-1)
&(1<
result
=mul
(result
,storage
)storage
=mul
(storage
,storage
)# storage矩陣在每次迴圈時平方i+=1# 返回右下角那一項的值
return
result[1
][1]我自己這邊(i7-7700k)測下來第2000000項接近1秒。
計算機小白想用python讓日常辦公高效點,適合哪個方向?
yezideY 1.phthon適合我的要求嗎?難易程度如何?不適合,客觀來說我身邊的科班同學沒有去學習也不會掌握用python處理文件資料,尤其是不僅僅是資料處理,還有固定的排版要求。2.據說python有很多方向,什麼web啥的 我這個要求應該選擇哪個方向啊?如果一定要用python,做的是資料...
python如何高效利用多核系統?
塵浩 嚴謹說py作為語言本身沒有限制多核之類,是其最主流的實現CPY採用了全域性直譯器鎖,導致在cpy下你多執行緒是無法多核並行的。但它仍然是個併發,且在IO為主的任務中多執行緒是有意義的,GIL只是鎖了計算資源。你可以換個實現,pypy之類的。也可以直接多程序。新開乙個直譯器執行等於多程序,是並行...
剛開始接觸Python,如何正確高效的開展Python學習?
zhaossbnu python安裝目錄下有乙個人doc資料夾,裡面又乙個chm檔案,你參考那個學習乙個 官方還有pdf版的Download Python 3.4.5 documentation 傅坦坦 看下基本語法,然後直接開始擼碼。比如前些天我要考學位英語,頻繁查網頁版的有道詞典,其實我的需求只...