rscの日記さんのところに、カエルのジャンプの問題を解くというのがあったので、僕も Ruby でやってみました。
或る回答にもありますが、これは本質的にフィボナッチ数列の問題です。葉っぱが n 枚のときのカエルの渡り方を num(n) とすると、直前の葉っぱから進んでくるか(num(n-1))か、ひとつ葉っぱを飛ばしてジャンプしてくるか(num(n-2))ですから、漸化式
num(n) = num(n-1) + num(n-2)
が成り立ちます。また葉っぱが 0 枚のときは単に飛び越えるだけですから、num(0) = 1。葉っぱが1枚のときは、葉っぱに乗って渡るかそれとも飛び越えるかのどちらかですから、num(1) = 2。これらを元に、漸化式を計算すればいいわけです。
コードはメソッド再帰の例になりますね。デフォルトは葉っぱが 8 枚になっています。
fibonacci.rb
def num(n) return $n_0 if n == 0 return $n_1 if n == 1 num(n-1) + num(n-2) end n = (ARGV[0] || 8).to_i $n_0 = 1 #num(0) $n_1 = 2 #num(1) puts num(n) #=>55
20 枚の場合は、こんな感じです。
>ruby fibonacci.rb 20 17711
極普通のフィボナッチ数列を求めるプログラムは、上のをちょっと変えて
def num(n) return 1 if n == 1 return 1 if n == 2 num(n-1) + num(n-2) end for i in 1..40 print "#{num(i)} " end
という感じでしょうか。実行すると
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155
となります。n = 40 くらいになると、かなり時間がかかります。
もちろん、再帰など使わなければすぐですね。普通に配列でやればいいわけです。これなら一瞬です。
num = [] num[1] = 1; num[2] = 1; print "1 1 " for i in 3..40 num[i] = num[i-1] + num[i-2] print "#{num[i]} " end
※追記(2016/1/16)
配列すらも使わずにできますね。(2017/6/13 修正)
a, b = 1, 1 while a < 10000000 print "#{a} " a, b = b, a + b end puts
※再追記(2018/2/1)
関数型プログラミングっぽく。
fib = ->(n) { fib_iter = ->(a, b, count) { count.zero? ? b : fib_iter.(a + b, a, count - 1) } fib_iter.(1, 0, n) } p fib.(100) #=>354224848179261915075
あるいは
fib = ->(n) { fib_iter = ->(ar, a, b, count) { count.zero? ? ar : fib_iter.(ar + [a], a + b, a, count - 1) } fib_iter.([], 1, 0, n) } p fib.(10) #=>[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
※再々追記(2018/10/3)
無限リストを使って。
def fib Enumerator.new do |y| a, b = 0, 1 loop do a, b = b, a + b y << a end end end p fib.take(100)
※再々々追記(2020/3/13)
Ruby 2.7 から入った Enumerator.produce
を使って。
fib = Enumerator.produce([0, 1]) {|a, b| [b, a + b]} p fib.take(10).map(&:last)
※再々々々追記(2020/12/4)
ここの記事を参考に。
module Fib extend Enumerable def self.each(size = Float::INFINITY) unless block_given? return to_enum(:each, size) end a, b = 0, 1 1.step(size) do yield a a, b = b, a + b end end def self.[](n) lazy.drop(n).first end end Fib.each(10) {|x| puts x} p Fib.each(10).to_a p Fib.to_a(10) #=>[0, 1, 1, 2, 3, 5, 8, 13, 21, 34] p Fib[50] #=>12586269025 require "prime" p Fib.lazy.select(&:prime?).first(10) #=>[2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437]
これはFib.each
の使い方が凝っていますね。参考にしました。