アルゴリズムいろいろ

Erlang

404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10


プログラマーなのに名前すら知らなかったアルゴリズムがほとんどでした。なんてこったい。
有名なところは覚えておきたいなーと思ったので身に付けるために実装してみることにしました。

ユークリッドの互除法

２つの整数の最大公約数を求める手順です。

AとBの最大公約数は、Bと「AをBで割った余り」の最大公約数に等しい。

という法則を発見した人がいて、これを応用すると２つの数の最大公約数が簡単に求められるのだそうです。
詳しい方法がWikipediaに載ってたので、それを見ながらErlangで実装してみたら…

gcd(A, 0) -> A;
gcd(A, B) -> gcd(B, A rem B).

なんということでしょうー。
上に書いた

AとBの最大公約数は、Bと「AをBで割った余り」の最大公約数に等しい。

と

Aと0の最大公約数はA。

これ以外何も書いてない関数ができあがりました。これでちゃんと動いてるんだから自分でもびっくりです。


うおー。なんだかわからんがすごい。
ユークリッドさんがすごいのかErlangがすごいのかよくわからない。
よくわからないけどエラいものを見てしまったような気がする。
なんだかめちゃくちゃ興奮してるんだけど上手く説明できない。残念です。

エラトステネスのふるい

素数を漏れなく無駄なく求める手順。
自然数の集まりをふるいにかけて「倍数」を除いていけば素数だけが残るよねっていうスンポーです。
これもユークリッドさんのみたいにスポーンとシンプルに実装できたりするのかな。いやーんどうしようとかおかしな妄想をしてフガフガいいながら書いてました。

%% エラトステネスのふるい（N以下の素数を全部返す）
primes(N) -> sieve(lists:seq(2, N)).

% 素数の候補をふるいにかける
sieve(Nums) ->
  [Num|_] = Nums,
  Max = lists:last(Nums),
  if
    (Num * Num) > Max -> Nums;
    true -> [Num|sieve(reject_multiple(Nums, Num))]
  end.

% ListからNの倍数を除去する
reject_multiple(List, N) ->
  lists:filter(fun(X) -> X rem N /= 0 end, List).

なんか妄想してたのと違う…。

つづき

勢いに乗って全部実装しようと思ったのですが時間が足りませんでした。
っていうかニュートン法 - Wikipediaを見たら数式がいっぱい出てきて頭が爆発しました。
気力が尽きなければgistで続きを書いていこうと思います。

感想

関数型言語の入門とかチュートリアルとか読んでると、最初の例でいきなり微分方程式が出てきたり「Hello World」の次がいきなりクイックソートだったりで、数学とかコンピューター学をまともに勉強してこなかった人間にとっては何がなんだかさっぱり理解できないことだらけで悲しくなることが多いのですが、あれは別に初心者をいじめてるわけではなくて、関数型言語と数学が非常に相性のいい関係で、関数型言語の特徴を示すには数学の問題を解かせるプログラムとかが最適な場合が多いので、いつもああいう感じになってしまうのだなーと思いました。