✔ [c++] array durchsuchen

K

kando19

Grünschnabel
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
 
Hi. Das heißt also, du willst Lösungen für die Gleichung

Code: 
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ß
 
Hey, super!

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

mfg
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück