# Algorithmus Finden für ein Problemm



## blackson1c (15. Mai 2007)

HI ich hab folgende aufgaben stellung :



> Schreiben Sie eine Java-Methode
> static void countSums(int[] a, int x)
> welche die Anzahl der Möglichkeiten ermittelt, die Zahl x als Summe von (beliebig vielen) Elementen
> des Arrays a darzustellen. Das Array a enthält nur positive Zahlen und keine Duplikate;
> ...



und ich hab irgendwie kein richtigen ansatzt für die aufgabe :

das hab ich bisher getan :

```
import java.io.*;

class Loesung {
	static int anzahl = 0;

	static int countSums(int[] a, int x) {
		int y=0, z=0;
		//auftrenung in Linken und Rechten Feld 
		int middle = a.length / 2;
		int[] aleft = new int[middle];
		int[] aright = new int[a.length - middle];
		for (y = 0; y < middle; y++) {
			aleft[y] = a[y];
		}
		for (y = 0; y < aright.length; y++) {
			aright[y] = a[middle + y];
		}
		//======================================================
		if (a.length == 1) {
			if (a[0] == x) {
			anzahl++;
			return 0;
			}
			}
			else {
			for (int i = 0; i < x; ++i) {
			return (countSums(aleft, i) + countSums(aright, x-i));
			}
			}
		return anzahl;
	}

	public static void main(String[] args) throws IOException {
		InputStreamReader inStream = new InputStreamReader(System.in);
		BufferedReader stdin = new BufferedReader(inStream);
		String eingabe;
		int[] a = new int[7];
		a[0] = 2;
		a[1] = 5;
		a[2] = 3;
		a[3] = 8;
		a[4] = 4;
		a[5] = 1;
		a[6] = 9;
		for (int i = 0; i < a.length; ++i) {
			System.out.print(a[i] + "   ");
		}
		System.out.println();
		System.out.print("Grenze eingeben: ");
		eingabe = stdin.readLine();
		int x = Integer.parseInt(eingabe);
		System.out.println("Ergebnis: " + countSums(a, x));
	}

}
```

kann mir jemand helfen, auf den richtigen weg zukommen ???


----------



## SlaterB (16. Mai 2007)

Tipp: niemals in deinem Leben baue ein stdin.readLine(); in ein Testprogramm,
schreibe 
int x = 3;
in dein Programm und gut bis wann immer das Programm funktioniert,
bzw. wenn du einen anderen Wert brauchst, dann ganz fix ändern in
int x = 4;
aber auf keinen keinen Fall eine Benutzereingabe, nervig

-------

du brauchst im ganzen Programm nur ein int-Array, deren Zahlen änderns sich ja auch nicht und werden nicht sortiert,
neue int-Array in countSums() anzulegen ist also nicht nötig,
merke dir nur geschickt anfang- und End-Index des aktuell betrachteten Bereichs

-------

summiere die Felder in einem Teilbereich, wenn deren Summe kleiner oder gleich der gesuchten Teilsumme ist, dann bist du in diesem Teil fertig

wenn du so eine Zählung hast, dann kannst du auch den Spezialfall 
if (a.length == 1) {
         if (a[0] == x) { 
weglassen, der ist da mit drin


der Fall, dass die Summe aller Felder in einem Teilbereich genau gleich der gesuchten Teilsumme ist,
ist auch der entscheidene bei dir noch fehlende Teil um Teilsummen zu finden,
dass eine Zahl übereinstimmt ist ja seltener

-------
wenn eine Teilsumme gefunden ist, dann nicht die Anzahl erhöhen,
sondern als Rückgabewert zurückgeben,
ob der Fund gebraucht wird, hängt ja davon ab, ob die andere Teilsumme auch gefunden wird

------

dass du in einer Schleife alle möglichen Aufteilungen der gesuchten Zahl auf die zwei Gebiete betrachtest, 
ist ein sehr wichtiger Schritt,

aber wieso schon bei i=0 ein return in der Schleife?
so wird ja nie i=1 erreicht, unter keinen Umständen,

die Teilfunde für alle i musst du aufsummieren

und für ein i darfst du 
countSums(aleft, i) + countSums(aright, x-i)
nicht addieren, sondern musst sie multiplizieren,

Beispiel: 
in linken Teil 3 Möglichkeiten für i, im rechten 4 für x-i
-> insgesamt 12 Kombinationen für x

in linken Teil 3 Möglichkeiten für i, im rechten 0 für x-i
-> insgesamt gar nix gefunden, bei Multiplikation kommt passenderweise 0 raus


diese Summe der for-Schleife ist letztlich nix anderes als der normale Rückgabewert 
wenn die Summe aller Felder in einem Teilbereich genau gleich der gesuchten Teilsumme ist

also auch nur zurückgeben (nicht etwa Exemplarvariable anzahl erhöhen) 
und wird im vorherigen Rekursionsschritt wieder in eine for-Schleife einfließen,
vielleicht wieder zu 0 werden, da eine andere Teilsumme nicht gefunden wurde,


das Endergebnis ist der Rückgabewert des allerobersten countSums()-Aufruf

--------

mit einfachen Beispiel anfangen, bei deinem Mega-Array kann man ja nix erkennen,
fange mit [2,3] an, wenn da für 2,3,5 jeweils 1 rauskommt und für andere 0, dann ist das schon ein gutes Ergebnis,

danach wirds mit [2,3,4] interessanter

davon ist das linke Teilarray [2,3], womit du gut prüfen kannst, 
ob du dort die gleichen Ergebnisse wie vorher bekommst

-------

und baue ohne Ende Ausgaben mit System.out.println ein
System.out.println("starte Suche in Teilarray a,b,  gesuchte Summe x: );

System.out.println("Zerlegung i, x-1, Funde links, Funde rechts, Produkt, Summe Funde in dieser Schleife bisher");
usw usw.


----------



## Marco13 (16. Mai 2007)

Wenn man den Brute-Force-Ansatz wählt, gilt hier eigentlich das gleiche wie da
http://www.java-forum.org/de/viewtopic.php?p=293731&highlight=#293731
nur zählst du in diesem Fall _binär_ :wink:

Angenommen, dein Array hat drei LMNT, zum Beispiel {3,5,2}. Dann kannst du bis 2^3 zählen, und erhältst damit die Zahlen, die beschreiben, welche Elemente du verwenden mußt
0 = 000 binär = 0 aufsummiert
1 = 001 binär = 2
2 = 010 binär = 5
3 = 011 binär = 5 + 2 = 7
4 = 100 binär = 3
5 = 101 binär = 3 + 2 = 5
6 = 110 binär = 3 + 5 = 8
7 = 111 binär = 3 + 5 + 2 = 10

Damit werden alle Kombinationen durchprobiert, was bei langen Arrays sehr aufwändig sein kann. Hab deinen Ansatz jetzt nicht nachvollzogen, aber vmtl. geht er schon in die "richtigere" (d.h. effizientere) Richtung: Wenn man rausfinden will, welche Kombinationen von Zahlen in diesem Beispiel '2' ergeben, braucht man schon keine Kombination zu berücksichtigen, die das 1. oder 2. Array-Element enthält - und das sind alle, bis auf eine...


----------



## SlaterB (16. Mai 2007)

tja,
> Ihre Lösung muss den Divide-and-Conquer Ansatz [..] nutzen

ist aber auch viel schicker


----------



## Marco13 (16. Mai 2007)

Sorry   hätte vielleicht mal die Aufgabenstellung genau lesen sollen   bin noch nicht ganz wach  :roll:


----------



## blackson1c (16. Mai 2007)

Also erstmal Danke für die ausführliche Erklärung

hab noch gestern weiter gebastelt, ohne das was hier steht gelesen zu haben
und das kamm dabei raus :


```
import java.io.*;

class Loesung {
	static int anzahl = 0;

	static int countSums(int[] a, int b) {
		
		int tempA = 0, tempL = 0, tempR = 0;
		for (int x = 0; x < a.length; x++) {
			tempA = a[x] + tempA;
		}
		if (tempA == b) {
			if(a.length>1)
			anzahl++;
			return anzahl;
		} else {
			if (1 == a.length) {
				if (a[0] == b) {
					anzahl++;
					return anzahl;
				}
				} else {
					int middle = a.length / 2;
					int left = 0;
					int right = a.length;
					int[] aleft = new int[middle];
					int[] aright = new int[right - middle];

					for (int y = 0; y < middle; y++) {
						aleft[y] = a[y];
						tempL = a[y] + tempL;
					}
					for (int y = 0; y < aright.length; y++) {
						aright[y] = a[middle + y];
						tempR = a[middle + y] + tempR;
					}

					if (tempL == b)
						anzahl++;
					if (tempR == b)
						anzahl++;

					for (int y = 0; y < aright.length; y++) {
						if (b == tempL + aright[y])
							anzahl++;
					}
					for (int y = 0; y < aleft.length; y++) {
						if (b == tempR + aleft[y])
							anzahl++;
					}
					if(aleft.length>1 && aright.length>1)
					for (int y = 0; y < aright.length; y++)
						for (int x = 0; x < aleft.length; x++) {
							if (aright[y] + aleft[x] == b)
								anzahl++;
						}
                  countSums(aleft,b);
                  countSums(aright,b);
				}

			}
		return anzahl;
		}
	

		
	

	public static void main(String[] args) throws IOException {
		InputStreamReader inStream = new InputStreamReader(System.in);
		BufferedReader stdin = new BufferedReader(inStream);
		String eingabe;
		int[] a = new int[7];
		a[0] = 2;
		a[1] = 5;
		a[2] = 3;
		a[3] = 8;
		a[4] = 4;
		a[5] = 1;
		a[6] = 9;
		for (int i = 0; i < a.length; ++i) {
			System.out.print(a[i] + "   ");
		}
		System.out.println();
		System.out.print("Grenze eingeben: ");
		eingabe = stdin.readLine();
		int x = Integer.parseInt(eingabe);
		System.out.println("Ergebnis: " + countSums(a, x));
	}

}
```

Das problem, das Programm erkennt nicht die 3 Kombinationen also X=a+b+c
und die Lösung ist auch nicht die beste/ sauberste


Versuche jetzt das nach dem Ansatz vom SlaterB zu machen. 
@SlaterB könntest du mir bischen ausführliches beispiel geben, weil ich versteh noch nicht was das mit dem countSums(aleft, i) * countSums(aright, x-i) 
erreicht wird. Ich versteh irgendwie nicht was ich genau im array summieren soll und was ich übergeben soll.

und wenn man die countSums()*countSums() macht, kriegt man da nicht die ganzen dublikate raus = 3+4+2 > 4+2+3  ist ja das selbe


----------



## SlaterB (16. Mai 2007)

ich hab doch schon Beispiele gegeben..?
aber nochmal:
Array [2,3,5,6,999,10023]
gesuchte Summe 11

Teilung: [2,3,5] gegen [6,999,10023]
in der for Schleife, i=5, also Suchsumme links = 5, Suchsumme rechts = 6

rechts wird 1 rauskommen
links 2 (2+3 oder 5),

ergibt zusammen 2*1 = 2 Möglichkeiten und nicht 2+1=3 Möglichkeiten,
denn insgesamt gibt es ja nur 2 Möglichkeiten: 2+3+6 und 5+6

alle linken Ergebnisse mit allen rechten kombinieren


----------



## blackson1c (16. Mai 2007)

So hab hier mal die neue Version aber mit der krieg ich ein Stack over Flow und ich weis nicht wieso :




```
package Loesung_4c;

import java.io.*;


public class Loesungc {
	
	static int countSums(int[] a, int b) {
		int tempA=0,anzahl=0,tempL=0,tempR=0,temp=0;
		int middle = a.length / 2;
		int right = a.length;
		
		for (int x = 0; x < a.length; x++) {
			tempA = a[x] + tempA;
		}
		
		if(tempA==b){
			anzahl++;
			return anzahl;
			}
		
		int[] aleft = new int[middle];
		int[] aright = new int[right - middle];
		
		for (int y = 0; y < middle; y++) {
			aleft[y] = a[y];
			tempL = a[y] + tempL;
			}
		for (int y = 0; y < aright.length; y++) {
			aright[y] = a[middle + y];
			tempR = a[middle + y] + tempR;
			}
		if(tempL==b){
			anzahl++;
		}
		if(tempR==b){
			anzahl++;
		}
			
		for(int i=0;i<=b;i++){
			temp=countSums(aleft,i) * countSums(aright, b-i); 
		}
		return anzahl+temp;	
		}
	public static void main(String[] args) throws IOException {
		InputStreamReader inStream = new InputStreamReader(System.in);
		BufferedReader stdin = new BufferedReader(inStream);
		String eingabe;
		int[] a = new int[7];
		a[0] = 2;
		a[1] = 5;
		a[2] = 3;
		a[3] = 8;
		a[4] = 4;
		a[5] = 1;
		a[6] = 9;
		for (int i = 0; i < a.length; ++i) {
			System.out.print(a[i] + "   ");
		}
		System.out.println();
		System.out.print("Grenze eingeben: ");
		eingabe = stdin.readLine();
		int x = Integer.parseInt(eingabe);
		System.out.println("Ergebnis: " + countSums(a, x));
	}

}
```

was hab ich falsch gemacht, bzw nicht verstanden


----------



## SlaterB (16. Mai 2007)

wenn du meine Tipps nicht berücksichtigst, dann kannst du zumindest von mir keine weitere Hilfe erwarten




> Tipp: niemals in deinem Leben baue ein stdin.readLine(); in ein Testprogramm,
> schreibe
> int x = 3;
> in dein Programm und gut bis wann immer das Programm funktioniert,
> ...


dein Programm ist unbenutzbar..
(ich wüßte auch gar nicht bei welche Eingabe der Overflow kommt)

--------



> und baue ohne Ende Ausgaben mit System.out.println ein
> System.out.println("starte Suche in Teilarray a,b, gesuchte Summe x: );
> 
> System.out.println("Zerlegung i, x-1, Funde links, Funde rechts, Produkt, Summe Funde in dieser Schleife bisher");
> usw usw.


insbesondere zu Beginn jeder Operation (hast ja nur eine) mit den Parametern, um die Endlosschleife zu erkennen

-------



> mit einfachen Beispiel anfangen, bei deinem Mega-Array kann man ja nix erkennen,
> fange mit [2,3] an, wenn da für 2,3,5 jeweils 1 rauskommt und für andere 0, dann ist das schon ein gutes Ergebnis,
> 
> danach wirds mit [2,3,4] interessanter
> ...


das mit einem großen Array jeder Fehler umso fataler endet ist ja klar


----------



## blackson1c (16. Mai 2007)

Ja , ok  hab jetzt  so gemacht, wie du es meintest

aber ich hab gerade so ein verständnis problemm, bin total verwirt

was muss ich mit dem x und dem Array machen, wenn ich sie in CountSums bekomme. bevor ich anfange das Array zu teilen.

Soll ich das X mit den elementen aus dem Array vergleichen
oder
Soll ich das X mit der summe alle Elemente aus dem Array vergleichen ???

oder bin ich gerade total verwirt, weil ich seit 2 tagen an dem problemm sitze


----------



## SlaterB (16. Mai 2007)

ich habe dazu bereits einen Hinweis geschrieben, 
und da ich schon ne Menge verraten habe, gebe ich nun eher Denkanstöße als noch mehr fertiges,

also:
wie würdest du es denn per Hand machen? wenn du den Algorithmus nicht auf dem Papier beherschst, brauchst du gar nicht erst zu programmieren anfangen,

ob Teil- oder Gesamtarray ist dabei egal,
Beispiel:
[2,3], gesuchte Summe 6, 
kann diese Summe überhaupt erreicht werden?
das ist einfach zu prüfen 

anderes Beispiel:
[1,2,3,4,5,6,7], gesuchte Summe 6, 
bringt dir die Information, dass eine der Zahlen gleich die 6 ist, etwas?

na gut, auf dem Papier geht man etwas anders vor als der PC mit Divide-and-Conquer


----------



## blackson1c (18. Mai 2007)

So hab jetzt das so gemacht wie du es wolltest, bin auch das beispiel auf dem Blatt papier durch gegangen
aber irgendwie will es trozdem nicht funktionieren .


Das ist das aktuele Programm :


```
import java.io.*;

public class Loesungc {

	static int countSums(int[] a, int x) {
		int sumA = 0;
		int anzahl = 0;
		for (int i = 0; i < a.length; i++) {
			sumA = sumA + a[i];
		}
		if (sumA == x) {
			return 1;
		} else {
			if (a.length == 1) {
				if (a[0] == x)
					return 1;
			} else {
				/*
				 * Teile Array a in (aLeft und aRight) und Teile X in (xleft und
				 * xright)
				 */
				int middle = (a.length / 2);
				int[] aleft = new int[middle];
				int[] aright = new int[a.length - middle];
				// werte von 0 bis middle von a nach aleft kopieren
				for (int i = 0; i < middle; i++) {
					aleft[i] = a[i];
				}
				// werte von middle bis ende von a nach aright kopieren
				for (int k = 0; k < a.length - middle; k++) {
					aright[k] = a[middle + k];
				}
				/*
				 * Teile X in xleft und xright dabei den Wert x in tempX
				 * speichern, für die For-Schleife im r werden die Returns
				 * gespeichert
				 */
				int tempX = x;
				int r = 0;
				//System.out.println("Aktueler Wert von r vor der dem Durchlauf: " +r);
				for (int y = 0; y <= x; y++) {
				  
				  r = r + (countSums(aleft, y) * countSums(aright, tempX- y));
					tempX--;
				  System.out.println("Aktueler Wert von r bei Durchlauf :" +y +" R: " +r +"  Mit dem Wert von X :" +x);
				}
				anzahl=anzahl+r;
			}
			return anzahl;
		}

	}

	public static void main(String[] args) throws IOException {
		InputStreamReader inStream = new InputStreamReader(System.in);
		BufferedReader stdin = new BufferedReader(inStream);
		String eingabe;
		int[] a = new int[5];
		a[0] = 2;
		a[1] = 5;
		a[2] = 3;
		a[3] = 7;
		a[4] = 1;
		for (int i = 0; i < a.length; ++i) {
			System.out.print(a[i] + "   ");
		}
		System.out.println();
		// System.out.print("Grenze eingeben: ");
		// eingabe = stdin.readLine();
		int x = 10;
		// Integer.parseInt(eingabe);
		System.out.println("Ergebnis: " + countSums(a, x));
	}

}
```

wo ist der Fehler in meiner Logik ???


----------



## SlaterB (18. Mai 2007)

ich habe dein Programm für mich mal vereinfacht, 
aber ich glaube, dir fehlte nur der Spezialfall
'wenn gesuchte Summe in einem Teilbereich 0 ist, dann gib sofort 1 zurück'

denn es gibt nur eine und auch genau eine Möglichkeit: keine der Zahlen in diesem Gebiet auswählen


--------


```
package test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Loesungc
{

    static int countSums(int[] a, int start, int ende, int x)
    {
        if (x == 0) {
            return 1;
        }
        int sumA = 0;
        for (int i = start; i < ende; i++)
        {
            sumA = sumA + a[i];
        }
        System.out.println("start: " + start + ", ende: " + ende + ", sumA: " + sumA + ", x: " + x);
        if (sumA == x)
        {
            return 1;
        }

        int breite = ende - start;
        if (breite == 1)
        {
            return 0;
        }
        int mitte = breite / 2 + start;

        int r = 0;
        // System.out.println("Aktueler Wert von r vor der dem Durchlauf: " +r);
        for (int y = 0; y <= x; y++)
        {

            r = r + (countSums(a, start, mitte, y) * countSums(a, mitte, ende, x - y));
            System.out.println("Aktueller Wert von r bei Durchlauf: " + y + ", R: " + r + "  Mit dem Wert von X :" + x);
        }
 

        return r;
    }

    public static void main(String[] args)
        throws IOException
    {
        String eingabe;
        int[] a = new int[3];
        a[0] = 2;
        a[1] = 3;
        a[2] = 5;
        for (int i = 0; i < a.length; ++i)
        {
            System.out.print(a[i] + "   ");
        }
        System.out.println();
        // System.out.print("Grenze eingeben: ");
        // eingabe = stdin.readLine();
        int x = 5;
        // Integer.parseInt(eingabe);
        System.out.println("Ergebnis: " + countSums(a, 0, a.length, x));
    }

}
```


----------



## blackson1c (18. Mai 2007)

OK, erst mal big thx
das du dir soviel Zeit genohmen hast, mir zu helfen

versuch gerade dein Code zu verstehen, und zu begreifen wo ich den fehler gemacht hab.


----------

