IT討論區(56) I巴條數何時了

1001 回覆
4 Like 0 Dislike
2019-02-10 13:53:59
The maths formula for the nth Fibonacci numbers involves non-integers, BTW. If you just implement it naively, it will break pretty quickly even for small n. Using the closed form
is not as straight forward as one would think. Pls refer to my old post in 高登 for all the details.
2019-02-10 13:56:35
Fibonacci numbers 用 neural network 計唔計到㗎
2019-02-10 16:10:26
睇公司。我通常便服加涼鞋。如果你去傳統公司例如銀行律師樓,著西裝無壞。如果係technical start-up可以business casual或便服。
2019-02-10 16:36:47
嚴格嚟講,最好time complexity係O(log n)個乘法,但乘法唔一定係O(1)。Fibonacci numbers可以用Binet's Formula嚟計。


https://artofproblemsolving.com/wiki/index.php?title=Binet%27s_Formula
(1+sqrt(5))/2 = 1.618033988749895 係黃金分割率 𝜙 。
(1-sqrt(5)/2) = -0.6180339887498949, 絕對值細過1。

當n足夠大時(1-sqrt(5)/2)^n變得小到可以不理,Fn 大約係:

Fn ≈ (𝜙 ^ n) / sqrt(5)

一般電腦64-bit以下加減乘除無需用big integer,可以O(1)做到。如果要唔overflow話:

(𝜙 ^ n) / sqrt(5) ≤ 2^64
𝜙 ^ n ≤ 2^64 * sqrt(5)
n ≤ log(2^64 * sqrt(5)) / log(𝜙)
n ≤ 93.85916172458816
即係話64-bit unsigned integer最盡係只可以表示第93個Fibonacci number。

93咁細根本唔洗用O(log n) 嘅matrix multiplication algorithms,用O(n) loop仲簡單,分分鐘仲快過用matrix。

當n > 93就要用big integer,加減乘除再唔係O(1)。
2019-02-10 16:42:15
Well, int type is 32-bit on many common systems (64-bit is usually long int) and 32-bit signed integer can only represent up to the 46th Fibonacci number. Unless one uses the most stupid recursive algorithm with exponential time complexity, it is a moot point to talk about asymptotic time complexity.
2019-02-10 17:00:12
如果係floating point,pow() 一般係用Taylor's series approximation,可以當O(1),但用floating point計Fibonacci number快就會有rounding error,而且n亦唔可以真係好大。IEEE 754 double precision floating point去到大約10^308就爆煲(第1474個Fibonacci number)。 如果唔係用Taylor's series,以我知最好time complexity係O(log n)個乘法,但乘法唔一定係O(1)。
2019-02-10 17:55:46
無上黎一陣變英文台
2019-02-10 17:57:25
我做開嘅工都要著恤衫西褲
所以直接放工見/請半日假見都咁著
2019-02-10 17:59:29
it9講中文都1999
仲expect佢地英文 ?
2019-02-10 17:59:34
見咩類型公司?
2019-02-10 18:08:46
我近排搵工有好多都要試下英文
不過i 巴今次講得啱
香港唔少IT 狗中文都1999
2019-02-10 18:24:25
玩python 有冇邊隻database推介?
for個人用
2019-02-10 18:29:58
in ap 以上 好多都要英文自我介紹
2019-02-10 18:34:45
it9:my name is it9.
i....i..i...am...am a pro..grammer.
Th...This all of..of my se..lf. self intro...duction
2019-02-10 19:08:41
inHouse angular2+ webApp development 就黎2年experience
想問下, 生蕃茄而家係唔係已經唔洗成日ot?
最近approch 個agent 佢話e 2年生蕃茄請多左人
所以ot 少左,無咁chur

有無巴打有最新行情
2019-02-10 19:19:36
agent為左昆你落搭有咩做唔出
2019-02-10 19:54:21

咁大膽
2019-02-10 19:57:11
2019-02-10 20:10:14
唔駛講中文 講js都1999
2019-02-10 20:12:12
靜係叫佢講個function點設計都1999
點解IT9會咁
講debug,有bugs..夾雜 it terms
聽到人地頭都暈埋
2019-02-10 20:13:38
因為software engineering呢科唔係必修
吹水台自選台熱 門最 新手機台時事台政事台World體育台娛樂台動漫台Apps台遊戲台影視台講故台健康台感情台家庭台潮流台美容台上班台財經台房屋台飲食台旅遊台學術台校園台汽車台音樂台創意台硬件台電器台攝影台玩具台寵物台軟件台活動台電訊台直播台站務台黑 洞