2008-09-14

Rでフィボナッチ数！

Rでフィボナッチ数を計算する関数を書いて遊んでみました。

フィボナッチ数

n番目のフィボナッチ数をで表すと、

と定義されます。一般項がひとつ前の項とさらにひとつ前の項の和になっています。
この漸化式で表わされる数列をフィボナッチ数列といい、最初の数項は以下のようになります。

書いてみた

とりあえずRの練習がしたかったので、試しにRを使ってフィボナッチを計算する関数を定義してみました。

漸化式の定義通りに再帰呼び出しを使って書いてみた結果がこれだよ。

fib <- function(n){
  if (n == 0) { return(0) }
  if (n == 1) { return(1) }
  fib(n-1) + fib(n-2)
}

うん、全然Rの練習にならなかった。
今すぐにC言語に落とせそうなコードですね。笑

2008-09-14

syou6162先生が一行でやってくれました

昨晩TwitterでRとフィボナッチ数のことをぼやいていたら、id:syou6162先生が「一行で書けるよ」的なことを仰っていたので、早速例を見せてくれるようにお願いしました。
そして見せてもらった結果がこれだよ。

(function(n){ifelse(n>1,Recall(n-1)+Recall(n-2),ifelse(n==1,1,0))})(1:10)

おお、何かよく分からないけど一行カッコイイ！流石id:syou6162先生！！

さっそく実行してみました。

> (function(n){ifelse(n>1,Recall(n-1)+Recall(n-2),ifelse(n==1,1,0))})(1:10)
 [1]  1  1  2  3  5  8 13 21 34 55

ちゃんとフィボナッチ数列のからまでの値が返ってきました。

最初に見た時はRecall()がどういう関数なのか分からなかったのですが、Rのヘルプによると現在定義している関数を再帰呼び出し(recall)する関数だそうです。
なるほど、無名関数で再起を行う場合はRecall()を使えばいいのですね。メモメモ。

ちなみにRecall()のヘルプはRで以下のようにすれば見ることができます。

?Recall

2008-09-14

Rでフィボナッチ数！(動的計画法版)

計算量爆発しろ(違

先ほどのfib(n)は、nの値が大きくなると計算量が指数関数的に爆発してしまいます。

例えばfib(5)を実行すると、以下のように展開して計算されます。

   fib(5)
-> fib(4) + fib(3)
-> fib(3) + fib(2) + fib(2) + fib(1)
-> fib(2) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + 1
-> fib(1) + fib(0) + 1 + 1 + 0 + 1 + 0 + 1
-> 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1
-> 5

展開中にfib(0)〜fib(3)を何度も呼び出しているのが分かると思います。
fib(1)なんかはトータルで5回も計算しています。
また、fib(6)を計算しようとすると、上記のfib(5)とfib(4)が呼び出され、さらに関数呼び出しの回数が増えてしまいます。

fib(30)とか計算しようとすると時間がかかりすぎて固まります。

動的計画法を使ってみた

というわけで、計算量を抑えた動的計画法版のfib(n)も定義してみました。
書いてみた結果がこれだよ。

fib <- function(n){
  if (n == 0) { return(0) }
  x <- numeric(max(n,2))
  x[1] <- x[2] <- 1
  m <- 3
  while (m <= n){
    x[m] <- x[m-1] + x[m-2]
    m <- m + 1
  }
  x[n]
}