More than 3 years have passed since last update.

フィボナッチ数列

Last updated at 2020-12-22Posted at 2020-12-22

今回の問題

再帰を用いてフィボナッチ数列を求める．

はじめに

p fib(0)

を実行するが，当然エラーが表示される．そのため，定義する．

def fib(n)
  if n==0
    return 0
  end
end

これで，fib(0)に対して０が返される．

require './assert_equal'
puts assert_equal(0, fib(0))

前回作成したassert_equal.rbで確認をする．成功すれば”succeeded in assert_equal”が表示される．

次にfib(1)を求める．先ほどのfib(n)にはnが0のときのみ0が返されるため，n=1のときにも返されるように変更しなければならない．

def fib(n)
  if n==0
    return 0
  end
  if n==1
    return 1
  end
end

とすれば，よい．以下は配列を用いることで重複を避けていく．


[[0,0],[1,1]].each do |pair|
  puts assert_equal(pair[1], fib(pair[0]))
end

[配列].each do |pair|を使うことで代入を複数行追加することなく，配列の要素の追加のみで済む．もう少し，理解しやすいように書き換えると

require './assert_equal'
[[0,0],[1,1]].each do |index, expected|
  puts assert_equal(expected, fib(index))
end

こうすることで直感的に理解できる．このままfib(2),fib(3),…….fib(n)と配列の要素を増やした際に対応できるようにコードを変更する．

def fib(n)
  return 0  if n==0
  return 1  if n<=2
  return fib(2) + fib(1)
end