Münzen Algorithmus

S

Sekiro24

Mitglied
Ich stehe vor einem Problem und weiss nicht weiter.
Wir sollen von der Uni aus ein Program erstellen, dass alle Kombinationen von einer beliebigen Anzahl unterschiedlicher Muenzen anzeigt. Dabei sollten wir wie folgt vorgehen:
Legen Sie die globen Integer-Variablen MAX und SUB fest, wobei SUB kleiner als MAX sein soll. Also SUB < MAX.
Im nächsten Schritt sollen MAX unterschiedliche Muenzen gegeben werden.
Anschließend soll jede Kombination aus SUB Münzen ausgegeben werden.
Zum Schluß soll die Gesamtzahl der Kombinationen ausgegeben werden.

Meine Frage:
Wie muss ich hierbei vorgehen, um zum Beispiel bei SUB = 5 von MAX = 8 unterschiedlichen Münzen, alle Kombinationen der 8 unterschiedlichen Münzen in 5 Iterationen(Stichwort) auszugeben und wie mache ich das dann für jede beliebige Anzahl von SUB aber kleiner MAX, wenn bei einem anderen mal SUB = 6 ist und MAX dann immernoch = 8 ist.
 
Hallo Sekiro24,
deine Frage ist etwas verwirrend gestellt. Sagen wir mal, wir haben insgesamt N verschiedene Münz-Typen. Bei Eurocent wären das 1C, 2C, 5C, 10C, 20C, 50C, 1€, 2€ also N = 8.
Ist bei dir MAX = N? Und was genau musst du ausgeben? Ich könnte mir vorstellen, dass die Aufgabe auf "wähle k verschiedene Münzen aus einem Pool von N" hinausläuft. Gibt es Regeln wonach du picken musst?

Davon ausgehend, dass wir Eurocent haben, und dass MAX = N = 8 ist, wären das hier also valide Kombinationen:
SUB = 3:
1C 2C 5C | 2C 5C 10C | 5C 10C 20C | ... | 50C 1€ 2€
SUB = 4:
1C 2C 5C 10C | 2C 5C 10C 20C | ... | 20C 50C 1€ 2€
SUB = MAX:
1C 2C 5C 10C 20C 50C 1€ 2€

Stimmt das so?

Gruß Technipion
 
Es geht bei der Aufgabe nur um die Kombination der MAX unterschiedlichen Münzen. Da spielt die Währung keine Rolle.
Sagen wir, wir haben MAX = N = 50 Münzen, dann sollen von 1 angefangen alle Kombinationen bis zu MAX = N = 50 ausgegeben werden. Von der Ausgabe soll genau das passieren :
Bsp:
MAX = 8
SUB=3
1, 2, 3 | 1, 2, 4, | 1, 2, 5 | 1, 2, 6 | .... | 6, 7, 8|
SUB = 4
1, 2, 3, 4| 1, 2, 3, 5 | 1, 2, 3, 6| ... |5, 6, 7, 8|

Also so habe ich es mir gedacht, damit auch die Iterationen einfach gehalten sind aber sonst ist es an sich ja richtig bis auf die Währung. Es sind hier nur Münzen gemeint.

Viele Grüße und Danke für deine Hilfe :)
 
Ah okay, also sollst du im Prinzip ein klassisches nCr-Problem lösen. Für die Theorie dahinter würde ich dich auf Wikipedia verweisen:
https://de.wikipedia.org/wiki/Urnenmodell#Ziehen_ohne_Zurücklegen_ohne_Beachtung_der_Reihenfolgehttps://de.wikipedia.org/wiki/Binomialkoeffizient#Der_Binomialkoeffizient_in_der_Kombinatorik
Ich habe dir hier mal ein kleines Java-Programm geschrieben, dass die Aufgabe für MAX = 50 und SUB = 3 löst:
Java: 
public class Example
{
  public static void main(String[] args) {
    final int MAX = 50; // Münzen von 1 bis 50

    int counter = 0;

    for (int m1 = 1; m1 <= MAX; m1++) {
      for (int m2 = m1+1; m2 <= MAX; m2++) {
        for (int m3 = m2+1; m3 <= MAX; m3++) {
          System.out.println(m1 + ", " + m2 + ", " + m3);
          counter++;
        }
      }
    }

    System.out.println("counter: " + counter);
  }
}
Das Programm gibt dir 19.600 Kombinationen von 3 Münzen (Werte 1 bis 50) aus. Gibt man bei Google "50 choose 3" ein, berechnet Google den Binomialkoeffizienten '50 über 3' zu 19.600, wir haben also richtig gerechnet.

Frage 1: Verstehst du den obigen Code und warum er die gesuchten Münzkombinationen (mit SUB = 3) ausgibt?

Frage 2: Kannst du den Code erweitern, sodass er Kombinationen für SUB = 4 ausgibt?

Frage 3: Kannst du den Code so erweitern, dass er für beliebige Werte von SUB die Kombinationen ausgibt?

Gruß Technipion
 
So ähnlich hatten wir das in der Aufgabe davor, da sollten wir das für eine feste Anzahl SUB machen.
Da hatten wir 6 unterschiedliche Münzen und mussten dann alle 4 Kombinationen daraus ausgeben, also da hatten wir dann 4 Schleifen, die ineinander geschachtelt waren.
Bei Variablem SUB bin ich mir nicht sicher wie ich daraus eine variable Anzahl an geschachtelten Schleifen machen soll.
 
Ich versuch dich mal in die Richtung zu schubsen....
Wenn du Technipion's Ansatz aus Post #4 anschaust, wirst du feststellen, dass Anzahl SUB der Anzahl For-Schleifen entspricht, ergo kann man die Anzahl For-Schleifen auch als "Rekursions-Tiefe" interpretieren.
Mal schauen, ob du verstehst was ich meine....
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück