【原創首發】跟著小灰學Python-遞推演算法

語言: CN / TW / HK

本文已參與「新人創作禮」活動,一起開啟掘金創作之路。 宣告:版權歸本人所有,違者必究。 轉載請註明來源 https://juejin.cn/post/7111942157082034212 1.1. 遞推演算法

1.1.1. 演算法定義

遞推演算法是一種簡單的演算法,即通過已知條件,利用特定關係得出中間推論,直至得到結果的演算法。

1.1.2. 基本思想

遞推演算法分為順推和逆推兩種,順推法是從已知條件出發,逐步推算出要解決的問題;逆推法從已知問題的結果出發,用迭代表達式逐步推算出問題的開始的條件,即順推法的逆過程。

1.1.3. 程式碼實現-兔子繁殖

問題描述:

兔子三個月起每個月生一隻小兔子,小兔子長到三個月後每個月有生一直兔子,假如兔子都不死,那麼第一個月從一隻小兔子到N個月後,問兔子的總數為多少?

演算法分析:

得每個月到兔子數量數列:

``` 1 (1)=1 1 (2)=1 1 1 (3)=2 1 1 1 (4)=3 1 1 1 1 1 (5)=5 1 1 1 1 1 1 1 1 1 (6)=8 ………… (N)=?

以上可知,為典型的斐波那契數列,即 f(n)=f(n-1)+f(n-2) n>2 f(n)=1 n<=2 ```

程式碼實現:

【例1-1】 兔子繁殖:

```python def fib(n):     if n<=2:         return 1     else:         return fib(n-1)+fib(n-2)

if name == 'main': n = 30     print("%d月後兔子的數量為:%d"%(n, fib(n))) ```

執行結果:

30月後兔子的數量為:832040