読者です 読者をやめる 読者になる 読者になる

フィボナッチ数列を Ruby で

Ruby 数学

rscの日記さんのところに、カエルのジャンプの問題を解くというのがあったので、僕も Ruby でやってみました。

或る回答にもありますが、これは本質的にフィボナッチ数列の問題です。葉っぱが n 枚のときのカエルの渡り方を num(n) とすると、直前の葉っぱから進んでくるか(num(n-1))か、ひとつ葉っぱを飛ばしてジャンプしてくるか(num(n-2))ですから、漸化式
  num(n) = num(n-1) + num(n-2)
が成り立ちます。また葉っぱが 0 枚のときは単に飛び越えるだけですから、num(0) = 1。葉っぱが1枚のときは、葉っぱに乗って渡るかそれとも飛び越えるかのどちらかですから、num(1) = 2。これらを元に、漸化式を計算すればいいわけです。

コードはメソッド再帰の例になりますね。デフォルトは葉っぱが 8 枚になっています。
fibonacci.rb

def num(n)
  return $n_0 if n == 0
  return $n_1 if n == 1
  num(n-1) + num(n-2)
end

n = (ARGV[0] || 8).to_i
$n_0 = 1  #num(0)
$n_1 = 2  #num(1)
puts num(n)      #=>55

20 枚の場合は、こんな感じです。

>ruby fibonacci.rb 20
17711


極普通のフィボナッチ数列を求めるプログラムは、上のをちょっと変えて

def num(n)
  return 1 if n == 1
  return 1 if n == 2
  num(n-1) + num(n-2)
end

for i in 1..40
  print "#{num(i)} "
end

という感じでしょうか。実行すると

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657
46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465
14930352 24157817 39088169 63245986 102334155

となります。n = 40 くらいになると、かなり時間がかかります。

もちろん、再帰など使わなければすぐですね。普通に配列でやればいいわけです。これなら一瞬です。

num = []
num[1] = 1; num[2] = 1; print "1 1 "
for i in 3..40
  num[i] = num[i-1] + num[i-2]
  print "#{num[i]} "
end



※追記(2016/1/16)
配列すらも使わずにできますね。

a, b = 1, 1
print "1 1 "
for i in 3..40
  a, b = b, a + b
  print "#{b} "
end
puts