最大公約数を求める
小さい作業を積み重ねていく
その1：公式を使わずにやってみる。
- 余りの計算はrem関数を使う。
Prelude> 5 % 3 <interactive>:9:3: Not in scope: `%' Prelude> 5 / 3 1.6666666666666667 Prelude> 5 `rem` 3 2 Prelude> 5 `rem` 1 0 Prelude> 5 `rem` 5 0 Prelude> :t rem rem :: Integral a => a -> a -> a Prelude> rem 5 2 1
- 数を決めたときに、その数までの数で余りを求める。
Prelude> map (rem 5) [1..5] [0,1,2,1,0] Prelude> (\x -> map (rem x) [1..x]) 5 [0,1,2,1,0]
- 上の余りがゼロになる数が、ある数を決めたときの約数となる。
Prelude> filter (\x -> rem 5 x == 0) [1..5] [1,5]
- ここまでをまとめてみると
Prelude> (\y -> (filter (\x -> rem y x == 0) [1..y]) ) 5 [1,5] Prelude> (\y -> (filter (\x -> rem y x == 0) [1..y]) ) 10 [1,2,5,10] Prelude> (\y -> (filter (\x -> rem y x == 0) [1..y]) ) 20 [1,2,4,5,10,20]
- リストが２つあったときに、等しい値を求めたい。
[1,5] -> [1,2,5,10] -> [1,5]
の用なことがしたい。これのmaxをとれば、最大公約数が求まる。
Prelude> let a = (\y -> (filter (\x -> rem y x == 0) [1..y]) ) 20 Prelude> let b = (\y -> (filter (\x -> rem y x == 0) [1..y]) ) 15 Prelude> a [1,2,4,5,10,20] Prelude> b [1,3,5,15]
を用意しておいて、リスト内表記を使ってみる。
Prelude> [a0 | a0 <- a , b0 <- b] [1,1,1,1,2,2,2,2,4,4,4,4,5,5,5,5,10,10,10,10,20,20,20,20] Prelude> [a0 | a0 <- a , b0 <- b, a0 == b0] [1,5]
- リストのmaxをもとめる。
Prelude> foldr1 max [2,8,4,1] 8
- ここまでを一旦まとめてみると
Prelude> let a = (\y -> (filter (\x -> rem y x == 0) [1..y]) ) 20 Prelude> let b = (\y -> (filter (\x -> rem y x == 0) [1..y]) ) 15 Prelude> foldr1 max [a0 | a0 <- a , b0 <- b, a0 == b0] 5
なんか出来てるっぽい。
- これをソースコードにまとめると。
------------ -- gcd ------------ divisor :: Int -> [Int] divisor n = filter (\x -> rem n x == 0) [1..n] commonList :: [Int] -> [Int] -> [Int] commonList a b = [a0 | a0 <- a , b0 <- b, a0 == b0] cd :: Int -> Int -> [Int] cd a b = commonList (divisor a) (divisor b) gcd :: Int -> Int -> Int gcd a b = foldl1 max $ cd a b
Prelude> :l moku01.hs [1 of 1] Compiling Main ( moku01.hs, interpreted ) Ok, modules loaded: Main. *Main> gcd 20 15 5 *Main>
- すこしリファクタリングしてみる。
------------ -- gcd ------------ divisor :: Int -> [Int] -- divisor n = filter (\x -> rem n x == 0) [1..n] divisor n = filter (\x -> rem n x == 0) [1..(div n 2)] -- commonList :: [Int] -> [Int] -> [Int] commonList :: Eq a => [a] -> [a] -> [a] commonList a b = [a0 | a0 <- a , b0 <- b, a0 == b0] cd :: Int -> Int -> [Int] cd a b = commonList (divisor a) (divisor b) gcd :: Int -> Int -> Int gcd a b = foldl1 max $ cd a b
その2：公式を使う
--- --- gcm --- gcm :: Int -> Int -> Int gcm a b | a == b = a | a > b = gcm (a -b) b | otherwise = gcm a (b-a)
*Main> gcm 196 42 14
その3：公式を使う
--- --- Euclidean Algorithm --- https://ja.wikipedia.org/wiki/ユークリッドの互除法 --- gcm :: Int -> Int -> Int gcm a b | a >= b && rem a b == 0 = b | rem b a == 0 = a | otherwise = gcm b (rem a b)
