练习 2.41

题目要求我们完成三个任务:

  1. 写一个函数,生成由相异整数组成的三元组
  2. 写一个谓词函数,它接受一个三元组和一个数值 sum ,检查三元组的三个元之和是否等于 sum ,如果是的话返回真,否则返回假
  3. 写一个过滤函数,使用步骤 2 写出的谓词函数作为过滤器,剔除所有不符合谓词函数要求的三元组

生成三元组

练习 2.40 ,我们写出了 unique-pairs 函数,它可以生成由相异整数组成的二元组:

1 ]=> (load "40-unique-pairs.scm")

;Loading "40-unique-pairs.scm"...
;  Loading "p78-enumerate-interval.scm"... done
;  Loading "p83-flatmap.scm"...
;    Loading "p78-accumulate.scm"... done
;  ... done
;... done
;Value: unique-pairs

1 ]=> (unique-pairs 5)

;Value 24: ((2 1) (3 1) (3 2) (4 1) (4 2) (4 3) (5 1) (5 2) (5 3) (5 4))

我们可以推广这个方法,把它用于生成由相异整数组成的三元组,方法如下:

;;; 41-unique-triples.scm

(load "p78-enumerate-interval.scm")
(load "p83-flatmap.scm")
(load "40-unique-pairs.scm")

(define (unique-triples n)
    (flatmap (lambda (i)
                 (map (lambda (j)                   ; cons 起 i 元素和二元组 j ,组成三元组
                          (cons i j))
                      (unique-pairs (- i 1))))      ; 生成不大于 i 的所有相异整数二元组
             (enumerate-interval 1 n)))             ; 生成 1 至 n 的所有整数,作为 i 

这个函数通过 (enumerate-interval 1 n) 生成 1n 作为变量 i ,再对每个 i 生成相异的二元组 (unique-pairs (- i 1)) ,最后用 cons 组合起 i(unique-pairs (- i 1)) ,得出的结果就是相异的三元组。

测试:

1 ]=> (load "41-unique-triples.scm")

;Loading "41-unique-triples.scm"...
;  Loading "p78-enumerate-interval.scm"... done
;  Loading "p83-flatmap.scm"...
;    Loading "p78-accumulate.scm"... done
;  ... done
;  Loading "40-unique-pairs.scm"...
;    Loading "p78-enumerate-interval.scm"... done
;    Loading "p83-flatmap.scm"...
;      Loading "p78-accumulate.scm"... done
;    ... done
;  ... done
;... done
;Value: unique-triples

1 ]=> (unique-triples 5)

;Value 11: ((3 2 1) (4 2 1) (4 3 1) (4 3 2) (5 2 1) (5 3 1) (5 3 2) (5 4 1) (5 4 2) (5 4 3))

谓词函数

谓词函数的定义如下:

;;; 41-triple-sum-equal-to.scm

(define (triple-sum-equal-to? sum triple)
    (= sum
       (+ (car triple)
          (cadr triple)
          (caddr triple))))

测试:

1 ]=> (load "41-triple-sum-equal-to.scm")

;Loading "41-triple-sum-equal-to.scm"... done
;Value: triple-sum-equal-to?

1 ]=> (triple-sum-equal-to? 6 (list 1 2 3))

;Value: #t

1 ]=> (triple-sum-equal-to? 0 (list 1 2 3))

;Value: #f

谓词函数的另一种更方便的定义方式是:

;;; 41-triple-sum-equal-to-using-fold.scm

(define (triple-sum-equal-to? sum triple)
    (= sum
       (fold-right + 0 triple)))

测试:

1 ]=> (load "41-triple-sum-equal-to-using-fold.scm")

;Loading "41-triple-sum-equal-to-using-fold.scm"... done
;Value: triple-sum-equal-to?

1 ]=> (triple-sum-equal-to? 3 (list 1 1 1))

;Value: #t

1 ]=> (triple-sum-equal-to? 0 (list 1 2 3))

;Value: #f

过滤函数

过滤的实质性工作可以使用 filter 函数来完成,我们只要写一个包装函数组合起谓词函数和 filter 就可以了:

;;; 41-remove-triples-not-equal-to.scm

(load "41-triple-sum-equal-to.scm")

(define (remove-triples-not-equal-to sum triple)
    (filter (lambda (current-triple)
                (triple-sum-equal-to? sum current-triple))
            triple))

remove-triples-not-equal-to 接受 sumtriple 两个参数,删除 triple 中所有三元组之和不等于 sum 的三元组:

1 ]=> (load "41-unique-triples.scm")

;Loading "41-unique-triples.scm"...
;  Loading "p78-enumerate-interval.scm"... done
;  Loading "p83-flatmap.scm"...
;    Loading "p78-accumulate.scm"... done
;  ... done
;  Loading "40-unique-pairs.scm"...
;    Loading "p78-enumerate-interval.scm"... done
;    Loading "p83-flatmap.scm"...
;      Loading "p78-accumulate.scm"... done
;    ... done
;  ... done
;... done
;Value: unique-triples

1 ]=> (load "41-remove-triples-not-equal-to.scm")

;Loading "41-remove-triples-not-equal-to.scm"...
;  Loading "41-triple-sum-equal-to.scm"... done
;... done
;Value: remove-triples-not-equal-to

1 ]=> (remove-triples-not-equal-to 5 (unique-triples 6))

;Value: ()

1 ]=> (remove-triples-not-equal-to 6 (unique-triples 6))

;Value 11: ((3 2 1))

1 ]=> (unique-triples 13)

;Value 14: ((3 2 1) (4 2 1) (4 3 1) (4 3 2) (5 2 1) (5 3 1) (5 3 2) (5 4 1) (5 4 2) (5 4 3) (6 2 1) (6 3 1) (6 3 2) (6 4 1) (6 4 2) (6 4 3) (6 5 1) (6 5 2) (6 5 3) (6 5 4) (7 2 1) (7 3 1) (7 3 2) (7 4 1) (7 4 2) (7 4 3) (7 5 1) (7 5 2) (7 5 3) (7 5 4) (7 6 1) (7 6 2) (7 6 3) (7 6 4) (7 6 5) (8 2 1) (8 3 1) (8 3 2) (8 4 1) (8 4 2) (8 4 3) (8 5 1) (8 5 2) (8 5 3) (8 5 4) (8 6 1) (8 6 2) (8 6 3) (8 6 4) (8 6 5) (8 7 1) (8 7 2) (8 7 3) (8 7 4) (8 7 5) (8 7 6) (9 2 1) (9 3 1) (9 3 2) (9 4 1) (9 4 2) (9 4 3) (9 5 1) (9 5 2) (9 5 3) (9 5 4) (9 6 1) (9 6 2) (9 6 3) (9 6 4) (9 6 5) (9 7 1) (9 7 2) (9 7 3) (9 7 4) (9 7 5) (9 7 6) (9 8 1) (9 8 2) (9 8 3) (9 8 4) (9 8 5) (9 8 6) (9 8 7) (10 2 1) (10 3 1) (10 3 2) (10 4 1) (10 4 2) (10 4 3) (10 5 1) (10 5 2) (10 5 3) (10 5 4) (10 6 1) (10 6 2) (10 6 3) (10 6 4) (10 6 5) (10 7 1) (10 7 2) (10 7 3) (10 7 4) (10 7 5) (10 7 6) (10 8 1) (10 8 2) (10 8 3) (10 8 4) (10 8 5) (10 8 6) (10 8 7) (10 9 1) (10 9 2) (10 9 3) (10 9 4) (10 9 5) (10 9 6) (10 9 7) (10 9 8) (11 2 1) (11 3 1) (11 3 2) (11 4 1) (11 4 2) (11 4 3) (11 5 1) (11 5 2) (11 5 3) (11 5 4) (11 6 1) (11 6 2) (11 6 3) (11 6 4) (11 6 5) (11 7 1) (11 7 2) (11 7 3) (11 7 4) (11 7 5) (11 7 6) (11 8 1) (11 8 2) (11 8 3) (11 8 4) (11 8 5) (11 8 6) (11 8 7) (11 9 1) (11 9 2) (11 9 3) (11 9 4) (11 9 5) (11 9 6) (11 9 7) (11 9 8) (11 10 1) (11 10 2) (11 10 3) (11 10 4) (11 10 5) (11 10 6) (11 10 7) (11 10 8) (11 10 9) (12 2 1) (12 3 1) (12 3 2) (12 4 1) (12 4 2) (12 4 3) (12 5 1) (12 5 2) (12 5 3) (12 5 4) (12 6 1) (12 6 2) (12 6 3) (12 6 4) (12 6 5) (12 7 1) (12 7 2) (12 7 3) (12 7 4) (12 7 5) (12 7 6) (12 8 1) (12 8 2) (12 8 3) (12 8 4) (12 8 5) (12 8 6) (12 8 7) (12 9 1) (12 9 2) (12 9 3) (12 9 4) (12 9 5) (12 9 6) (12 9 7) (12 9 8) (12 10 1) (12 10 2) (12 10 3) (12 10 4) (12 10 5) (12 10 6) (12 10 7) (12 10 8) (12 10 9) (12 11 1) (12 11 2) (12 11 3) (12 11 4) (12 11 5) (12 11 6) (12 11 7) (12 11 8) (12 11 9) (12 11 10) (13 2 1) (13 3 1) (13 3 2) (13 4 1) (13 4 2) (13 4 3) (13 5 1) (13 5 2) (13 5 3) (13 5 4) (13 6 1) (13 6 2) (13 6 3) (13 6 4) (13 6 5) (13 7 1) (13 7 2) (13 7 3) (13 7 4) (13 7 5) (13 7 6) (13 8 1) (13 8 2) (13 8 3) (13 8 4) (13 8 5) (13 8 6) (13 8 7) (13 9 1) (13 9 2) (13 9 3) (13 9 4) (13 9 5) (13 9 6) (13 9 7) (13 9 8) (13 10 1) (13 10 2) (13 10 3) (13 10 4) (13 10 5) (13 10 6) (13 10 7) (13 10 8) (13 10 9) (13 11 1) (13 11 2) (13 11 3) (13 11 4) (13 11 5) (13 11 6) (13 11 7) (13 11 8) (13 11 9) (13 11 10) (13 12 1) (13 12 2) (13 12 3) (13 12 4) (13 12 5) (13 12 6) (13 12 7) (13 12 8) (13 12 9) (13 12 10) (13 12 11))

1 ]=> (remove-triples-not-equal-to 10 (unique-triples 13))

;Value 15: ((5 3 2) (5 4 1) (6 3 1) (7 2 1))

讨论

blog comments powered by Disqus