関数型っぽくフィボナッチ

ブログの間が空きすぎたときの、オイラープロジェクト。25問目。フィボナッチ数列で初めて1000桁を超えるのはいくつ目か、という問題。

普通にクラスを作ってメモ化。

class Fib
  def initialize
    @memo = {}
  end

  def calc(n)
    @memo[n] ||= begin
      (n <= 2) ? 1: calc(n - 1) + calc(n - 2)
    end
  end
end

f = Fib.new

(1..10000).each do |n|
  if f.calc(n).to_s.size >= 1000 then
    print n, ":", f.calc(n), "\n"
    break
  end
end

というか、ふつうに下から計算すればカンタンだし速い。

i = 3
x, y = 1, 2

while y.to_s.size < 1000
  x, y = y, x + y
  i += 1
end

puts i

関数型っぽく、関数を受け取ってメモ化を有効にするアプローチ。

def memoize
  h = {}
  lambda {|n| h.has_key?(n) ? h[n]: (h[n] = yield n) }
end

fib = memoize { |n|
  (n <= 2) ? 1: fib.(n - 1) + fib.(n - 2)
}

1.upto(12) do |i| 
  puts fib.(i)
end

(12..10000).each do |n|
  f = fib.(n)
  if f.to_s.size >= 1000 then
    print n, ":", f, "\n"
    break
  end
end

Rubyっぽくない。