Non ho idea di come risolvere SICP esercizio 1.11

https://stackoverflow.com/questions/2365993

23-09-2019
|

Domanda

Una funzione f è definita dalla regola che f(n) = n se n < 3 e f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) se n > 3. Scrivere una procedura che calcola f mediante un processo ricorsivo. Scrivere una procedura che calcola f mediante un processo iterativo.

L'implementazione in modo ricorsivo è abbastanza semplice. Ma non riuscivo a capire come farlo in modo iterativo. Ho provato a confronto con l'esempio dato di Fibonacci, ma non sapevo come usarlo come analogia. Così ho rinunciato (mannaggia a me) e Googled per una spiegazione , e ho trovato questo:

(define (f n)
   (if (< n 3)
       n
       (f-iter 2 1 0 n)))

(define (f-iter a b c count)
   (if (< count 3)
       a
       (f-iter (+ a (* 2 b) (* 3 c))
               a
               b
               (- count 1))))

Dopo averlo letto, ho capito il codice e come funziona. Ma quello che non capisco è il processo necessario per ottenere dalla definizione ricorsiva della funzione da questo. Non capisco come il codice potrebbe essersi formata nella testa di qualcuno.

Ci può spiegare il processo di pensiero necessaria per arrivare alla soluzione?

Soluzione

È necessario per acquisire lo stato in alcuni accumulatori e aggiornare lo stato ad ogni iterazione.

Se avete esperienza in un linguaggio imperativo, immaginate scrivere un ciclo while e il monitoraggio di informazioni in variabili durante ogni iterazione del ciclo. Che variabili avresti bisogno? Come si aggiornarli? Questo è esattamente quello che hai da fare per rendere un iterativo (tail-ricorsiva) serie di chiamate in Scheme.

In altre parole, potrebbe aiutare a cominciare a pensare a questo come un ciclo while, invece di una definizione ricorsiva. Alla fine sarete abbastanza fluente con ricorsive -.> Trasformazioni iterativi che non avrete bisogno di un aiuto extra per iniziare

Per questo particolare esempio, si deve guardare da vicino le tre chiamate di funzione, perché non è immediatamente chiaro come rappresentare loro. Tuttavia, qui è il processo di pensiero probabile: (in Python pseudo-codice per sottolineare l'obbligatorietà)

Ogni passo ricorsivo tiene traccia delle tre cose:

f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3)

Quindi ho bisogno di tre pezzi di Stato per monitorare la corrente, il penultimo dei valori di f scorso e. (Che è, f(n-1), f(n-2) and f(n-3).) Li chiamano a, b, c. Devo aggiornare questi pezzi all'interno di ogni ciclo:

for _ in 2..n:
    a = NEWVALUE
    b = a
    c = b
return a

Allora, qual è NEWVALUE? Bene, ora che abbiamo rappresentazioni di f(n-1), f(n-2) and f(n-3), è solo l'equazione ricorsiva:

for _ in 2..n:
    a = a + 2 * b + 3 * c
    b = a
    c = b
return a

Ora tutto quello che resta è quello di capire i valori iniziali di a, b and c. Ma questo è facile, poiché sappiamo che f(n) = n if n < 3.

if n < 3: return n
a = 2 # f(n-1) where n = 3
b = 1 # f(n-2)
c = 0 # f(n-3)
# now start off counting at 3
for _ in 3..n:
    a = a + 2 * b + 3 * c
    b = a
    c = b
return a

Questo è ancora un po 'diverso dalla versione iterativa Scheme, ma spero si può vedere il processo di pensiero ora.

Altri suggerimenti

Credo che ti stai chiedendo come si potrebbe scoprire l'algoritmo naturalmente, al di fuori di un 'modello di progettazione'.

E 'stato utile per me per guardare l'espansione della f (n) ad ogni valore n:

f(0) = 0  |
f(1) = 1  | all known values
f(2) = 2  |

f(3) = f(2) + 2f(1) + 3f(0)
f(4) = f(3) + 2f(2) + 3f(1)
f(5) = f(4) + 2f(3) + 3f(2)
f(6) = f(5) + 2f(4) + 3f(3)

Guardando più da vicino f (3), vediamo che possiamo calcolare immediatamente dai valori noti. Di cosa abbiamo bisogno per calcolare f (4)?

Abbiamo bisogno di almeno calcolare f (3) + [il resto]. Ma, come si calcola f (3), calcoliamo f (2) ef (1) pure, che ci capita di necessità per il calcolo [il resto] di f (4).

f(3) = f(2) + 2f(1) + 3f(0)
            ↘       ↘
f(4) = f(3) + 2f(2) + 3f(1)

Quindi, per qualsiasi numero n, posso iniziare calcolando f (3), e riutilizzare i valori che uso per calcolare f (3) Per calcolare f (4) ... e il modello continua ...

f(3) = f(2) + 2f(1) + 3f(0)
            ↘       ↘
f(4) = f(3) + 2f(2) + 3f(1)
            ↘       ↘
f(5) = f(4) + 2f(3) + 3f(2)

Dal momento che noi li riutilizzo, consente di dare loro un nome a, b, c. subscripted con il passo che siamo, e passeggiata attraverso un calcolo di f (5):

  Step 1:    f(3) = f(2) + 2f(1) + 3f(0) or f(3) = a₁ + 2b₁ +3c₁

dove

una ₁ = f (2) = 2,

b ₁ = f (1) = 1,

c ₁ = 0

poiché f (n) = n per n <3.

In questo modo:

f (3) = a ₁ + 2b ₁ + 3c ₁ = 4

  Step 2:  f(4) = f(3) + 2a₁ + 3b₁

una ₂ = f (3) = 4 (sopra calcolato nella fase 1),

b ₂ = a ₁ = f (2) = 2,

c ₂ = b ₁ = f (1) = 1

In questo modo:

f (4) = 4 + 2 * 2 + 3 * 1 = 11

  Step 3:  f(5) = f(4) + 2a₂ + 3b₂

una ₃ = f (4) = 11 (sopra calcolato nel passaggio 2),

b ₃ = a ₂ = f (3) = 4,

c ₃ = b ₂ = f (2) = 2

In questo modo:

f (5) = 11 + 2 * 4 + 3 * 2 = 25

Durante il calcolo di cui sopra stato che cattura nel calcolo precedente e passarlo al passo successivo, particularily:

una _passo = risultato del passo - 1

b _passo = a _{passaggio - 1}

c _passo = b _{passo -1}

Una volta che ho visto questo, poi venire con la versione iterativa era semplice.

Dato che la posta si è collegato al descrive molto circa la soluzione, cercherò di dare solo informazioni complementari.

Si sta cercando di definire una funzione ricorsiva in coda nello Schema qui, dato un (non-tail) definizione ricorsiva.

Il caso base della ricorsione (f (n) = n se n <3) viene gestito da entrambe le funzioni. Io non sono davvero sicuro perché l'autore fa questo; la prima funzione potrebbe essere semplicemente:

(define (f n)
   (f-iter 2 1 0 n))

La forma generale potrebbe essere:

(define (f-iter ... n)
   (if (base-case? n)
       base-result
       (f-iter ...)))

Nota io non compilare i parametri per F-iter ancora, perché è necessario prima capire che cosa le esigenze dello stato per essere passato da un'iterazione ad un altro.

Ora, diamo un'occhiata alle dipendenze della forma ricorsiva di f (n). Fa riferimento f (n - 1), f (n - 2), e f (n - 3), quindi abbiamo bisogno di mantenere intorno a questi valori. E, naturalmente, abbiamo bisogno del valore di n per sé, in modo che possiamo fermare l'iterazione su di esso.

Ecco come si arriva con la chiamata ricorsiva in coda: calcoliamo f (n) da utilizzare come f (n - 1), ruotare f (n - 1) a f (n - 2) e f (n - 2) a f (n -. 3), e la conta decremento

Se questo fa ancora non aiuto, prova a fare una domanda più specifica -. È davvero difficile rispondere quando si scrive "Non capisco" dato una spiegazione relativamente approfondita già

ho intenzione di entrare in questo in un approccio leggermente diverso rispetto alle altre risposte qui, è concentrato su come codifica stile può rendere il processo di pensiero dietro un algoritmo come questo più facile da comprendere.

Il problema con di Bill approccio , citato nella tua domanda , è che non è immediatamente chiaro che cosa significa si traduce con le variabili di stato, a, b e c. I loro nomi trasmettere alcuna informazione, e post di Bill non descrive alcuna invariante o altra regola che obbediscono. Trovo più facile sia per formulare e comprendere algoritmi iterativi se le variabili di stato obbediscono alcune regole documentate che descrivono le loro relazioni gli uni agli altri.

Con questo in mente, considerare questa formulazione alternativa della esattamente lo stesso algoritmo, che differisce da Bill soltanto ad avere nomi delle variabili più significativi per a, b e c e un contatore variabile incrementare anziché un decremento uno:

(define (f n)
    (if (< n 3)
        n
        (f-iter n 2 0 1 2)))

(define (f-iter n 
                i 
                f-of-i-minus-2
                f-of-i-minus-1
                f-of-i)
    (if (= i n)
        f-of-i
        (f-iter n
                (+ i 1)
                f-of-i-minus-1
                f-of-i
                (+ f-of-i
                   (* 2 f-of-i-minus-1)
                   (* 3 f-of-i-minus-2)))))

Improvvisamente la correttezza dell'algoritmo - e il processo di pensiero dietro la sua creazione - è semplice da vedere e descrivere. Per calcolare f(n):

Abbiamo una variabile i contatore che inizia a 2 e sale al n, incrementare di 1 a ogni chiamata a f-iter.
Ad ogni passo lungo la strada, teniamo traccia di f(i), f(i-1) e f(i-2), che è sufficiente per permetterci di calcolare f(i+1).
Una volta i=n, abbiamo finito.

Una funzione f è definita dalla regola che f(n) = n, if n<3 e f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3), if n > 3. Scrivere una procedura che calcola f mediante un processo ricorsivo.

è già scritto:

f(n) = n,                                  (* if *)  n < 3
     = f(n - 1) + 2f(n - 2) + 3f(n - 3),   (* if *)  n > 3

Che ci crediate o no, una volta era un tale linguaggio . Per scrivere questo verso il basso in un'altra lingua è solo una questione di sintassi. E tra l'altro, la definizione come voi (MIS) citarlo ha un bug, che ora è molto evidente e chiaro.

scrivere una procedura che calcola f mediante un processo iterativo.

andare avanti ( c'è la tua spiegazione) in contrasto con la ricorsione sta andando all'indietro in un primo momento:

f(n)   =  f(n - 1) + 2f(n - 2) + 3f(n - 3) 
       =  a        + 2b        + 3c
f(n+1) =  f(n    ) + 2f(n - 1) + 3f(n - 2)
       =  a'       + 2b'       + 3c'          a' = a+2b+3c, b' = a, c' = b
......

Questo descrive così transizioni di stato del problema il

 (n, a, b, c)  ->  (n+1, a+2*b+3*c, a, b)

potrebbe codificare come

g (n, a, b, c) = g (n+1, a+2*b+3*c, a, b)

ma naturalmente non sarebbe mai fermata. Quindi dobbiamo invece avere

f n = g (2, 2, 1, 0)
  where
  g (k, a, b, c) = g (k+1, a+2*b+3*c, a, b),    (* if *) k < n
  g (k, a, b, c) = a,                           otherwise

e questo è già esattamente come il codice hai chiesto, fino a sintassi.

Contare fino a n è più naturale qui, seguendo il nostro paradigma di "andare avanti", ma il conto alla rovescia per 0 come il codice che cita non è ovviamente del tutto equivalente.

I casi d'angolo e possibili errori off-by-one sono lasciati fuori come ~~esercizio~~ tecnicismi non interessanti.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow