Document Links
Recursion(再帰)
フィボナッチ数列を解く
今回はフィボナッチ数列をRecursion(再帰)で求めるわけだが，フィボナッチ数列って知ってるよね？
初めてその名称を聞いたのは映画「ダ・ヴィンチ・コード」かな？（まあ，あれは初項の0が無かったが）
ということで，フィボナッチ数列ってのは
F(0)=0, F(1)=1, F(n+2)=F(n)+F(n+1) (n>=0)
という漸化式で定義される数列です．
解説
第1項と第2項について
前述したように，第1項と第2項は0,1なので，とりあえず，その部分を判定する関数を書く．
fibonacci01.rb
def fib(n)
if n == 0
return 0
end
if n == 1
return 1
end
end
require './aeroc'
[[0,0],[1,1]].each do |pair|
puts assert_equal(pair[1], fib(pair[0]))
end
assert_equalの引数が(pair[1],pair[0])となっているが，これはaeroc.rbのassert_equalと整合を取るため．
実行結果
$ ruby fibonacci01.rb
expected :: 0
result :: 0
succeeded in assert_equal.
expected :: 1
result :: 1
succeeded in assert_equal.
第3項について
定義に当てはめると，F(2)=F(0)+F(1)となる．
これを反映させると，（かなり強引だが）
fibonacci2.rb
def fib(n)
if n == 0
return 0
end
if n <= 2
return 1
end
end
require './aeroc'
[[0,0],[1,1],[2,1]].each do |index, expected|
puts assert_equal(expected, fib(index))
end
引数を|pair|としていたがわかりにくいため，|index,expected|に変更
実行結果
$ ruby fibonacci2.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.
ちょいとコードがゴチャついてきたので修正．
fibonacci2re.rb
def fib(n)
return 0 if n == 0
return 1 if n <= 2
end
require './aeroc'
[[0,0],[1,1],[2,1]].each do |index, expected|
puts assert_equal(expected, fib(index))
end
methodを大幅に削減できた．
一般式について
定義ではF(n+2)=F(n)+F(n+1)とあるが，これをコードにするのは無理（理由は分かるじゃろうて）．
コードにするなら，F(n)=F(n-1)+F(n-2)だよね．
fibonacci.rb
def fib(n)
return 0 if n == 0
return 1 if n == 1
fib(n - 1) + fib(n - 2)
end
require './aeroc'
[[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
引数を|pair|としていたがわかりにくいため，|index,expected|に変更
実行結果
$ ruby fibonacci.rb
expected :: 0
result :: 0
succeeded in assert_equal.
expected :: 1
result :: 1
succeeded in assert_equal.
・
・
・
expected :: 13
result :: 13
succeeded in assert_equal.
expected :: 21
result :: 21
succeeded in assert_equal.
完成！
Class化
冒頭
オブジェクト指向を学んでいくわけだが，キーとなるのが，
- 隠蔽(capsulation)
- 継承(inheritance)
- 多態(polymorphism)
とのこと．
例えば，
def puts_hello name
puts "Hello #{name}."
end
def gets_name
name = ARGV[0] || 'world'
return name
end
name = gets_name
puts_hello name
実行結果
$ ruby hello.rb
Hello World.
$ ruby hello.rb Name
Hello Name.
mainでloopがある．
こいつを消したいので，修正すると
class Hello
def initialize
@name = gets_name
puts_hello
end
def puts_hello
puts "Hello #{@name}."
end
def gets_name
name = ARGV[0] || 'world'
return name
end
end
Hello.new
完成．
締め
今回はRecursion（再帰）とClass化（冒頭）について学んだ．
次回，Class化について
- source ~/school/multi/my_ruby/grad_members_20f/members/evendemiaire/post/recursion.org