Complete the Sequence!

今年四月份的时候，我开始重新学起了 Haskell。按照往年的惯例，开始在 SPOJ 上刷题（严格来说不能叫刷，以我卑微的算法能力，一天能做掉一道题目已经是万幸了）。其实，我主要是把以前用别的语言做过的题目，再用 Haskell 做一遍。其中，有一道题 CMPLS - Complete the Sequence! 虽然，不是很难，但是其解题过程着实有趣，尤其是用 Haskell 的时候。

题目的大概意思是给定一个数列 P(n)以及前 S 项目, 求这个数列的后 C 项。其中数列的通项公式可表示为:

\begin{equation} P(n)=a_D.n^D+a_{D-1}.n^{D-1}+...+a_1.n+a_0 \end{equation}

上一次做这道题目的时候，我还在学 ruby 也就是 6 年前的样子。我重新翻看自己的解法的时候简直生不如死。代码是这样的。

 1: class Array
 2:   def const? n
 3:     1.upto(n) do |i|
 4:       return false if self[i]!=first
 5:     end
 6:     return true
 7:   end
 8:   def diff! n
 9:     0.upto(n-1) do |i|
10:       self[i]=self[i+1]-self[i]
11:     end
12:   end
13:   def computer n
14:     return Array.new(n,first) if const? size-1
15:     count=size-1
16:     while true
17:       diff!count
18:       count-=1
19:       break if const?count
20:     end
21:     n.times.inject(Array.new(n)) do |res,j|
22:       count.upto(size-2) do |i|
23:         self[i+1]+=self[i]
24:       end
25:       res[j]=last
26:       res
27:     end
28:   end
29: end
30: 
31: ss= gets.to_i.times.inject([]) do |s,j|
32:   n=gets.split[1].to_i
33:   s<<gets.split.map{|s| s.to_i}.computer(n).join(" ")
34: end
35: 
36: puts ss

在经过一段时间的读码之后，我开始有了一点思路。举个例子，输入序列是：1, 8, 27, 64, 125。也就是正整数的立方的数列。 \(P(n)=n^3\) 。后一个数减去前一个数得到一个新数列 7, 19, 37, 61。继续做前面的操作，获得数列 12, 18, 24。继续操作，获得数列 6, 6。终于我们得到了一个常数列。回看一下，倒数第二个数列是等差数列其通项公式为 \(P(n)=6+6n\) 。

 1  8 27 64 125
 7 19 37 61
12 18 24
 6  6

我把原来的数列命名为 \(A(n)\) ，相邻两项的差的数列设为 \(D(n)\) 。则有定义很容易得到以下结论:

\begin{equation} A(n)=A(n-1)+D(n-1) \end{equation}

而经过刚刚的操作我们发现似乎经过操作之后，最后能得到一个常数列。其实这点很好证明。假设 \(A(n)\) 的通项公式的最高次幂为 \(x\) ，那么相邻两数相减就可以把这个最高次幂消去，于是 \(D(n)\) 的通项公式就是最高次为 \(x-1\) 的多项式。如此操作下去就能将 \(n\) 的次方消去，最后剩下常数了。然后，在从常数列算出等差数列，从等差数列继续推算出高次数列。上面的 ruby 代码就是这两个过程。我这里把这两个过程分别叫做 seeds 和 series。seeds 算出从原始数列到各个差数列的首项，而 series 则反向从差数列推算出原始数列。这次我用 Haskell 来解这道题目。首先解决几个小问题。在 Haskell 中，如何表示一个常数列。这个很简单，在 GHC.List 包中有一个函数 repeat :: a -> [a]，比如 repeat 1, 就是 1,1,1,1...常数列。由于 Haskell 的懒惰特性，repeat 1 不会立即求值，只有等到需要的时候才会求值，比如 take 10 (repeat 1)，这个表达式只会求出数列的前 10 项，因为从第 11 项开始数列暂时不被使用，所以停止求值。然而我觉得使用 repeat 函数并不过瘾。可以用下面的表达式定义常数列。

ones :: [Int]
ones = 1 : ones

等差数列如何表示

odds :: [Int]
odds = 1 : map (+2) odds

-- or

odds = let twos = 2 : twos
       in 1 : zipWith (+) odds twos

第一种方法比较直白，用语言来表述就是，后一项等于前一项加 2。而第二种表达看上去有些啰嗦，我也用语言解释一下，twos 是一个常数列，odds 数列的每一项等于其前一项和在 twos 数列对应的项的和。把 twos 数列当成差数列，那么 odds 数列就是原数列。也就是说:

dn :: [Int]
dn = undefined

an :: [Int]
an = a1 : zipWith (+) an dn

有了这个两个表达式，就可以写 seeds 和 series 函数了。

 1: {-# OPTIONS_GHC -optc-O2 #-}
 2: 
 3: import Control.Monad
 4: 
 5: series :: [Int] -> [Int]
 6: series [x]    = let s = x : s in s
 7: series (x:xs) = let s = x : zipWith (+) (series xs) s in s
 8: 
 9: seeds :: [Int] -> [Int]
10: seeds xs@(x:ts) = if all (==x) ts
11:                   then [x]
12:                   else x : seeds (zipWith (-) ts xs)
13: 
14: cmpls :: Int -> Int -> [Int] -> [Int]
15: cmpls s c = take c . drop s . series . seeds
16: 
17: solveProblems :: [String] -> IO ()
18: solveProblems = foldM_ f []
19:   where f []     l = return . map read . words $ l
20:         f [s, c] l = putStrLn (unwords . map show $ cmpls s c (map read . words $ l))
21:                      >> return []
22: 
23: main :: IO ()
24: main = getContents >>= solveProblems . tail . lines

2016-07-09 2016-11-14 spoj, algorithm, haskell Shane Xu

Complete the Sequence!

Comments