フィボナッチ数とひまわり - まめめも
最近何かと話題のフィボナッチ数計算の高速化ですが、 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
フィボナッチ数列に関する３つのアルゴリズムの速度比較＠Ruby - 簡潔なQ
アルゴリズムの違いが速度に明確に表れるわかりやすい例のひとつであるフィボナッチ数列を使って速度比較。 気軽に多倍長が使える言語でないと、線形とlogの違いは見えづらい。 #!/usr/bin/ruby -Ku require 'matrix' def fib_recursive(n) case n when 0 return 0 when 1 return 1 else return fib_recursive(n-1)+fib_recursive(n-2) end end def fib_linear(n) a, b = 0, 1 n.times do a, b = b, a+b end return a end def fib_log(n) (Matrix[[1,1],[1,0]]**n)[0,1] end def omit_bignum(n, dig = 20) s = n.to_s
Rubyの末尾再帰最適化を理解する - hp12c
ブログを下記に移転しました。デザイン変更により移転先では記事が一層読みやすくなっていますので、よろしければ移動をお願い致します。 Rubyの末尾再帰最適化を理解する : melborne.github.com - RubyではSchemeなどとは異なって 末尾再帰の最適化を勝手にしてはくれません 再帰は再帰なんかじゃない！末尾再帰こそが真の再帰なんだ！ でもid:athosさんが Rubyで末尾再帰最適化を実現するコードを書いてくれました Rubyで末尾再帰最適化をする。 - Homoiconic Days 自分の実力だと一見しただけでは何をしているか理解できなかったので 少し自分用にコードを整理してその処理を追ってみます class Module def tco(meth) called = false tmp = nil orig_meth = "orig_#{meth}" alias
迷路の最短経路を求めるには？ - ザリガニが見ていた...。
相当、出遅れた感はあるが、以下の試験問題をやってみた。（Rubyで） さて試験問題です。 内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。 たとえば、S:スタート G:ゴール *:壁 $:解答の経路 としたとき、 ************************** *S* * * * * * * ************* * * * * ************ * * * * ************** *********** * * ** *********************** * * G * * * *********** * * * * ******* * * * * * **************************という入力に対し、 **************************
QuickDrawはどのように素早く円を描いていたのか？ - ザリガニが見ていた...。
かつてのMac OS9までの描画エンジンの主役はQuickDrawが担っていた。GUIなOSでは、文字も含めてすべてをグラフィックとして扱うので、画面に見えているすべてのもの*1はQuickDrawによって描かれていたことになる。描画エンジンは、GUIなOS開発の要となる技術である。その出来が、GUIなOS開発の成否を分けるとも言える。 そして、最初期のQuickDrawは、ビル・アトキンソンがたった一人で開発したそうである。 当時（25年以上前）のCPUは、動作クロックが8MHzという性能だった。（現在は2GHz=2000MHzかつ、複数コアが当たり前） そのような性能であっても、違和感なくマウスで操作できるOS環境にするために、斬新な発想や試行錯誤を重ね、相当な努力の末に開発されたのがLisaやMacintoshであった。 Amazon.co.jp： レボリューション・イン・ザ・バレー
Rubyで作る実験的Quicksilverのようなもの - ザリガニが見ていた...。
前回探った、略語（Abbreviation）と関連するテキストを点数付けするアルゴリズムは、Quicksilverの使い勝手を左右する重要な要素の一つだ。とすると、このアルゴリズムを取り込めば、なんちゃってQuicksilverもどきが出来るかもしれない...。と思って、まったく実用的ではないのだけど、実験的なソフトウェアとして試してみた。 作業環境 MacBook OSX 10.6.2 ruby 1.8.7 (2009-04-08 patchlevel 160) [i686-darwin9] 以下、コード中に半角￥が見える場合は、すべて半角＼に置き換える必要があり。 Ruby版 scoreForAbbreviation Stringクラスを拡張して、to_scoreメソッドを追加した。 正規表現を利用して実装した。 マッチした部分とその前後の文字列が簡単に取得できるので、Objectiv
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
初めてのおもちゃ箱 [Ruby][アルゴリズム入門]乱数