今天下午收到高宇涵老师的寄来的《程序员的算法趣题》,这本书的第 1 题是回文十进制数

求用十进制、二进制、八进制表示都是回文数的所有数字中,大于十进制数 10 的最小值。

书中的解题思路是:

因为是二进制的回文数,所以如果最低位是 0,那么相应地最高位也是 0。但是,以 0 开头肯定是不恰当的,由此可知最低位为 1。

如果用二进制表示时最低位为 1,那这个数一定是奇数,因此只考虑奇数的情况就可以。接下来可以简单地编写程序,从 10 的下一个数字 11 开始,按顺序搜索。

书中使用 Ruby 和 JavaScript 编写程序求解,如果使用 Haskell 编写程序求解:

import Data.Digits ( digitsRev )
main = print $ head $ filter (\n -> and [(\a -> a ==
  reverse a) $ digitsRev b n | b <- [10,8,2]]) [11,13..]

这个程序运行 0.01 秒后,得到答案:

58510 = 11118 = 10010010012

进阶

书中的算法对于这个问题是恰当的,但是如果要寻找更大的满足要求的数,就太慢了。我们可以事先构造出十进制奇回文数,以加快寻找速度。由此,我使用 Haskell 语言编写以下程序:

import Data.Digits ( digitsRev )
main = print $ concat [filter (\n -> and [(\a -> a == reverse a) $
  digitsRev b n | b <- [2,8]]) [read $ x : s ++ y ++ reverse s ++ [x]
  | x <- "13579", s <- if n /= 0 then [replicate (n - length t) '0'
  ++ t | i <- [0 .. 10^n-1], let t = show i] else [""], y <- if z
  then map show [0..9] else [""]] | n <- [0..3], z <- [False, True]]

简要说明:

  • 第 2 至 3 行检查所给的十进制奇回文数是不是二进制和八进制回文数。
  • 最后一行 z = False 时生成 xabccbax 形状的十进制奇回文数,x 是奇数(见第 4 行)。
  • 最后一行 z = True 时生成 xabcycbax 形状的十进制奇回文数,第 4 行的 s 就是"abc" 。
  • 最后一行的 n 决定生成的十进制奇回文数的位数,共 2n+2 (z = False) 或 2n+3 (z = True) 位。

在这个程序中的最后一行中,n 从 0 至 3,用于在 2 位至 9 位的十进制奇回文数中寻找。运行这个程序,瞬间(用时 0.4 秒)得到:

71984891710 = 52720027258 = 1010101110100000000101110101012

但是,我没有找到更大的满足要求的数。不知道是否还存在这样的数。