!Ubuntu-20.04.1 !ruby-2.7.1p83
これは講義用のまとめサイトです。見た人は是非LGTMを押しといてください。
やったこと
- 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