最近研究一些算法, 入門的就是斐波那契數(shù)列
如果你問(wèn)什么是斐波那契數(shù)列? ?既然你誠(chéng)心誠(chéng)意的發(fā)問(wèn)了, ?我就大發(fā)慈悲的告訴你! ?
斐波那契數(shù)列, 又稱黃金分割序列 ( 0.0很高大上的名字, 但我始終不太理解為什么又這么稱呼 )
即, 給定初始2個(gè)值, 第三位起, 每一項(xiàng)位前兩位之和
例如: ?給定初始值 0, 1 那么, ?斐波那契數(shù)列為 ??0, 1, 1, 2, 3, 5, 8, 13, 21, 34......
可以看出其 數(shù)學(xué)公式 為:
n = 1時(shí) ? f(n) = 0; ?n = 2時(shí) ? f(n) = 1;?
n >3時(shí) ?f(n) = f(n-1) + f(n-2)
(注: 留意下, 這里我們采用是數(shù)學(xué)位, ?即第一位為0, ?編程久的人喜歡稱為第0位 ^-^ )
現(xiàn)在, 我們想實(shí)現(xiàn)的是, 用Swift寫 斐波那契序列 方法, 并且我任意輸入第幾位數(shù)字, 會(huì)給我返回正確結(jié)果
且要保證運(yùn)算最少(這個(gè)重點(diǎn))
拆分下可以看出, 處理斐波 即重點(diǎn)處理 ??f(n) = f(n-1) + f(n-2), ?往下細(xì)分
f(n-1) = f(n-2) + f(n-3)
f(n-2) = f(n-3) + f(n-4)
f(n-3) = f(n-4) + f(n-5)
....
f(2) = 1
f(1) = 0
反復(fù)調(diào)用自身方法, 直到 n= 2, n=1, ?這樣可以寫出
因?yàn)檩斎氲亩际钦麛?shù), 所以用的UInt。 調(diào)用下這個(gè)方法
結(jié)果沒(méi)錯(cuò), 但我更關(guān)心是執(zhí)行多少次呢? ?增加些打印, ?再把輸入數(shù)字調(diào)小一些看看
這次輸入 5, 看下結(jié)果
調(diào)用了9次, ?輸入6調(diào)用15次 , 輸入7調(diào)用25次......(這個(gè)就不截圖了>_< ) ? 原因在于每次調(diào)用fib1()都需要遞歸調(diào)用fib1(n-1) 和 fib1(n-2)直至 fib1(1)和fib1(2), ? 即每次對(duì)fib1()調(diào)用都會(huì)額外增加兩次fib1()調(diào)用,?如果計(jì)算個(gè)大點(diǎn)的數(shù)豈不就完蛋了 !??
雖然寫出了斐波那契數(shù)列方法, ?但這只是機(jī)械式翻譯, 顯然不是一個(gè)合格程序員該選擇的, 所以我們要簡(jiǎn)化斐波那契數(shù)列方法。
這里就要用到容器來(lái)儲(chǔ)存之前計(jì)算結(jié)果, ?減少重復(fù)計(jì)算, 就像人腦一樣, 記憶了第5位為3, 第6位為5, 很容易計(jì)算出第7位為8, ?第8位為13
那么定義三個(gè)容器 ?a = f(n - 2); b = f(n - 1); c; ?增加1位則令 c = a + b, a = b, b = c, 此時(shí)b就是輸出的值, 再增加就是重復(fù)之前操作即循環(huán), ?為了增加可讀性, 我這里分別用 last, next, add 代表a, b, c ? 那么可以寫出
還是輸入8, 我們看下
方法調(diào)用只有6次, 輸入9用7次, 這樣就寫出簡(jiǎn)化的斐波那契數(shù)列
當(dāng)然還有更優(yōu)的方法 ^_^, ?for循環(huán)主體使用元組, 增加代碼間接性
