所屬專題:[組合數學](README.md);[動態規劃](README.md)
 
## 問題
在著名的“斐波那契兔子”問題中,有如下的假定:
1. 兔子種群在第一個月從一對新生的兔子開始;
2. 兔子們在出生一個月后達到生育年齡;
3. 在任何一個月,每一只育齡兔子會與另一只育齡兔子交配;
4. 兔子交配后一個月,會生下一對兔子(一只雄兔與一只雌兔);
5. 不考慮兔子壽命限制,兔子會一直繁殖下去。
在這里,我們對“斐波那契兔子”問題進行推廣,每對兔子交配后一個月,將產下`$ k $`對兔子,求解若干個月后的兔子總對數。
**輸入:** 兩個正整數`$ n\le40 $`與`$ k\le5 $`。
**輸出:** 第`$ n $`個月時兔子的總對數。假定我們從1對兔子開始,在每一代,一對兔子會生下`$ k $`對兔子(而不是原始“斐波那契兔子”問題中的1對)。
**樣例數據:**
```
5 3
```
**樣例輸出:**
```
19
```
 
## 背景知識
這個問題來源于歷史上著名的數學問題“斐波那契兔子”問題。在原問題的設定中,兔子數量隨時間(代際)發展的變化如下圖所示:(圖片來源:[ROSALIND](http://rosalind.info/media/problems/fib/))
*****
<div align="center"><img src="http://rosalind.info/media/problems/fib/rabbit_tree.thumb.png"></div>
<div align="center">斐波那契兔子數量在前六個月的增長圖示</div>
*****
斐波那契兔子問題還涉及遞推數列等數學問題。詳情請查閱ROSALIND網站上[關于該問題的背景說明](http://rosalind.info/problems/fib/)。
 
## 解答
```
def fib_new(n, k):
"""給定兔子代數n與單次繁殖數k,遵循斐波那契規則,計算n代兔子的總數"""
num = [0, 1, 1]
for i in range(3, n+1):
num.append(k*num[i-2]+num[i-1])
return num[n]
## --main--
with open("rosalind_fib.txt", 'r') as f1:
n,k = map(int, f1.read().split())
with open("rosalind_fib_out.txt", 'w') as f2:
f2.write(str(fib_new(n, k)))
```