第七章

凑24的推广

其实上面的“凑24” 可以推广一下,我们可以用一个程序来生成那 些表达式树,这样我们就可以解决用任意数目的输入数凑足任何一个 数,用任何操作符。实现如下:

(define (get-it numbers operators target)
  (let loop ((rest numbers))
    (let ((ai (number-between 0 (- (length rest) 1)))
          (bi (number-between 0 (- (length rest) 1))))
      (assert (distinct? (list ai bi)))
      (let ((a (list-ref rest ai))
            (b (list-ref rest bi)))
        (let* ((op (apply-amb operators))
               (subexp (list op a b)))

          (if (and (memv op '(+ *)) (real? a) (real? b))
              (assert (> (eval (cadr subexp) (interaction-environment))
                         (eval (caddr subexp) (interaction-environment)))))

          (if (memv op '(+ *))
              (cond ((and (pair? a)
                          (eqv? op (car a))
                          (not (pair? b)))
                     (set! subexp `(,@a ,b)))
                    ((and (pair? b)
                          (eqv? op (car b))
                          (not (pair? a)))
                     (set! subexp `(,@b ,a)))
                    ((and (pair? a)
                          (pair? b)
                          (eqv? op (car a))
                          (eqv? op (car b)))
                     (set! subexp (append a (cdr b))))))

          (if (eq? op '/) (assert
                           (not (= 0 (eval (caddr subexp)
                                           (interaction-environment))))))

          (if (= 2 (length rest))
              (begin
                (assert (= target
                                (eval subexp (interaction-environment))))
                     subexp)
              (loop (cons subexp (del a (del b rest))))
              ))))))

这个函数 get-it 接受三个参数。第一个是允许使用的数字,第二个 是允许使用的操作符(必须是二元操作符),第三个参数是要得到什么 结果。

你发现其实这个程序虽然强大很多,反而比上面的 get-24 还要短小。 实际上它的原理就是自底向上构造一个表达式树,然后断言这个表达 式的值为 target.

我们的帮助函数 del 是用来从一个 list 里去掉一个元素的。

比如我们可以这样使用:

(bag-of (get-it '(1 3 6 12) '('+ '- '* '/) 24))

这就相当 get-24 对于参数 1 3 6 12。

我们还可以自己定义一些操作符,比如“平方和”符号 "++":

(define (++ a b)
  (+ (* a a) (* b b)))

然后我用

(get-it '(2 8 4 3 6 12) '('+ '- '* '/ '++) 100)

就可以求得用这5种操作符对这6个数进行操作,所有能得到 100 的 表达式。

我们甚至可以使用分数数甚至复数!

(get-it '(3 5 10 7) '('+ '- '* '/ '++) 12.5)
(get-it '(1+2i 5 2 3-3i) '('+ '- '* '/ '++) 27+9i)