mihe7
Top Contributor
Der sagte aber irgendwas wie expecto plutonium.Nee, das war Putin mit seinem Elderstab ...
Der sagte aber irgendwas wie expecto plutonium.Nee, das war Putin mit seinem Elderstab ...
Da kann ich nur Arthur Weasley zitieren: „Er hat genuschelt“Der sagte aber irgendwas wie expecto plutonium.
Ja, aber SIE wollen uns erzählen, ...Ich glaube, wir sind da jetzt einer ganz großen Sache auf der Spur …
Das kann nur @White_Fox beantworten.Nuscheln die Russen evtl. generell?
Also wir hätten da zum Beispiel -10. Dann wäre es ja 0. Aber auch -7 und -3. Bräuchte ein paar Tipps, stehe irgendwie auf dem Schlauch und die Klausur ist bald...Und was ist Dein Vorschlag, wie man da helfen kann? Nur so ein Zitat hilft nicht weiter.
Von mir aus können wir das dabei auch belassen. Dann ist das der Check des aktuellen Elements.
Dann müssen wir jetzt nur einmal schauen, was für Fälle wir dann im Anschluss klären müssen. Das können wir ja einmal an paar Beispielen ausführen.
Wir hatten eine Summe von 5, aktuelles Element 5. Was für Fälle kann es geben, damit mit dem nächsten Element ein SubArray mit Summe 0 vorhanden ist?
import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.IntStream;
public class SubSumZero {
public static int subSetSum(int[] liste, int from, int to) {
return IntStream.range(from, to).reduce(0, (a, b) -> a + liste[b]);
}
public static int[][] subSetsZero(int[] liste) {
ArrayList<int[]> indices = new ArrayList<>();
for (int i = 0; i <= liste.length; i++) {
for (int j = i + 1; j <= liste.length; j++) {
indices.add(new int[]{i, j});
}
}
ArrayList<int[]> indicesZero = new ArrayList<>();
for (int[] a : indices) {
if (subSetSum(liste, a[0], a[1]) == 0) {
indicesZero.add(a);
}
}
int[][] aa = new int[indicesZero.size()][];
for (int i = 0; i < aa.length; i++) {
aa[i] = indicesZero.get(i);
}
return aa;
}
public static void main(String[] args) {
int[] liste = {0, 5, -4, -1, -3, +3, 0, 0, 1, 2, 2, 4, 1, 0};
int[][] indicesZero = subSetsZero(liste);
System.out.println(Arrays.toString(liste));
System.out.println(Arrays.deepToString(indicesZero));
for (int[] a : indicesZero) {
System.out.print(Arrays.toString(a));
for (int i = a[0]; i < a[1]; i++) {
System.out.print(", " + liste[i]);
}
System.out.println();
}
}
}
[0, 5, -4, -1, -3, 3, 0, 0, 1, 2, 2, 4, 1, 0]
[[0, 1], [0, 4], [0, 6], [0, 7], [0, 8], [1, 4], [1, 6], [1, 7], [1, 8], [2, 11], [3, 9], [4, 6], [4, 7], [4, 8], [6, 7], [6, 8], [7, 8], [13, 14]]
[0, 1], 0
[0, 4], 0, 5, -4, -1
[0, 6], 0, 5, -4, -1, -3, 3
[0, 7], 0, 5, -4, -1, -3, 3, 0
[0, 8], 0, 5, -4, -1, -3, 3, 0, 0
[1, 4], 5, -4, -1
[1, 6], 5, -4, -1, -3, 3
[1, 7], 5, -4, -1, -3, 3, 0
[1, 8], 5, -4, -1, -3, 3, 0, 0
[2, 11], -4, -1, -3, 3, 0, 0, 1, 2, 2
[3, 9], -1, -3, 3, 0, 0, 1
[4, 6], -3, 3
[4, 7], -3, 3, 0
[4, 8], -3, 3, 0, 0
[6, 7], 0
[6, 8], 0, 0
[7, 8], 0
[13, 14], 0
Kannst du den einmal angeben? rekursiv ist es nur etwas schwieriger...Auch der Methodenkopf ist festgelegt
Falsch! Rekursiv ist es wesentlich(!) einfacher, weil man sich nur um einen einzigen Schritt kümmern muss.rekursiv ist es nur etwas schwieriger...
public static boolean subsetSum(int[] list, int index, int sum) {
// Abbruchbedingung für 'false'. WICHTIG: 'false' ist nicht zwingend endgültig, sondern gilt
// zunächst nur für die aktuelle Summen-Sequenz
if (______) return ______;
// Abbruchbedingung(-en) für 'true' -> führt zur kompletten Auflösung der rekursiven Verschachtelung
// und gibt schließlich 'true' an die main()-Methode.
if (______ || ______) return ______;
// ab hier löst sich im 'false'-Fall sie rekursive Verschachtelung bis zum Anfang der aktuellen Summen-Sequenz auf.
// Wenn dieser erreicht wird, beginnt eine neue Summenbildung mit dem nächsthöheren Index.
if (______) return ______;
// ansonsten 'false' durchreichen, ggf. bis an die Main()-Methode.
return ______;
}
- subsetSum2(list, index + 1, sum + list[index])
- index >= list.length
- false
- sum == 0
- false
- subsetSum2(list, index + 1, 0)
- true
- sum + list[index] == 0
Ja, einfach. Das Problem bei rekursiven Lösungen ist oft, dass sie gerade so einfach sind, man denkt nur viel zu kompliziert. (Hm, einfach? Kurz schon, aber eine Problemlösung rekursiv zu formulieren ... braucht Übung.
Das ist aber falsch.- subsetSum2(list, index + 1, 0)
Der wurde doch am Anfang des Threads schon angeben. Thread lesen vor einer Antwort hilft und verhindert, dass Dinge gepostet werden, die nichts zum Thread beitragen.Kannst du den einmal angeben? rekursiv ist es nur etwas schwieriger...
Dabei haben wir den eigentlichen Algorithmus schon fast ganz beschrieben. Und wir sind jetzt fast am Ende angekommen. Und er hat sich übrigens für eine andere Variante entschieden - da wird nur ein Punkt geprüft und dafür 3 Dinge rekursiv getestet.Aber ich glaube, der TE hängt wirklich fest.
Also wenn wir 5 als aktSumme und 5 als aktuelles Element haben:Also wir hätten da zum Beispiel -10. Dann wäre es ja 0. Aber auch -7 und -3. Bräuchte ein paar Tipps, stehe irgendwie auf dem Schlauch und die Klausur ist bald...
/ 1 | n=0
f(n) = + 1 | n=1
\ f(n-1)+f(n-2) | n > 1
Die Umsetzung bei Rekursiv ist auf jeden Fall einfacher, aber man muss halt den Gedanken erst einmal verstanden haben. Den zu erarbeiten kann durchaus problematisch sein.Falsch! Rekursiv ist es wesentlich(!) einfacher, weil man sich nur um einen einzigen Schritt kümmern muss.
Für eine iterative Lösung müsste ich ernsthaft nachdenkenUnd die iterative Lösung ist hier auch nicht wirklich kompliziert.
Daher auch mein Kommentar.Dass da so eine Lösung wie #57 angeboten wird
🤣(nennen wir ihn einfach einmal Tobias)
wenn jemand versucht fahrrad fahren zu lernen hilft es nicht demjenigen zu sagen dass es mit dem auto schneller geht...@KonradN Ich weiß ehrlich gesagt nicht, warum du hier so einen müll redest? Bist du vielleicht einfach mit dem falschen Fuß aufgestanden, oder verstehst du wirklich einfachste, korrekte Lösungen nicht?
Naja bin natürlich immer dankbar für antworten aber die oben gepostete Lösung war insofern nicht hilfreich, als dass ich ja bereits eine zum mindest zum Teil iterative Lösung hatte. Mir ging es darum, eine vollständig rekursive Lösung zu erarbeiten, damit ich da leicht eine Rekursionsgleichung ermitteln kann. Ausserdem war der Methodenkopf vorgegeben, das ist ja eine konkrete Aufgabe die ich da bearbeitet habe und durch das Lesen des Threads sollte das ja eigentlich schon klargeworden sein. Eine vollständig iterative Lösung hatte ich übrigens auch durch 2 verschachtelte Schleifen, es geht also auch sehr viel naheliegender@KonradN Ich weiß ehrlich gesagt nicht, warum du hier so einen müll redest? Bist du vielleicht einfach mit dem falschen Fuß aufgestanden, oder verstehst du wirklich einfachste, korrekte Lösungen nicht?
Ach Tobias,@KonradN Ich weiß ehrlich gesagt nicht, warum du hier so einen müll redest? Bist du vielleicht einfach mit dem falschen Fuß aufgestanden, oder verstehst du wirklich einfachste, korrekte Lösungen nicht?
public static int subSetSum(int[] liste, int from, int to) {
return IntStream.range(from, to)
.map(i -> liste[i])
.sum();
}
Ja, Du wirst da eine relativ einfache, gut oder zumindest besser verständliche Lösung gehabt haben, die weniger (hier) unnützes Zeug gemacht hat. Und im Sinne der Aufgabe wirst Du auch ohne Dinge wie Streams und den Collection Klassen des Frameworks ausgekommen sein. Daher ist das auch nicht weiter zu diskutieren denke ich malNaja bin natürlich immer dankbar für antworten aber die oben gepostete Lösung war insofern nicht hilfreich, als dass ich ja bereits eine zum mindest zum Teil iterative Lösung hatte. Mir ging es darum, eine vollständig rekursive Lösung zu erarbeiten, damit ich da leicht eine Rekursionsgleichung ermitteln kann. Ausserdem war der Methodenkopf vorgegeben, das ist ja eine konkrete Aufgabe die ich da bearbeitet habe und durch das Lesen des Threads sollte das ja eigentlich schon klargeworden sein. Eine vollständig iterative Lösung hatte ich übrigens auch durch 2 verschachtelte Schleifen, es geht also auch sehr viel naheliegender
Also hätten wir das dann so :
1. Prüfen ob index < liste.length
2. Dann schauen ob Summe + liste[index] == 0
3. Wir schauen ob liste[index] == 0
Also irgendwie verstehe ich den Sinn hinter der ganzen Sache nicht. Vielleicht hat jmd etwas Code da würde ichs vielleicht besser verstehen
/ false | i > n
f(l,i,s) = + true | ln = 0 | s+ln = 0
\ f(l,i+1, s+ln) | f(l, i+1, ln) | i <= n & ln != 0 & s+ln != 0
public static boolean subsetSum(int[] list, int index, int sum) {
if (index >= list.length) return false;
if (liste[index] == 0 || sum + liste[index] == 0) return true;
return subsetSum(list, index+1, sum+liste[index]) || subsetSum(list, index+1, liste[index]);
}
int[] list = {1, 2, 3, 4, 5, -1, 7, 8, -13, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32};
Man kann da einiges optimieren, wenn man will. Nur: wer will das schon?Das war in der Tat auch mein ursprünglicher Lösungsansatz, ABER ...