Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Salve ragazzi , sto implementando il problema del cambio delle monete con il paradigma della programmazione dinamica.
di seguito il testo dell' esercizio:
Codice sorgente - presumibilmente C/C++
Dati
Un intero n>0
Un insieme di banconote D con valori {d1,…,dm}
Calcolare il minimo numero di banconote in cui la quantità n può essere cambiata
ho implementato il codice ma sembra non funzionare, il compilatore è sempre minGw, va sempre in overflow a run time, sicuramente sono sbagliati i due for( e ciò che c' è dentro), sono sicuro che la soluzione è banale ma purtroppo non riesco ad uscirne da questo problema. Non riesco nemmeno a trovare un sorgente di esempio. Ne avete, o sapete spiegarmi questo benedetto algoritmo?
Codice sorgente - presumibilmente C++
#include <stdio.h>
#include <stdlib.h>
#define max 50
int cambio(int taglibanconote[],int valorecambiare);
int main (void){
int*tagli,n,i,banconota,originale;
i=0;
//HUMAN INTERFACE
printf("Benvenuto nel programma del cambio delle monete\n");
printf("Per iniziare, definisci il numero dei tagli delle banconote in uso nel tuo paese\n");
scanf("%d",&n);
tagli=(int*)malloc(n *sizeof(int));//alloco la memoria necessaria
if(tagli==NULL){// controllo la memoria allocata
printf("Spiacente, non posso allocare la memoria, spazio non sufficiente\n");
return-1 ;
}
// Riempimento ARRAY
printf("Inserisci ora i tagli delle banconote in uso nel tuo paese\n");
for(i=0;i<n; i++){
scanf("%d",&banconota);
tagli[i]= banconota;
}
// acquisizione del Valore da cambiare
printf("Ora, inserisci il valore che vuoi cambiare\n");
scanf("%d",&originale);
// inizio dell' algoritmo
cambio(tagli,originale);
// termine del programma
printf("Sto liberando la memoria\n");
free(tagli);
printf("Programma terminato con successo\n");
}
//funzione cambia monete
int cambio(int taglibanconote[],int valorecambiare){
int i,j,min;
i=0;
min=65536;
int moneteprovate[max];
printf("Vuoi cambiare %d euro , provo a darti la moneta %d \n",valorecambiare,moneteprovate[i]);
Ciao, esiste un problema di fondo, che se il taglio di banconote non prevede l'unità, non tutti i valori potranno essere cambiati.
Esempio, tre banconote da 50-10-5 euro , valore da cambiare 82
1 banconota da 50 , 3 da dieci , e mancherebbero i 2 euro ???
Per il resto, tu risolvi questo problema continuamente con la tua mente, rendi conscio quello che fai e ricavane l'algoritmo.
esempio:
hai un valore da cambiare con il minor numero di monete
prendi il valore e vedi quante banconote di taglio più grosso puoi usare
quello che avanza, controlli quante banconote di taglio immediatamente minore servono
e procedi cosi fino ad arrivare al valore voluto.
e saprai che in questo modo avrai impiegato il minor numero di banconote.
