モータルフィボナッチ数列の実装

フィボナッチ数列は前の数二つを足した数が次の数になるというシンプルな数列ですが、調べてみるとどうやら「うさぎの増え方」もこの数列に従っているらしいです。

以下に示すように、フィボナッチ数列は再帰関数を使うことで簡単に作ることができます。

今回はフィボナッチ数列の中でも、うさぎの寿命に着目して考えてみたいと思います。

例えば、１ヶ月に１世代増えるうさぎのペアが最初オスメス一匹ずついたとします。

この時のうさぎの寿命を３ヶ月すると、６ヶ月後には最初の方のうさぎが子孫繁栄の使命を全うして死んでいるので、合計4匹と言うことになります。

これをうまく実装していきます。

初めに、基本となる数列を定義しておきます。

def fibo(n):
    if n < 2:
        return n
    return fibo_recursive(n-1) + fibo_recursive(n-2)

これで、寿命を無視した任意のnヶ月目のうさぎの総数を求めることができるようになりました。

ついでに、増え方を可視化してみたいと思います。

from matplotlib import pyplot as plt
fig = plt.figure()
x = [i+900 for i in range(100)]
y = [fibo(i) for i in x]
plt.scatter(x,y)
fig.savefig('a.jpg')

なんか1000付近で急に増えてってますね。

上記で作成した関数を使用して、寿命を考慮していきます。

def mortal_fibo(n,m):
    f = Decimal(str(fibo(n)))
    for i in range(n-m):
        f -= Decimal(str(fibo(i+1)))
    return f 

第一引数にヶ月を、第二引数に寿命（月）を入れてあげると、nヶ月立った時に存在しているうさぎの総数を求めることができます。

誤差について

pythonはメモリが許す限り実質無限桁の整数を扱うことができますが、二進数で計算するため、処理時はfloat型として扱われます。

このせいで、数が大きくなるにつれて正確な値ではなくなっていきます。

これでは頼りにならないので、Decimalモジュールを使って応急処置をしているつもりです。