Algorithmus für Summenberechnung
-
Ich möchte einen Algorithmus schreiben, der verschiedene Summen von übergebenen Summanden in ein Array ablegt.
Der Kern soll soweit modifizierbar sein, dass man daraus Funktionen mit folgenden Möglichkeiten erstellen kann:
Dem Algorithmus werden n Summanden smd[n] übergeben.
1. Möglichkeit
Es sollen alle möglichen Summen bebildet werden (jeder Summand kann max. 1 mal benutzt werden).
z.B. n = 3 und die Summanden sind 2, 7 und 4
s[0] = 2
s[1] = 4
s[3] = 6 (2+4)
s[4] = 7
s[5] = 9 (2+7)
s[6] = 11 (4+7)
s[7] = 13 (2+4+7)
Doppelte Summen sollen erkannt und nicht in das Array geschrieben werden.
Die Summen müssen jedoch nicht sortiert sein.2. Möglichkeit
Dem Algorithmus wird zusätzlich ein MAX_LIMIT übergeben. Es werden alle Summen gebildet, welche das Limit nicht überschreiben.
Im Gegensatz zur ersten Möglichkeit können die Summanden beliebig oft in der Summe verwendet werden.
z.B. n = 2 und die Summanden sind 2 und 7. Das Limit ist 12
s[0] = 2
s[1] = 4 (2+2)
s[3] = 6 (2+4)
s[4] = 7
s[5] = 8 (2+2+2+2)
s[6] = 9 (2+7)
s[7] = 10 (2+2+2+2+2)
s[6] = 11 (2+2+7)
s[7] = 12 (2+2+2+2+2+2)3. Möglichkeit
Es wird wieder ein MAX_LIMIT übergeben. Es werden nur Summen akzeptiert, die dem MAX_LIMIT entsprechen.
z.B. n = 3 und die Summanden sind 2, 5 und 3. Das Limit ist 10
s[0] = 10 (2+2+2+2+2)
s[1] = 10 (2+3+5)
s[2] = 10 (2+2+3+3)
s[3] = 10 (5+5)
eine andere Anordnung der Summanden wie z.B. (2+3+5) -> (3+5+2) dabei zählen nicht.Das ganze möchte ich in C implantieren.
Wichtig ist mir, dass der Algorithmus möglichst effizient arbeitet und auch bei größeren Werten (n = ~1000) noch in einem angemessenem Zeitraum Ergebnisse liefert.Bisher fehlt mir einfach der Denkanstoß bzw. der Grundgedanke um das zu realisieren.
Ich hoffe auf Eure Hilfe
-
Ist das ernst gemeint? "alle möglichen Summen" --> 2^n Summen --> 2^1000 ints passen sicher nicht in deinen Speicher :>
Problem 3 ist außerdem NP-schwer
-
Simonek schrieb:
Das ganze möchte ich in C implantieren.
ich glaub' ansi/iso würde sowas ablehnen
-
life schrieb:
Ist das ernst gemeint? "alle möglichen Summen" --> 2^n Summen --> 2^1000 ints passen sicher nicht in deinen Speicher :>
Problem 3 ist außerdem NP-schwer
Problem 3 kannste ja trotzdem in O(n*MAX_LIMIT) lösen. Ob das was hilft ist vor allem von MAX_LIMIT abhängig.
-
Jester schrieb:
life schrieb:
Ist das ernst gemeint? "alle möglichen Summen" --> 2^n Summen --> 2^1000 ints passen sicher nicht in deinen Speicher :>
Problem 3 ist außerdem NP-schwer
Problem 3 kannste ja trotzdem in O(n*MAX_LIMIT) lösen. Ob das was hilft ist vor allem von MAX_LIMIT abhängig.
ja. Siehe z.b. http://www.c-plusplus.net/forum/viewtopic-var-t-is-155179-and-postdays-is-0-and-postorder-is-asc-and-start-is-0.html
-
1000 Elemente war übertrieben...ich wollte halt damit ausdrücken, dass der Algorithmus auch bei größeren Mengen noch zuverlässig arbeitet.
Der Link ist interessant!
werde gleich weiterlesen...
-
Ich hab mich an der 3. Möglichkeit versucht, aber mir fehlt irgendwie die zündende Idee...
Ich hab mal so angefangen, dass die sich Anfangssumme aus den wenigsten (daher größten) Werten zusammensetzt.
Die Werte habe ich in einem Array abgespeichert und ein zusätzliches Array mit Multiplikatoren gemacht.
Die Summe wird dann einfach eine Schleife ausgegeben:
for(count2=0;count2<anz;count2++) { summe += multi[count2]*zahl[count2]; printf("%3d*%3d ", multi[count2], zahl[count2]); if ( count2 < anz-1 ) printf("+ "); } printf("= %d\n", summe);Es geht jetzt praktisch nur noch darum, wie ich die Multiplikatoren anpasse.
Wenn ich z.B. als SUMME 100 habe und als Zahlen 50, 20 und 10 soll die Schleife so ablaufen:50 + 50 50 + 20 + 20 + 10 50 + 20 + 10 + 10 + 10 50 + 10 + 10 + 10 + 10 20 + 20 + 20 + 20 + 20 20 + 20 + 20 + 20 + 10 + 10 20 + 20 + 20 + 10 + 10 + 10 + 10 20 + 20 + 10 + 10 + 10 + 10 + 10 + 10 20 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10Wie passe ich jetzt die Multiplikatoren an?