SICP – cap. 1 – formulare astrazioni con procedure di ordine superiore – esercizi – 40

6a00

SICP rockz! ma richiede tempo e attenzione. Purtroppo viene relegato (da me, sigh!) nei momenti di pausa. Ma ecco, continuo da qui e ne arriva un altro pezzettino 😀

Exercise 1.33: You can obtain an even more general version of accumulate (exercise 1.32 [post precedente, quello linkato]) by introducing the notion of a filter on the terms to be combined. That is, combine only those terms derived from values in the range that satisfy a specified condition. The resulting filtered-accumulate abstraction takes the same arguments as accumulate, together with an additional predicate of one argument that specifies the filter. Write filtered-accumulate as a procedure. Show how to express the following using filtered-accumulate:

a. the sum of the squares of the prime numbers in the interval a to b (assuming that you have a prime? predicate already written)

b. the product of all the positive integers less than n that are relatively prime to n (i.e., all positive integers i < n such that GCD(i,n) = 1).

La soluzione di Bill the Lizard è incredibilmente bella 😀
Al solito con la spiegazione esauriente, un modello.

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

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

(define (fast-prime? n)
   (define (smallest-divisor n)
      (define (find-divisor n test-divisor)
         (define (next x)
            (if (= x 2) 3 (+ x 2)))
         (define (divides? a b)
            (= (remainder b a) 0))
         (cond ((> (square test-divisor) n) n)
               ((divides? test-divisor n) test-divisor)
               (else (find-divisor n (next test-divisor)))))
      (find-divisor n 2))
   (= n (smallest-divisor n)))

(define (sum-squared-primes a b)
   (filtered-accum fast-prime? + 0 square a inc b))

(define (inc x) (+ x 1))

(define (square x)
   (* x x))

s83

Poi si passa alla seconda parte, i coprimi. Anche qui vale tutto quanto detto sopra.

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

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

(define (fast-prime? n)
   (define (smallest-divisor n)
      (define (find-divisor n test-divisor)
         (define (next x)
            (if (= x 2) 3 (+ x 2)))
         (define (divides? a b)
            (= (remainder b a) 0))
         (cond ((> (square test-divisor) n) n)
               ((divides? test-divisor n) test-divisor)
               (else (find-divisor n (next test-divisor)))))
      (find-divisor n 2))
   (= n (smallest-divisor n)))

(define (sum-squared-primes a b)
   (filtered-accum fast-prime? + 0 square a inc b))

(define (inc x) (+ x 1))

(define (identity x) x)

(define (gcd a b)
   (if (= b 0)
       a
       (gcd b (remainder a b))))

(define (product-of-coprimes n)
  (define (coprime? i)
     (= 1 (gcd i n)))
  (filtered-accum coprime? * 1 identity 1 inc (- n 1)))

s84

Diversa la soluzione (non commentata) di Ken Dyck, da provare.
Simile a Bill la soluzione di s-sicp.

Dovrei avere più tempo 😦

:mrgreen:

Posta un commento o usa questo indirizzo per il trackback.

Trackback

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.

%d blogger hanno fatto clic su Mi Piace per questo: