algorithm」カテゴリーアーカイブ

ダイクストラ法(2)

昨日のダイクストラ法を C でやってみた。 [email protected] $ ./dijkstra 10 0 -> 2 -> 4 -> 5

カテゴリー: algorithm, C | コメントする

ダイクストラ法

ダイクストラ法とは、グラフ上の最短経路問題をとくアルゴリズム。↓このページに詳しいアルゴリズムの説明がある。  cf. ダイクストラ法(最短経路問題) – deq notes Ruby でやってみた。例題は、 … 続きを読む

カテゴリー: algorithm, Ruby | 1件のコメント

文字列間のレーベンシュタイン距離を求める

レーベンシュタイン距離というのを知った。 Wikipedia のレーベンシュタイン距離の項によると: レーベンシュタイン距離(レーベンシュタインきょり)は、二つの文字列がどの程度異なっているかを示す距離(距離空間を参照) … 続きを読む

カテゴリー: algorithm, JavaScript | 2件のコメント

二分木を使ったソート

単純な二分木を使ったソート。構造体で二分木を表現するのと、malloc() / free() の練習。 [email protected] $ ./btreesort unsorted: 80 77 21 42 50 … 続きを読む

カテゴリー: algorithm, C | コメントする

二分木を使ったソート

ヒープじゃなくて単純な二分木を使ったソート。すなわち、 左の子は親よりも小さい 右の子は親よりも大きい という構造。で、これを通りがけ順(左の枝、根、右の枝の順に調べる)に出力すると昇順にソートされる。 [email protected]続きを読む

カテゴリー: algorithm, Ruby | コメントする

配列を使ったヒープソート

一昨日は二分木を使ったヒープソートを作った。配列を使ったヒープの構造についてはここのページのヒープの項が分かりやすい。  cf. 二分木 (binary tree) とヒープ (heap) – Algorit … 続きを読む

カテゴリー: algorithm, Ruby | コメントする

二分ヒープ(ヒープ木)を使ったヒープソート

ヒープソートって配列を使ってやるのがフツウみたいだけど、アルゴリズムのアイデアに忠実に二分ヒープ(木)を使ってやってみた。参考にしたページはココらへん。  cf. 二分木 (binary tree) とヒープ (heap … 続きを読む

カテゴリー: algorithm, Ruby | コメントする

Rubyでクイックソート

cf. RubyでクイックソートとRSpecでそのテストを書いてみる – 凸ろぐ なんだかまどろっこしい書き方をしてるなあ。これでいいんじゃないか? [email protected] $ ruby qs … 続きを読む

カテゴリー: algorithm, Ruby | コメントする

Schemeでユークリッドの互除法

今日は時間がないので埋草的エントリ。ユークリッドの互除法で最大公約数を求める。 [email protected] $ gosh gcd.scm 21

カテゴリー: algorithm, Scheme | コメントする

Schemeでマージソート

やってみた。 実行結果: ^o^ > gosh merge-sort.scm (1 2 3 4 5 6 7 8 9)

カテゴリー: algorithm, Scheme | コメントする