Ruby でアルゴリズム

奥村晴彦さんの「C言語による最新アルゴリズム事典」技術評論社、1991年、の C 言語プログラムの Ruby への翻訳に挑戦します。プログラムの説明は同書を読んでください。変換はできるだけ逐語的に行っています。プログラムの動作は原作の C プログラムのそれと比較してチェックしていますが、うまく動作しないときは C から Ruby への変換のさいに起きたものです。バグレポートは tnomura@mnet.ne.jp までお願いします。

この Ruby 翻訳版はできるだけレイアウトも含めて原作の C プログラムを変更しないようにしたため、必ずしもRuby らしいコーディングスタイルとは言えないかもしれませんが、プログラムがきちんと動作することを優先しました。C から Ruby への翻訳の著作権に関しては Ruby のライセンスに準じます。配布、改変は自由です。ただし、プログラム本体には原作者の著作権があるものと考えます。

105.rb百五減算
3dgraph.rb3次元グラフ
5num.rb五数要約 (実行には statutil.rb が必要です。)
acker.rbAckermann (アッカーマン)関数
area.rb面積
atan.rb逆三角関数
bernoull.rbBernoulli (ベルヌーイ) 数
bessel.rbBessel (ベッセル) 関数
bifur.rbカオスとアトラクタ (実行には window.rb が必要です。)
binomial.rb2項分布
bsrch.rb2分探索
bubsort.rbバブルソート
cannibal.rb宣教師と人食い人
cardano.rb三次方程式。Ruby 1.6 では Math.acos がないので動きません。Ruby 1.8 なら OK。
ccurve.rbC曲線
cfint.rb連分数補間
change.rb小銭の払い方
chaos.rbカオスとアトラクタ
chaos_g.rbカオスとアトラクタ(gnuplot で表示を行うバージョン)
chi2.rbカイ2乗分布
collatz.rbCollatz (コラッツ) の予想
combinat.rb組合せの数
contour.rb等高線(f(x,y) = 1, x = 1, y = 1, step = .1 くらいからはじめてください。実行には plotter.rb が必要です。)
complex_algo.rbRuby には標準ライブラリの complex.rb があるのでファイル名には complex_algo.rb を使いました。演算子のオーバーライドなどちょっぴり Ruby 風にしてありますが、基本的なアルゴリズムは原作のままです。
corrcoef.rb相関係数 (実行には statutil.rb が必要です)
crypt.rb暗合
dayweek.rb曜日
delta2.rbAitken (エイトケン) の Delta^2 法
dijkstra.datdijkstra.rb 用のデータファイル。ruby dijkstra.rb < dijkstra.dat で実行します。
dijkstra.rb最短路問題
distsort.rb分布数えソート
dragon.rbドラゴンカーブ (実行には plotter.rb が必要です。)
dragon2.rbドラゴンカーブ (実行には plotter.rb が必要です。)
e.rb自然対数の底
egypfrac.rbエジプトの分数
eigen.rbQR法 (実行には matutil.rb が必要です)
euler.rb一筆書き
eval.rb式の評価
factoriz.rb素因数分解
factrep.rb階乗進法
fib.rbFibonacci (フィボナッチ) 数列
fibonacc.rbFibonacci (フィボナッチ) 探索
fracint.rbフラクタル補間
gamma.rbガンマ関数、ベータ関数
gauss.rbGauss (ガウス) 法 (実行には matutil.rb が必要です)
gcd.rb最大公約数
genperm.rb順列生成
gjmatinv.rb逆行列 (実行には matutil.rb が必要です)
goldsect.rb黄金分割
hanoi.rbハノイの塔
heapsort.rbヒープソート
hilbert.rbHilbert (ヒルベルト) 曲線
hyperb.rb双曲線関数・逆双曲線関数
ifs.rbフラクタルによる画像圧縮 (実行には window.rb が必要です。)
ifs_tree1.rbフラクタルによる画像圧縮 (樹木)
ifs_tree2.rbフラクタルによる画像圧縮 (樹木)
ifs_tri.rbフラクタルによる画像圧縮 (Sierpinski の三角形)
inssort.rb挿入ソート
inv.rb合同式
invr.rb 逆行列 (実行には matutil.rb が必要です。)
irandom.rb幾何分布、二項分布、Poisson (ポアソン) 分布
isbn.rbISBN番号
ishi1.rb石取りゲーム 1
ishi2.rb石取りゲーム 2
isomer.rb異性体の問題
jos1.rbJosephus (ヨセフス) の問題
jos2.rbJosephus (ヨセフス) の問題
knapsack.rbナップザックの問題
knight.rb騎士巡歴の問題
koch.rbKoh (コッホ) 曲線
komachi.rb小町算
krnd.rbKnuthの乱数発生法
life.rbライフ・ゲーム
lissaj.rbLissajous (リサージュ) 図形
lorenz.rbLorenz (ローレンツ) アトラクタ
lucas.rb素数のLucasテスト
maceps.rb機械エプシロン
magicsq.rb魔方陣
mapsort.rb逆写像ソート
marriage.rb安定な結婚の問題
matinv.rb逆行列 (実行には matutil.rb が必要です)
matutil.rb行列操作の小道具集
maxmin.rb最大値・最小値
maze.rb迷路
monte.rbモンテカルロ法
movebloc.rbブロック移動
newt1.rbNewton (ニュートン) 法
newt2.rbNewton (ニュートン) 法
newton.rbNewton (ニュートン) 法
nextperm.rb順列
nim.rb三山くずし
normal.rb正規分布
numint.rb数値積分
orddif.rb常微分方程式
partit.rb分割数
permfac.rb順列(階乗進法との相互変換)
permnum.rb順列(自然数との相互変換)
permsign.rb置換の符号
pi1.rb円周率
pi2.rb円周率
plotter.rbグラフィックス。 gnuplot がインストールされている必要があります。グラフィックを扱うプログラムは gnuplot を利用しています。
postfix.rb後置記法
primes.rb素数
primroot.rb原始根
qsort1.rbクイックソート
quadeq.rb2次方程式
radconv.rb基数の変換
random.rb確率分布
rank1.rb順位づけ
rank2.rb順位づけ
repdec.rb小数の循環節
rndsamp1.rb無作為抽出
rndsamp2.rb無作為抽出
rndsamp3.rb無作為抽出
sboymoo.rbBoyer--Moore法
select.rb選択
seqsrch.rb逐次探索
shelsort.rbShellソート
slctsort.rb選択ソート
sosrch.rb自己組織化探索
spline.rbスプライン補間
sqrt.rb平方根。Ruby の Float クラスは double のようです。Ruby で long double を扱う方法が分からなかったのでこの翻訳版では long double の出力が C 言語プログラムとは異なりますが、一応直訳したものを置いておきます。
srchmat.rb2次元の探索
statutil.rb多変量データ。(データ入力用のプログラム。他のプログラムから引用します。)
stemleaf.rb幹葉表示
strmatch.rb文字列照合。Ruby の String オブジェクトでは終端文字はなく、範囲外の照会をすると nil が返るようになっています。
sum.rb情報落ち(Ruby では桁落ちが検証できませんでした。)
tarai.rbたらいまわし関数
tetromin.rbテトロミノの箱詰パズル
toposort.rbトポロジカル・ソーティング。ruby toposort.rb < toposort.datで実行します。
toposort.datトポロジカル・ソーティングのデータファイル
tree.rb2分探索木 (原作はポインタのポインタを使ったコンパクトなコードになっています。Rubyではポインタがなく eval を使ってポインタらしき動作をさせたので実用的ではないかも知れません。しかし、原作の C プログラムと対比させるとそのアイディアがよく分かります。)
treecurv.rb樹木曲線。実行するには plotter.rb が必要です。
warshall.datwarshal.rb用のデータファイル。ruby warshal.rb < warshal.dat で実行します。
warshall.rb推移的閉包
water.rb水をはかる問題
weights.rb秤の問題
window.rbグラフィックス・ルーチン。gnuplot がインストールされている必要があります。
zeta.rbRiemannのゼータ関数