n Zahlen aus einem Array addieren

[Hitchblade]

Hallo Leute!

Bin gerade neu im Forum und war noch nie richtig in einem Forum.
Wenn ich was falsch gemacht habe, bitte sagen.

Ich dachte bis jetzt dass ich schon Ahnung von Java hab, aber ich bin mittlerweile echt am zweifeln...

Die Problemstellung sieht so aus:

Es ist eine Menge n und m gegeben. n besagt im Prinzip wie viele Zahlen in dem bestimmten Array addiert werden sollen. Es ist aber nicht bekannt welche Zahlen des Arrays addiert werden müssen. Das heißt ich muss im Prinzip alle Möglichkeiten ausrechnen bis die Summe den Wert m besitzt.

Bin ich vollkommen bescheuert oder ist es doch so schwer?

Helft mir bitte! :toll:

Falls ihr noch fragen habt, sagt bescheid...

 

[rme]

Hallo

Keine Sorge, du machst alles richtig, was das Forum betrifft

Bist du dir sicher, dass n und m Mengen sind?

Lautet die Aufgabe vielleicht so, dass du ein Array mit Zahlen gegeben hast und sollst nun n Zahlen wählen, sodass die Summe m ergibt? Das klingt arg nach einer Variante von Subset-Sum, d.h. es gibt keine effiziente Lösung dafür, außer alles zu probieren. Bei dir ist immerhin n gegeben, sodass du direkt alle Permutationen der Länge n probieren kannst.

Hilft das?

 

[Hitchblade]

Zunächst mal danke für die schnelle Antwort...

Dann bin ich ja froh.

Ja genau. So habe ich das gemeint.

Genau. Es ist eigentlich die Einzige Möglichkeit alles durch zu probieren.

Mein Problem ist dass ich nach ca 8 Ansätzen (... und gefühlten 60 Stunden) einfach nicht mehr weiß was ich machen soll...

 

[rme]

Wie sahen deine Ansätze denn ungefähr aus? Hattest du bei einem das Gefühl, kurz davor zu sein? Oder bist du mittlerweile so kaputt davon, dass du gern einen Ansatz hättest, den du dann runterprogrammieren kannst?

 

[Hitchblade]

Naja...

Der beste Ansatz sieht ca so aus:

Array und die Möglichkeiten (Angenommen n = 4)
Array[1] - - - - - - - - ...
Array[2] - - - - -
Array[3] - - - - - ...
Array[4] - - - - - ...
Array[5] - - - - - ...
Array[6] - - - - ...

Ich hoffe man kann ungefähr erkennen was ich meinte... Anfangs hatte ich den ansatz dass ich die 'i'te Zahl + die 'i'te+1te Zahl nahm... Das waren aber zu wenig Möglichkeiten...

Ich bin echt kein Mensch der unbedingt die Lösung haben will, aber mich quält diese Aufgabe schon seit 3 Nächten...

Mit anderen Worten... Ja, ich hätte gerne einen Ansatz den ich runterprogrammiere.

btw Ich bin tierisch übermüdet... :toll:

 

[Hitchblade]

Okay. Man kann doch nicht erkennen was ich meinte... Im Prinzip habe ich alle möglichkeiten aufgemalt um zu gucken wie ich wo eine schleife erstellen könnte usw...

 

[rme]

Als Freund der funktionalen Programmierung fällt mir als erstes ein rekursiver Ansatz ein:

Ich würde eine Methode schreiben, der das Array übergeben wird und die zurückgibt, ob sie Erfolg hat. Als weitere Parameter bekommt sie die verbleibende Summe und die verbleibende erlaubte Zahl an Elementen. Also der erste Aufruf mit prüfe(array, n, m).

Wenn n noch nicht 0 ist, nimmt die Funktion das erste Element aus dem Array, sofern die Summe dann noch nicht überschritten ist, und ruft sich selbst rekursiv auf, wobei dann das Array ohne das genommen Element, n um 1 reduziert und m und den Wert des genommen Elements reduziert wird.

Falls das zu langsam ist, müsste man die Tatsache besser ausnutzen, dass genau n Element gefordert sind.

Falls es eine StackOverFlowException gibt, weil es zu viele Elemente sind: Endrekursiv formulieren und auflösen.

 

[Hitchblade]

Ich würde eine Methode schreiben, der das Array übergeben wird und die zurückgibt, ob sie Erfolg hat. Als weitere Parameter bekommt sie die verbleibende Summe und die verbleibende erlaubte Zahl an Elementen. Also der erste Aufruf mit prüfe(array, n, m).

Wenn n noch nicht 0 ist, nimmt die Funktion das erste Element aus dem Array, sofern die Summe dann noch nicht überschritten ist, und ruft sich selbst rekursiv auf, wobei dann das Array ohne das genommen Element, n um 1 reduziert und m und den Wert des genommen Elements reduziert wird.

Also...

Als Beispiel: array = {6, 3, -7, 1, -4, 0}, n = 3, m = -1

private static boolean prüfe(int[] array, int n, int m)
{
If (n != 0)
{
if (array[0] < m)
{
return prüfe(array, n-1, m);
}
}
return true;
}

Das kann aber net stimmen... Ich bin einfach zu kaputt... Erst recht bei Rekursionen...

Danke aber ich werde es wohl net schaffen wenn dir oder mir net durch ein Wunder ein Ansatz mit Schleifen einfällt. :toll:

 

[rme]

Genauer lesen m und array müssen natürlich auch angepasst werden. Kannst du Haskell? Dann kann ich dir den Ansatz da schnell zeigen. Aber wenn du für Rekursionen gerade zu müde bist, lieber nicht..

 

[Hitchblade]

Haskell sagt mir leider nichts...

Ich bin generell für alles zu müde. Aber ich probier es nochmal wenn du "in der Leitung" bleibst.

 

[rme]

Mach mal und zeig dann deinen Ansatz

 

[Hitchblade]

Brauche ich dafür nicht noch eine zahler Variable die ich mit übergebe?

 

[rme]

Was soll sie denn zählen? Ich dachte, man könnte einfach von der Summe und der Anzahl der Elemente abziehen, bis eins 0 wird - und dann überlegen, ob das gerade gut oder schlecht ist.

 

[Hitchblade]

Angenommen zusätzlich des vorherigen Beispiel mit i = 0...

private static boolean prüfe(int[] array, int n, int m, int i)
{
	if (n != 0)
	{
		if (array[i] < m)
		{
			array[i] = 0;
			return prüfe(array, n-1, m, i++);
		}
		return true
	}
}

 

[rme]

Achso, mit Zähler meinst du eine Art Laufindex. Ja, das spart es dir natürlich, ein neues Array zu übergeben - also auch gut und richtig

 

[Hitchblade]

Aber das was ich geschrieben habe ist noch lange nicht richtig,... ... ... oder?

 

[rme]

Nein, das ist noch nicht vollständig. Du musst dir klarmachen, was die Methoden momentan macht und was es bedeutet, wenn ein Aufruf false zurückgibt. Das bedeutet nämlich, dass die Rekursion ab dort mit dem Wählen von i nicht erfolgreich war. Also muss es wohl anders probiert werden.. usw.

 

[Hitchblade]

Hmm... Oke... Ich merke schon dass ich es zumindest heute Abend nicht mehr schaffe...

Habe zum Glück bis Freitag Zeit und probiere es morgen nochmals mit klarem Kopf. Werde mich bestimmt nochmal melden.

Aber schonmal ein riesiges Dankeschön! Du hast mir sehr weitergeholfen, auch wenn ich mir ein Ansatz mit Rekursion nicht erhoft habe.^^


gn8.