python實現斐波拉契數列

Corwien 發布于2019-07-30 16:02 / 1061人閱讀

摘要：描述斐波那契數列由列昂納多斐波那契以兔子繁殖為例子而引入，故又稱為兔子數列。這個數列從第項開始，每一項都等于前兩項之和。遞歸版本遞歸版本使用傳參及默認參數，減少冗余元算的同時也減少了函數調用。

描述

斐波那契數列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
由列昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數列”。

這個數列從第3項開始，每一項都等于前兩項之和。
如果設F(n）為該數列的第n項（n∈N*），那么這句話可以寫成如下形式：:F(n)=F(n-1)+F(n-2)

遞歸版本

通過這個公式，容易想到第一個遞歸版本

    def f(n):
        """遞歸版本 1"""
        return 1 if n <= 2 else f(n - 1) + f(n - 2)

遞歸版本 1 簡單明了，但是存在很多冗余運算，導致運行效果堪憂。

    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 通過字典避免了冗余元算，但是存在大量函數調用的開銷。

    def f(n, a=1, b=1):
        """遞歸版本 3"""
        return a if n <= 1 else f(n - 1, b, a + b)

遞歸版本 3 使用傳參及默認參數，減少冗余元算的同時也減少了函數調用。

迭代版本

有遞歸版本，怎么少的了迭代版本

    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 通過一個列表存儲了每次運算的結果，也很直觀

    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 類似，使用字典而不是列表存儲，占用空間更大

    def f(n):
        """迭代版本 3"""
        a, b = 1, 1
        for _ in range(n - 2):
            a, b = b, a + b
        return b

迭代版本 3 較前面2個迭代版本，通過交換技巧，節省了空間，效率有了提升

公式版本

這個數列有通項公式，所以還可以來個公式版本

    def f(n):
        """公式版本"""
        sqf = math.sqrt(5)
        return int(sqf / 5 * (math.pow(((1 + sqf) / 2), n) - math.pow(((1 - sqf) / 2), n)))

提示

python遞歸版本重新設置遞歸層數限制

import sys
sys.setrecursionlimit(1000000)

公式版本n較大時會引發溢出

OverflowError: math range error

總結

又想了個遞歸版本，利用了python中一個令人詬病的寫法（可變類型作為默認參數）提升效率

    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 時，千次執行時間（s）

云服務器 GPU云服務器斐波拉契 java中斐波拉契非波拉契斐波納契

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/41444.html

JS數據結構與算法_樹

摘要：上一篇數據結構與算法集合字典一遞歸學習樹離不開遞歸。先序遍歷的一種應用是打印一個結構化的文檔下面的圖描繪了先序遍歷方法的訪問路徑后序遍歷后序遍歷則是先訪問節點的后代節點，再訪問節點本身。上一篇：JS數據結構與算法_集合&字典一、遞歸學習樹離不開遞歸。 1.1 介紹遞歸是一種解決問題的方法，它解決問題的各個小部分，直到解決最初的大問題。遞歸通常涉及函數調用自身。通俗的解釋：年級...

tabalt 2019-08-26 13:35 評論0 收藏0
算法記錄 >> 斐波那契數列

摘要：今天去面試筆試題斐波那契數列實現，雖然很簡單。回來想想既然算法這么重要那就從這個開始來記錄自己的算法庫吧。在數學上，斐波納契數列以如下被以遞歸的方法定義，，。斐波拉契算法規律很簡單，，觀察下數列值就很容易總結出來了。一、寫在前面算法這塊對于大多數程序員（包括我）來說可能都是一個薄弱的地方，如何彌補尼？每個人都知道那就是學習、特別是算法沒有任何捷徑可走。在這記錄平時自己工作和生...

robin 2019-08-16 17:52 評論0 收藏0
使用JavaScript ES6的新特性計算Fibonacci（非波拉契數列）

摘要：采用的生成非波拉契數列提供了原生的支持，語法非常有特色，關鍵字后面緊跟一個星號。的詳細介紹參考官網先看如何用這個黑科技重新實現非波拉契樹立的生成。在這個內部，我們定義了一個無限循環，用于計算非波拉契數列。程序員面試系列 Java面試系列-webapp文件夾和WebContent文件夾的區別？程序員面試系列：Spring MVC能響應HTTP請求的原因？ Java程序員面試系列-什么...

yanbingyun1990 2019-08-23 12:29 評論0 收藏0
RxJS API解析（四）

摘要：任何程序設計語言在講解遞歸特性時，基本都會舉漢諾塔斐波拉契數列的例子。沒錯，請你對比一下斐波拉契數列和定義的相似之處遞歸完成后產生值的過程就是的過程。 Rx*(Observable.combineLatest)方法方法定義 Rx.Observable.combineLatest(...args, [resultSelector]) 作用通過處理函數總是將指定的可觀察對象序列中最新發...

cheng10 2019-08-19 17:28 評論0 收藏0
太原面經分享：如何用js實現返回斐波那契數列的第n個值的函數

摘要：那其實這個問題還可以換個問法實現一個函數，輸入一個數字能返回斐波那契數列的第個值。文章預告更多的前端面試分享我都會第一時間更新在我的公眾號閏土大叔里面，歡迎關注面試攢經驗，lets go！值此高考來臨之際，閑不住的我又雙叒叕出發去面試攢經驗了，去了公司交待一番流程后，面試官甩給了我一張A4紙，上面寫著一道js算法筆試題（一開始我并不知道這是在考察js算法），上面寫著1、1、2、3、...

Galence 2019-08-26 12:01 評論0 收藏0