資訊專欄INFORMATION COLUMN
摘要：描述斐波那契數(shù)列由列昂納多斐波那契以兔子繁殖為例子而引入，故又稱為兔子數(shù)列。這個(gè)數(shù)列從第項(xiàng)開始，每一項(xiàng)都等于前兩項(xiàng)之和。遞歸版本遞歸版本使用傳參及默認(rèn)參數(shù)，減少冗余元算的同時(shí)也減少了函數(shù)調(diào)用。
描述
斐波那契數(shù)列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
由列昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”。
這個(gè)數(shù)列從第3項(xiàng)開始，每一項(xiàng)都等于前兩項(xiàng)之和。
如果設(shè)F(n）為該數(shù)列的第n項(xiàng)（n∈N*），那么這句話可以寫成如下形式：:F(n)=F(n-1)+F(n-2)
通過這個(gè)公式，容易想到第一個(gè)遞歸版本
def f(n):
"""遞歸版本 1"""
return 1 if n <= 2 else f(n - 1) + f(n - 2)
遞歸版本 1 簡(jiǎn)單明了，但是存在很多冗余運(yùn)算，導(dǎo)致運(yùn)行效果堪憂。
def f(n):
"""遞歸版本 2"""
cache = {1: 1, 2: 1}
s = lambda n: cache.get(n) or cache.setdefault(n, s(n - 1) + s(n - 2))
return s(n)
遞歸版本 2 通過字典避免了冗余元算，但是存在大量函數(shù)調(diào)用的開銷。
def f(n, a=1, b=1):
"""遞歸版本 3"""
return a if n <= 1 else f(n - 1, b, a + b)
遞歸版本 3 使用傳參及默認(rèn)參數(shù)，減少冗余元算的同時(shí)也減少了函數(shù)調(diào)用。
迭代版本有遞歸版本，怎么少的了迭代版本
def f(n):
"""迭代版本 1"""
lst = [1, 1]
for i in range(2, n):
lst.append(lst[i - 2] + lst[i - 1])
return lst[-1]
迭代版本 1 通過一個(gè)列表存儲(chǔ)了每次運(yùn)算的結(jié)果，也很直觀
def f(n):
"""迭代版本 2"""
dct = {1: 1, 2: 1}
for i in range(3, n + 1):
dct[i] = dct[i - 1] + dct[i - 2]
return dct[n]
迭代版本 2 和迭代版本 1 類似，使用字典而不是列表存儲(chǔ)，占用空間更大
def f(n):
"""迭代版本 3"""
a, b = 1, 1
for _ in range(n - 2):
a, b = b, a + b
return b
迭代版本 3 較前面2個(gè)迭代版本，通過交換技巧，節(jié)省了空間，效率有了提升
公式版本這個(gè)數(shù)列有通項(xiàng)公式，所以還可以來個(gè)公式版本
def f(n):
"""公式版本"""
sqf = math.sqrt(5)
return int(sqf / 5 * (math.pow(((1 + sqf) / 2), n) - math.pow(((1 - sqf) / 2), n)))
提示
python遞歸版本重新設(shè)置遞歸層數(shù)限制
import sys sys.setrecursionlimit(1000000)
公式版本n較大時(shí)會(huì)引發(fā)溢出
OverflowError: math range error總結(jié)
又想了個(gè)遞歸版本，利用了python中一個(gè)令人詬病的寫法（可變類型作為默認(rèn)參數(shù)）提升效率
def f(n, cache={1: 1, 2: 1}):
"""遞歸版本完全體"""
return cache.get(n) or cache.setdefault(n, f(n - 2, cache) + f(n - 1, cache))
n=1000 時(shí)，千次執(zhí)行時(shí)間（s）
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/41444.html
摘要：上一篇數(shù)據(jù)結(jié)構(gòu)與算法集合字典一遞歸學(xué)習(xí)樹離不開遞歸。先序遍歷的一種應(yīng)用是打印一個(gè)結(jié)構(gòu)化的文檔下面的圖描繪了先序遍歷方法的訪問路徑后序遍歷后序遍歷則是先訪問節(jié)點(diǎn)的后代節(jié)點(diǎn)，再訪問節(jié)點(diǎn)本身。 上一篇：JS數(shù)據(jù)結(jié)構(gòu)與算法_集合&字典 一、遞歸 學(xué)習(xí)樹離不開遞歸。 1.1 介紹 遞歸是一種解決問題的方法，它解決問題的各個(gè)小部分，直到解決最初的大問題。遞歸通常涉及函數(shù)調(diào)用自身。 通俗的解釋：年級(jí)...
摘要：今天去面試筆試題斐波那契數(shù)列實(shí)現(xiàn)，雖然很簡(jiǎn)單?；貋硐胂爰热凰惴ㄟ@么重要那就從這個(gè)開始來記錄自己的算法庫吧。在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞歸的方法定義，，。斐波拉契算法規(guī)律很簡(jiǎn)單，，觀察下數(shù)列值就很容易總結(jié)出來了。 一、寫在前面 算法這塊對(duì)于大多數(shù)程序員（包括我）來說可能都是一個(gè)薄弱的地方，如何彌補(bǔ)尼？ 每個(gè)人都知道那就是學(xué)習(xí)、特別是算法沒有任何捷徑可走。 在這記錄平時(shí)自己工作和生...
摘要：采用的生成非波拉契數(shù)列提供了原生的支持，語法非常有特色，關(guān)鍵字后面緊跟一個(gè)星號(hào)。的詳細(xì)介紹參考官網(wǎng)先看如何用這個(gè)黑科技重新實(shí)現(xiàn)非波拉契樹立的生成。在這個(gè)內(nèi)部，我們定義了一個(gè)無限循環(huán)，用于計(jì)算非波拉契數(shù)列。 程序員面試系列 Java面試系列-webapp文件夾和WebContent文件夾的區(qū)別？ 程序員面試系列：Spring MVC能響應(yīng)HTTP請(qǐng)求的原因？ Java程序員面試系列-什么...
摘要：任何程序設(shè)計(jì)語言在講解遞歸特性時(shí)，基本都會(huì)舉漢諾塔斐波拉契數(shù)列的例子。沒錯(cuò)，請(qǐng)你對(duì)比一下斐波拉契數(shù)列和定義的相似之處遞歸完成后產(chǎn)生值的過程就是的過程。 Rx*(Observable.combineLatest)方法 方法定義 Rx.Observable.combineLatest(...args, [resultSelector]) 作用 通過處理函數(shù)總是將指定的可觀察對(duì)象序列中最新發(fā)...
摘要：那其實(shí)這個(gè)問題還可以換個(gè)問法實(shí)現(xiàn)一個(gè)函數(shù)，輸入一個(gè)數(shù)字能返回斐波那契數(shù)列的第個(gè)值。文章預(yù)告更多的前端面試分享我都會(huì)第一時(shí)間更新在我的公眾號(hào)閏土大叔里面，歡迎關(guān)注 面試攢經(jīng)驗(yàn)，lets go！ 值此高考來臨之際，閑不住的我又雙叒叕出發(fā)去面試攢經(jīng)驗(yàn)了，去了公司交待一番流程后，面試官甩給了我一張A4紙，上面寫著一道js算法筆試題（一開始我并不知道這是在考察js算法），上面寫著1、1、2、3、...
閱讀 2594·2023-04-25 18:13
閱讀 827·2021-11-22 12:10
閱讀 3005·2021-11-22 11:57
閱讀 2163·2021-11-19 11:26
閱讀 2202·2021-09-22 15:40
閱讀 1486·2021-09-03 10:28
閱讀 2726·2019-08-30 15:53
閱讀 1974·2019-08-30 15:44
