Search on the blog

2011年6月17日金曜日

Haskellで有名アルゴリズム実装(1)

「Haskellで有名アルゴリズムを実装しよう。」企画をスタートした。三日坊主にならないように注意したい。
とりあえず、今日は簡単なやつから。

最大公約数(GCD)と最小公倍数(LCM)を求めるプログラムをHaskellで書きます。

 まず、GCD。
gcd' :: Integer -> Integer -> Integer
gcd' a 0 = a
gcd' a b = gcd' b (a `mod` b)

 実は、標準ライブラリにgcdという関数があります。自作したものはgcd'としました。
Haskellには整数値を扱う型が2つあります。IntとIntegerです。Intは32bit符号付き整数、Integerは多倍長整数です。多倍長整数が標準で使えるので便利です。
 あと、注目すべきところは、パターンマッチです。引数の”値”によって、同じ関数でも異なる定義ができます。

 次に、LCM。LCMはGCDを使って計算することができます。
lcm' :: Integer -> Integer -> Integer
lcm' a b = a * b `quot` (gcd' a b)

lcmも標準ライブラリにあるので、lcm'と関数名を付けました。
今日はここまで。Call it a day.

0 件のコメント:

コメントを投稿