Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
Ich versuche die "Euro-Münzen für 100g" Aufgabe zu lösen. Ich würd das Problem gerne rekursiv lösen, weiss jedoch nicht, wie ich überhaupt anfangen soll...
Übungen zu Rekursion habe ich schon gemacht, also das allgemeine System ist mir bekannt, die Übungen waren jedoch im Vergleich zu dieser Aufgabe sehr einfach!
Wie sollte ich nun vorgehen bei der Aufgabe? Einen Ansatz / Idee von euch zu bekommen wäre schön.
Danke!
und wie man die Basisfälle geschickt nutzt:
Man hat also ein Problem, welches sich auf die Basisfälle reduzieren lässt.
100g bestehen aus dem Gewicht 1 Muenze und dem Gewicht einer Muenz-Kombination.
Eine Muenz-Kombination besteht aus 1 Muenze - oder 1 Muenze und einer weiteren Kombination. Es macht keinen Sinn mehr, nach Kombinationen zu suchen, wenn das Gesamtgewicht über 100g liegt.
Man schaut also nach, ob ein Basisfall vorliegt und handelt demensprechend:
ist das Gewicht=100, so hat man eine Lösung.
ist das Gewicht>100, so hat man keine Lösung und muss erstmal einen Schritt zurückgehen (denn wenn man schon über 100 ist, findet man keine weitere Kombo ).
ist das Gewicht <100, so kann man entweder schauen, ob man noch eine Kombo mit derselben Muenze bilden kann und ob es mit einer weiteren Muenze geht.
Code:
muenz_array={8,7,5,3,1};
global_loesungs_counter=0;
bilde_kombo(aktuelle_sum,aktuelle_muenze)
{
gewicht=aktuelle_sum+muenz_array[aktuelle_muenze];
if (gewicht==100)
{global_loesungs_counter++; return;}
if (gewicht>100)
return;
if (gewicht<100)
{
bilde_combo(gewicht,aktuelle_muenze); //einmal mit der aktuellen muenze probieren
if (aktuelle_muenze<muenz_array.length())
{
muenz_array++; //und fallls es geht, mit der nächsten
bilde_combo(gewicht,aktuelle_muenze);
}
}
}
Perfekte Erklärung... so hab ich mir das gedacht! =)
Klasse....
Läuft auch alles soweit sehr gut. Ist das Ergebnis von 697 Kombinationen korrekt?!
Ich habe zwei verschiedene gesehen in dem Thread der Programmieraufgabe, bin mir daher nicht sicher, da beide auf mein Ergebnis nicht zutreffen =)
Tolle Erklärung für die Aufgabe noch mal... echt super 8)
Zu dem Ergebnis: nee, 697 stimmt nicht ganz. Sorry,habe den Pseudocode nicht getestet und sehe da nun einen Denkfehler drin:
Code:
if (gewicht<100)
{
bilde_combo(gewicht,aktuelle_muenze); <--- man sollte ALLE noch verbleibende münzen testen
if (aktuelle_muenze<muenz_array.length())
{
muenz_array++; //und fallls es geht, mit der nächsten
bilde_combo(gewicht,aktuelle_muenze);
}
}
also: solange die Kombination unter 100 g bleibt und man noch verschiedene Münzen zur Auswahl hat, so sollte man ALLE testen. Gewichtbildung kann man sich eigentlich sparen und immer das aktuelle Gewicht als Referenz nehmen.
Code:
final static int WEIGHT=100*100;
final static int coins[]={850,780,750,574,410,392,306,230};
static int global_loesungs_counter=0;
public static void bilde_kombo(int aktuelle_sum, int aktuelle_muenze)
{
if (aktuelle_sum == WEIGHT) //ist das aktuelle gewicht ==100, haben wir eine lösung
{
global_loesungs_counter++;
return;
}
if (aktuelle_sum > WEIGHT) //sonst sind wir drüber
return;
if (aktuelle_sum < WEIGHT) // wir sind drunter und sollten erstmal weitere kombinationen probieren
{
while (aktuelle_muenze < coins.length)
{
int gewicht=aktuelle_sum + coins[aktuelle_muenze];
bilde_kombo(gewicht,aktuelle_muenze);
aktuelle_muenze++;
}
}
}
}
PS: weil ich im Code mit ganzen Zahlen arbeiten möchte, sind alle Gewichte *100