斐波那契數列

我想每個人都會寫斐波那契數列吧！！

斐波那契數列的定義

f(0) = 1,f(1) = 1,f(n) = f(n-1) + f(n-2)

基于遞歸的方式實現，講到遞歸都會用到：

def fib_sequence(n):def fib_rec(n):if n == 0 or n ==1:return nreturn fib_rec(n-1) + fib_rec(n-2)list = []for i in range(n):list += [fib_rec(i)]return list

斐波那契數列也是動態規劃的常用范例，這個例子相當于直接告訴你了遞推公式，子問題已經幫助你分解了。但是遞歸調用，出現了多個子問題重復，我們需要想辦法優化，如何優化遞歸了？比較常用的基于遞歸，我們記錄子問題的結果，假如調用到重復子問題就直接引用以計算的結果，這個就是備忘模型，因為還是基于遞歸，所以是自頂向下設計的：

def fib_top_down_(n):list = [-1]*(n)list[0] = 0list[1] = 1def fib_top_down(n):if list[n] == -1:list[n] = fib_top_down(n-1)+fib_top_down(n-2)return list[n]fib_top_down(n-1)return list

自頂向下設計，出現了多個子問題重復，我們需要想辦法優化，還有一種可以優化的辦法：遍歷計算每一下子問題，從最小的子問題開始計算，這樣就可以避免重復計算，這就是我們一般使用的迭代的方法，所以是基于自底向上推理的，又叫演繹模型：

#%% def fib_botton_up_(n):list = [0,1]for i in range(2,n):list.append(list[i-1] + list[i-2])return list

運行結果：

#%% print fib_sequence(20) #%% print fib_top_down_(20) #%% print fib_botton_up_(20)runfile('/root/test/dynamic_program.py', wdir='/root/test') [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

總結

以上是生活随笔為你收集整理的动态规划：斐波那契数列里面的东西？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。