Summanden für Summe gesucht (Formel?)

Neue Frage »

thursen Auf diesen Beitrag antworten »
Summanden für Summe gesucht (Formel?)
Meine Frage:
Ausgangswerte: Summe, Mögliche Summanden
Ziel: Drei Summanden, die die Summe ergeben

Einfaches Beispiel:
Summe = 15
Mögliche Summanden: 1, 2, 4, 7, 10, 13
Ergebnis: 4 + 4 + 7

######
Direktes Beispiel 1:

Mögliche Summanden:
Alle Kombinationen, die eine 32 Bit Zahl ergeben aus folgendem Pool:
"\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0b\x0c\x0e\x0f\x10\x11\x12\x13"
"\x14\x15\x16\x17\x18\x19\x1a\x1b\x1c\x1d\x1e\x1f\x20\x21\x22\x23\x24"
"\x25\x26\x27\x28\x29\x2a\x2b\x2c\x2d\x2e\x30\x31\x32\x33\x34\x35\x36"
"\x37\x38\x39\x3b\x3c\x3d\x3e\x41\x42\x43\x44\x45\x46\x47\x48\x49\x4a"
"\x4b\x4c\x4d\x4e\x4f\x50\x51\x52\x53\x54\x55\x56\x57\x58\x59\x5a\x5b"
"\x5c\x5d\x5e\x5f\x60\x61\x62\x63\x64\x65\x66\x67\x68\x69\x6a\x6b\x6c"
"\x6d\x6e\x6f\x70\x71\x72\x73\x74\x75\x76\x77\x78\x79\x7a\x7b\x7c\x7d"
"\x7e\x7f" (121 Bytes)

(121 mögliche Bytes)^4 Stellen = 214358881 mögliche Summanden

Zielsumme = 11800188B

Ergebnis = 55555521 + 55555421 + 6D556F49
######

Direktes Beispiel 2:
Mögliche Summanden:
"\x05\x06\x07\x08\x09\x0b\x0c\x0e\x0f\x10\x11\x12\x13"
"\x14\x15\x16\x17\x18\x19\x1a\x1b\x1c\x1d\x1e\x1f\x20\x21\x22\x23\x24"
"\x25\x26\x27\x28\x29\x2a\x2b\x2c\x2d\x2e\x30\x31\x32\x33\x34\x35\x36"
"\x37\x38\x39\x3b\x3c\x3d\x3e\x41\x42\x43\x44\x45\x46\x47\x48\x49\x4a"
"\x4b\x4c\x4d\x4e\x4f\x52\x53\x54\x55\x56\x57\x58\x59\x5a\x5b"
"\x5c\x5d\x5e\x5f\x60\x61\x62\x63\x64\x65\x66\x67\x68\x69\x6a\x6b\x6c"
"\x6d\x6e\x6f\x70\x71\x72\x73\x74\x75\x76\x77\x78\x79\x7a\x7b\x7c\x7d"
"\x7e\x7f" (115 Bytes)

(115 mögliche Bytes)^4 Stellen = 174900625 mögliche Summanden

Zielsumme = 150158A51

Ergebnis: 75612171 + 75612171 + 6553476F
#######

Erstelle eine Formel bzw. Rechenweise, wie die möglichen Summanden berechnet werden können.
Es reicht eine mögliche Kombination von Summanden.

Bedingung: Die möglichen Summanden sowie die Zielsumme müssen variabel sein. Es müssen immer drei Summanden sein.

Meine Ideen:
Ich habe ein Programm geschrieben, was einfach alle möglichen Summen ausrechnet und mit der Zielsumme vergleicht. Das funktioniert bei wenigen Summen (Ein Pool bis 10 Bytes) super aber darüber hinaus, dauern die Berechnungen zu lange.
Elvis Auf diesen Beitrag antworten »

Beginne mit großen Summanden und beende, wenn die Summe nicht mehr erreicht werden kann.
Beispiel: 13+2+1=16, 13+1+1=15, 10+4+1=15, 10+2+2=14, 7+4+4=15, 7+4+2=13, 4+4+4=12. ENDE.
HAL 9000 Auf diesen Beitrag antworten »

Wenn deine Summandenstruktur öfter so ist wie in deinen "direkten" Beispielen 1 und 2, dann lohnt sich doch sicher ein stufenweises Vorgehen - mal an Beispiel 1 demonstriert:

1) niederwertiges Byte:

Finden aller (einiger?) Dreierkombinationen zulässiger Bytes mit



für die möglichen Überträge

2) zweitniederwertigstes Byte:

Finden aller (einiger?) Dreierkombinationen zulässiger Bytes mit



für die möglichen Überträge

...

4) höchstwertiges Byte:

Finden einer Dreierkombinationen zulässiger Bytes mit

.

Man kann ja erstmal versuchen, ob man mit keinem Zwischenübertrag "durchkommt", d.h. . Wenn man aber beispielsweise in Punkt 2) keine solche mit findet, dann geht man einen Schritt zurück und sucht mit usw. ... Sollte solange nicht dauern.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »