1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

第十回講義メモ

Last updated at Posted at 2020-12-31

!Mac OS X-10.15.7 !ruby-2.6.3p62

Recursion

例題

フィボナッチ数列を求める.

fib(n) = fib(n-1)+fib(n-2)
0 1 1 2 3 5 8 13 21 ...

fib(0) = 0

Fibonacci数列の初項は0まずは, 関数にしてしまう.

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

前回作ったassert_equal.rbassertionで出力と期待値が一致しているかどうか確認
#+begin_src ruby
require './assert_equal'
puts assert_equal(0, fib(0))

結果

expected :: 0
result   :: 0
succeeded in assert_equal.

fib(1) = 1

n = 1の時を確認.

require './assert_equal'

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

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

require './assert_equal'

 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

配列の受け取りをより明示的にする/.

index, expected = pair

と修正できるので,以下のように修正

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

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

以下コード.

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

最終形

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

上記が抜けているため, if文の条件分岐をもう少し狭める.

最終的に,

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

結果

> ruby fobonacci.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
expected :: 34
result   :: 34
succeeded in assert_equal

上手く動作したことがたしかめられた.

参考サイト

https://qiita.com/daddygongon/items/1bb27b8920c201d5c520


  • source ~/my_ruby/grad_members_20f/members/drop-sd/lectures/no10.org
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?