ユークリッドの互助法という名前のアルゴリズムを紹介します。これは最大公約数を求めるアルゴリズムで、
ある整数x,yの最大公約数gcd(x,y)の解を求めるとして、yが0であればx、そうでなければgcd(y, x % y)が解となる。
という至って単純なアルゴリズムです。
以下のコードはこのアルゴリズムを再帰で実装したものです。ループで実装したコードはコメントアウトされています。(再帰のほうが断然エレガントである) (さらに…)
2010年7月20日 | カテゴリー：アルゴリズム
プログラマなら誰もが知っている再帰ですが、よくC言語のポインタと並んで初心者がよくつまづく概念としても有名(?）です。今回はこの再帰(特に末尾再帰について)と基本的な制御構造の一つであるループとの関係について考えてみます。
ループ構文というのは大抵の言語に存在する制御構造ですが、世の中にはループ構文が存在しない言語もたくさんあります(gotoでジャンプしてるわけではありませんよ)。このような言語ではループの代わりに再帰呼び出しを使います。 (さらに…)
2010年7月6日 | カテゴリー：アルゴリズム
素数判定アルゴリズムのエラトステネスの篩というアルゴリズムを紹介します。
エラトステネスの篩は指定された値以下の素数を求めるアルゴリズムです。
まず、2から指定された数値までの整数の数列を作成します。
次に小さい方から数値を取り出し、印がついていなければそれを素数とします。
そして素数の倍数の数値すべてに素数でないことを示す印をつけます。 (さらに…)
2010年6月22日 | カテゴリー：アルゴリズム
