Решение упражнения 2.41 из SICP

31 January, 2008 (22:59) | Решения упражнений

Определим сначала процедуру, генерирующую все наборы различных троек. Она строится аналогично процедуре, генерирующей все уникальные пары из прошлого упражнения (можно даже использовать unique-pairs в реализации, но я этого не буду делать:

(define (unique-triples n)
    (flatmap (lambda (i)
          (flatmap (lambda (j)
                (map (lambda (k) (list i j k))
                     (enumerate-interval 1 (- j 1))))
                   (enumerate-interval 1 (- i 1))))
             (enumerate-interval 1 n)))

Теперь применим к набору троек, построенному процедурой unique-triples, фильтр, проверяющий равенство суммы элементов тройки заданному числу s:

(define (triples-with-sum s n)
  (filter (lambda (t) (= (accumulate + 0 t) s))
          (unique-triples n)))

Процедура triples-with-sum является решением этого упражнения.

Это не единственное возможное решение. Как я уже писал выше, можно переиспользовать определенную ранее процедуру unique-pairs. Можно также не разбивать весь процесс на два этапа (генерацию троек и фильтрацию), а сразу строить тройки таким образом, чтобы их сумма была равна s.

Comments

Comment from nobody
Date: July 9, 2008, 8:17 pm

Когда я сначала попытался написать unique-triples так, как у вас (по аналогии с unique-pairs), я просто запутался на третьем уровне вложенности :) Поэтому я написал её так:

(define (prepend-nums n seq)
  (accumulate append
              '()
             (map (lambda (elem)
                    (map (lambda (i) (cons i elem))
                         (enumerate-interval 1 n)))
                  seq))) 

(define (ordered-triples n)
  (prepend-nums n
                (prepend-nums n
                              (prepend-nums n '(()) ))))

Write a comment