Java :: Aufgabe #239
2 Lösungen
Begleichung einer Rechnung ausschließlich mit Münzen
Anfänger - Java
von hollst
- 02.05.2019 um 15:46 Uhr
Angenommen, ihr hättet an der Kasse einen Betrag X zwischen (einschließlich) einem Cent und einem Euro zu bezahlen.
Schreibe ein Program, dass die Anzahl der Möglichkeiten berechnet, X ausschließlich mit 1, 2, 5 und 10 Cent-Münzen zu begleichen.
Beispiel: X = 5 Cent -> 4 Möglichkeiten (5; 2 + 2 + 1; 2 + 1 + 1+ 1; 1 + 1 + 1 + 1 + 1)
Achtung: für einen EURO (100 Cent) gibt es bereits 2.156 Möglichkeiten!
Viel Spaß!
Schreibe ein Program, dass die Anzahl der Möglichkeiten berechnet, X ausschließlich mit 1, 2, 5 und 10 Cent-Münzen zu begleichen.
Beispiel: X = 5 Cent -> 4 Möglichkeiten (5; 2 + 2 + 1; 2 + 1 + 1+ 1; 1 + 1 + 1 + 1 + 1)
Achtung: für einen EURO (100 Cent) gibt es bereits 2.156 Möglichkeiten!
Viel Spaß!
Lösungen:
Java-Codeimport java.util.Arrays;
public class Java_239 {
public static long waysToPay(int[] coinValues, int numCoins, int valueToPay){
//Tabelle speichert die Anzahl der Lösungen von i
long[] table = new long[valueToPay+1];
Arrays.fill(table,0);
table[0] = 1;
for (int i=0; i<numCoins; i++){
for (int j=coinValues[i]; j <=valueToPay; j++){
table[j] += table[j-coinValues[i]];
}
}
return table[valueToPay];
}
public static void main(String[] args) {
int arr[] = {1, 2, 5, 10};
int m = arr.length;
int n = 100;
long counter = waysToPay(arr,m,n);
System.out.println("Für den Betrag von " + n + " gibt es " + counter + " Möglichkeiten");
}
}
Folgende Lösung geht wie im Beispiel davon aus, dass die Reihenfolge der Münzen keine Rolle spielt, dass somit (2 + 2 + 1; 2 + 1 + 2; 1 + 2 + 2) als eine Möglichkeit gezählt wird. Folglich gibt es für 100 Cent nur 71 Möglichkeiten. (Kleiner Widerspruch in der Aufgabenstellung, dort spielt bei den 100 Cent und 2.156 Möglichkeiten die Reihenfolge eine Rolle :) )
Java-Code
Java-Code
public class BetragX {
public static final int X = 100;
public static void main(String[] args) {
byte coin = 0;
int possibilities = 1;
for(int a = 0; a < X;) {
int aRef = a;
int possibilitiesRef = possibilities;
switch(coin) {
case 0:
a += 10;
possibilities += 7;
break;
case 1:
a += 5;
possibilities += 3;
break;
case 2:
a += 2;
possibilities += 1;
break;
case 3:
a+= 1;
break;
}
if (a > X) {
a = aRef;
possibilities = possibilitiesRef;
coin++;
}
}
System.out.println(possibilities);
}
}