- In riempimento
- Letta
- Risposta
Fibonacci con la programmazione dinamica
I numeri di Fibonacci sono il classico primo esempio di programmazione dinamica. La ricorsione semplice chiede gli stessi termini ancora e ancora, ma con una tabella che ricorda ogni termine il lavoro cresce solo con n. Scegli un termine, scegli bottom-up o top-down e procedi passo passo per vedere ogni cella riempita una sola volta. Premi Avvia per vedere la tabella riempirsi, oppure Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare dove vuoi. Scegli n, il termine da calcolare, e il metodo: Bottom-up riempie la tabella da sinistra, Top-down mantiene la ricorsione ma guarda prima nella tabella, e la riga sotto la tabella diventa la pila delle chiamate aperte. Nuovo esempio sceglie un altro n. Con il riquadro selezionato, le frecce vanno avanti e indietro di un passo, la barra spaziatrice avvia e mette in pausa, e Home e Fine saltano all'inizio e alla fine.
Come funziona
- Scrivi n, il termine da calcolare, e scegli Bottom-up o Top-down.
- Premi Avvia, oppure usa Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare dove vuoi.
- Guarda ogni cella leggere le due celle che la precedono. Con Top-down, la riga sotto la tabella è la pila delle chiamate aperte.
Bottom-up e top-down
Il metodo bottom-up, detto anche tabulazione, parte da F(0) = 0 e F(1) = 1 e riempie la tabella da sinistra a destra: ogni nuova cella è la somma delle due celle precedenti. Il metodo top-down, detto anche memoizzazione, mantiene la definizione ricorsiva: per trovare F(n), chiede F(n − 1) e F(n − 2). La differenza rispetto alla ricorsione semplice è che ogni chiamata guarda prima nella tabella, e calcola un termine solo se la sua cella è ancora vuota. Entrambi riempiono ogni cella una volta e usano n − 1 addizioni.
Perché la ricorsione semplice è così lenta
Senza tabella, F(n) chiama F(n − 1) e F(n − 2), entrambe chiamano F(n − 3) e così via: le chiamate formano un albero in cui gli stessi termini compaiono più e più volte. Il numero di chiamate è 2·F(n + 1) − 1, che cresce veloce quanto i numeri di Fibonacci stessi: 177 chiamate per F(10), 21.891 per F(20) e più di 331 milioni per F(40). Sottoproblemi sovrapposti come questi sono proprio ciò per cui esiste la programmazione dinamica.
Domande frequenti
Che cos'è la programmazione dinamica?
Un modo di risolvere un problema dividendolo in problemi più piccoli che si sovrappongono, risolvendo ciascuno una sola volta e conservando la sua risposta in una tabella. I numeri di Fibonacci sono l'esempio più semplice: ogni termine si costruisce dai due precedenti.
Qual è la differenza tra memoizzazione e tabulazione?
La memoizzazione mantiene il codice ricorsivo e salva ogni risposta la prima volta che viene calcolata, così le chiamate successive la leggono e basta. La tabulazione riempie la tabella in un ordine che garantisce che ogni risposta di cui una cella ha bisogno sia già lì. Entrambe fanno le stesse addizioni; la tabulazione evita la pila delle chiamate, e la memoizzazione calcola solo le celle che servono davvero.
Quante addizioni servono per F(n)?
n − 1 con una tabella: una per ogni termine da F(2) a F(n). Vengono letti solo gli ultimi due termini, quindi un programma può anche tenere solo due numeri invece dell'intera tabella.
Perché l'app si ferma a n = 40?
F(40) = 102.334.155 sta ancora comodamente sullo schermo, e la ricorsione semplice avrebbe già bisogno di 331.160.281 chiamate per calcolarlo. I termini più grandi crescono in fretta: F(78) è il più grande che un numero JavaScript rappresenta esattamente.
Viene inviato qualcosa da qualche parte?
No. Tutto viene calcolato nel tuo browser, e le tue ultime impostazioni restano nella memoria locale di questo browser.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Vai all'editor