in int array einen pattern(eine zahl) finden

[nachzuegler]

Schreiben Sie eine rekursive Java-Methode

 static boolean darstellbar(int[] a, int sum)

welche herausfindet, ob sich sum als Summe einiger Zahlen des Arrays darstellen lässt. Beispiele:
a = {5, 8, 1, 4}
sum = 12
Rückgabewert der Methode: true (denn 8 + 4 = 12)
a = {5, 8, 1, 4}
sum = 18
Rückgabewert der Methode: true (denn 5 + 8 + 1 + 4 = 18)
a = {5, 4, 1, 1}
sum = 1
Rückgabewert der Methode: true (denn 1 ist in a enthalten)
a = {5, 4, 1, 1}
sum = 2
Rückgabewert der Methode: true (denn 1 + 1 = 2)
a = {5, 4, 1, 1}
sum = 3
Rückgabewert der Methode: false (denn es sind nur zwei Einsen enthalten,
es ist also nicht erlaubt 1 + 1 + 1 zu
rechnen)
a = {7}
sum = 0
Rückgabewert der Methode: true (0 lässt sich immer darstellen, man nimmt
einfach KEINE der Zahlen des Arrays)

Ic versuche seit vorgestern diese Aufgabe zu lösen, aber ich konnte leider nicht zurecht kommen. hat jemand eine idee für diese aufgabe? Das wäre auch hilfreich einen weg zu zeigen..
Danke im Voraus

 

[function]

Welchen Ansatz hast du denn bis jetzt so versucht, oder wo hängt es denn? Ich glaube nicht das hier jemand deine Hausaufgaben machen wird.

 

[javimka]

Am effizientesten löst sich das wohl mit Dynamische Programmierung ? Wikipedia

 

[nachzuegler]

ich habe gar nichts vor, meine Aufgaben jmd andere machen zu lassen. ok ich schreibe hier was ich bisher gemacht habe.. Aber eigentlich sind die unterstehende method nicht so richtig.. ich brauche Hilfe für die denkweise, ich meine, welchen Weg muss man folgen?

  static boolean darstellbar(int[] a, int sum, int i, int aggregate)
  {
    if ((i < a.length) && (sum == 0 || (sum == a[i]))) {
      return true;
    } else if ((i < a.length) && sum != a[i]) {
      return darstellbar(a, sum, ++i, aggregate);
    } else {
      i = 0;
      aggregate= a[i];
      for (int j = i + 1; j < a.length; j++) {
        aggregate+= a[j];
        darstellbar(a, sum, ++j, aggregate);
      }
      return darstellbar(a, sum, ++i, aggregate);
    }
  }

 

[javimka]

Angenommen, es wird darstellbar({1,2,3,4,5},8) aufgerufen. Die Frage ist also, kannst du mit den gegebenen Zahlen die Summe 8 bilden.

Jetzt betrachtest du das erste Element a1 des Arrays (oder kannst auch von hinten anfangen) und stellst dir die Frage:
i) Kann ich die Zahl 8-a1 aus den restlichen Elementen erreichen? Falls ja, dann kannst du ja a1 auch noch dazuaddieren und kriegst 8. Falls nicht, nützt dir das Element a1 halt nichts.
Herausfinden kannst du das mit einem rekursiven Aufruf, hier wäre es darstellbar({2,3,4,5},7)
ii) Kann ich die Zahl 8 aus den restlichen Elementen erreichen? Falls ja, dann kannst du 8 auch mit a1 erreichen, falls nicht, eben nicht.
Herausfinden kannst du das mit einem rekursiven Aufruf, hier wäre es darstellbar({2,3,4,5},8)

Wenn i) oder ii) true zurückgeben, dann gibst du auch true zurück, wenn beide false zurückgeben, geht es offenbar nicht.

 

[nachzuegler]

Angenommen, es wird darstellbar({1,2,3,4,5},8) aufgerufen. Die Frage ist also, kannst du mit den gegebenen Zahlen die Summe 8 bilden.

Jetzt betrachtest du das erste Element a1 des Arrays (oder kannst auch von hinten anfangen) und stellst dir die Frage:
i) Kann ich die Zahl 8-a1 aus den restlichen Elementen erreichen? Falls ja, dann kannst du ja a1 auch noch dazuaddieren und kriegst 8. Falls nicht, nützt dir das Element a1 halt nichts.
Herausfinden kannst du das mit einem rekursiven Aufruf, hier wäre es darstellbar({2,3,4,5},7)
ii) Kann ich die Zahl 8 aus den restlichen Elementen erreichen? Falls ja, dann kannst du 8 auch mit a1 erreichen, falls nicht, eben nicht.
Herausfinden kannst du das mit einem rekursiven Aufruf, hier wäre es darstellbar({2,3,4,5},8)

Wenn i) oder ii) true zurückgeben, dann gibst du auch true zurück, wenn beide false zurückgeben, geht es offenbar nicht.

Liebe/r javimka, vielen dank für die schnelle antwort,
aber ich denke, ich habe dich und verfahren nicht genau verstanden, muss ich nur i) oder auch ii) anwenden? und kannst dur mir ein bisschen mehr erklären, was das bedeutet?

"Kann ich die Zahl 8-a1 aus den restlichen Elementen erreichen?" 8 minus das erste element oder?

Das wäre sehr nett von dir, wenn du ein wenig ausführlicher erklärst.. (ich galube, deiner beitrag war schon ausführlich aber ich habe nicht genau verstanden )

danke im Voraus

 

[Marco13]

Man braucht i) und ii) - aber ii) verwendet man nur, wenn i) nicht schon zum Erfolg geführt hat.

8-a1 soll "8 minus das erste element" bedeuten.

Das, was du gepostet hattest, war vom Ansatz her gar nicht so falsch, aber halt noch ein paar kleine Fehler drin, und etwas schwierig nachzuvollziehen.

Bei "primitiver" Rekursion gibt es eigentlich immer zwei Dinge, die man abhandeln muss, nämlich den Basisfall und den Rekursionsschritt. Um das ganze übersichtlicher zu machen, könnte man den Basisfall (bzw. die Abbruchbedngungen) zuerst abhandeln.

Außerdem kann sowas wie

    private static String indent(int n)
    {
        String s = "";
        while (s.length() < 4*n)
        {
            s += " ";
        }
        return s;
    }


    static boolean darstellbar(int[] a, int sum, int i, int aggregate)
    {
        System.out.println(indent(i)+"darstellbar "+java.util.Arrays.toString(a)+" i "+i+" sum "+sum+" aggregate "+aggregate);
...

hilfreich sein, um nachzuvollziehen, warum es ihn mit einem StackOverflowError raushaut...


EDIT: Noch'n Tipp: Das Aggregate braucht man eigentlich nicht. In Worten:

Man kann die Zahl
X   als Summe von Zahlen aus {A, B, C ... } darstellen, wenn man die Zahl
X   als Summe von Zahlen aus {   B, C ... } darstellen kann, oder wenn man die Zahl
X-A als Summe von Zahlen aus {   B, C ... } darstellen kann

 

[nachzuegler]

danke marco13, ich weiss schon, dass bei Rekursion immer den Basisfall und den Rekursionsschritt dabei sein muss . du hast recht, die methode ist schwer nachvollzuziehen, aber verfahren ist auch falsch. Eigentlich versuche ich zu verstehen, was javimka geschrieben hat, nämlich,
i) Kann ich die Zahl 8-a1 aus den restlichen Elementen erreichen? Falls ja, dann kannst du ja a1 auch noch dazuaddieren und kriegst 8. Falls nicht, nützt dir das Element a1 halt nichts.
was bedeutet das? wie kann ich "Falls ja" case schaffen? wenn ich das schon gewusst hätte, hätte ich die methode implementieren können oder?

 

[javimka]

Da musst du auf die Rekursion vertrauen. Wenn du mit den restlichen Elementen 8-a1 generieren kannst, dann weisst du, dass du einfach auch noch a1 dazunehmen musst und dann kannst du mit den Elementen aus dem Array 8 generieren.
Aber wenn du 8-a1 nicht mit den restlichen Elementen erstellen kannst, dann nützt es nichts, wenn du a1 auch noch hast, egal, wie du es einsetzt, du wirst nicht sie Summe 8 erreichen können.

Das tolle an der Rekursion ist, dass wenn du dieselbe Methode mit 8-a1 und den restlichen Elementen ausführst, sie genau das gleiche Prinzip wieder anwendet. Die Methode wird wieder das erste Element a2 abhacken und sich wiederum rekursiv mit den restlichen Elementen und 8-a1-a2 aufrufen usw.

Wichtig ist noch folgendes: Wenn das Array nur ein Element hat, dann musst du überprüfen, ob es genau das Element ist, das als Argument übergeben wird, welches per Summer erreicht werden soll. darstellbar({4},4) muss logischerweise sofort true zurückgeben, aber darstellbar({3},4) false.

 

[nachzuegler]

Danke javimka für die schnelle antwort, seit 3 tagen beschäftige ich mich mit dieser aufgabe, irgindwie kriege ich die nicht, und mir wurde allmählich langweiliger.. Wenn ich deinen Weg anwenden möchte, fällt mir folgendes auf..
Nehmen wir an, dass wir als elemente von a {2,4,5,10} und sum(gesuchte) 19 haben..

also darstellbar({2,4,5,10},19)

1) {4,5,10}, 17 d.h ich brauche 2 nicht.. weil ich mit {4,5,10} nicht 17 generieren kann. Nächster schritt,
2) {2,5,10}, 13 d.h ich brauche 4 auch nicht.. (aber ich brauche eigentlich.)
3) {2,4,10}, 8 d.h ich brauche 5 auch nicht.. (aber ich brauche eigentlich.)
4) {2,4,5}, -2 was mache ich da? (oder wie verstehe ich, ob ich 10 brauche??)


Kannst du mir bitte erklären, was mache ich falsch, oder wie soll ich machen?

 

[Marco13]

So eine Rekursion läßt sich besser als eine Art "Stack"trace veranschaulichen:

darstellbar({2,4,5,10},19)
    darstellbar({4,5,10},17)    
        darstellbar({5,10},13)
            darstellbar({10},8) -> false
        darstellbar({10},13)
            darstellbar({},3) -> false
        ...
    darstellbar({4,5,10},19)    
        darstellbar({5,10},15)    
            darstellbar({10},10)    
                darstellbar({},0)  -> true

... so grob

 

[bygones]

Außerdem kann sowas wie

    private static String indent(int n)
    {
        String s = "";
        while (s.length() < 4*n)
        {
            s += " ";
        }
        return s;
    }


    static boolean darstellbar(int[] a, int sum, int i, int aggregate)
    {
        System.out.println(indent(i)+"darstellbar "+java.util.Arrays.toString(a)+" i "+i+" sum "+sum+" aggregate "+aggregate);
...

hilfreich sein, um nachzuvollziehen, warum es ihn mit einem StackOverflowError raushaut...

mal so am Rande...

warum nicht einfach printf nutzen ? erspart man sich eigene indent sachen

 

[Marco13]

Ja, stimmt (dazu hätt' ich aber in der Doku nach dem richtigen %2.0s$s-Pattern gucken müssen - ist ja nur eine Debug-Ausgabe )

 

[Methinks]

Hallo zusammen,
muss die selbe Aufgabe bearbeiten und hab auch meine Methode einigermassen zusammen, funktioniert auch größtenteils, aber das Problem ist, dass es bei verschiedener Reihenfolge der Elemente nicht das selbe ausspuckt. Also für z.B a = {5, 8, 1, 4} liefert die Methode true, für a = {5, 8, 4, 1} aber false.
Kann mir vielleicht jemand helfen, den Fehler zu beheben?

static boolean darstellbar(int[] a, int sum) {
    int g = a.length;
    int[] b = new int[g-1];
    for (int i = 0; i < b.length; i++) {
      b[i] = a[i];
      if (sum == 0 || sum - a[g-1] == a[i]) {
        return true;
      }
    }   
    if (b.length == 0) {
      return false;
    } else {
      sum = sum - a[g-1];
      return darstellbar(b, sum);
    }
  }

 

[Marco13]

   } else {
      sum = sum - a[g-1];
      return darstellbar(b, sum);
    }

schau' mal, ob da für "sum" irgendwann mal was negatives rauskommt ... und falls ja, was das heißt, und wie man es verhindern könnte...

 

[Methinks]

Wenn man sum = 12 setzt heißt das, dass sum der Reihe nach 12, 11, 7 und -1 wird. Wählt man die Reihenfolge a = {8, 5, 4, 1] wird sum 12, 11, 7, 2. Das heißt, ich hab niemals sum == 0 oder sum = ein Element von a.
Wie behebe ich das? Muss ich das jetzt noch mit einem anderen b durchlaufen lassen, wo ich nicht das letzte sondern ein anderes Element abspalte? Oder denke ich jetzt zu kompliziert?

 

[Marco13]

Hab's jetzt an deinem Code konkret nicht getestet, aber allgemein: Wenn man einen Arrayeintrag X von "sum" abzieht, und mit den verbleibenden Einträgen "sum-X" nicht erreichen kann, dann muss man noch versuchen, sum (ohne das "-X") mit den verbleibenden Einträgen zu erreichen...

 

[Gast2]

Hier mal ne rekursive Variante, stand im ersten Post glaub ich.

private static boolean darstellbar(int[] a, int sum) {
    if (sum == 0) return true;
    if (a.length == 0) return false;
    if (arraySum(a) < sum) return false;

    return darstellbar(subArray(a, 1), sum) || darstellbar(subArray(a, 1), sum - a[0]);
}

private static int[] subArray(int[] arr, int start, int end) {
    int[] res = new int[end - start + 1];
    for (int i = start; i <= end; i++) {
        res[i-start] = arr[i];
    }

    return res;
}

private static int[] subArray(int[] arr, int start) {
    return subArray(arr, start, arr.length - 1);
}

private static int arraySum(int[] arr) {
    int sum = 0;
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i];
    }

    return sum;
}

 

[Methinks]

Hab's jetzt an deinem Code konkret nicht getestet, aber allgemein: Wenn man einen Arrayeintrag X von "sum" abzieht, und mit den verbleibenden Einträgen "sum-X" nicht erreichen kann, dann muss man noch versuchen, sum (ohne das "-X") mit den verbleibenden Einträgen zu erreichen...

Ich glaub jetzt hab' ich's. Danke für die schnelle Hilfe.

 

[nachzuegler]

So eine Rekursion läßt sich besser als eine Art "Stack"trace veranschaulichen:

darstellbar({2,4,5,10},19)
    darstellbar({4,5,10},17)    
        darstellbar({5,10},13)
            darstellbar({10},8) -> false
        darstellbar({10},13)
            darstellbar({},3) -> false
        ...
    darstellbar({4,5,10},19)    
        darstellbar({5,10},15)    
            darstellbar({10},10)    
                darstellbar({},0)  -> true

... so grob

Danke schön marco13 für die antwort, aber warum ruft man nach der
darstellbar({10},8) -> false
darstellbar({10},13)
auf?

und ist das zweite getrennte Beispiel ??

" darstellbar({4,5,10},19)
darstellbar({5,10},15)
darstellbar({10},10)
darstellbar({},0) -> true"

 

[Marco13]

Das ist EIN Beispiel - bei den "..." hatte ich einen Teil ausgelassen.

Nach dem
darstellbar({10},8) -> false
ruft man nicht "von Hand"
darstellbar({10},13)
auf, sondern das ist ein weiterer rekursiver Aufruf. Deswegen diese Einrückung

        darstellbar({5,10},13)           // Er überprüft, ob 13 mit { 5, 10 } darstellbar ist...
            darstellbar({10},8) -> false // ... stellt fest, dass das nicht geht...
        darstellbar({10},13)             //... und probiert dann weiter, ob 10 vielleicht mit {10} darstellbar ist
            darstellbar({},3) -> false

Mist - hatte gerade ein schönes Bild dazu gemalt, aber ist beim Speichern schiefgegangen

Man kann sich die Suche als eine Art "Baum" vorstellen. Bei jeder Zahl hat er die Wahl, zu versuchen, die aktuelle Zahl im Array zu verwenden oder eben nicht. Im Beispiel oben hat er eben versucht, die 5 zu verwenden, aber damit keine Lösung gefunden. Deswegen probiert er danach eine Lösung zu finden, wenn er die 5 NICHT verwendet...

 

[ersti[09]]

Hallo, ich habe zu der Aufgabe noch eine Frage und würde mich nun interessieren, wie man sich die Zahlen anzeigen lassen kann.
Also zum beispiel:
{5 8 1 4} Und ich möchte die Summe 12 haben, dass er mir anzeigt:
12 = 8 + 4

In meinem Code zeigt er mir bis jetzt nur an, ob die Summe darstellbar ist.
Habe aber gerade keine Idee, wie er mir die Zusammensetzung anzeigt.

class Zielsumme {

  public static void main(String[] args) {
    // Ermitteln der Dateilaenge
    In.open("zahlen.txt");
    int length = 0;
    while (In.done()) {
      In.readInt();
      ++length;
    }
    --length;
    int[] a = new int[length];
    // Schliessen und Wiederoeffnen setzt Dateizeiger
    // auf Anfang
    In.close();
    // Einlesen der Datei
    In.open("zahlen.txt");
    for (int i = 0; i < length; ++i) {
      a[i] = In.readInt();
      Out.print(a[i] + "  ");
    }
    In.close();
    Out.print("Gewuenschte Summe: ");
    int sum = In.readInt();
    Out.println("Summe ist " 
                + (darstellbar(a, sum) ? "" : "nicht ")
                + "darstellbar");
  }

  static boolean darstellbar(int[] a, int sum) {
    if (sum == 0) {
      return true;
    } else if (a.length == 1) {
      return sum == a[0];
    } else {
      // aKurz = Kopie von a ohne letztes Element
      int[] aKurz = new int[a.length - 1];
      for (int i = 0; i < a.length - 1; ++i) {
        aKurz[i] = a[i];
      }
      return darstellbar(aKurz, sum)
             || darstellbar(aKurz, sum - a[a.length - 1]);
    }
  }

}