编程解数学题——构造算式求出100

1 2 3 4 5 6 7 8 9 = 100

在等式左边的每个数字之前填上，加号(+) 或减号(-) ,也可以选择什么都不填，使表达式的值为100，请列出所有结果是100的填法。

这是一道常见的数学题，下面就是两个满足要求的填法：

12 + 3 + 4 + 5 - 6 - 7 + 89 = 100

-1 + 2 - 3 + 4 + 5 + 6 + 78 + 9 = 100

要列出所有符合要求的填法，需要尝试所有的填法，想必同学已经能估算出来有多少种填法了。

在数字1之前，只有两种选择：加号和不填，实际是一种情况，另一种情况是填上减号。

在数字2和9之前，则均有3种选择。

如下图所示：

我们不难得出一共有：2*3*3*3*3*3*3*3*3 = 13122种填法。

下面我们分三部分来考虑这个问题：

如何表示一种填法？

获得所有的填法；

在所有的填法中找出符合条件的解。

如何表示一种填法？

可能的表示方法会很多，简明起见，我们使用刚刚学过的Scheme的列表， 来表示一种填法。

从下图中，我们不难看出一个特定的填法与一个列表有着一种一一对应的关系 ：

12 + 3 + 4 + 5 - 6 - 7 + 89

'(12 3 4 5 -6 -7 89)

-1 + 2 - 3 + 4 + 5 + 6 + 78 + 9

'(-1 2 -3 4 5 6 78 9)

用这样一个列表来表示"一种填法"的话，这个列表的各元素之和，即是这种填法的结果。

上图F₉中一共有13122个元素，每个元素代表一种填法，

对应着S₉中也有13122个元素，每个元素是一个列表，对应着一种填法。

获得所有的填法

也就是得到F₉,即S₉。

我们不妨假设已经生成了前两个数的所有填法的表示，也就是得到了与之对应的全部列表的集合S₂。

这个列表集合S₂的规模是2 * 3 = 6种

(1 2)

(1 -2)

(12)

(-1 2)

(-1 -2)

(-12)

那么，我们如何在S₂的基础上得到S₃呢？

1.在S₂的每个列表后面加一个元素3

得到:

(1 2 3)

(1 -2 3)

(12 3)

(-1 2 3)

(-1 -2 3)

(-12 3)

2.在S₂的每个列表后面加一个元素-3

得到:

(1 2 -3)

(1 -2 -3)

(12 -3)

(-1 2 -3)

(-1 -2 -3)

(-12 -3)

3.在S₂的每个列表最后的一个元素后面粘上3

得到:

(1 23)

(1 -23)

(123)

(-1 23)

(-1 -23)

(-123)

把上述三步的结果合并起来，得到的正是S₃。

上面讲解的是从S₂推出S₃的情况，实际上从Sn推出Sn+1也是类似的。整个步骤可以用下图来表达

特别注意因为 数字1前面填加号(+)和不填是一种情况

所以S₁有两个元素'(1)和'(-1)

根据上面的讨论，我们不难得出下面的代码

(define (solve lst v)

(if (null? lst)

(list v)

(let

([e (car lst)])

(append

(solve (cdr lst) (append v (list e )))

(solve (cdr lst) (append v (list (- e))))

(if (null? v )

'()

(let* (

[r (reverse v)]

[le (car r)])

(solve (cdr lst)(reverse (cons ((if (positive? le) + -) (* 10 le) e ) (cdr r))))))))))

(for-each displayln (take (solve (range 1 10 ) '()) 10 ))

(length (solve (range 1 10) '()));;

(1 2 3 4 5 6 7 8 9)

(1 2 3 4 5 6 7 8 -9)

(1 2 3 4 5 6 7 89)

(1 2 3 4 5 6 7 -8 9)

(1 2 3 4 5 6 7 -8 -9)

(1 2 3 4 5 6 7 -89)

(1 2 3 4 5 6 78 9)

(1 2 3 4 5 6 78 -9)

(1 2 3 4 5 6 789)

(1 2 3 4 5 6 -7 8 9)

......

13122

S₉ 实在太长了，我们使用take函数列出了前 10个元素， 也就是10个列表，对应着10种填法。

另外，我们还给出了 S₉ 的元素数 13122。

关于代码，有几点说明：

1.lst是尚未处理的列表，当lst处理结束后返回v对应的是上面的树形图中的 叶子结点(未绘出)上的值，append最终将所有的叶子结点的值合成一个集合，所以返回v的时候，要使用(list v )这样的形式；

2.把一个数字b粘到另一个数字a后面，有两种情况，

当a ≥ 0时， 结果是10a + b

当a < 0时， 结果是10a - b

程序中运用(if (positive? le) + - )来选择适当的操作符；

3.Scheme的range函数，生成的列表中，包含第一个参数，不包含第二个参数

这与Python的range一致。

(range 1 10)的结果是(1 2 3 4 5 6 7 89)

我们再来验证一下S₂，S₃的值

S₂

(solve (range 1 3) '())

((1 2)

(1 -2)

(12)

(-1 2)

(-1 -2)

(-12))

S₃

(solve (range 1 4) '())

((1 2 3) (1 2 -3) (1 23)

(1 -2 3) (1 -2 -3) (1-23)

(12 3) (12-3) (123)

(-1 2 3) (-1 2 -3) (-123)

(-1 -2 3) (-1 -2 -3) (-1 -23)

(-12 3) (-12-3) (-123))

请同学位再琢磨一下，从S₂得到S₃的过程

在所有的填法中找出符合条件的解

有了所有填法的集合，简单filter出所有满足条件的填法就可以了，

我们通过一个匿名函数来判断一个列表的和是否是100。

由下面这条语句，我们就得出了所有的解：

(for-each displayln (filter (lambda (x) (= (sum x ) 100 )) (solve (range 1 10)'())))

(1 2 3 -4 5 6 78 9)

(1 2 34 -5 67 -8 9)

(1 23 -4 5 6 78 -9)

(1 23 -4 56 7 8 9)

(12 3 4 5 -6 -7 89)

(12 3 -4 5 67 8 9)

(12 -3 -4 5 -6 7 89)

(123 4 -5 67 -89)

(123 45 -67 8 -9)

(123 -4 -5 -6 -7 8 -9)

(123 -45 -67 89)

(-1 2 -3 4 5 6 78 9)

如果需要更人性化的显示，可以简单写个转换函数如下

注意这段代码中compose的用法

(for-each

(compose displayln

(lambda (lst)

(string-append

(number->string (car lst ))

(apply string-append

(map

(lambda (x)

(if (> x0)

(string-append "+" (number->string x))

(number->string x))) (cdr lst))) " = 100")))

(filter (lambda (x) (= (sum x ) 100 )) (solve (range 1 10)'())))

1+2+3-4+5+6+78+9 = 100

1+2+34-5+67-8+9 = 100

1+23-4+5+6+78-9 = 100

1+23-4+56+7+8+9 = 100

12+3+4+5-6-7+89 = 100

12+3-4+5+67+8+9 = 100

12-3-4+5-6+7+89 = 100

123+4-5+67-89 = 100

123+45-67+8-9 = 100

123-4-5-6-7+8-9 = 100

123-45-67+89 = 100

-1+2-3+4+5+6+78+9 = 100

以下是对应的Python的代码

def solve(lst,v):

if lst :

e = lst[0]

s = solve(lst[1:], v+[e]) + solve(lst[1:], v+[-e])

if v:

f = v[-1] * 10 + e if v[-1] > 0 else v[-1] *10 - e

return s + solve(lst[1:], v[:-1] + [f])

else :

return s

else :

return [v]

for v in filter( (lambda x : sum(x) == 100), solve( range(1,10),[] )) :

print(v)

[1, 2, 3, -4, 5, 6, 78, 9]

[1, 2, 34, -5, 67, -8, 9]

[1, 23, -4, 5, 6, 78, -9]

[1, 23, -4, 56, 7, 8, 9]

[12, 3, 4, 5, -6, -7, 89]

[12, 3, -4, 5, 67, 8, 9]

[12, -3, -4, 5, -6, 7, 89]

[123, 4, -5, 67, -89]

[123, 45, -67, 8, -9]

[123, -4, -5, -6, -7, 8, -9]

[123, -45, -67, 89]

[-1, 2, -3, 4, 5, 6, 78, 9]

我们可以在上述程序的基础上，做各种各样的尝试

(for-each displayln (filter (lambda (x) (= (sum x ) 500 )) (solve (range 1 10)'())))

;1到9得出500

(1 -2 345 67 89)

(1 -234 -56 789)

(-12 34 567 -89)

(for-each displayln (filter (lambda (x) (= (sum x ) 100 )) (solve (range 1 9)'())))

;1到8得出100

(1 23 -4 5 67 8)

(1 -2 34 -5 -6 78)

(1 -2 -3 45 67 -8)

(12 3 -4 5 6 78)

(12 34 -5 67 -8)

(for-each displayln (filter (lambda (x) (= (sum x ) 100 )) (solve (range 1 8)'())))

;1到7得出100

(1 2 34 56 7)

(1 23 4 5 67)

(for-each displayln (filter (lambda (x) (= (sum x ) 100 )) (solve (range 9 0-1) '())))

;9到1得出100

(9 8 76 5 4 -3 2 -1)

(9 8 76 5 -4 3 2 1)

(9 -8 7 65 -4 32 -1)

(9 -8 76 54 -32 1)

(9 -8 76 -5 4 3 21)

(98 7 6 -5 -4 -3 2 -1)

(98 7 -6 5 -4 3 -2 -1)

(98 7 -6 5 -4 -3 2 1)

(98 7 -6 -5 4 3 -2 1)

(98 -7 6 5 4 -3 -2 -1)

(98 -7 6 5 -4 3 -2 1)

(98 -7 6 -5 4 3 2 -1)

(98 -7 -6 5 4 3 2 1)

(98 -7 -6 -5 -4 3 21)

(98 -76 54 3 21)

(-9 8 7 65 -4 32 1)

(-9 8 76 5 -4 3 21)

(-9 -8 76 -5 43 2 1)

同学们可以进一步思考一下，如果操作符不仅是加号， 减号，还可以是乘号，除号，该如何设计程序呢？