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