- In riempimento
- Letta
- Risposta
Problema del resto
Con pochi tipi di monete, come si paga un importo esatto con il minor numero possibile di monete, e in quanti modi si può fare? La risposta greedy, prima la moneta più grande, funziona con il denaro vero ma fallisce con alcuni insiemi di monete. Una tabella che costruisce ogni importo a partire da quelli più piccoli trova sempre la risposta giusta. Tocca una moneta nel vassoio per metterla sul bancone, e tocca una moneta sul bancone per riprenderla. L'indicatore si riempie fino all'importo: formalo esattamente, con meno monete che puoi. Minimo di monete mostra la risposta migliore, e Greedy mostra cosa ottieni prendendo sempre la moneta più grande che ci sta, che non sempre dà il minimo. Cambia le monete (in centesimi) e l'importo nel pannello. La vista Tabella mostra come la programmazione dinamica trova il minimo di monete, o conta il numero di modi per formare l'importo: premi Avvia per vedere la tabella riempirsi, oppure Passo e Indietro per procedere un passo alla volta, e trascina il cursore dei passi per saltare dove vuoi. Ogni moneta si può usare tutte le volte che vuoi. Con la tabella selezionata, i tasti freccia avanzano di un passo, la barra spaziatrice avvia e mette in pausa, e Home e Fine saltano all'inizio e alla fine.
Come funziona
- Tocca le monete nel vassoio per comporre esattamente l'importo e guarda l'indicatore riempirsi in centesimi.
- Prova a usare meno monete possibile, poi premi Minimo di monete o Greedy per confrontare.
- Apri la vista Tabella e premi Avvia per vedere ogni cella leggere l'importo più piccolo da cui dipende.
Minimo di monete
L'importo 0 non richiede monete. Per ogni importo più grande, prova ogni moneta che non lo supera: quello che resta dopo quella moneta è un importo più piccolo, già nella tabella, quindi una moneta in più dà un candidato. Il candidato più piccolo va nella cella, e la moneta che lo ha dato viene salvata nella riga sotto. Quando la tabella è piena, le monete si rileggono a partire dall'obiettivo: prendi la sua ultima moneta, passa all'importo che resta e ripeti fino a 0.
Numero di modi
Per contare combinazioni invece di ordinamenti, la tabella aggiunge una moneta per riga. Una cella conta i modi per formare il suo importo con le monete fino alla sua riga: i modi senza la moneta più recente, cioè la cella sopra, più i modi che usano la moneta più recente almeno una volta, cioè la cella altrettante colonne a sinistra nella stessa riga. Poiché le monete vengono aggiunte in un ordine fisso, 1 + 2 e 2 + 1 sono lo stesso modo e vengono contati una volta sola.
Domande frequenti
Perché il metodo greedy fallisce?
Il greedy prende sempre la moneta più grande che ci sta e non torna mai indietro. Con le monete 1, 3 e 4 e un importo di 6, prende 4, poi 1 e 1: tre monete, quando ne basterebbero due da 3. Per sistemi di monete come l'euro o il dollaro statunitense il greedy risulta ottimale; questi sistemi si dicono canonici.
Qual è la differenza tra contare i modi e contare gli ordinamenti?
I modi considerano 1 + 2 e 2 + 1 la stessa combinazione; gli ordinamenti li contano separatamente. L'app conta i modi, aggiungendo le monete una riga alla volta. Per contare invece gli ordinamenti si scorrono gli importi e per ciascuno si prova ogni moneta.
Quanto è veloce l'algoritmo del problema del resto?
Entrambe le tabelle richiedono un numero di passi pari al numero di tipi di monete per l'importo. È veloce per importi nell'ordine delle migliaia, ma un importo può essere un numero enorme, quindi, misurato in base al numero di cifre, il problema in generale è NP-difficile.
E se un importo non si può formare?
La sua cella resta a ∞, per esempio gli importi 1 e 3 con le monete 2 e 5. Nella modalità Numero di modi il suo conteggio è semplicemente 0.
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