人気ブログランキング | 話題のタグを見る

ユークリッドの互除法

Haskell でユークリッドの互除法をプログラムしてみた。

まず関数の名前を euclid にした。euclid は引数 m と n をとる。

euclid :: Int -> Int -> Int
euclid m n

まず m が n より小さいときは m と n を交換する。

  | m < n = euclid n m

n が0のときは、mが求める最大公約数なのでそれを戻り値として戻す。

  | n == 0 = m

それ以外は、m のかわりに n をとり、n の代わりに m を n で割った余りをとる。

  | otherwise euclid n (mod m n)

これでプログラムはできあがり。完成したのが次のプログラム。

euclid :: Int -> Int -> Int
euclid m n
  | m < n = euclid n m
  | n == 0 = m
  | otherwise = euclid n (mod m n)

実行例

Main> euclid 30 42
6

最大公約数を求める関数は gcd という名前で Prelude に標準でついている。

Main> gcd 30 42
6

ちなみに最小公倍数は lcm
by tnomura9 | 2011-06-06 20:32 | Haskell | Comments(0)
<< ピタゴラス数の作り方 パスカルの三角形を作ってみた >>