議事録(52)

CodeKataKata

• フィボナッチ数の算出
• みんなのコードは以下
• https://gist.github.com/misogi/1613a37c60969367db33

fib_to = ARGV[0].to_i
fibs = (2..fib_to).each_with_object([0, 1]) do |n, fibs|
 fibs[n] = fibs[n - 1] + fibs[n - 2]
end
puts fibs[fib_to]

• https://gist.github.com/jacoyutorius/44fc7e4c9deb329b816c

class FibonacciNumber
	def get x
		case x
		when 0, 1
			return 1
		else
			get(x - 2) + get(x - 1)
		end
	end
end

if __FILE__ == $0
	p FibonacciNumber.new.get(10)
	p FibonacciNumber.new.get(50)
end

require "spec_helper"
require "fib"

describe "FibonacciNumber spec" do 
	it "0の場合、1" do 
		expect(FibonacciNumber.new.get(1)).to eq 1
	end
	it "1の場合、1" do 
		expect(FibonacciNumber.new.get(1)).to eq 1
	end
	it "2の場合、2" do 
		expect(FibonacciNumber.new.get(2)).to eq 2
	end
	it "3の場合、3" do 
		expect(FibonacciNumber.new.get(3)).to eq 3
	end
	it "5の場合、5" do 
		expect(FibonacciNumber.new.get(5)).to eq 8
	end
	it "8の場合、21" do 
		expect(FibonacciNumber.new.get(8)).to eq 34
	end
	it "9の場合、55" do 
		expect(FibonacciNumber.new.get(9)).to eq 55
	end
	it "10の場合、55" do 
		expect(FibonacciNumber.new.get(10)).to eq 89
	end
	# it "99の場合、" do 
	# 	expect(FibonacciNumber.new.get(10)).to eq 55
	# end
end

def fib(x)
  fibonacci = Array.new(x)
  i = 0
  for i in 0..x
    if i == 0 || i == 1
      fibonacci[i] = 1
    else
      fibonacci[i] = fibonacci[i-1] + fibonacci[i-2]
    end
  end
  return fibonacci[x-1]
end

puts fib(1)
puts fib(2)
puts fib(3)
puts fib(4)
puts fib(10)
puts fib(100)
puts fib(1000)
puts fib(10000)
puts fib(100000)

def fib(x)
  case x
  when 1, 2
    1
  else
    fib(x - 2) + fib(x - 1)
  end
end
puts fib(ARGV[0].to_i)

• ワンライナー
• https://gist.github.com/misogi/0aa77ecc8efd95f45ce5

fib = -> (n) { x, y = 0, 1; n.times { x, y = y, x + y }; x }
p fib.call(100) == 354224848179261915075 # test

• キャッシュ（メモ化）有効化版

def fib(x, a)
  case x
  when 1
    a[1] = 1
  when 2
    a[2] = 1
  else
    return a[x] if a[x]
    return a[x] = fib(x - 2, a) + fib(x - 1, a)
  end

def fib(x)
	#ゼロ始まり
	a = 0  #ふたつ前の結果
	b = 1  #ひとつ前の結果
	c = 1  #現在の結果
	for i in 0..x-1
	    c = a + b
	    a = b
	    b = c
	end
	return c
end

puts fib(0)
puts fib(1)
puts fib(2)
puts fib(3)
puts fib(4)
puts fib(5)
puts fib(6)
puts fib(7)
puts fib(8)
puts fib(9)
puts fib(10)
puts fib(100)
puts fib(1000)
puts fib(10000)
puts fib(100000)
#puts fib(1000000) おそい

• フィボナッチ数100まではここにのってる[http://www.suguru.jp/Fibonacci/Fib100.html]
• 配列にドンドコ値をセットしていく方式だと、メモリを消費しまくったり遅かったりした
• Rubyは数値が大きくなると自動的に内部的に他の型へ変えてくれる。メモリが在る限りデカい数値へ

LT

• misogiさんが発表
• paizaみたいなサイトでコードを書く練習をすると楽しいし自分の為になるよと言う話
• スライド http://www.slideshare.net/m1sogi/odai-drivendevelopment

KPT