-
最近の投稿
最近のコメント
アーカイブ
カテゴリー
メタ情報
「algorithm」カテゴリーアーカイブ
ダイクストラ法(2)
昨日のダイクストラ法を C でやってみた。 [email protected] $ ./dijkstra 10 0 -> 2 -> 4 -> 5
ダイクストラ法
ダイクストラ法とは、グラフ上の最短経路問題をとくアルゴリズム。↓このページに詳しいアルゴリズムの説明がある。 cf. ダイクストラ法(最短経路問題) – deq notes Ruby でやってみた。例題は、 … 続きを読む
文字列間のレーベンシュタイン距離を求める
レーベンシュタイン距離というのを知った。 Wikipedia のレーベンシュタイン距離の項によると: レーベンシュタイン距離(レーベンシュタインきょり)は、二つの文字列がどの程度異なっているかを示す距離(距離空間を参照) … 続きを読む
カテゴリー: algorithm, JavaScript
2件のコメント
二分木を使ったソート
単純な二分木を使ったソート。構造体で二分木を表現するのと、malloc() / free() の練習。 [email protected] $ ./btreesort unsorted: 80 77 21 42 50 … 続きを読む
二分木を使ったソート
ヒープじゃなくて単純な二分木を使ったソート。すなわち、 左の子は親よりも小さい 右の子は親よりも大きい という構造。で、これを通りがけ順(左の枝、根、右の枝の順に調べる)に出力すると昇順にソートされる。 [email protected] … 続きを読む
配列を使ったヒープソート
一昨日は二分木を使ったヒープソートを作った。配列を使ったヒープの構造についてはここのページのヒープの項が分かりやすい。 cf. 二分木 (binary tree) とヒープ (heap) – Algorit … 続きを読む
二分ヒープ(ヒープ木)を使ったヒープソート
ヒープソートって配列を使ってやるのがフツウみたいだけど、アルゴリズムのアイデアに忠実に二分ヒープ(木)を使ってやってみた。参考にしたページはココらへん。 cf. 二分木 (binary tree) とヒープ (heap … 続きを読む
Rubyでクイックソート
cf. RubyでクイックソートとRSpecでそのテストを書いてみる – 凸ろぐ なんだかまどろっこしい書き方をしてるなあ。これでいいんじゃないか? [email protected] $ ruby qs … 続きを読む
Schemeでユークリッドの互除法
今日は時間がないので埋草的エントリ。ユークリッドの互除法で最大公約数を求める。 [email protected] $ gosh gcd.scm 21
Schemeでマージソート
やってみた。 実行結果: ^o^ > gosh merge-sort.scm (1 2 3 4 5 6 7 8 9)