Lino il giornalaio.

Descrizione del problema

Il giornalaio Lino è un appassionato di matematica e, prima di consegnare il resto ai propri clienti, si diverte a calcolare mentalmente quante differenti possibilità esistono per consegnare tale resto.

Ad esempio, considerando l'Euro come valuta, per consegnare 6 centesimi di resto esistono le seguenti 5 possibilità:

Lino si sta però accorgendo che a causa della lentezza nella consegna del resto sta perdendo molti clienti. Pertanto, aiuta Lino a calcolare il numero di possibili combinazioni.

Dati di input
Il file input.txt contiene nella prima riga un intero positivo N che rappresenta il numero di monete diverse disponibili.
La seconda riga contiene un intero positivo R che rappresenta il resto da consegnare al cliente.
Ciascuna delle successive N righe contiene un intero positivo che indica il valore di ogni singolo tipo di moneta.

Dati di output
Il file output.txt è composto da una riga contenente un solo intero, che rappresenta il numero di tutte le possibili combinazioni di monete per la consegna del resto R (notare che possono essere usate più copie dello stesso tipo di moneta, per esempio 6 monete da cinque centesimi).

Assunzioni:

Esempio di input/output

file
input.txt		file
output.txt
85
6
1
2
5
10
20
50
100
200

Esempio di input/output

file
input.txt		file
output.txt
60
6
5
10
20
50
100
200

Analisi del problema

Si suppone di aver acquisito dal file di input i dati e di aver memorizzato:

  1. il resto nella variabile Resto

  2. i tagli delle singole monete nell'array Taglio

    Cioè
    Resto = 6
    Taglio[0] = 1
    Taglio[1] = 2
    Taglio[2] = 5
    Taglio[3] = 10
    Taglio[4] = 20
    Taglio[5] = 50

Per tentare di individuare il procedimento risolutivo, si osservino i modi in cui si può formare il resto 6:

  1. 6 monete da un centesimo,

  2. 4 monete da un centesimo e 1 da due centesimi,

  3. 2 monete da un centesimo e 2 da due centesimi,

  4. 1 moneta da un centesimo e 1 da cinque centesimi,

  5. 3 monete da due centesimi.

Per pervenire al primo risultato (6 monete da 1 centesimo):
Contare il numero di monete del Taglio[0] che si avvicinano per difetto, o formano esattamente l'importo Resto
Per ottenere tale conteggio:
dividere il Resto per il valore della moneta del Taglio[0]

a) NrMon0 = Resto / Taglio[0]

Nel caso specifico, essendo il valore del taglio minimo pari a 1 centesimo, il risultato fornisce il numero esatto di monete che formano l'importo.

Lo stesso Resto, però si ottiene con un numero minore di monete da 1 centesimo sommato ad altre monete di taglio superiore. (si vedano la seconda, la terza e la quarta combinazione).

Quindi il valore della variabile NrMon0 calcolato è il massimo numero che consente di uguagliare o avvicinare per difetto il Resto, si devono valutare anche le possibilità di ottenere lo stesso resto con valori inferiori di NrMon0, quindi si calcoli l'importo:

b) Somma0 = NrMon0·Taglio[0]

Poi si deve confrontare l'importo Somma0, formato da tale numero di monete, con il Resto:

    Se Somma0 è uguale al Resto

Se il confronto dà esito vero si è trovata una combinazione e si devono provare altre combinazioni usando un numero inferiore di monete:

    Allora:
        contare una combinazione,
        decrementare di uno il valore di NrMon0,
        ripetere dal punto b)

In caso contrario sicuramente la somma formata è inferiore al resto, bisogna perciò calcolare, usando una seconda variabile Somma1, quanto manca:

    Altrimenti:
        Somma1 = Resto - Somma0

Anche in questo caso bisogna valutare quante monete del taglio[1] occorrono per formare l'importo che manca:

        c) NrMon1 = Somma1 / Taglio[1]

Il procedimento si ripete perchè anche in questo caso si deve valutare se con un numero inferiore di monete del taglio[1] sommate a monete del Taglio[2] consentono di formare l'importo mancante:

        Se NrMon1·Taglio[1] + Somma0 uguaglia il Resto
        Allora:
            contare una combinazione,
            decrementare il valore NrMon1,
            ripetere dal punto c)
        Altrimenti:
            calcolare quanto manca
             . . .
             ecc.

Osservando la successione di operazioni ci si rende conto che i due rami (Allora ... Altrimenti) che seguono il confronto (Se) tra la somma ed il resto sono costituiti dalle stesse operazioni su variabili che, pur essendo diverse, hanno lo stesso significato:

ci sono le variabili NrMon0 e NrMon1, le variabili Somma0 e Somma1, continuando ci si accorgerà che serviranno le variabili NrMon2, NrMon3, ... Somma2, Somma3 ...

il procedimento in linguaggio C

Ripercorrendo i passi descritti si perviene alla seguente codifica:

Commenti

L'istruzione continue all'interno di un ciclo porta il flusso del programma al termine del ciclo, dove si incrementa la variabile di controllo del ciclo.

Ad esempio nel primo ciclo, dove la variabile di controllo è i, se, con i=6 si verifica l'uguaglianza tra Somma0 e Resto allora si conta una combinazione e l'istruzione continue provoca la continuazione del ciclo con il prossimo valore di i (cioè 5), altrimenti si entra nel ciclo successivo, dove la variabile di controllo è j.

Ci si è fermati ai primi tre tagli di monete, quindi si sono realizzati solo tre cicli. In pratica si sarebbe dovuto verificare il funzionamento del programma anche con solo 2 cicli.

Il metodo di costruzione del programma consiste nel risolvere il problema concentrandosi su problemi parziali. di complessità limitata, e solo dopo aver accertato che si ottengono risultati validi, si procede con la risoluzione di un'altra parte del problema.

Riconoscere la ricorsione.

Le operazioni che si ripetono sono comprese tra quella che calcola il Numero di monete di un certo taglio fino alla parentesi graffa di chiusura dell'istruzione if.

Questo blocco di istruzioni, opportunamente generalizzato con l'uso di un array per le variabili NrMon[ ] e un altro array per le variabili Somma[ ], diventa una funzione che chiama se stessa, passando come parametro il valore del taglio, a iniziare dal più piccolo, a terminare quando si giunge ad una somma residua minore del valore del Taglio di moneta oppure quando si sono esauriti i controlli su tutti i tagli.

Versione Ricorsiva della soluzione

I dati dovrebbero essere acquisiti dal file di input, ma questa operazione viene lasciata per esercizio, in questo esempio si indicano le variabili globali. Si tratta di:

Prima di proseguire nella lettura della soluzione si esorta il lettore a tentare di scrivere autonomamente la funzione ricorsiva.

la funzione che realizza la ricorsione.

Nella soluzione proposta di seguito si sono usati alcuni valori costanti. Il loro significato dovrebbe essere chiaramente deducibile dal contesto, e comunque possono essere generalizzati.

La funzione main ha il compito di acquisire i valori delle monete e altri valori descritti nella formulazione del problema, dopo di che è pronta per richiamare la funzione: NrMonete(0)

Il richiamo di tale funzione avviene dopo l'assegnazione dei valori agli elementi dell'array Taglio.

Al ritorno dalla funzione, nella variabile conta si trova il numero di combinazioni cercate.