Anzahl der Möglichkeiten 20 € zu bezahlen

[Velko]

Moin Freunde,

ich muss ein Programm schreiben, welches die Anzahl der Möglichkeiten wieder gibt zu bezahlen für einen bestimmten Betrag (Betrag <= 20). Jedoch muss das Programm Rekursiv geschrieben werden.

Um ehrlich zu sein, fehlt mir der Ansatz. Rekursion ist eh nicht wirklich meine Stärke.

Es sind keine Scheine erlaubt sondern nur die regulären Münzen.

Vielen Dank für die Hilfe!

 

[clownsmobil]

Eine beliebte Schulaufgabe . Lösungen dafür gibt's wie Sand am Meer. Eine kurze Google-Suche hat das hier ausgespuckt: http://forum.byte-welt.net/java-forum/allgemeine-themen/11089-rekursion-bezahlwege-muenzen.html. Schaus dir mal an und versuche es umzusetzen. Wenn noch Unklarheiten sind, dann einfach Fragen .

 

[Velko]

Hey! Erstmal vielen Dank für deine Liebe Antwort!

Ich habe mir die ersten Beiträge angeschaut und versuche mit folgender Methode zu arbeiten: Ich fange mit der höchsten Münze an und arbeite mich dann herunter. (Die Code Schnippsel habe ich mir mit absicht nicht angeguckt)

Ich habe jetzt eine Grobe Idee geschrieben, die rein theoretisch die Möglichkeiten wieder gibt mit 1 und 2 Cent Münzen. Jedoch klappt es bei mir gerade nur bei geraden Zahlen(Dieses Problem werde ich noch seperat betrachten)

Mein Code!

public class Üben {
    public static void Pay (int n){
         int [] Münzen = {1,2};
          int Betrag = 3432;
          int p = 0;
          int Zähler = 0;
          int Zwischenwert = 0;
          int Whilezähler = 0;
   
          while (Betrag !=Münzen[n]* p){
          if (Betrag ==Münzen[n]* p){
              Zähler += 1;
          }
          //Falls Höchste Münze nicht mehr funktioniert
          else if (Betrag != Münzen[n] * p){
              while (Betrag != Zwischenwert){
                Zwischenwert = (Münzen[n] * p) + (Münzen[n-1] * Whilezähler);
                Whilezähler +=1;         
              }
         Zähler +=1;  
          }
        p +=1;
    }
          System.out.print(Zähler + 1);} //return Pay (Betrag, n-1)

    public static void main(String args[]) {
      int n = 1;
      Pay(n);
  }
}

Der Rekursive Aufruf, wäre dann bei mir mit einer zweiten Funktion (Diese Funktion ist nur testweise) in der (m(Betrag), n-1(Münzenanzahl für das Array) zurück gegeben wird.

Ich habe jetzt nur ein Problem, ich möchte, dass das Array Münzen[n] die oberste Münze(theoretisch die 2 Euro Münze) mit immer kleineren Münzen vergleicht [n-1],[n-2], [n-3],[n-4]...[n-n].
Und wenn das getan wurde, wird der Rekusive Teil gestartet und ab da wird dann die oberste Münze, also dann 1 € mit den nächst kleineren Münze Betrachtet.

Ich hoffe, das ist einigermaßen verständlich!

Jedoch weiß ich nicht so richtig, wie ich dies implementieren soll. Hat vielleicht jemand eine Idee?

Mit freundlichen Grüßen!

Edit: Ich glaube, das Problem mit ungeraden Münzbeiträge, muss ich doch wesentlich früher lösen

Edit: An meiner inneren While-Schleife muss ich auch noch was ändern, sonst wird Sie unendlich lange ausgeführt.