目次
このページではFibonacci数列をTDDの手順を踏んで作成する．今回は以下の順で説明する．
Fibonacci数列とは
Fibonacci数列とは
0 1 1 2 3 5 8 13 21 ...
という数列だ，これは一般的に，
fib(n) = fib(n-1) + fib(n-2)
と表すことができる．今回はこれを再帰を用いて表すプログラムを作成する．
今回の手法の説明
今回はテスト駆動開発(TDD)の手順，red, green, refactoringを意識して作成する．
red -> やりたいことをとりあえず書いてテストしてみてエラーを確認する
green -> エラーを削除してひとまず動くものを作成する
refactoring -> きれいに意味のあるコードにする
ということらしい．とりあえず動くものを作ってからコードをきれいにする方が効率がいいとかなんとか．
初項の作成
初項，第二項は一般的に表すことができないので先に作っておく．
Fibonacci数列の初項は0である．
red : fibというメソッドを作成しFibonacci数列を作成する．まずは以下のようにテスト．
p fib(0)
このように書いてテストをするが，何も書いていないため動くわけがない．
だがこれでいい．このエラーを取り除いていく．
また，前回作成したassert_equal.rbを呼び出しテストできる環境を用意しておく．
require './assert_equal'
puts assert_equal(0, fib(0))
green : 「n = 0 の場合は値が0である」ことを表すメソッドを作成する
require './assert_equal'
def fib(n)
if n == 0
return 0
end
end
puts assert_equal(0, fib(0))
こうすることでひとまず初項を表示することができた．次はこれをきれいにしていく．
refactoring :
require './assert_equal'
def fib(n)
return 0 if n == 0
end
puts assert_equal(0, fib(0))
こうすることで二行短くなった．英語の文法のようでみやすいし．
第二項の作成
red : 次は第二項を作成する．
require './assert_equal'
def fib(n)
return 0 if n == 0
end
puts assert_equal(0, fib(0))
puts assert_equal(1, fib(1))
green : 先程と同様にすればいい，
require './assert_equal'
def fib(n)
return 0 if n == 0
if n == 1
return 1
end
end
puts assert_equal(0, fib(0))
puts assert_equal(1, fib(1))
refactoring : こちらも同様に．
require './assert_equal'
def fib(n)
return 0 if n == 0
return 1 if n == 1
end
puts assert_equal(0, fib(0))
puts assert_equal(1, fib(1))
assert_equalの部分が増えてきたのでここもrefactoringする．
require './assert_equal'
def fib(n)
return 0 if n == 0
return 1 if n == 1
end
[[0,0],[1,1]].each do |pair|
puts assert_equal(pair[0], fib(pair[1]))
end
第三項の作成
red : まずはテスト．テスト部分だけ下に表示する．
require './assert_equal'
[[0,0],[1,1],[2,1]].each do |pair|
puts assert_equal(pair[0], fib(pair[1]))
end
green :
require './assert_equal'
def fib(n)
return 0 if n == 0
return 1 if n == 1
return 1
end
[[0,0],[1,1],[2,1]].each do |pair|
puts assert_equal(pair[0], fib(pair[1]))
end
これでも最後がエラーになる，なぜならassert_equalは(予想，結果)と受け取るからである．なので逆にしてみると．．．
require './assert_equal'
def fib(n)
return 0 if n == 0
return 1 if n == 1
return 1
end
[[0,0],[1,1],[2,1]].each do |pair|
puts assert_equal(pair[1], fib(pair[0]))
end
refactoring :
先程のエラーが起こらないようわかりやすく単語で表記する．
[[0,0],[1,1],[2,1]].each do |index, expected|
puts assert_equal(expected, fib(index))
end
こうすることで後で見やすくなる．
第四項以降の作成
最後に上記を基に一般的な動作を表す．
red :
require './assert_equal'
[[0,0],[1,1],[2,1],[3,2],[4,3],
[5,5],[6,8],[7,13],[8,21]].each do |index, expected|
puts assert_equal(expected, fib(index))
end
これを動くようにする，
green :
連続した二項を足したものが次の項になるので
fib(n) = fib(n-1) + fib(n-2)
となる．これを実装すると，
require './assert_equal'
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]].each do |index, expected|
puts assert_equal(expected, fib(index))
end
まとめ
今回は再帰を利用してFibonacci数列を表示した．
- source ~/prog/github/grad_members_20f/members/miyanagi/post/fibo.org