アルゴリズムとは

in  

アルゴリズムの例をいくつか紹介します。

アルゴリズム

アルゴリズムとはある入力から出力を得るための問題を解く手順のことを言います。例えば数の列を順番に並べるソーティング問題や、文字列を照合する問題などが扱われます。

素数を求めるアルゴリズム

エラトステネスの篩

エラトステネスの篩は、指定された上限までのすべての素数を見つけるアルゴリズムです。素数とは、1より大きい自然数であり、1とその数自身以外に正の約数を持たない数を指します。このアルゴリズムでは、まず2以上のすべての自然数を素数候補としてリストアップします。次に、最小の候補である2から始めて、それぞれの素数候補の倍数をリストから除外していきます。除外されずに残った数はすべて素数です。

具体的には、2から順にその数の倍数をリストから除外していきます。例えば、2の倍数を除外した後、次に残った最小の数は3です。3の倍数を除外し、次に残った最小の数で倍数を除外していく作業を、指定された上限まで続けます。このプロセスを通じて、素数だけが篩い残されます。

# 初期リスト: 最初に、2から30までのすべての数をリストアップします。
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

# 2を残し、2の倍数を除外します。
2 3 _ 5 _ 7 _ 9 _  11  _ 13  _ 15  _ 17  _ 19  _ 21  _ 23  _ 25  _ 27  _ 29  _

# 3を残し、残りの3の倍数を除外します。
2 3 _ 5 _ 7 _ _ _  11  _ 13  _  _  _ 17  _ 19  _  _  _ 23  _  _  _  _  _ 29  _

Go言語における実装では、sieveというブール配列を使って素数候補を管理します。この配列の各要素は、対応するインデックスの数が素数候補であるかどうかを表します（trueは素数候補、falseは非素数）。最初に2以上のすべての数を素数候補としてtrueに設定し、その後、既知の素数の倍数をfalseに設定していきます。最終的にtrueのままのインデックスの数が実際の素数となります。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func Elatosthenes(limit int) []int {
    if limit < 2 {
		return []int{}
    }

    // 2以上の整数を素数候補として初期化
    sieve := make([]bool, limit+1)
    for i := 2; i <= limit; i++ {
        sieve[i] = true
    }

    // エラトステネスの篩の適用
    for p := 2; p*p <= limit; p++ {
        if sieve[p] {
		    // pの二乗より小さい数の倍数は、以前のステップで既に除外されている
            for multiple := p * p; multiple <= limit; multiple += p {
                sieve[multiple] = false
            }
        }
    }

    // 素数の抽出
    var primes []int
    for i := 2; i <= limit; i++ {
        if sieve[i] {
            primes = append(primes, i)
        }
    }

    return primes
}

最大公約数を求めるアルゴリズム

ユークリッド互徐法

ユークリッド互徐法とは最大公約数を求めるアルゴリズムです。 ある二つの値の最大公約数を求めるときに、割り算をした商と余りをさらに割り算していき、割り切れた時の値が最大公約数になります。

Scalaで実装すると下記のようになります。

1
2
3
4
5
6
7
8

val a = 3355
val b = 2379

def euclid (x: Int, y: Int): Int = {
    // 余りが0ならその値を、0でない場合は割った数と余りで再計算する
    if (x % y == 0) y else euclid(y , x % y)
}
println(euclid(a, b))

実行結果は下記のようになります。

61
文字列照合

Share