Algorithmus Finden für ein Problemm

[blackson1c]

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;
es ist nicht sortiert. Jedes Element darf pro Summe nur einmal verwendet werden. Beispiel:
a: 2 5 3 8 4 1 9
x: 9
Ergebnis: 5
(denn: 9 = 2 + 3 + 4
9 = 5 + 3 + 1
9 = 5 + 4
9 = 8 + 1
9 = 9)
Das Programm soll nur das Ergebnis ausgeben, nicht die Begründung. Ihre Lösung muss den
Divide-and-Conquer Ansatz und die folgende Beobachtung nutzen:
Das Array a sei in zwei ungefähr gleich große Teilfelder aLeft und aRight zerlegt
(wie bei Mergesort). Dann entspricht jede Darstellung von x als Summe von Elementen
aus a einer Zerlegung x = yLeft + yRight, wobei yLeft die Summe von
Elementen aus aLeft und yRight die Summe von Elementen aus aRight ist.

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]

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]

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]

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

ist aber auch viel schicker

 

[Marco13]

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

 

[blackson1c]

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]

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]

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]

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,
bzw. wenn du einen anderen Wert brauchst, dann ganz fix ändern in
int x = 4;
aber auf keinen keinen Fall eine Benutzereingabe, nervig

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

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

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

 

[blackson1c]

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]

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]

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]

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]

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.