お題:Fibonacci数列
fib(n) = fib(n-1)+fib(n-2)
0 1 1 2 3 5 8 13 21 ...
をrecursion(再帰)で求めなさい．
解説
fib(0) = 0
Fibonacci数列の初項は0
def fib(n)
if n==0
return 0
end
end
前回作成したassert_equal.rbで出力が期待値と一致しているかを確認.
require './assert_equal'
puts assert_equal(0, fib(0))
結果
expected :: 0
result :: 0
succeeded in assert_equal
fib(1) =1
次はfib(1)=1.まずはassertion
puts assert_equal(1, fib(1))
もちろん失敗するので書き換える.
def fib(n)
if n==0
return 0
end
if n==1
return 1
end
end
結果
expected :: 0
result :: 0
succeeded in assert_equal
expected :: 1
result :: 1
succeeded in assert_equal
これでOK.
テスト側の重複が気になってきたので，配列に
[[0,0],[1,1]].each do |pair|
puts assert_equal(pair[0], fib(pair[1]))
end
結果は同じ
fib(2) = fib(1) + fib(0) = 1
まずはテスト
[[0,0],[1,1],[2,1]].each do |pair|
これではダメ.
> ruby fibonacci.rb
expeced:0
result :0
succeeded in assert_equal
expeced:1
result :1
succeeded in assert_equal
expeced:2
result :1
failed in assert_equal
条件分岐をもう少しいじって，
def fib(n)
if n==0
return 0
end
if n<=2
return 1
end
end
これでいけると思うので実行.
> ruby fibonacci.rb
expeced :: 0
result :: 0
succeeded in assert_equal
expeced :: 1
result :: 1
succeeded in assert_equal
expeced :: 2
result :: 1
failed in assert_equal
あれ?
実は，assert_equalは(expect, result)とうけとっているため配列変数pairの示数indexが逆.
require './assert_equal'
[[0,0],[1,1],[2,1]].each do |pair|
puts assert_equal(pair[1], fib(pair[0]))
end
が正解．
refactoring
もう少し配列の受け取りを明示的にすると，
index, expected = pair
と修正できて
require './assert_equal'
[[0,0],[1,1],[2,1]].each do |index, expected|
puts assert_equal(expected, fib(index))
end
こっちのほうが分かりやすい.
refactoring
メソッドが長くなってきたので短く書き直す.
def fib(n)
return 0 if n==0
return 1 if n<=2
end
と2行に削減
fib(3) = 2 = fib(2) + fib(1)
テストは
[[0,0],[1,1],[2,1],[3,2]].each do |index, expected|
return 2になってほしいのでfib(2)+fib(1)にする.
def fib(n)
return 0 if n==0
return 1 if n<=2
return fib(2) + fib(1)
end
結果
> ruby fibonacci.rb
expeced :: 0
result :: 0
succeeded in assert_equal
expeced :: 1
result :: 1
succeeded in assert_equal
expeced :: 1
result :: 1
succeeded in assert_equal
expeced :: 2
result :: 2
succeeded in assert_equal
fib(4) = fib(3) + fib(2) = 2 + 1 = 3
次は4. 期待値は3
[[0,0],[1,1],[2,1],[3,2],[4,3]].each do |index, expected|
テスト結果は当然fail.最後のreturnを定義通りに
fib(n) = fib(n-1) + fib(n-2)
と修正
結果
> ruby fibonacci.rb
expeced :: 0
result :: 0
succeeded in assert_equal
expeced :: 1
result :: 1
succeeded in assert_equal
expeced :: 1
result :: 1
succeeded in assert_equal
expeced :: 2
result :: 2
succeeded in assert_equal
expeced :: 3
result :: 3
succeeded in assert_equal
全てsucceed
そのまま続きもやってみる.
[[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
結果
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
全部いけた.
ただ一つ抜けているのは，
fib(2) = fib(1) + fib(0) = 1 + 0
なんで，fibのなかの条件分岐はもう少し狭められて，
return 1 if n == 1
で十分
最終的に
require './assert_equal.rb'
def fib(n)
return 0 if n == 0
return 1 if n == 1
return fib(n-1)+fib(n-2)
end
[[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
- source ~/grad_members_20f/members/yoshida/c5_fibonacci.org