其实上面的“凑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)