トップ > Ruby > フィボナッチ数列を Ruby で

フィボナッチ数列を 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）
配列すらも使わずにできますね。（2017/6/13 修正）

a, b = 1, 1
while a < 10000000
  print "#{a} "
  a, b = b, a + b
end
puts

　

※再追記（2018/2/1）
関数型プログラミングっぽく。

fib = ->(n) {
  fib_iter = ->(a, b, count) {
    count.zero? ? b : fib_iter.(a + b, a, count - 1)
  }
  fib_iter.(1, 0, n)
}

p fib.(100)    #=>354224848179261915075

あるいは

fib = ->(n) {
  fib_iter = ->(ar, a, b, count) {
    count.zero? ? ar : fib_iter.(ar + [a], a + b, a, count - 1)
  }
  fib_iter.([], 1, 0, n)
}

p fib.(10)    #=>[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

　

※再々追記（2018/10/3）
無限リストを使って。

def fib
  Enumerator.new do |y|
    a, b = 0, 1
    loop do
      a, b = b, a + b
      y << a
    end
  end
end

p fib.take(100)

　

※再々々追記（2020/3/13）
Ruby 2.7 から入った Enumerator.produce を使って。

fib = Enumerator.produce([0, 1]) {|a, b| [b, a + b]}

p fib.take(10).map(&:last)

　

※再々々々追記（2020/12/4）
ここの記事を参考に。

module Fib
  extend Enumerable

  def self.each(size = Float::INFINITY)
    unless block_given?
      return to_enum(:each, size)
    end

    a, b = 0, 1
    1.step(size) do
      yield a
      a, b = b, a + b
    end
  end
  
  def self.[](n)
    lazy.drop(n).first
  end
end


Fib.each(10) {|x| puts x}

p Fib.each(10).to_a
p Fib.to_a(10)
#=>[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

p Fib[50]    #=>12586269025

require "prime"
p Fib.lazy.select(&:prime?).first(10)
#=>[2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437]

これはFib.eachの使い方が凝っていますね。参考にしました。