斐波那契法(即贪心算法)

源程序

在“埃及分数(一)”中,我们讨论了斐波那契法(即贪心算法)。现在使用 Haskell 语言写一个程序来实现该算法吧,下面就是 fib.hs:

 1: import System.Environment
 2: import Data.Ratio
 3: 
 4: main = do
 5:   args <- getArgs
 6:   let x = (\[p, q] -> p % q) $ map read args
 7:   putStr $ (show x) ++ ": "
 8:   mapM_ (putStr . (++" ") . show) $ fib x
 9:   putStrLn ""
10: 
11: fib x
12:   | p == 1 = [denominator x]
13:   | otherwise =
14:     let q = (div (denominator x) p) + 1
15:     in q : fib (x - (1 % q))
16:   where p = numerator x

源程序分析

  • 第 1 行导入 System.Environment 模块,是因为第 5 行的 getArgs 函数属于该模块。
  • 第 2 行导入 Data.Ratio 模块,是因为本程序使用了 Rational 数据类型。
  • 第 5 行的 getArgs 函数用于获取命令行参数。
  • 第 6 行从命令行参数中解析出分数 x 。read 函数将字符串转换为所需的数据类型,这里是 Integer 类型。“%”用于将两个 Integer 类型构造为一个 Rational 类型。小括号中的 lambda 表达式作为一个匿名函数作用在 map read args 上,将 [Integer] 转换为 Rational 。
  • 第 7 行输出分数 x 本身。show 函数将任意类型(这里是 Rational 类型)转换为字符串。
  • 第 8 行调用稍后定义的 fib 函数使用斐波那契法将分数 x 展开为相异单位分数的和。
  • 第 11 至 16 行定义了 fib 函数。这是一个递归函数。该函数的类型是 Rational -> [Integer] 。
  • 第 16 行将分数 x 的分子赋值给 p 。
  • 第 12 行处理分子等于 1 的情况,这时分数 x 已经是单位分数了,直接将分母加到列表中返回就行了。
  • 第 13 至 15 行处理分子大于 1 的情况。
  • 第 14 行将分数 x 的分母除以分子所得的商加 1 后赋值给 q 。
  • 第 15 行用 x - 1/q 作为参数递归调用 fib 函数本身,然后将 q 添加到所得列表的最前面。

编译和运行

直接使用 runhaskell 解释器来运行:

$ runhaskell fib.hs 5 121
5 % 121: 25 757 763309 873960180913 1527612795642093418846225
$ runhaskell fib.hs 118 121
118 % 121: 2 3 8 60 4840

注意,在 Haskell 语言中,有理数(即分数)使用 Rational 数据类型表示,并且使用“%”分隔分子和分母。

当然,也可以使用 ghc 编译器编译后再运行:

$ ghc fib.hs
[1 of 1] Compiling Main             ( fib.hs, fib.o )
Linking fib ...
$ ./fib 101 414
101 % 414: 5 23 2070 

嗯,运行结果符合我们的预期。

计算单位分数的和

源程序

再写个 Haskell 语言程序来验算结果吧,下面就是 invSum.hs:

1: import System.Environment
2: import Data.Ratio
3: 
4: main = do
5:   args <- getArgs
6:   print $ sum $ map (1%) $ map read args

源程序分析

  • 这个程序主要功能都在第 6 行中实现。
  • 首先,使用 map read args 将 [String] 转换为 [Integer] 。
  • 其次,使用 map (1%) 将 [Integer] 转换为 [Rational],内容是该整数的倒数。“%”是需要两个参数的中缀函数,它将两个 Integer 参数分别作为分子和分母构成一个 Rational 。而“(1%)”是经过柯里化Currying)后成为只接受一个参数的函数,它把 Integer 参数求倒数得到一个 Rational 。
  • 再次,使用 sum 函数将 [Rational] 列表里的所有元素求和,得到一个 Rational 。
  • 最后,使用 print 函数将 Rational 打印出来。

运行

运行结果:

$ runhaskell invSum.hs 25 757 763309 873960180913 1527612795642093418846225
5 % 121
$ runhaskell invSum.hs 2 3 8 60 4840
118 % 121
$ runhaskell invSum.hs 5 23 2070
101 % 414

一切正常。

与 C 语言程序相比较

在“埃及分数(二)”中,有这两个程序的 C 语言版本。可以看出,Haskell 程序比相应的 C 语言程序要简短。在 C 语言程序中,显式地调用了 GNU MP 高精度算术库进行运算。而在 Haskell 语言程序中,使用了 Integer 和 Rational 数据类型进行运算,隐式地调用了 GNU MP 高精度算术库。

参考资料

  1. Wikipedia: Greedy algorithm for Egyptian fractions
  2. The Haskell Programming Language
  3. Haskell: Basic Libraries
  4. Haskell: Prelude: Integer
  5. Haskell: Prelude: Rational
  6. Haskell: Prelude: List operations
  7. Haskell: Data.Ratio

Haskell