SICP – cap. 1 – Costruire astrazioni tramite procedure – esercizi – 23

Amsterdam

Continuo da qui, oggi un altro esercizio, da qui.

Exercise 1.19: There is a clever algorithm for computing the Fibonacci numbers in a logarithmic number of steps. Recall the transformation of the state variables a and b in the fib-iter process [qui]: a ← a + b and b ← a. Call this transformation T, and observe that applying T over and over again n times, starting with 1 and 0, produces the pair Fib(n + 1) and Fib(n). In other words, the Fibonacci numbers are produced by applying Tn, the nth power of the transformation T, starting with the pair (1,0). Now consider T to be the special case of p = 0 and q = 1 in a family of transformations Tpq, where Tpq transforms the pair (a,b) according to a ← bq + aq + ap and b ← bp + aq. Show that if we apply such a transformation Tpq twice, the effect is the same as using a single transformation Tpq of the same form, and compute p' and q' in terms of p and q. This gives us an explicit way to square these transformations, and thus we can compute Tn using successive squaring, as in the fast-expt procedure. Put this all together to complete the following procedure, which runs in a logarithmic number of steps:

(define (fib n)
  (fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                         ; compute q'
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

Unmmm… mumble – munble… 😳

OK, per lo spiegone dettagliato c’è Bill the Lizard.
Una soluzione diversa da Ken Dyck.
Il sito comunitario SICP-Solutions (per me s-sol) propone due soluzioni, la seconda delle quali richiederebbe uno studio tutto per lei.
Il più sintetico di tutti è Weiqun Zhang, che si limita a indicare i valori di p' e q'.

OK, adotto Bill.

s36

e ottengo

s37

er una verifica veloce, ricordando che fib(n) = fib(n-1) + fib(n-2) posso calcolare fib(n-2) = fib(n) - fib(n-1) e per n = 1000 ottengo

s38

: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: