Haskell H99 Question 32
http://www.haskell.org/haskellwiki/99_questions/31_to_41
Haskellの練習問題H99の32問目。
最大公約数をとのことですが、ユークリッドの互除法を使えとの指示なので、wikipediaで勉強:
アルゴリズム
1. 入力を m, n (m ≧ n) とする。
2. n = 0 なら、 m を出力してアルゴリズムを終了する。
3. m を n で割った余りを新たに n とし、更に 元のnを新たにm とし 2. に戻る。
とりあえず素直にそのまま実装:
myGCD :: Int -> Int -> Int myGCD x y | abs x >= abs y = myGCDin x y | otherwise = myGCDin y x where myGCDin m n | mod m n == 0 = abs n | otherwise = myGCDin m (mod m n)
m >= n でないといけないとのことなので、最初に判定をして、内部の関数に引き渡し、m >= n を前提に残りのアルゴリズムを記述。
何のひねりもありません。
追加で負のケースに対応するため、絶対値での判定に変更(abs)。
模範解答を見てみたら若干違うアルゴリズムを書いていてすっきりしていた。
http://www.haskell.org/haskellwiki/99_questions/Solutions/32