Problem 4: Largest palindrome product
Problem 4
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
第一个解答
这道题目非常简单，就是要找出最大的由两个三位数的乘积构成的回文数。在 Haskell 交互环境暴力破解：
Prelude> maximum [ n | a <- [100..999], b <- [a..999], let n = a*b, (\x -> x == reverse x) $ show n ]
在上述程序中：
-
假设这两个三位数分别是 a 和 b，那么 a 的取值范围就是 [100..999]，由于乘法交换律，b 的取值范围可设置为 [a..999]。
-
设置 n 为这两个三位数的乘积，show n 将 n 转换为字符串，reverse x 将字符串 x 倒转，所以这个 lamda 表达式就是判断 n 是否为回文数。
-
最后使用 maximum 函数得到这个回文数列表中的最大的元素。
将上述程序中的 maximum 改为 length，可以得到列表的长度为 1239，即两个三位数的乘积可以用 1239 种方式（不计两个三位数的次序）构成回文数。例如，163*627 = 102201 和 209*489 = 102201 算两种不同的方式，而 139*759 = 105501 和 759*139 = 105501 不算两种不同的方式。
将上述程序中的 maximum 改为 length $ nub，可以得到列表的长度为 655，即两个三位数的乘积可以构成 655 个不同的回文数。这里的 nub 函数的作用是删除列表中的重复元素，只留下不相同的元素。
将上述程序的中的 [ n | 改为 [ (n,a,b) |，就不但可以知道最大的由两个三位的乘积的构成的回文数是什么，同时也知道了这两个三位数是什么。
第二个解答
假设所求的回文数 n 的构成形式是 xyzzyx，那么：
- n = 100000x + 10000y + 1000z + 100z + 10y + x = 100001x + 10010y + 1100z
因此有以下的 Haskell 程序：
Prelude> maximum [ n | x <- [1..9], y <- [0..9], z <- [0..9], n <- [100001*x + 10010*y + 1100*z], not $ null [ a | a <- [100..999], mod n a == 0 && div n a < 1000 ] ]
在上述程序中：
-
x 的取值范围是 [1..9]，y 和 z 的取值范围都是 [0..9]。n 就是由上述公式计算的所有可能的回文数。
-
在最右边的列表中，a 是一个三位数，取值范围是 [100..999]，mod n a == 0 要求 a 能够整除 n，然后 div n a < 1000 保证了 n 的另外一个因数也是三位数。
-
not $ null 筛选出非空的列表，也就保证了 n 这个回文数是由两个三位数的乘积构成的。例如，回文数 997799 = 11*90709，就不是两个三位数的乘积。
-
最后使用 maximum 得到这个回文数列表中的最大元素。
将上述程序中的 maximum 改为 length，可以得到列表的长度为 279，即两个三位数的乘积可以构成 279 个不同的六位数的回文数。前面讲过：两个三位数的乘积可以构成 655 个不同的回文数。也就是说，这 655 个回文数中有 279 个是六位数，其余 376 个是五位数。
谁更快
第一个解答简单、直接，第二个解答稍微复杂一点。不仔细分析，还不好说哪个解答运行速度更快。那么直接使用 Haskell 编译器 ghc 分别编译这两个程序，然后使用 Linux 的 time 命令计时。得到的结果是，第一个解答用时 0.161 秒，第二个解答用时 0.104 秒。
投机取巧的优化
如果我们相信两个不小于 900 的三位数的乘积可以构成回文数，那么第一个解答中的 a <- [100..999] 可以改为 a <- [900..999]。这样，只需要 0.006 秒就可以算出答案。
如果我们相信形如 9yzzy9 这样的回文数可以由两个三位数的乘积构成，那么第二个解答中的 x <- [1..9] 就可以改为 x <- [9]。这样，只需要 0.017 秒就可以算出答案。
第二个程序的改进
Prelude> head [ n | x <- [9,8..1], y <- [9,8..0], z <- [9,8..0], n <- [100001*x + 10010*y + 1100*z], not $ null [ m | m <- [100..999], mod n m == 0 && div n m < 1000 ] ]
改变如下：
-
将 x <- [1..9], y <-[0..9], z <- [0..9] 改为 x <- [9,8..1], y <- [9,8..0], z <- [9,8..0]，即从正算改为倒算。
-
最左边的 maximum 函数改为 head 函数。
注意，如果只做第一点改动，新程序的运行时间和旧程序相同，没有变化。这是因为从正算改为倒算，都是要遍历这些数，运算量没有变化。而第二点改动是最关键的，Haskell 的 head 函数遇到列表中满足条件的第一个数就停止计算，输出结果，所以运行时间大大缩短，从 0.104 秒减少到 0.019 秒。
第一个程序的改进
Prelude> fst $ last $ takeWhile (\(n,x) -> n < x) $ scanl1 (\(z,_) (n,x) -> (max z n,x)) $ [ (n,a^2) | a <- [999,998..100], b <- [a,a-1..100], let n = a*b, (\x -> x == reverse x) $ show n ]
在上述程序中：
-
假设这两个三位数分别是 a 和 b，将 a 设置为从 999 下降到 100，将 b 设置为从 a 下降到 100。
-
设置 n 为这两个三位数的乘积，show n 将 n 转换为字符串，reverse x 将字符串 x 倒转，所以这个 lamda 表达式就是判断 n 是否为回文数。
-
得到的列表的元素是元组 (n,a^2)，其中 n 是所求的回文数，a2 用于判断何时停止计算，以节省时间。
-
scanl1 函数生成到目前为止最大的回文数和 a2 构成的元组构成的列表。即：将列表 [ (n, a^2) ] 变换为列表 [ (max n, a^2) ]。
-
takeWhile 函数用来过滤列表，停止于列表中最后一个最大回文数小于 a2 的元素。此时，程序将终止，不再继续计算，这就节省了时间。
-
last 函数取得该列表的最后一个元素，该元素是一个元组。
-
fst 函数取得该元组的第一个元素，就是所求的最大的回文数。
新程序运行时间大大缩短，从 0.161 秒减少到 0.022 秒。
改进的硬道理
如果将上述程序最左边的 fst $ last 改为 length，可以得到列表长度为 54，这比旧程序的列表长度 1239 小多了，这就是新程序比旧程序快得多的原因。
如果将上述程序最左边的 fst $ last $ 删除，可以得到这个长度为 54 的列表的具体内容：
[(580085,990025),(580085,990025),(906609,986049),(906609,982081),(906609,974169),(906609,974169),(906609,964324),(906609,958441),(906609,958441),(906609,958441),(906609,958441),(906609,958441),(906609,958441),(906609,958441),(906609,958441),(906609,956484),(906609,956484),(906609,954529),(906609,950625),(906609,948676),(906609,942841),(906609,937024),(906609,937024),(906609,937024),(906609,937024),(906609,937024),(906609,937024),(906609,937024),(906609,937024),(906609,937024),(906609,933156),(906609,933156),(906609,929296),(906609,927369),(906609,925444),(906609,925444),(906609,925444),(906609,925444),(906609,923521),(906609,919681),(906609,917764),(906609,915849),(906609,915849),(906609,915849),(906609,915849),(906609,915849),(906609,915849),(906609,915849),(906609,915849),(906609,915849),(906609,915849),(906609,912025),(906609,908209),(906609,908209)]
可以看出，最大的回文数在列表的第 3 项已经出现了，但是我们需要计算到第 55 项才知道以后没有更大的回文数了。
只保留上述程序的右半边，并稍做修改：
Prelude> take 55 [ (n,a,b,a^2) | a <- [999,998..100], b <- [a,a-1..100], let n = a*b, (\x -> x == reverse x) $ show n ]
运行结果：
[(580085,995,583,990025),(514415,995,517,990025),(906609,993,913,986049),(119911,991,121,982081),(282282,987,286,974169),(141141,987,143,974169),(853358,982,869,964324),(650056,979,664,958441),(601106,979,614,958441),(592295,979,605,958441),(543345,979,555,958441),(485584,979,496,958441),(436634,979,446,958441),(378873,979,387,958441),(329923,979,337,958441),(408804,978,418,956484),(204402,978,209,956484),(623326,977,638,954529),(525525,975,539,950625),(299992,974,308,948676),(469964,971,484,942841),(886688,968,916,937024),(804408,968,831,937024),(698896,968,722,937024),(631136,968,652,937024),(616616,968,637,937024),(443344,968,458,937024),(428824,968,443,937024),(270072,968,279,937024),(255552,968,264,937024),(828828,966,858,933156),(414414,966,429,933156),(487784,964,506,929296),(180081,963,187,927369),(888888,962,924,925444),(666666,962,693,925444),(444444,962,462,925444),(222222,962,231,925444),(348843,961,363,923521),(770077,959,803,919681),(653356,958,682,917764),(855558,957,894,915849),(807708,957,844,915849),(696696,957,728,915849),(648846,957,678,915849),(531135,957,555,915849),(489984,957,512,915849),(372273,957,389,915849),(324423,957,339,915849),(165561,957,173,915849),(117711,957,123,915849),(577775,955,605,912025),(723327,953,759,908209),(649946,953,682,908209),(272272,952,286,906304)]
现在列表的元素是个四元组，这个四元组的第一个元素是回文数（n），第二个元素（a）和第三个元素（b）的乘积构成第一个元素（n），第四个元素是第二个元素的平方（a2）。这个列表的第 55 项在前面的程序中就被扔掉了，因为 a2 已经小于要寻找的最大回文数了，后面不可能出现更大回文数了。仔细分析这个输出结果，可以看出这个程序的运行过程，理解其工作原理。
另外还可参阅：004_overview.pdf。
