エラトステネスの篩

素数判定アルゴリズムのエラトステネスの篩というアルゴリズムを紹介します。
エラトステネスの篩は指定された値以下の素数を求めるアルゴリズムです。

まず、2から指定された数値までの整数の数列を作成します。

次に小さい方から数値を取り出し、印がついていなければそれを素数とします。

そして素数の倍数の数値すべてに素数でないことを示す印をつけます。 (さらに…)

2010年6月22日 | カテゴリー：アルゴリズム

探索アルゴリズム (4)

前回の深さ優先探索に続いて今回は幅優先探索を紹介します。
幅優先探索 (Breadth First Search) はノードの子孫の中から世代が近い者を優先して探索していくアルゴリズムで、最短経路探索などに使われます。

このアルゴリズムの手順は以下のようになります。

1.探索中のノードを格納するキューを用意する
2.探索のルートとなるノードをキューに格納する
3.キューが空なら終了する
4.キューからノードを一つ取り出す (さらに…)

2010年6月8日 | カテゴリー：アルゴリズム

探索アルゴリズム (3)

前回まではリスト探索を行ないましたが、今回からはツリー探索を行ないます。
今回紹介するのは深さ優先探索 (DFS, Depth-First Search) です。

深さ優先探索とはその名のとおり、ツリー構造の深さの方向を優先して探索を行なうアルゴリズムです。深さ優先探索は再帰処理と相性がよく、次のように手順を再帰的に繰り返すだけで実装することができます。 (さらに…)

2010年5月11日 | カテゴリー：アルゴリズム