SICP フィボナッチ数列 問題1.19 http://sicp.iijlab.net/fulltext/x124.html

fibonacci.rb

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

def fib2(n)
	fib_iter2(1, 0, n)
end

def fib_iter2(a, b, count)
	return b if count == 0
	fib_iter2(a + b, a, count - 1)
end

def fib3(n)
	fib_iter3(1, 0, 0, 1, n)
end

def fib_iter3(a, b, p, q, count)
	return b if count == 0
	if count.even?
		fib_iter3(
			a,
			b,
			p ** 2 + q ** 2,
			q ** 2 + 2 * p * q,
			count / 2)
	else
		fib_iter3(
			b * q + a * q + a * p,
			b * p + a * q,
			p,
			q,
			count - 1
			)
	end
end

[:fib, :fib2, :fib3].each do |fib|
	print "----#{fib}-----\n"
	20.times do |i|
		p send(fib, i) 	
	end
end

SICP
フィボナッチ数列
問題1.19 http://sicp.iijlab.net/fulltext/x124.html