Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Problema del cambio monete
Forum - C/C++ - Problema del cambio monete

Avatar
swet (Normal User)
Pro


Messaggi: 128
Iscritto: 01/01/2009

Segnala al moderatore
Postato alle 18:37
Mercoledì, 22/04/2015
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++

  1. Dati
  2. Un intero n>0
  3. Un insieme di banconote D con valori {d1,…,dm}
  4. 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++

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define max 50
  5. int cambio(int taglibanconote[],int valorecambiare);
  6. int main (void){
  7.         int *tagli,n,i,banconota,originale;
  8.         i=0;
  9.         //HUMAN INTERFACE
  10.                 printf("Benvenuto nel programma del cambio delle monete\n");
  11.                 printf("Per iniziare, definisci il numero dei tagli delle banconote in uso nel tuo paese\n");
  12.                         scanf("%d",&n);
  13.                         tagli=(int*)malloc(n * sizeof(int ));//alloco la memoria necessaria
  14.                 if(tagli==NULL) { // controllo la memoria allocata
  15.                         printf("Spiacente, non posso allocare la memoria, spazio non sufficiente\n");
  16.                         return -1 ;
  17.                 }
  18.                 // Riempimento ARRAY
  19.                 printf("Inserisci ora i tagli delle banconote in uso nel tuo paese\n");
  20.                 for (i=0;i<n; i++){
  21.                         scanf("%d",&banconota);
  22.                         tagli[i]= banconota;
  23.                        
  24.                 }
  25.                
  26.                 // acquisizione del Valore da cambiare
  27.                 printf("Ora, inserisci il valore che vuoi cambiare\n");
  28.                 scanf("%d",&originale);
  29.                 // inizio dell' algoritmo
  30.                 cambio(tagli,originale);
  31.                
  32.                 // termine del programma
  33.                 printf("Sto liberando la memoria\n");
  34.                 free(tagli);
  35.                 printf("Programma terminato con successo\n");
  36.                        
  37.                
  38. }
  39.  
  40. //funzione cambia monete
  41. int cambio(int taglibanconote[],int valorecambiare){
  42.         int i,j,min;
  43.         i=0;
  44.        
  45.         min=65536;
  46.        
  47. int moneteprovate[max];
  48.  
  49. printf("Vuoi cambiare %d euro , provo a darti la moneta %d \n",valorecambiare,moneteprovate[i]);
  50.  
  51. for (i=0;i<valorecambiare;i++){
  52.        
  53.        
  54.                 for (j=0;j<3;j++){ // 3 tagli banconote
  55.                
  56.                                         if (cambio(moneteprovate[j],1+(valorecambiare-min) < min)){
  57.                                                 valorecambiare-=min;
  58.                                         printf("%d\n",valorecambiare);
  59.                                 taglibanconote[i]=min; 
  60.                                         }
  61.                
  62.                 }
  63.                
  64.                 printf("%d",min);
  65.        
  66.  
  67. }
  68. }





PM Quote
Avatar
torn24 (Normal User)
Pro


Messaggi: 138
Iscritto: 04/01/2008

Segnala al moderatore
Postato alle 7:35
Giovedì, 23/04/2015
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.


Se si impara dai propri sbagli
non è cosi drammatico  sbagliare !
PM Quote