引言

《Haskell趣学指南》第20页:

Haskell-p20

在 Haskell 中,最常用的类型是整数类型,共有两种:

  • Int 是有界的,它的值一定界于最小值和最大值之间。在 64-bit 机器上,最小值一般为 -263,最大值为 263 - 1 。
  • Integer 是无界的,这就意味着可以用它存放非常非常大的数,不过它的效率不如 Int 高。

这两个整数类型都属于 Integral 类型类。由于Haskell 支持类型推导,我们在程序中可以不必指明具体的类型。

学习一门新的编程语言的最好方法是动手写一些程序。那么,让我们来使用 Haskell 求解 ACM 题吧,这些题目均来源于 Sphere Online Judge (SPOJ) 网站。

Small factorials

这是一道求解 100 以内的数的阶乘的题目,主要内容所下所示:

Small factorials: You are asked to calculate factorials of some small positive integers.

Input: An integer t, 1<=t<=100, denoting the number of testcases, followed by t lines, each containing a single integer n, 1<=n<=100.

Output: For each integer n given at input, display a line with the value of n!

Time limit: 1s

Source limit: 2000B

也就是说,要求在一秒之内计算出大约 100 个 100 以内的数的阶乘。注意阶乘增长是非常快的,100! 就有 158 位十进制数字。下面就是 Haskell 程序:

1: main = do
2:   n <- getLine
3:   x <- sequence $ replicate (read n) getLine
4:   mapM_ (print . product . (flip take [1..]) . read) x

在该网站提交后,结果是“accepted”,运行时间是 0.01 秒,内存占用为 3.6 MB。程序分析如下:

  • 第 2 行使用 getLine 函数读入要计算的除乘的个数。
  • 第 3 行的 read 函数将字符串 n 转换为整数,然后使用 sequence 和 getLine 函数一次性读入所有要计算的数到列表 x 中。
  • 第 4 行完成所有的计算工作。
  • 使用 mapM_ 函数逐个处理列表 x 中的元素。
  • read 函数将字符串转换为整数,假设为 z。
  • (flip take [1..]) 得到列表 [1..z] 。
  • product 函数将列表 [1..z] 中所有元素相乘,得到 z! 。
  • print 函数输出计算结果。

Factorial

这道题目的主要内容所下所示:

Factorial:

The most important part of a GSM network is so called Base Transceiver Station (BTS). These transceivers form the areas called cells(this term gave the name to the cellular phone) and every phone connects to the BTS with the strongest signal (in a little simplified view). Of course, BTSes need some attention and technicians need to check their function periodically.

ACM technicians faced a very interesting problem recently. Given a set of BTSes to visit, they needed to find the shortest path to visit all of the given points and return back to the central company building. Programmers have spent several months studying this problem but with no results. They were unable to find the solution fast enough. After a long time, one of the programmers found this problem in a conference article. Unfortunately, he found that the problem is so called "Travelling Salesman Problem" and it is very hard to solve. If we have N BTSes to be visited, we can visit them in any order, giving us N! possibilities to examine. The function expressing that number is called factorial and can be computed as a product 1.2.3.4....N. The number is very high even for a relatively small N.

The programmers understood they had no chance to solve the problem. But because they have already received the research grant from the government, they needed to continue with their studies and produce at least someresults. So they started to study behaviour of the factorial function.

For example, they defined the function Z. For any positive integer N, Z(N) is the number of zeros at the end of the decimal form of number N!. They noticed that this function never decreases. If we have two numbers N1

Input: There is a single positive integer T on the first line of input (equal to about 100,000). It stands for the number of numbers to follow. Then there are T lines, each containing exactly one positive integer number N, 1 <= N <= 1,000,000,000.

Output: For every number N, output a single line containing the single non-negative integer Z(N).

Time limit: 6s

这道题目讲述了一个在移动通信网络中寻找通信基站的最短路径的故事,在这个故事中程序员发现该算法的复杂度是 O(n!) 的,所以无法得到有效的解。由于他们已经收了政府的钱,所以必须至少给出一些结果。因此他们就转而研究整数的阶乘末尾有几个零问题。这道题目要求计算指定的正整数的阶乘末尾有多少个零。但是要计算的数大约有十万个,而每个数可能达到十亿,并且需要在六秒之内计算完毕。天哪,阶乘函数可是增长得非常快的,十亿的阶乘有多少位十进制数字?我晕了!其实,这是一个经典问题,并不需要用到大整数,使用普通的 Int 就足够了:

 1: import Control.Monad
 2: 
 3: main = do
 4:   n <- getLine
 5:   forM_ [1 .. read n] (\_ -> do
 6:     x <- getLine
 7:     print $ (tailzeros . read) x
 8:     )
 9: 
10: tailzeros 0 = 0
11: tailzeros n = let m = div n 5 in m + tailzeros m

在该网站提交后,结果是“accepted”,运行时间是 3.80 秒,内存占用为 3.6 MB。程序分析如下:

  • 第 1 行导入 Control.Monad 模块是为了第 5 行的 forM_ 函数。
  • 第 4 行使用 getLine 函数读入要计算的阶乘的个数。
  • 第 5 行使用 forM_ 函数循环地进行处理。
  • 第 6 行使用 getLine 函数读入要计算的数。
  • 第 7 行使用随后定义的 tailzeros 函数计算某个数的阶乘的末尾有多少个零。
  • 第 10 行处理 tailzeros 函数的递归的边界条件,表明 0! 末尾有 0 个 0 。
  • 第 11 行处理 n > 0 的情况,递归地调用 tailzeros 函数本身来计算。

Not So Fast Multiplication

这是一道大整数乘法的题目,主要内容如下所示:

Not So Fast Multiplication: Multiply the given numbers.

Input:
n [the number of multiplications <= 1,000]
a b [numbers to multiply (at most 10,000 decimal digits each)]
Text grouped in [ ] does not appear in the input file.

Output: The results of multiplications.

Warning: large Input/Output data, be careful with certain languages

Time limit: 12s

也就是说,要求在十二秒之内计算大约一千道的整数乘法,而参数与运算的每个整数大约都有一万个十进制数字。Haskell 程序如下所示:

1: import Control.Monad
2: 
3: main = do
4:   n <- getLine
5:   forM_ [1 .. read n] (\_ -> do
6:     x <- getLine
7:     print $ ((\[a, b] -> a * b) . (map read) . words) x
8:     )

在该网站提交,结果是“accepted”。运行时间是 6.44 秒,内存占用为 5.6 MB。该程序的主要部分是在第 7 行,分析如下:

  • 首先使用 words 函数将使用空格分隔的字符串转换为列表。
  • (map read) 将这个字符串列表转换为整数列表。
  • 然后使用 lambda 表达式将列表中的两个元素相乘。
  • 最后使用 print 函数将乘积输出。

Adding Reversed Numbers

这道题目的主要内容所下所示:

Adding Reversed Numbers:

The Antique Comedians of Malidinesia prefer comedies to tragedies. Unfortunately, most of the ancient plays are tragedies. Therefore the dramatic advisor of ACM has decided to transfigure some tragedies into comedies. Obviously, this work is very hard because the basic sense of the play must be kept intact, although all the things change to their opposites. For example the numbers: if any number appears in the tragedy, it must be converted to its reversed form before being accepted into the comedy play.

Reversed number is a number written in arabic numerals but the order of digits is reversed. The first digit becomes last and vice versa. For example, if the main hero had 1245 strawberries in the tragedy, he has 5421 of them now. Note that all the leading zeros are omitted. That means if the number ends with a zero, the zero is lost by reversing (e.g. 1200 gives 21). Also note that the reversed number never has any trailing zeros.

ACM needs to calculate with reversed numbers. Your task is to add two reversed numbers and output their reversed sum. Of course, the result is not unique because any particular number is a reversed form of several numbers (e.g. 21 could be 12, 120 or 1200 before reversing). Thus we must assume that no zeros were lost by reversing (e.g. assume that the original number was 12).

Input: The input consists of N cases (equal to about 10,000). The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly one line with two positive integers separated by space. These are the reversed numbers you are to add.

Output: For each case, print exactly one line containing only one integer - the reversed sum of two reversed numbers. Omit any leading zeros in the output.

Time limit: 5s

讲述古代的洗具和杯具的故事,为了把杯具转换为洗具,需要把一些(很大的)整数倒转过来。题目给出大约一万对已经倒转了整数,要求计算出每一对整数的和,然后再倒转。好了,下面就是我们的 Haskell 程序:

 1: import Control.Monad
 2: 
 3: main = do
 4:   n <- getLine
 5:   forM_ [1 .. read n] (\_ -> do
 6:     x <- getLine
 7:     print $ ((\[a, b] -> rev $ rev a + rev b) . (map read) . words) x
 8:     )
 9: 
10: rev = read . reverse . show

在该网站提交后,运行结果是“accepted”,运行时间是 1.65 秒,内存占用为 3.6 MB。程序分析如下:

  • 第 7 行进行主要的计算,这和上一小节的程序的第 7 行差不多,只是其中的 lambda 表达式不同。那里是计算乘法,这里是计算倒过来的加法。
  • 第 10 行的 rev 函数将一个整数倒过来。首先使用 show 函数将整数转换为字符串,然后再使用 reverse 函数将字符串倒过来,最后使用 read 函数将字符串转换回整数。

Julka

这道题目的主要内容如下所示:

Julka:

Julka surprised her teacher at preschool by solving the following riddle:

Klaudia and Natalia have 10 apples together, but Klaudia has two apples more than Natalia. How many apples does each of he girls have?

Julka said without thinking: Klaudia has 6 apples and Natalia 4 apples. The teacher tried to check if Julka's answer wasn't accidental and repeated the riddle every time increasing the numbers. Every time Julka answered correctly. The surprised teacher wanted to continue questioning Julka, but with big numbers she could't solve the riddle fast enough herself. Help the teacher and write a program which will give her the right answers.

Task:Write a program which

reads from standard input the number of apples the girls have together and how many more apples Klaudia has, counts the number of apples belonging to Klaudia and the number of apples belonging to Natalia, writes the outcome to standard output

Input: Ten test cases (given one under another, you have to process all!). Every test case consists of two lines. The first line says how many apples both girls have together. The second line says how many more apples Klaudia has. Both numbers are positive integers. It is known that both girls have no more than 10100 (1 and 100 zeros) apples together. As you can see apples can be very small.

Output: For every test case your program should output two lines. The first line should contain the number of apples belonging to Klaudia. The second line should contain the number of apples belonging to Natalia.

Time limit: 2s

这次讲述几个小女孩和苹果的故事。要求我们计算的大整数大约有 100 个十进制数字。Haskell 程序如下所示:

 1: import Control.Monad
 2: 
 3: main = do
 4:   forM_ [1..10] (\_ -> do
 5:     x <- sequence $ replicate 2 getLine
 6:     print $ f (+) x
 7:     print $ f (-) x
 8:     )
 9: 
10: f g = (\[a, b] -> div (g a b) 2) . (map read)

在该网站提交后,运行结果是“accepted”,运行时间是 0.00 秒,内存占用为 3.6 MB。程序分析如下:

  • 第 4 行直接进行 10 次循环,因为这次题目的输入固定为 20 行,分为 10 组。
  • 第 5 行使用 sequence 和 getLine 函数一次性读入两行到列表 x 中。
  • 第 6 行和第 7 行分别调用随后定义的 f 函数进行计算,一次是加法计算,一次是减法计算。注意,(+) 和 (-) 函数作为参数传入 f 函数。
  • 第 10 行就是进行具体计算的 f 函数了。其中的参数 g 的类型是函数,所以 f 是个高阶函数。

后记

这些题目的其他语言解法,可参阅我 2010 年 7 月发表在博客园的文章:大整数和ACM题。那篇文章中使用了 Ruby、F#、C# 等编程语言。


Haskell