創作內容

0 GP

從費氏數列中來探討,把程式寫好這件事到底需不需要數學好

作者:哈哈喔│2019-04-18 21:12:08│贊助:0│人氣:77
最近在網路上看到有人問了一個python的小程式,
解完之後發現是很有趣的問題,也很發人深思,故在此紀錄一下,順便探討這個已經被討論到爛掉的問題。

寫程式,到底需不需要數學在背後支撐?

問題是這樣的:
費氏數列,又叫Fibonacci number
規則:第一項為1,第二項為1,往後每一項數字為前二項數字和

目標:求出費氏數列中,小於四百萬的所有數字中,該項是偶數的所有數字和。


相信有碰過離散或者聽過費氏數列的人不在少數,又或者你聽過黃金比例
費氏數列涵蓋的內容不只是有關數學領域的研究,在生活上也很常見到,
如川普的臉就是一個例子:


回歸正題,
當想解這一道題目時,
有人可能會寫出以下這樣的程式:

執行時間大約一秒

也有可能有人看到遞迴就馬上想出一個程式:

這下不要說是幾秒能完成了,電腦爛一點可能放著去睡一晚都還沒有結果。


想當然爾,上述兩者不可能是好的解法,
第二種一定是直接淘汰的,第一種我們也可以發現明顯的缺點:
用%運算子來取餘數的時間實在太長,
就算第一種方式是用Dynamic programming的方式,依然不夠好!

這時,如果有點概念的人,會拿出一張紙寫下費氏數列來觀察:
1, 1, “2”, 3, 5, “8”, 13, 21, “34”, 55, 89, “144”, 233, 377, “610”, 987, 1597, “2584”, …
可以發現,每隔3個Fibonacci number就是一個偶數項。

而且觀察奇數項,3 = 1 + 1 * 2, 5 = 1 * 2 + 1 * 3
13 = 3 + 5 * 2, 21 = 3 * 2 + 5 * 3
後二個奇數必定是前兩個奇數的線性組合,
因此我們可以導出一般式如下:

把它寫成程式的話,實現如下:


但這樣依然是一個O(n)的作法(其實是pseudo polynomial,因為input的四百萬只是一個數字),似乎沒有快多少......


那我們到底該怎麼做呢?
首先,有學過離散的人應該知道Fibonacci number是有closed form的,
不知道的人也可以看一下影片中的推導,
其公式如下:

這時我們令

其中phi是 golden ratio(i.e. 黃金比例),
計算一下:

可得原式為
由於我們之前的觀察,每隔 3 個 Fibonacci number 就是一個偶數項,
因此我們想求的總和可以寫成如下:

但我們不知道 t 應該是多少,
我們應該要找到一個 t 使得f(3t)會是費氏數列中在4000000以內最大的偶數,
才會符合題目的條件。

寫個小程式計算一下:

輸出結果為11
但這種計算方法會讓我們的時間掉到非常數時間去。

所以有更好的做法來算出 t,
我們可以改用近似的方式計算看看,因為
在 n 越來越大時會趨近於 0,允許我們直接忽略不計(誤差 1 以內):

也可以寫個小程式跑一下 :


確認一下:
所以f(33)時確實是 4000000 內最大的Fibonacci number
故 t = 33 / 3 = 11
得出 t 後,我們現在把 t 帶回去得:

利用高中的求和公式,
等比級數和 = (首項-末項) / (1 - 公比)


得到漂亮的 closed form,計算上就是 O(1)
因此程式可以寫成如下:

這下不管寫四百萬內還是多少,都可以在最短時間內求出來了!

我們把完整的流程程式化,從頭到尾將其寫完整大概長這樣:


結果便可以在O(1)時間內計算出來
(註:sqrt已經是FPU裡算術運算指令直接實作的電路,可以直接當成常數時間來看。)
答案就是4613732!

這是一個很實際使用簡單數學來簡化時間複雜度的運用,
當數字一大,結果可能會差得更遠。

寫完這道題之後覺得特別有趣,
也發現不管在多簡單的程式中,數學都有可能發揮它的功用。
把數學隨著程式撰寫技巧同時精進,對一個程式設計員來說絕對有很大的助益。
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4363544
All rights reserved. 版權所有,保留一切權利

相關創作

留言共 0 篇留言

我要留言提醒:您尚未登入,請先登入再留言

喜歡★shownlin 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:撐過第一學期的資工所生活...

追蹤私訊

作品資料夾

xo41998707所有人
A-KUMA惡魔契約更新!有愛有緣的大家快來踩踏踩踏吧OUO!看更多我要大聲說1小時前


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】