Euro-Münzen für 100g

Hallo!

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! :)

Gruß
Felix
 
Erkläre doch mal kurz, was die "100 Euro-Münzen für 100g"-Aufgabe ist.
 
Ja, genau ... um die Aufgabe geht es!
Ich bin bisher auch nicht weitergekommen, habe also immer noch keinen Ansatz oder eine Idee.
 
Das Ergebnis kommt ein klein wenig darauf an, mit welche Sprache man das umsetzen möchte. Der Ansatz ist allerdings ziemlich gut übertragbar.

Also, Du suchst zuerst die Basisfälle (Abbruchbedingung):

1)aktuelle_summe+aktuelle_muenze=100. (erfüllt - mach was enstsprechendes wie Counter hochzählen oder etwas ausgeben)

2)aktuelle_summe+aktuelle_muenze>100 (zuviel) (gehe nicht mehr weiter).

3)aktuelle_summe+aktuelle_muenze<100 -> hier gibt es womöglich noch eine Lösung und man muss weiter probieren

Nun überlegt man sich eine Funktion:
Code:
muenz_array={8,7,5,3,1};

bilde_kombo(aktuelle_sum,aktuelle_muenze)
{

}

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); 
      }
  }
}
 
Hallo CDW!

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)

Gruß
Felix
 
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
 
Zurück
Oben