/*                             Geldwechsler */

/* Programm zur Berechnung der Anzahl der Moeglichkeiten, einen bestimmten */
/* Geldbetrag (DM und Pfennige) in Geldscheine und Geldmuenzen auszuzahlen. */
/* Der Geldbetrag wird im Programm als Geldbetrag in der kleinsten Einheit */
/* der Waehrung angesehen (in Deutschland also in Pfennigen).  */
/* Gleiche Scheine und Muenzen (5 DM) werden als ein(!) Schein betrachtet. */
/* Da die Berechnung grosser Geldbetraege lange dauert und es sehr schnell */
/* zu einer Zahlenbereichsueberschreitung kommt, ist es empfehlenswert, mit */
/* kleinen Geldbetraegen (<10 DM) zu testen. */
/* Verbesserungsvorschlaege oder Anfragen per E-Mail erwuenscht. */
/* Autor  : Kai Fuchs */
/* E-Mail : Kai.Fuchs@Student.Uni-Magdeburg.De */

#include <stdio.h>

unsigned long change(unsigned long pfennig,
                     unsigned long rest,
			      long *geld)                       /* Kommentar 1 */
{
 if (geld[1]==0) return(1);                                     /* Kommentar 2 */
 if (rest>=2*geld[0]) return(change(pfennig,rest-geld[0],geld)+
    change(rest-geld[0],rest-geld[0],geld+1));                  /* Kommentar 3 */
 if (rest>1+geld[0]) return(change(pfennig,pfennig,geld+1)+
    change(rest-geld[0],rest-geld[0],geld+1));                  /* Kommentar 4 */
 return((rest/geld[0])+change(pfennig,pfennig,geld+1));         /* Kommentar 5 */
}

/* Kommentar 1: */
/* Dies ist der applikative Algorithmus, der die Geldsumme zerlegt. */
/* Aufruf: wechsel=change(zu_wechselnder_Geldbetrag, */
/*              	  noch_uebriger_Geldbetrag, */
/*       		  Feld der noch uebrigen Geldmuenzen/scheine); */

/* Kommentar 2 */
/* Wenn die kleinste Geldmuenze erreicht ist (wenn das naechste Zeichen im Feld */
/* eine Null ist), so gibt es genau eine Moeglichkeit, den Geldbetrag nur(!) in */
/* die kleinste Geldmuenze zu zerlegen. */

/* Kommentar 3 */
/* Wenn der/die Geldschein/ -muenze noch zweimal den Geldbetrag wechseln kann, */
/* so wechsle den Geldbetrag nocheinmal in die/den aktuelle/n Muenze/Schein: */
/*  ---> change(pfennig,rest-geld[0],geld) */
/* Dann wechsle den nach dem Wechseln uebrigen Geldbetrag noch in die/den */
/* naechstkleinere/n Muenze/Schein: */
/*  ---> change(rest-geld[0],rest-geld[0],geld+1) */
/* Dann liefere die Summe an die Funktion zurueck, die dich aufgerufen hat. */

/* Kommentar 4 */
/* Wenn nach dem Wechseln des Geldbetrages ein wechselbarer Geldbetrag bleibt, */
/* so wechsle diesen in die/den naechstkleinere/n Muenze/Schein: */
/*  ---> change(rest-geld[0],rest-geld[0],geld+1) */
/* Wechsle nun den vollen Geldbetrag in die/den naechstkleinere/n Muenze/Schein: */
/*  ---> change(pfennig,pfennig,geld+1) */
/* Dann liefere die Summe an die Funktion zurueck, die dich aufgerufen hat. */

/* Kommentar 5 */
/* In allen anderen Faellen : */
/*  Wechsle den vollen Geldbetrag in die/den naechstkleinere/n Muenze/Schein: */
/*   ---> change(pfennig,pfennig,geld+1) */
/*  Wenn der/die Geldschein/-muenze den Geldbetrag wechseln kann (rest=geld[0]+1 */
/*  oder rest=geld[0]), so ist rest/geld[0]=1. Ist der/die Geldschein/-muenze */
/*  groesser als der Geldbetrag, so ist rest/geld[0]=0. */
/*  Liefere die Summe an die Funktion zurueck, die dich aufgerufen hat. */

void main()
{
 unsigned long pfennig, wechsel;
 long werte[16]={100000,50000,20000,10000,5000,2000,1000,500,200,
                 100,50,10,5,2,1,0};       /* Feld aller moeglichen Geldwerte */
                                           /* wird von der '0' abgeschlossen */
 float dmark;
 printf("Welchen Geldbetrag wollen Sie gewechselt haben (z.Bsp 2.13)? ");
 scanf("%f",&dmark);
 pfennig=dmark*100;                        /* Geldbetrag in Pfennige umrechnen */
 wechsel=change(pfennig,pfennig,werte);    /* Funktionsaufruf */
 printf("\nBei %.2f DM gibt es %lu Wechselmoeglichkeiten.\n",dmark,wechsel);
}