haskell 基础题解（04）

最大公约数与最小公倍数

【题目】已知两个整数M，N，求它们的最大公约数和最小公倍数

先是用最笨的办法考虑。所谓最大公约数就是从大到小地找一个数，这个数能同时整除M和N。

gcd' :: Integral a => a -> a -> a
gcd' m n = 
  let c = min m n - 1
      st = [ x | x <- [c,c-1 .. 1], m `mod` x == 0 && n `mod` x == 0]
  in head st

main :: IO ()
main = do
  m <- readLn
  n <- readLn
  print $ gcd' m n
           

运行以后，分

两行

输入两个整数，程序会计算它们的 gcd。

这个算法取名为 gcd’，是因为标准库中已经提供了一个 gcd 了。

在有副作用的main函数中，故意用了个 readLn ，它会从一行中读取数据，关键是它类型是多态的（有多种可能性，可以是Int, String, 甚至自定义的复杂类型）。

Haskell 的多态是另一种强大，完全不同于面向对象中的多态机制。从这个例子中可以看到，它的多态是在

编译期

的多态，在程序通过编译后，多态的类型都确定下来了。

编译期多态的好处是：让编译器监督我们正确地使用（它与动态语言的只能在运行中发现问题形成鲜明的对比）。

再来个递归的高效解法，这个是我们国家引以为傲的古代数学成就（辗转相除法）。

gcd' a 0 = a
gcd' a b = gcd' b (a `mod` b)

main = do
  s <- getLine
  let [x,y] = words s 
  print $ gcd' (read x) (read y) 
           

这回运行程序后，需要在一行输入两个整数，空格分开。

真正算法只两行。a, b 大小顺序无所谓。这是数学的恐怖力量。

至于最小公倍数，也可以仿照完成。

但，也可以利用已有的成果，因为：

最 小 公 倍 数 = 两 数 乘 积 / 最 大 公 约 数 最小公倍数 = 两数乘积 / 最大公约数 最小公倍数=两数乘积/最大公约数

愿意证明的话，自已试试吧。