P93 - 算术谜题
An arithmetic puzzle
官方模块：
Problems.P93核心函数：arithmeticPuzzle
题目描述
保持数字顺序，在相邻数字之间插入 + - * / = 和必要括号，使等号两侧按有理数运算后相等。等号恰好出现一次，不能除以零。
表达式生成
方法一：递归枚举区间切分
1import Data.List (nub)
2import Data.Ratio ((%))
3
4data Expr = Expr Rational String
5
6expressions :: [Integer] -> [Expr]
7expressions [] = []
8expressions [n] = [Expr (n % 1) (show n)]
9expressions numbers = concat
10 [combine left right
11 | split <- [1 .. length numbers - 1]
12 , left <- expressions (take split numbers)
13 , right <- expressions (drop split numbers)]
14
15combine (Expr a sa) (Expr b sb) =
16 [Expr (a+b) (paren sa "+" sb),
17 Expr (a-b) (paren sa "-" sb),
18 Expr (a*b) (paren sa "*" sb)]
19 ++ [Expr (a/b) (paren sa "/" sb) | b /= 0]
20 where paren l op r = "(" ++ l ++ op ++ r ++ ")"
构造等式
1arithmeticPuzzle :: [Integer] -> [String]
2arithmeticPuzzle numbers = nub
3 [strip l ++ " = " ++ strip r
4 | split <- [1 .. length numbers - 1]
5 , Expr lv l <- expressions (take split numbers)
6 , Expr rv r <- expressions (drop split numbers)
7 , lv == rv]
8 where
9 strip text
10 | length text >= 2 && head text == '(' && last text == ')' = init (tail text)
11 | otherwise = text
为了让求值语义完全明确，这个实现保留了一些非必要括号；可在展示层根据运算符优先级进一步化简，不影响求解核心。
方法二：区间动态规划
1import Data.Array (Array, (!), array)
2
3arithmeticPuzzleDP :: [Integer] -> [String]
4arithmeticPuzzleDP numbers = nub
5 [strip leftText ++ " = " ++ strip rightText
6 | split <- [1 .. length numbers - 1]
7 , Expr leftValue leftText <- table ! (0, split)
8 , Expr rightValue rightText <- table ! (split, length numbers)
9 , leftValue == rightValue]
10 where
11 table :: Array (Int, Int) [Expr]
12 table = array ((0, 1), (length numbers - 1, length numbers))
13 [((start, end), build start end)
14 | width <- [1..length numbers]
15 , start <- [0..length numbers - width]
16 , let end = start + width]
17
18 build start end
19 | end == start + 1 =
20 [Expr (numbers !! start % 1) (show (numbers !! start))]
21 | otherwise = concat
22 [combine left right
23 | split <- [start + 1 .. end - 1]
24 , left <- table ! (start, split)
25 , right <- table ! (split, end)]
26
27 strip text
28 | length text >= 2 && head text == '(' && last text == ')' =
29 init (tail text)
30 | otherwise = text
递归版本会在不同等号位置和括号结构中重复计算相同数字区间。动态规划表以半开区间 (start,end) 为键，每个区间的所有表达式只生成一次，再被更大区间复用。
方法对比
| 方法 | 子区间结果 |
|---|---|
| 递归枚举 | 每次遇到都重新生成 |
| 区间 DP | 缓存在数组中复用 |
测试
1>>> not (null (arithmeticPuzzle [2,3,5,7,11]))
2True
3>>> arithmeticPuzzle [1]
4[]
5>>> not (null (arithmeticPuzzleDP [2,3,5,7,11]))
6True
所有二叉括号结构与四种运算组合会指数增长，使用 Rational 则保证等值比较没有浮点误差。