ROSALIND｜Rabbits and Recurrence Relations (FIB)

發表於

假設兔子需一個月性成熟，，性成熟後每對兔子每個月必繁殖 k 對子代，且不因任何因素死亡，則求 n 月後的兔子對數。

Given: Positive integers n≤40 and k≤5.

Return: The total number of rabbit pairs that will be present after n months, if we begin with 1 pair and in each generation, every pair of reproduction-age rabbits produces a litter of k rabbit pairs (instead of only 1 pair).

(https://rosalind.info/problems/fib/)

背景知識

  • Sequence: 數列為項目的集合
  • recurrence relation: 數列的後項可為前項所定義
  • Fibonacci sequence: 費氏數列乃首項與次項為 1 ，第 n 項為 n - 1 項及 n - 2 項之和的遞迴數列

解題觀念

除了透過歸納既有數列的歸納遞迴關係以外，亦可利用符號輔助思考思考。首先，令 $F_n$ 為第 n 個月的兔子數，$R_n$ 為第 n 個月成熟的兔子數，$r_n$ 為第 n 個月未成熟的兔子數。則
$$ F_n = R_n + r_n \tag{1}$$
是以第 n 個月成熟的兔子數可表示為
$$ R_n = R_{n−1} + r_{n−1} = F_{n-1} \tag{2}$$
又因每一世代可生產 $k$ 對兔子，所以第 n 個月未成熟的兔子數為
$$ r_n = k⋅R_{n−1} \tag{3}$$
結合式子 (1)、 (2) 及 (3) 可得
$$ Fn = R_{n−1} + r_{n−1} + k⋅R_{n−1} \tag{4}$$
由於
$$ R_{n−1} = F_{n−2} \tag{5}$$
$$ F_{n−1} = R_{n−1} + r_{n−1} \tag{6}$$
因此
$$ F_n = F_{n−1} + k⋅F_{n−2} \tag{7}$$

利用 python、R 或 bash 以遞迴方法求費氏數列的形式類似，只是要留意各自的 function 定義方法。

程式實作

Python 實作

1
2
3
4
5
def fib(n, k):
    if n <= 2:
        return 1
    else:
        return fib(n - 1, k) + fib(n - 2, k) * k

R 實作

1
2
3
4
5
6
7
fib <- function(n , k) {
  if (n <= 2) {
    return(1)
  } else {
    return(fib(n - 1, k) + fib(n - 2, k) * k)
  }
}

bash 實作

bash 的四則運算寫法可參考 Shell 設計入門：算術運算

1
2
3
4
5
6
7
8
9
10
fib () {
    n=$1
    k=$2
    if [[ $n -le 2 ]]
    then
         echo 1
    else
         echo $[$(fib $[n-1] $k) + $[$(fib $[n-2] $k) * $k]]
    fi
}

複雜度分析

雖然遞迴法的邏輯清晰，但以此法求費氏數列第 n 項的效率甚差。為了計算 $F_n$，得計算 $F_{n-1}$ 和 $F_{n-2}$，而求 $F_{n-1}$ 又需計算 $F_{n-2}$ 和 $F_{n-3}$，其中 $F_{n-2}$ 重複計算了兩次，而重複計算的次數又隨 n 值增加。簡言之，由於每項數列皆衍伸出額外兩項的計算，求解費氏數列的第 n 項需要近 2^n 步驟，所以時間複雜度為 O(2^n)。詳細解說可參考：初學者學演算法｜從費氏數列認識何謂遞迴

相較之下，使用迴圈可以 O(n) 求費氏數列第 n 項（下為 python 程式碼）

1
2
3
4
5
6
7
8
9
10
def FibLoop(n, k):
    s = [1, 1]
    i = 2
    while i < n:
        s.append(s[i - 1] + s[i - 2] * k)
        i += 1
    return s[n - 1]

print FibLoop(5, 3)