読者です 読者をやめる 読者になる 読者になる

IT練習ノート

IT関連で調べたこと(実際は嵌ったこと)を書いています。

最大公約数を求める

小さい作業を積み重ねていく

その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]
  • リストが2つあったときに、等しい値を求めたい。
[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)