計算機科学
解きたい問題 障害物のある平面において起点と終点を結ぶ経路を探索し直線数を最小化したい。 障害物は線分で与えられる。 経路の長さは目的としない。 この画像は問題の単なる一例であり、障害物は平面上に自由に置けるものとする。 解決手順 適当な細かさ…
問題 連結無向グラフのカットのうち最小のものを求める。 実装 ソースコード(IdeOne) 解説 乱択アルゴリズムによる実装。 一辺をランダムに選んで縮約していく。 最後に2点残る。これらの点に縮約された点が大域最小カットである可能性は以上。 頂点の数をと…
問題の定義 平面上のn個の点の中からユークリッド距離が最小の点の組み合わせを出力する。 実装 ソースコード(Ideone) 解説 入力をランダムにシャッフルしたのちに逐次添加アルゴリズムを用いる。 アルゴリズムが実行される任意の時点において、一辺の長さの…
説明 乱択逐次構成法で点列から凸包を求めます。 三角形から始めて順次凸包を大きくしていく。 実行時間はO(nlogn)。
コンペ形式 レナとミナミの国際プログラミング選手権 【幼なじみ or 許嫁】国際プログラミング選手権を制したコード7選+α こちらに参加しました。
説明 QuickSelectと呼ばれているO(n)時間アルゴリズムを利用する。
ここによるとコンパイラの中間表現として CPS(Continuation Passing Style) v.s. ANF(A - Normal Form) という構図があるらしい。
目的 Fast Fourier Transform (FFT) のアルゴリズムとして Cooley-Turky 法が紹介されることが多いと思いますが、あまり触れられることのない、もうひとつのアルゴリズムである Stockham 法について書きたいと思います。
INRIA OCAML本家 Documentation and user’s manual OCamlJP camlcity.org OCamlCore.org
Project Euler の Problem 58 で大きめの数の素数判定が必要になった。しかし Ruby 1.9.2 でも素数の生成および判定は遅く思われた。 Problem 58なので以下のページを参考に[0,2^32)の素数判定テーブルを作成することに。 merom686's diary 32bitCPUで2^32未…