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

18 October, 2007 (21:49) | Решения упражнений

Процедура, реализующая фильтрующий аккумулятор, будет иметь следующий вид:

(define (filtered-accumulate combiner null-value term a next b filter) 
  (if (> a b) 
      null-value 
      (if (filter a) 
          (combiner (term a) 
                    (filtered-accumulate combiner null-value term (next a) next b filter)) 
          (filtered-accumulate combiner null-value term (next a) next b filter))))

Сумма квадратов простых чисел в интервале от a до b может быть вычислена так:

(define (sum-prime-squares a b) 
  (define (inc x) (+ x 1)) 
  (filtered-accumulate + 0 square a inc b prime?))

Произведение всех положительных целых чисел меньше n, которые просты по отношению к n, можно вычислить так:

(define (product-prime-for n) 
  (define (id x) x) 
  (define (inc x) (+ x 1)) 
  (define (prime-for-n? k) 
    (= (gcd n k) 1)) 
  (filtered-accumulate * 1 id 1 inc n prime-for-n?))

Фильтрующий аккумулятор легко может быть переписан и в виде, порождающем итеративный процесс.

Comments

Comment from Dima
Date: June 16, 2008, 1:15 am

Do you think this would work?

(define (filtered-accumulate a b term next combiner null-value filter)
  (define (helper a)
    (if (> a b)
        null-value
        (combiner (if (filter a) 
                      (term a)
                      null-value)
                  (helper (next a)))))
  (helper a))

It seems to work for sum and product, but is it truly general enough?

Thanks for your site, by the way. It’s by far the best SICP solution site I’ve seen.

Comment from nobody
Date: July 3, 2008, 10:03 pm

@Dima:
It seems that you intended to write an iterative soultion, but you have actually written a recursive one.

Кстати, filtered-accumulate можно реализовать и при помощи accumulate:

(define (filtered-accumulate combiner null-value term a next b filter)
  (define (new-term x)
    (if (filter x)
        (term x)
        null-value))
  (accumulate combiner null-value new-term a next b))

Comment from Irv
Date: January 8, 2016, 3:14 pm

итеративный вариант:

(define (filtered-accumulate combiner null-value term a next b filter?)
  (define (iter x result)
    (if (> x b)
        result
        (iter 
         (next x) 
         (if (filter? x)
             (combiner result (term x))
             result))))
  (iter a null-value))

Write a comment