アルゴリズムとは

in  

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

アルゴリズム

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

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

エラトステネスの篩

エラトステネスの篩とは素数を求めるアルゴリズムです。 2の倍数は素数ではないので、偶数を除いた奇数の集合に対して素数でないものをふるい落としていきます。 素数でないものとは合成数(2つ以上の素数の積で表せる数)になります。

下記のPythonでの実装例は53までの整数のうち素数を出力するプログラムです。 奇数のリストに対して小さい数から順番に余りが0になる値を消していきます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def elatosthenes(limit: int):
    # 0, 1 は素数ではない
    if limit < 2:
        return []

    # 2と奇数のリストを作る
    ret = [2] + [i for i in range (3, limit + 1,  2)]
    for number in range (3, limit + 1,  2):
        for sieve in range (number**2, limit + 1, number):
            ret = list(filter(lambda x: (x % sieve != 0), ret))
    return ret

if __name__ == "__main__":
    print(elatosthenes(112))

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

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]

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

ユークリッド互徐法

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

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