Informatik Programmierung bestimmte Summe aus einer Reihe von Zahlen?
Hallo,
ich habe eine Aufgabe bekommen, in der aus einer Liste von Zahlen eine bestimmte Summe rausbekommen muss und diese Zahlenkombination dann ausgeben soll.
Ich habe bis jetzt das hier programmiert, aber ich komme nicht mehr weiter und gelange nur noch in eine Endlos-Schleife.
Die Zahlen sind 433, 382, 169, 153, 24 und 7 und es soll die Zahlenkombination rauskommen bei der die Summe gleich 888 ist.
import java.util.Random;
public class Pfeil
{
public static void main(String args[])
{
int erg = 0;
while (erg != 888)
{
erg = 0;
int [] arr={433, 382, 169, 153, 24,7};
Random r=new Random();
int zahl1=r.nextInt(arr.length);
int zahl2=r.nextInt(arr.length);
int zahl3=r.nextInt(arr.length);
int zahl4=r.nextInt(arr.length);
int zahl5=r.nextInt(arr.length);
int zahl6=r.nextInt(arr.length);
erg = zahl1+zahl2+zahl3+zahl4+zahl5+zahl6;
if ( erg == 888)
{
System.out.println(zahl1+""+zahl2+""+zahl3+""+zahl4+""+zahl5+""+zahl6);
}
}
}
}
Darf jede Zahl nur ein einziges mal verwendet werden, oder mehrmals ?
kann auch mehrmals vorkommen.
6 Antworten
Da meine bessere Hälfte wieder Ewigkeiten im Bad verbringt, habe ich die letzten 30 Minuten mal ein entsprechendes Programm für deine Frage geschrieben.
Ich erhebe keinen Anspruch an Code-Ästhetik oder -Effizienz. Wer das ganze rekursiv schreiben würde, hatte noch nie einen StackOverflowError in Java. Ich schon bei einem Sudokulöser, deswegen vermeide ich Rekursion praktisch immer!
Auch ist das Programm so geschrieben, dass es auf alle Arten Kombinationen ausgelegt ist, nicht nur für deine Zahlen. Die Zahlen werden als Parameter beim Programmaufruf übergeben. In deinem Fall also:
java Kombinationsfinder 888 433 382 169 153 24 7
Den Code findest du hier:
Einen Online Java Compiler hier:
https://www.jdoodle.com/online-java-compiler/
Als Ergebnis wird mit deinen Zahlen folgendes Ergebnis geliefert:
Finde alle Kombinationen der Werte:
888, 433, 382, 169, 153, 24, 7
--------------------------------
433 + 382 + 24 + 7 * 7 = 888 !!!
433 + 2 * 169 + 4 * 24 + 3 * 7 = 888 !!!
433 + 169 + 153 + 19 * 7 = 888 !!!
433 + 169 + 9 * 24 + 10 * 7 = 888 !!!
433 + 169 + 2 * 24 + 34 * 7 = 888 !!!
433 + 2 * 153 + 3 * 24 + 11 * 7 = 888 !!!
433 + 153 + 12 * 24 + 2 * 7 = 888 !!!
433 + 153 + 5 * 24 + 26 * 7 = 888 !!!
433 + 14 * 24 + 17 * 7 = 888 !!!
433 + 7 * 24 + 41 * 7 = 888 !!!
433 + 65 * 7 = 888 !!!
2 * 382 + 4 * 24 + 4 * 7 = 888 !!!
382 + 2 * 169 + 7 * 24 = 888 !!!
382 + 2 * 169 + 24 * 7 = 888 !!!
382 + 169 + 2 * 153 + 24 + 7 = 888 !!!
382 + 169 + 153 + 3 * 24 + 16 * 7 = 888 !!!
382 + 169 + 12 * 24 + 7 * 7 = 888 !!!
382 + 169 + 5 * 24 + 31 * 7 = 888 !!!
382 + 2 * 153 + 6 * 24 + 8 * 7 = 888 !!!
382 + 153 + 8 * 24 + 23 * 7 = 888 !!!
382 + 153 + 24 + 47 * 7 = 888 !!!
382 + 17 * 24 + 14 * 7 = 888 !!!
382 + 10 * 24 + 38 * 7 = 888 !!!
382 + 3 * 24 + 62 * 7 = 888 !!!
4 * 169 + 153 + 24 + 5 * 7 = 888 !!!
4 * 169 + 3 * 24 + 20 * 7 = 888 !!!
3 * 169 + 153 + 6 * 24 + 12 * 7 = 888 !!!
3 * 169 + 15 * 24 + 3 * 7 = 888 !!!
3 * 169 + 8 * 24 + 27 * 7 = 888 !!!
3 * 169 + 24 + 51 * 7 = 888 !!!
2 * 169 + 3 * 153 + 13 * 7 = 888 !!!
2 * 169 + 2 * 153 + 9 * 24 + 4 * 7 = 888 !!!
2 * 169 + 2 * 153 + 2 * 24 + 28 * 7 = 888 !!!
2 * 169 + 153 + 11 * 24 + 19 * 7 = 888 !!!
2 * 169 + 153 + 4 * 24 + 43 * 7 = 888 !!!
2 * 169 + 20 * 24 + 10 * 7 = 888 !!!
2 * 169 + 13 * 24 + 34 * 7 = 888 !!!
2 * 169 + 6 * 24 + 58 * 7 = 888 !!!
169 + 4 * 153 + 3 * 24 + 5 * 7 = 888 !!!
169 + 3 * 153 + 5 * 24 + 20 * 7 = 888 !!!
169 + 2 * 153 + 14 * 24 + 11 * 7 = 888 !!!
169 + 2 * 153 + 7 * 24 + 35 * 7 = 888 !!!
169 + 2 * 153 + 59 * 7 = 888 !!!
169 + 153 + 23 * 24 + 2 * 7 = 888 !!!
169 + 153 + 16 * 24 + 26 * 7 = 888 !!!
169 + 153 + 9 * 24 + 50 * 7 = 888 !!!
169 + 153 + 2 * 24 + 74 * 7 = 888 !!!
169 + 25 * 24 + 17 * 7 = 888 !!!
169 + 18 * 24 + 41 * 7 = 888 !!!
169 + 11 * 24 + 65 * 7 = 888 !!!
169 + 4 * 24 + 89 * 7 = 888 !!!
4 * 153 + 8 * 24 + 12 * 7 = 888 !!!
4 * 153 + 24 + 36 * 7 = 888 !!!
3 * 153 + 17 * 24 + 3 * 7 = 888 !!!
3 * 153 + 10 * 24 + 27 * 7 = 888 !!!
3 * 153 + 3 * 24 + 51 * 7 = 888 !!!
2 * 153 + 19 * 24 + 18 * 7 = 888 !!!
2 * 153 + 12 * 24 + 42 * 7 = 888 !!!
2 * 153 + 5 * 24 + 66 * 7 = 888 !!!
153 + 28 * 24 + 9 * 7 = 888 !!!
153 + 21 * 24 + 33 * 7 = 888 !!!
153 + 14 * 24 + 57 * 7 = 888 !!!
153 + 7 * 24 + 81 * 7 = 888 !!!
153 + 105 * 7 = 888 !!!
37 * 24 = 888 !!!
30 * 24 + 24 * 7 = 888 !!!
23 * 24 + 48 * 7 = 888 !!!
16 * 24 + 72 * 7 = 888 !!!
9 * 24 + 96 * 7 = 888 !!!
2 * 24 + 120 * 7 = 888 !!!
--------------------------------
Alle 70 Kombinationen in 16535 Durchläufen gefunden!
Ich hoffe, es hilft dir weiter.
Mit Raten durch Zufallszahlen kommst Du wohl kaum auf ein Ergebnis.
Wenn jede Zahl mehrfach vorkommen darf, ist es ein einfaches ganzzahliges Teilsummenproblem. Das lässt sich für kleine Mengen rekursiv lösen:
Bei Deinem Beispiel heißt das: Löse das Problem für
- Summe=888 (mit 0*433)
- Summe=455 (mit 1*433)
- Summe=22 (mit 2*433)
und jeweisl den restlichen Zahlen 382, 169, 153, 24, 7.
Wenn keine Zahlen mehr übrig sind, hast Du genau dann eine Lösung, wenn Summe==0 ist:
/** find values count[0..size], s.th.
* total == sum(count[i]*weight[i]) for 0≤i≤size
* @return #solutions found
**/
static int fill (int total, int size, int[] weight, int count[]) {
if (size<=0) {
if (total==0) {
print(weight, count);
return 1; // solution found
}
return 0; // no solution
}
--size;
int solutions = 0;
for ( count[size]=0; count[size]*weight[size]<=total; ++count[size] )
solutions += fill( total-count[size]*weight[size], size, weight, count);
return solutions;
}
static void print (final int[] weight, final int count[]) {
assert weight.length==count.length;
String delim = "\n==> ";
for ( int i=0; i<weight.length; ++i )
if (count[i]>0) {
System.out.printf( "%s%d*%d", delim, count[i], weight[i]);
delim = "+";
}
}
Diese Implementierung hat noch reichlich Luft für Optimierungen. Aber das wird erst interessant, wenn viel mehr Zahlen und/oder eine viel größere Summe gegeben sind.
Da du geschrieben hast, dass Zahlen auch mehrfach vorkommen dürfen.
Hier mal eine Liste von Kombinationen, die ich gefunden habe :
Die Zahl 24 mit sich selbst addiert und zwar 37 mal = 888, weil 24 ein Teiler von 888 ist.
24 + 24 + 120 + 120 + 120 + 120 + 120 + 120 + 120 = 888
30 mal hintereinander die 24 addiert und danach 24 mal hintereinander die 7 addiert = 888
23 mal hintereinander die 24 addiert und danach 48 mal hintereinander die 7 addiert = 888
16 mal hintereinander die 24 addiert und danach 72 mal hintereinander die 7 addiert = 888
1 mal die 433 und danach 65 mal hintereinander die 7 addiert = 888
Das sind alle Kombinationen die ich finden konnte. Vielleicht nutzt es dir ja was.
Super, dann hast du ja noch eine Kombination gefunden !
Super. Ich hatte das Prinzip, welches ich in meiner Antwort beschrieben habe, nur im Kopf durchgespielt und das war die erste Kombination, die ich gefunden habe. ^^
Ich hatte es auch zufällig gemacht, denke aber mit einer sogenannten systematischen Brute-Force-Suche macht man es am besten, wenn man wirklich alle Kombinationen finden will.
Ich wüsste keine andere sinnvolle Möglichkeit.
Mit jeder Art von Zufallssuche provoziert man nahezu eine Endlos-Schleife (von den unzähligen Wiederholungen bereits getesteter Kombination mal ganz zu schweigen) und ich wüsste keine andere Möglichkeit systematisch zu einer Lösung zu kommen.
Aber bitte nicht rekursiv. Hatte in Java mal einen Sudokulöser geschrieben. Zu erst mit Rekursion - bereits beim Testsudoku hatte ich den Speicher für die Funktion ausgereizt. Hinterher alles mit Iteration gemacht - war lästige Schreibarbeit, aber lieferte in < 1 Sekunde eine Lösung. ^^
Sowas würde ich eher rekursive lösen. Dein Baum hat oben die gewünschte Zahl und erzeugt ein neues Teilproblem für die Zahl minus der Zahlen aus deiner Reihe. Und dies wird eben bis nach unten fortgeführt. Die Sachen die am Ende mit 0 enden sind deine Treffer, die du dann innerhalb eines Arrays hochgeben kannst in dem Stack. Da sich viele der Kombinationen wiederholen könnten, gerade bei kleineren Zahlen wäre das ein Problem für dynamische Programmierung, sprich memoization.
Sprich dein erstes Problem ist wie man 888 bekommt. Das wird zu Teilproblemen von 888 - 433, 888 - 382, 888 - 169.. etc.
Da durch entstehen dann neue Probleme, sprich wie du mit dieser Zahlenkombination 455 aufsummiert (888 - 433) etc.
Ich persönlich würde einen Algorithmus schreiben, der ähnlich vorgeht, wie beim Sudoku lösen.
Man sortiert die Zahlen absteigend (in deinem Beispielarray schon erledigt) und pickt sich die größte Zahl.
Diese addiert man so lange, bis man über der gewünschten Zahl hinauskommt:
433 + 433 = 866 | weiter mit 433 addieren
433 + 433 + 433 = 1299 | letzten Schritt rückgängig machen
433 + 433 + 382 = 1248 | letzten Schritt rückgängig machen
433 + 433 + 169 = 1034 | letzten Schritt rückgängig machen
433 + 433 + 153 = 1019 | letzten Schritt rückgängig machen
433 + 433 + 24 = 890 | letzten Schritt rückgängig machen
433 + 433 + 7 = 873 | aktuelle Zahl weiter hinzu addieren
433 + 433 + 7 + 7 = 880 | und wieder
433 + 433 + 7 + 7 + 7 = 887 | und wieder
433 + 433 + 7 + 7 + 7 + 7 = 894
Da wir mit 7 bei der letzten Zahl angekommen sind und über 888 hinaus sind, lässt sich keine Kombination mit 2*433 bilden, also gehen wir zu 433 zurück und gehen zur 382 als zweite Zahl über:
433 + 382 = 815 | weiter mit 382 addieren
433 + 382 + 382 = 1197 | letzten Schritt rückgängig machen
433 + 382 + 169 = 984 | letzten Schritt rückgängig machen
433 + 382 + 153 = 968 | letzten Schritt rückgängig machen
433 + 382 + 24 = 839 | weiter mit 24
433 + 382 + 24 + 24 = 863 | weiter mit 24
433 + 382 + 24 + 24 + 24 = 887 | weiter mit 24
433 + 382 + 24 + 24 + 24 + 24 = 911 | einen Schritt zurück
433 + 382 + 24 + 24 + 24 + 7 = 894 | einen Schritt zurück
433 + 382 + 24 + 24 + 7 = 870 | weiter mit 7
433 + 382 + 24 + 24 + 7 + 7 = 877 | weiter mit 7
433 + 382 + 24 + 24 + 7 + 7 + 7 = 884 | weiter mit 7
433 + 382 + 24 + 24 + 7 + 7 + 7 + 7 = 891 | zurück
433 + 382 + 24 + 7 + ... | usw.
433 + 382 + 7 + ... | usw.
Es passt auch nicht mit 433 + 382 keine Kombination, also nehmen wir nun 433 + 169:
433 + 169 = 602 | weiter mit 169
433 + 169 + 169 = 771 | weiter mit 169
433 + 169 + 169 + 169 = 940 | letzten Schritt zurück
433 + 169 + 169 + 153 = 924 | letzten Schritt zurück
433 + 169 + 169 + 24 = 795 | weiter mit 24
433 + 169 + 169 + 24 + 24 = 819 | weiter mit 24
433 + 169 + 169 + 24 + 24 + 24 = 843 | weiter mit 24
433 + 169 + 169 + 24 + 24 + 24 + 24 = 867 | weiter mit 24
433 + 169 + 169 + 24 + 24 + 24 + 24 = 891 | zurück
433 + 169 + 169 + 24 + 24 + 24 + 24 + 7 = 874 | weiter mit 7
433 + 169 + 169 + 24 + 24 + 24 + 24 + 7 + 7 = 881 | weiter mit 7
433 + 169 + 169 + 24 + 24 + 24 + 24 + 7 + 7 + 7 = 888
Ziel erreicht. So würde man im Grunde jede denkbare Kombination ausprobieren. Allerdings würde ich es auf 100-200 Summanden begrenzen oder sowas, sonst brauchst du einen Supercomputer. ;-)
Nachtrag: Allerdings ist es lohnenswert erstmal zu gucken, ob sich die gewünschte Zahl nicht durch einen der Summanden restlos teilen lässt.
Wie von AusMeinemAlltag beschrieben also zum Beispiel
if (888 % 24 == 0)
Damit kann man schon mal relativ unkompliziert (mit array.length Durchläufen) ermitteln, ob es nicht eine simple zu errechnende Kombination gibt. ;-)
Also z.B. so:
Boolean found_solution = false;
int magic_number=888;
for (int i=0; i<arr.length; i++) {
if (magic_number%arr[i]==0) {
System.out.println(""+arr[i]+" * " + (magic_number/arr[i]) + " = " + magic_number + "");
found_solution = true;
break;
}
}
if (found_soulution==false) {
while (erg != 888) {
...
}
}
Wäre die Variante, dir mir der Algorithmus ausspuckt, der mir im Kopf vorschwebt.
Wobei ich zugebe, dass es am sinnvollsten wäre, erstmal zu gucken, ob sich die gewünschte Kombination nicht restlos durch eines der Glieder teilen lässt (wie die von dir beschriebene => 37*24).