Fibonacci Sequence

Mathematica

今日は実家から通学したため午前中に学校に着けた。でも遠いから時間かかるなぁ。で、午前中は卒研にお邪魔して、お昼を先生達と食べた。その後しばらくは寝てたが、研究を再開して成果が得られた。

フィボナッチ数列は F[1] = 1 , F[2] = 1 , F[n] = F[n-1] + F[n-2] で定義される。Mathematicaでそのまま定義すると

F[1] = 1; F[2] = 1;
F[n_] := F[n - 1] + F[n - 2]

となり、これを実行すると

F[10]
34

のように出力される。これでも良いと言えば良いのだが、nを大きくすると劇的に遅くなってしまう。そこでフィボナッチ数列を得るのにもっと効率の良いルーチンを実装する事に成功した。

Fiboseq[n_] :=
    Module[{Fibo = {1, 1}}, Do[Fibo = Append[Fibo, Fibo[[i - 1]] + 
    Fibo[[i - 2]]], {i, 3, n}]; Fibo[[n]]]

これは漸化式を使った定義とは比較にならない位早い。前者ではn=30程度でも十数秒かかったが、後者ではn=1000でも数秒以内に、n=10000でも1分以内に計算できた。