/**
  * Copyright (c): Uwe Schmidt, FH Wedel
  *
  * You may study, modify and distribute this source code
  * FOR NON-COMMERCIAL PURPOSES ONLY.
  * This copyright message has to remain unchanged.
  *
  * Note that this document is provided 'as is',
  * WITHOUT WARRANTY of any kind either expressed or implied.
  */

/**
 * @autor Uwe Schmidt
 *
 * Geld wechseln
 *
 * Auf wieviele Arten kann man eine Mark wechseln?
 *
 * die Muenzwerte werden in einem Feld gespeichert,
 * das ab 0 indiziert wird
 */

//--------------------

class WechselGeld {

  public static
  void main( String[] args ) {

    int[] Pfennige = {
      1, 2, 5,
      10, 50,
      100, 200, 500,
      1000, 2000, 5000,
      10000, 20000, 50000,
      100000
    };

    GeldWechsler pf = new GeldWechsler(Pfennige);

    int n = 1;
    int res;

    try {
      n = Integer.valueOf(args[0]).intValue();
    } catch (Exception e) {}

    res = pf.wechseln(n);

    System.out.println
      ( "Geld wechseln\n\n" +
	n +
	" Pf. " +
	( n==1 ? "kann" : "koennen") +
	" auf " +
	res +
	" Art" +
	( res==1 ? "" : "en" ) +
	" gewechselt werden");
  }
}

//--------------------

/**
 * Die Geldwechselklasse mit einer Feld-Variable muenzen
 * fuer die erlaubten Muenzwerte
 */

class GeldWechsler {

  int[] muenzen;

  //--------------------

  GeldWechsler(int[] muenzen) {
    this.muenzen = muenzen;
  }

  //--------------------

  /**
   * @param betrag soll gewechselt werden
   * @param muenzarten bestimmt die Menge der Muenzen, die beim Wechseln
   * verwendet werden sollen, alle Werte in dem Feld muenzen im Intervall
   * 0 bis muenzarten einschliesslich werden verwendet
   */

  protected
  int wechseln(int betrag,
	       int muenzarten) {
    return
      ( betrag == 0 )
      ? 1
      : (
	 ( (betrag < 0) || (muenzarten < 0) )
	 ? 0
	 : ( wechseln( betrag - muenzen[muenzarten],
		       muenzarten)
             +
	     wechseln( betrag,
		       muenzarten - 1) ));
  }

  //--------------------

  /** die oeffentlich rechtliche Routine,
    * die die rekursive "wechseln" Routine startet
    */

  public
  int wechseln(int betrag) {
    return
      wechseln( betrag,
		muenzen.length -1);
  }
}

//--------------------