Algorithmus, beliebige Anzahl doubles kombinieren

[dflasjjs]

Hi,

ich habe drei Geldbeträge: 1, 10 und 100 Euro.
Jetzt möchte ich eine Rechnung damit machen, der Benutzer gibt dazu eine weitere Zahl an, nämlich wie oft er Geldbeträge erhält.

Benutzer gibt also beispielsweise 2 ein. Jetzt brauch ich einen Algorithmus, der mir alle möglichen Kombinationen (Anzahl ist immer 3^(Zahl die Benutzer eingibt) zusammenstellt.
Bei 2 wäre das denn eben:
1 und 1€
1 und 10 €
1 und 100€
10 und 1€
10 und 10 €
10 und 100€
100 und 1€
100 und 10 €
100 und 100€

Das Algorithmus soll eben immer funktionieren, egal ob der Benutzer 2 oder 7 eingibt.
Wie kann ich das umsetzen?

 

[Painii]

Wie kann ich das umsetzen?

Ich würds mit Schleifen machen die durch die Werte zählen und dafür alle Kombinationen aufschreiben. Ist nicht wirklich schwer, dauert aber für große Eingaben entsprechend lange.

 

[dflasjjs]

Ja, aber wie zähle ich durch die Werte am besten? Kombinationen Aufschreiben ist selbst bei Benutzereingabe 7 nicht mehr drin. Wenn der Benutzer aber 7 eintippt, bräuchte ja auch noch 7 Zählvariablen oder wie würdest du das machen?

 

[Painii]

Ja, aber wie zähle ich durch die Werte am besten? Kombinationen Aufschreiben ist selbst bei Benutzereingabe 7 nicht mehr drin. Wenn der Benutzer aber 7 eintippt, bräuchte ja auch noch 7 Zählvariablen oder wie würdest du das machen?

Rekursion.
Hast ja immer das gleiche Teilproblem.

 

[Landei]

Du kannst einfach alle Kombinationen von n Beträgen (1,10,100) als Zahl von 0..(3^n-1) auffassen. Dabei bekommtst du die Nummer des Betrags (0,1,2 für 1,10,100) durch die Operation %3, für die nächste "Stelle" musst du ganzzahlig durch 3 dividieren. Klingt kompliziert, du rechnest aber einfach nur im Dreiersystem statt im gewohnten Zehnersystem.

Aus'm Kopp & ungestestet:

int[] betrag = {1,10,100};
int n = 3; //oder was auch immer
int max = 1;
for(int i = 0; i < n; i++) {
  max *= 3;
}

//Alle Kombinationen auslesen
for(int i = 0; i < max; i++) {
   int k = i;
   for(j = 0; j < n; j++) {
      System.out.println("" + betrag[k%3] + "€ ");
      k = k / 3; 
   }
   System.out.println();
}

 

[dflasjjs]

Klasse, funzt super. Danke dir!

 

[ARadauer]

so musst du die beträge nicht fix codieren...

 int zahl = 10;
     
     int[] werte = new int[zahl];
     werte[0] =1;
     for(int i = 0; i< werte.length-1; i++){
        werte[i+1]=werte[i]*10;
     }
     
     System.out.println(Arrays.toString(werte));
     
     for(int i = 0; i < zahl; i++){
        for(int j = 0; j < zahl; j++){
           System.out.println(werte[i]+" und "+werte[j]+ " €");
        }
     }
     
   }

wobei ich vermute, dass das nicht die aufgabe war.. ich denke du hast da was falsch verstanden...

 

[Marco13]

Gibt's auch hier http://www.java-forum.org/codeschnipsel-u-projekte/81973-combinatorics.html