フィボナッチ数とひまわり - まめめも
最近何かと話題のフィボナッチ数計算の高速化ですが、 F(n) = (fib(n+1), fib(n)) （2次元の縦ベクトルだが表記の都合で横に書く） A = ((1, 1), (1, 0)) （第1行が(1, 1)で第2行が(1, 0)の行列） すると，F(n) = A F(n-1) = A A F(n-2) = A A A F(n-3) = ...となるから，F(n)を計算するためには，Aのn乗を計算して，それに右からF(0)をかければ良いことになる。 計算量の工夫でプログラムは劇的に速くなる 以前この記事を読んだときも、ははー、と思ったのですが、そのときは実装してみなかったのでちょっと実装してみました。 require "matrix" def fib(n) aux = proc do |m, a| case m when 0 then Matrix.I(2) when 1 then
10000までの完全数を列挙せよ - rubyco（るびこ）の日記
エラトステネスの篩もよいけれど、別の問題もやろうよ。ということで「完全数」です。 def perfect(n = 100, &block) sum = Array.new(n + 1, 1) (2..n).each do |i| if i == sum[i] block.call(i) end k = i + i while k <= n sum[k] += i k += i end end sum end perfect(10000) do |k| print "#{k}, " end #=> 6, 28, 496, 8128,あらら？ エラトステネスの篩とほぼ同じになっちゃった♪ 完全数 (Wikipedia) 追記：おお、Danさんが反応してくださいました。感謝です♪ http://blog.livedoor.jp/dankogai/archives/50538972.html
O(log n)でフィボナッチ数を求める - 趣味的にっき
O(log n)でフィボナッチ数のN番目を求める方法をRubyで実装してみました。この間のSICP勉強会で教えてもらったやつです。 まず普通のフィボナッチ数。こいつはO(n)です。 def fib1(n) a, b = 0, 1 n.times do a, b = a + b, a end a end O(log n)版のフィボナッチ数。なんでこれでフィボナッチ数が求められるかは、ここを参照してください。ちなみにRubyのMatrixの**は、O(log n)で実装されています。 require 'matrix' def fib2(n) a = Matrix[[1, 1], [1, 0]] b = Matrix[[0], [1]] (a ** n * b)[0, 0] end こんな感じでベンチマークをとってみました。 require 'benchmark' n = 100_000 Ben
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
