More than 3 years have passed since last update.

【Week 10】recursion, ruby_fifth

Ruby

Last updated at 2020-12-28Posted at 2020-12-28

はじめに

マルチスケールシミュレーション特論の講義メモです．講義メモのインデックスはコチラ

今回の参考資料はチャート式ruby-V(Recursive Fibonacci)です．

チャート式 Ruby

参照記事はコチラ

fibonacci

フィボナッチ数列とは

0 1 1 2 3 5 8 13 21 ...

のように

fib(n) = fib(n-1)+fib(n-2)

を満たす数列である．この関数 fib をテスト駆動開発で作成していく．

テスト駆動開発ではとりあえず出力してみて，期待する出力と異なっていれば修正していくような進め方をする．今回は 1 つずつ項を追って，プログラムを完成させる．

fib(0) = 0

フィボナッチ数列の初項は 0 なので，関数 fib は

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

puts fib(0)

期待する出力と等しいか確認したいので，前回作成した assert_equal を使って確認する．

require './assert_equal_final.rb'

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

puts assert_equal(0,fib(0))

実行すると

> ruby fibonacci.rb
expected :: 0
result   :: 0
succeeded in assert_equal.

期待通りの出力が得られた．assert_equal 便利！

fib(1) = 1

続いて第 2 項は 1 なので，関数 fib は

require './assert_equal_final.rb'

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

puts assert_equal(1,fib(1))

実行すると

> ruby fibonacci.rb
expected :: 1
result   :: 1
succeeded in assert_equal.

期待通りの出力が得られた．ここで，テスト部分の書き換えを楽にするために，少し改変する．

require './assert_equal_final.rb'

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

fib(2) = fib(1) + fib(0) = 1

一度テストしてみる．

[[0,0],[1,1],[1,2]].each do |pair|

と追加して，実行すると

> ruby fibonacci.rb
expected :: 0
result   :: 0
succeeded in assert_equal.

expected :: 1
result   :: 1
succeeded in assert_equal.

expected :: 1
result   :: 
failed in assert_equal.

0, 1 以外は定義されてないので仕方ないよね．それでは 2 のときの条件も追加する．

require './assert_equal_final.rb'

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

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

ついでに each 文の受け渡しもよりわかりやすいように改良しておく．

if 文が重くなってきたが，条件文は 1 行で表すことができるので忘れずにリファクタリングする．

require './assert_equal_final.rb'

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

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

fib(3) = fib(2) + fib(1) = 2

続いて第 3 項．まずはテスト．

[[0,0],[1,1],[2,1],[3,2]].each do |index, expected|

> ruby fibonacci.rb
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   :: 
failed in assert_equal.

仕方ないです．TDD はまず green にすることが大切だそうなので，

require './assert_equal_final.rb'

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

[[0,0],[1,1],[2,1],[3,2]].each do |index, expected|
  puts assert_equal(expected,fib(index))
end

さすがに強引すぎる気がする．

アルゴリズム的に正しくは

return fib(2) + fib(1)

なので

require './assert_equal_final.rb'

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

[[0,0],[1,1],[2,1],[3,2]].each do |index, expected|
  puts assert_equal(expected,fib(index))
end

実行すると

> ruby fibonacci.rb
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.

このときf(2)ってずっと呼び出されるんじゃあ…

うまくいってるのがよくわからない．

fib(4) = fib(3) + fib(2) = 2 + 1 = 3

続いて第 4 項．まずはテスト．

[[0,0],[1,1],[2,1],[3,2],[4,3]].each do |index, expected|

> ruby fibonacci.rb
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   :: 2
failed in assert_equal.

もちろんエラーが出る．

3 つ目の return を定義通り

fib(n) = fib(n-1) + fib(n-2)

と修正する．このとき

return 1 if n == 1

でよいので，最終的には以下のようなプログラムとなる．

require './assert_equal_final.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]].each do |index, expected|
    puts assert_equal(expected,fib(index))
end

実行すると

> ruby fibonacci.rb
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.

問題なくフィボナッチ数列の関数 fib をテスト駆動開発で作成できた．

Ruby 開発周辺情報

今回はチャート式 Ruby のみです．

次回の講義内容 <2020-12-02 Wed>

次回の講義は

チャート式ruby-VI(hello class)

だそうです．

source ~/grad_members_20f/members/e79a93e5b7b1/posts/class/c10_20201125.org

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up