フィボナッチ数とひまわり - まめめも
最近何かと話題のフィボナッチ数計算の高速化ですが、 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
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://rubysource.com/narihiro-nakamura-rubys-gc-innovator/
