やったこと

Fibonacci数列

Fibonacci数列

お題

Fibonacci数列を求めるプログラムを作れ
例えば「0」を入力したら数列の初項の0が表示されてほしい

方針

単に

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[0], fib(pair[1]))
end

というように、いちいち条件を書いていくのはきりがない
そこで何を入力しようと勝手に計算してくれるようにすることを考える

実際にどうやるか

勝手に計算してくれるようにするのには初項(0番目)とその次の項だけはこちらで教えてあげないといけない
その次以降は、Fibonacci数列の定義によると、n番目の項は(n-1)番目+(n-2)番目ということなので、それをプログラムにしてやる。

def fib(n)
  if n==0
    return 0
  else if n==1
    return 1
  else
    return fib(n-1) + fib(n-2)
  end
end
p fib(6)

という感じになる。

refactoring

だけどこのままだとコードが長いので、もっとぎゅっとまとめましょうということで

def fib(n)
  return 0 if n==0
  return 1 if n==1
  return fib(n-1) + fib(n-2)
end
p fib(6)

となった。
これだけだと、n=6の時はfib(5)とfib(4)の結果を足すので、fib(5)とfib(4)は定義されてないので動かないはず

> 8

…ってあれ！？動くの！？なんで？試しにfib(30)とかにしてもちゃんと値が返ってきた
でもどこにも再帰的に処理するような記述はした覚えがないのでこれに関してはよく分かりません。誰か教えて
(12/17追記)
先生からのコメントで気づきました。よく考えたらfibに8を渡すと4行目に行ってfib(7)とfib(6)が呼び出され、fibに7,6が渡されるとfibの4行目に行って…とちゃんと再帰的に呼び出されてました
長時間PCの前に座ってると思考が凝り固まって簡単なことにも気づけなくなるのでいかんですな。適度に散歩でも行きましょう

テスト数を増やす

いくつもテストするならeach doを使いましょう。

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

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

で

> 0
> 1
> 1
> 8

と、一気に返ってきますね

assert_equalを使って本当にちゃんと計算で来てるか確認する

先週作ったassert_equalの機能を使い、9番目まで本当にちゃんと計算出来てるか確認する

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

require './assert_equal.rb'
[[0,0],[1,1],[2,1],[3,2],[4,3],
 [5,5],[6,8],[7,13],[8,21],[9,34],
].each do |index, expected|
  puts assert_equal(expected,fib(index))
end

indexとexpectedの組み合わせでできた配列をassert_equal関数に渡して判定してもらうというもの

["expected", 0]
["result", 0]
succeeded in assert_equal

["expected", 1]
["result", 1]
succeeded in assert_equal

["expected", 1]
["result", 1]
succeeded in assert_equal

["expected", 2]
["result", 2]
succeeded in assert_equal

["expected", 3]
["result", 3]
succeeded in assert_equal

["expected", 5]
["result", 5]
succeeded in assert_equal

["expected", 8]
["result", 8]
succeeded in assert_equal

["expected", 13]
["result", 13]
succeeded in assert_equal

["expected", 21]
["result", 21]
succeeded in assert_equal

["expected", 34]
["result", 34]
succeeded in assert_equal

オールクリア

参考記事

チャート式ruby-V(Recursive Fibonacci)

source ~/MasahiroOba/grad_members_20f/members/MasahiroOba/chapter10.org