Day11 | Rosalind 生資解題 - 004. FIB（Rabbits and Recurrence Relations）+斐波那契數列遞迴

題目連結：https://rosalind.info/problems/fib/

這題稍稍有點複雜、讓人看不懂
因為題目敘述同時提到了「費氏數列」、「繁殖模型」

但是費氏數列的觀點，在這題可以不要用到，只需要以直觀的概念思考即可

首先來看題目

輸入

5 3

輸出

19

啥鬼！？？

為何這兩個數字湊在一起會冒出19？
不可能呀，根本八竿子打不著

哦，原來是
輸入的5是回合數，每一對成熟兔每回合能夠生出3對小兔子
在最初的第一個月只有一對小兔子，一個月後，他們會長大成熟（便有繁殖能力）
並且不用考慮兔子公母、奇偶數量的問題（都是以“一對”來做計算）

迭代解法（較直觀）：

n, k = 5, 3  # n:回合數、k:每次繁衍數
R, r = 0, 1  # R: 成熟兔數量、r: 初生兔數量

for i in range(n - 1):  # 初始狀態已經是第1個月，所以n-1
    new_born = R * k  # 上一輪的成熟兔生小孩了
    R += r  # 上一輪的初生兔子成熟了
    r = new_born

print(R + r)

更精簡的版本（費波那契風格迭代）

def rabbit_population(n, k):
    R, r = 0, 1  # R: 成熟兔數量、r: 初生兔數量

    for _ in range(1, n):
        R, r = r, r + k * R
    return r

print(rabbit_population(5, 3))

費氏數列

F(n) = F(n-1) + F(n-2)
vs
F(n) = F(n-1) + k * F(n-2)

遞迴(recursive)解法：

def rabbit_population(n, k):
    if n == 1 or n == 2:  # 尚未繁殖，前兩個月都只有一對兔子
        return 1

    # 第n個月兔總數 = 前一個月的兔總數 ＋ 新出生的
    # 新出生的：前一個月成熟兔*k => 前一個月成熟兔數量怎麼計算？就是前兩個月兔總數
    return rabbit_population(n - 1, k) + rabbit_population(n - 2, k) * k

print(rabbit_population(5, 3))

遞迴解法，既不直觀、執行速度又慢
但是在“概念表達”上非常清晰
站在「自我複製」這點的立場就很容易明白，以每個個體的功能角度來思考

BTW，此題目敘述會讓人誤會的地方：

1. 沒有明確提到幾個月才變成成熟的兔子、具有繁衍能力
2. 以「兔子交配」為例反而摻雜過多的資訊：
   究竟是一對才能生 or 一隻就能繁衍？
   若給定「奇數隻」，父母是否需要-1來取偶數？
   是不是要一公一母？

如果換作我出題，我的思路如下：

1. 排除掉異性因素，以「細菌」為例：

只需要複製自己就能繁殖

以細菌為例看似合理恰當，可是在「k分裂法」會有問題
因為 細菌or細胞 雖是無性繁殖，但只存在「二分裂法」
題目就需要額外說明這是「特異的菌」，每次可以複製k組DNA...

2. 排除掉「二分裂法」的因素

2-1 以「樹枝冒出枝枒」為例：

一個枝幹，每個月會長出k個新枝枒
每個新枝枒在一個月後會成熟、變成枝幹，每個月分出k個新枝枒

但是不適合的點在於：
普遍會認為樹狀結構是「一次性分支」，樹枝長一次就固定了
要想像成每月長新枝枒，會不直觀
甚至想到那個畫面有點會噁心（老舊枝幹還一直冒出新枝枒...已經長出祖宗180代了）

2-2 若以「病毒複製」為例：

病毒在宿主細胞內複製
一個病毒感染了宿主細胞，經過一輪後，能從細胞中爆出k個新病毒

但通常爆完之後，就沒辦法再爆第二次了
（若細胞能再爆第二次、第三次，那畫面也非常噁心...）
似乎與上樹「樹枝枝枒」的模式相同

2-3 若以「病毒擴散」為例：

社會式的傳播
一個感染者經過潛伏期後，每輪會傳染k個新的人，並持續傳染下去
對於新感染者，在潛伏期後，也開始每輪傳染k個人。

每個感染者都能提供「持續的影響力」
病毒擴散模型，似乎是至今最恰當、最貼切的比喻

3. 遊戲化版本：「黏土分身」

一個魔法黏土人，在成形後可以每回合捏出k個新分身
每個新分身需要1回合凝固成行，之後就能繼續分裂

直接創造一個全新的概念
規則清楚的遊戲模型，不受生物學真實限制
看起來也更有趣