✔ [c++] array durchsuchen

[kando19]

Hallo,

hab dieses Forum schön öfters auf meiner Suche nach Lösungen zu Rate gezogen, nur diesmal hab ich keinen entsprechenden Eintrag finden können. Hoffe ihr könnt mir weiter helfen

Mein Problem:
Gegeben hab ich ein Array aus Gleitkommazahlen mit einer Dezimalstelle. Nun möchte ich daraus eine zufällige Kombination von einer oder mehreren Zahlen finden, die eine bestimmte gegebene Summe bilden.

Ein Beispiel:
Array = 3,2 | 2,1 | 5,4 | 6,4 | 1,6 | 2,2
Summe = 6,4

mögliche Lösungen:
2*3,2
2*2,1 + 2,2
6,4
2*1,6 + 3,2

Der Algorithmus soll nun eine dieser Lösungen zurückliefern.

Ich komm dabei einfach auf keinen gescheiten Ansatz .
Aja, das Array hat so an die 100 Einträge...

Danke schon mal im Vorraus!

mfg,
kando

 

[deepthroat]

Hi. Das heißt also, du willst Lösungen für die Gleichung

a0*x0 + a1*x1 + ... + an*xn = z

berechnen.

Dabei hast du die a[0 ... n] und z bereits vorgegeben und müßtest dementsprechend die x[0..n] bestimmen.

Dazu fängst du z.B. bei x[k] = 0 für alle k: 0 <= k <= n an und berechnest das Ergebnis der Gleichung (Dazu ist es sinnvoll wenn du dir erstmal eine Funktion schreibst, die 2 Arrays / Vektoren gleicher Größer übergeben bekommt und das Skalarprodukt berechnet.)

Wenn das Ergebnis == z ist, dann hast du eine Lösung gefunden.

Der nächste Schritt ist, den Wert für z.B. x[0] zu inkrementieren und wieder das Ergebnis der Gleichung auszurechnen. Wenn du allerdings x[0] inkrementierst, dann ist das neue Ergebnis gleich dem alten Ergebnis + x[0], so das du nicht nochmal die gesamte Berechnung durchführen mußt.

Diese Inkrementierung machst du solange bis das Ergebnis größer als z wird. (unter der Annahme, des es sich ausschließlich um positive Zahlen in a handelt) Dann inkrementierst du x[1], setzt x[0] = 0 und das ganze Spiel geht wieder von vorne los...

Gruß

 

[kando19]

Hey, super!

Hat funktioniert . Das ganze als mathematische Gleichung zu sehn, ist mir überhaupt nicht in den Sinn gekommen! Danke!

mfg

 

[deepthroat]

Hi.

Hey, super!

Hat funktioniert . Das ganze als mathematische Gleichung zu sehn, ist mir überhaupt nicht in den Sinn gekommen! Danke!

Bitte. Wenn deine Frage dann damit beantwortet ist, dann markiere das Thema als erledigt. Danke.

Gruß