jeudi 7 mai 2015
SubSquence
Posted on 02:59 by verona
Hallo,
ich soll eine Methode implementieren, die die Teilfolge maximaler Summe anhand des folgenden Algorithmus berechnet:
Die Folge ist F = {a[1], ... , a[n]}, a[1] != 0, n > 0
Nachbedingung: F(l,r) ist eine zusammenhängende Teilfolge maximaler Summe von F.
Gegeben ist folgende Java-Datei:
Die von mir bereits umgesetzt Methode sieht so aus:
Mein Problem
Ich weiß nicht, was ich in der Methode zurück geben soll. Den Pseudocode in Java zu verfassen war ja ziemlich einfach, aber ich verstehe nicht, was es mit dem Typ SubSequence auf sich hat. Ich vermute, dass an der Stelle
die Werte
eingesetzt werden sollen. Wenn ich aber zum Beispiel
einsetze, komme ich auf die falschen Ergebnisse.
Wie kann ich das umsetzen? Generell ist es das erste Mal, dass ich mit solchen selber erzeugten Datentypen arbeiten soll, deswegen fehlt mir auf jeden Fall Erfahrung damit.
ich soll eine Methode implementieren, die die Teilfolge maximaler Summe anhand des folgenden Algorithmus berechnet:
Java Code:
-
-
/* Initialisierung */
-
glob max <- 0
-
suffix max <- 0
-
l <- 1; r <- 0
-
sl <- 1; m <- 0
-
/* Ende der Initialisierung */
-
-
while m < n do
-
m <- m + 1
-
if a[m] + suffix max > glob max then
-
suffix max am + suffix max
-
glob max <- suffix max
-
l <- sl; r <- m
-
else if a[m] + suffix max >= 0 then
-
suffix max <- a[m] + suffix max
-
else
-
suffix max <- 0
-
sl <- m + 1
-
endif
-
endif
-
endwhile
Die Folge ist F = {a[1], ... , a[n]}, a[1] != 0, n > 0
Nachbedingung: F(l,r) ist eine zusammenhängende Teilfolge maximaler Summe von F.
Gegeben ist folgende Java-Datei:
Java Code:
-
-
public class MaxSubSeq {
-
public static final class SubSequence {
-
// Anfangsindex der Teilfolge
-
final int start;
-
// Länge der Teilfolge
-
final int length;
-
// Summe der Teilfolge
-
final int sum;
-
-
public SubSequence(int start, int length, int sum) {
-
this.start = start;
-
this.length = length;
-
this.sum = sum;
-
}
-
-
if(!(object instanceof SubSequence))
-
return false;
-
SubSequence other = (SubSequence)object;
-
return start == other.start
-
&& length == other.length
-
&& sum == other.sum;
-
}
-
};
-
-
static SubSequence optimalMaxSubSequence(int[] sequence) {
-
// bitte implementieren Sie diese Methode!
-
// geben Sie ein Objekt vom Typ SubSequence zurück,
-
// das die maximale Teilfolge beschreibt.
-
return new SubSequence(0, 0, 0);
-
}
-
-
public static SubSequence naiveMaxSubSequence(int[] sequence) {
-
int global_start = 0, global_length = 0, global_sum = 0;
-
-
for(int len = 1; len <= sequence.length; len++) {
-
for(int i = 0; i < sequence.length - len + 1; i++) {
-
int sum = 0;
-
for(int j = 0; j < len; j++)
-
sum += sequence[i + j];
-
-
if(sum > global_sum) {
-
global_start = i;
-
global_length = len;
-
global_sum = sum;
-
}
-
}
-
}
-
-
return new SubSequence(global_start, global_length, global_sum);
-
}
-
-
int seq_length = 10;
-
-
-
int num_trails = 10;
-
int range = 20;
-
-
for(int i = 0; i < num_trails; i++) {
-
int[] sequence = new int[seq_length];
-
for(int j = 0; j < seq_length; j++) {
-
int abs = random.nextInt(range);
-
sequence[j] = (random.nextBoolean() ? -abs : abs);
-
}
-
-
SubSequence max = optimalMaxSubSequence(sequence);
-
System.out.println(" optimalMaxSubSequence() returned (start: " + max.start + ", length: " + max.length
-
+ ", sum: " + max.sum + ")");
-
-
SubSequence correct = naiveMaxSubSequence(sequence);
-
if(max.equals(correct)) {
-
}else{
-
+ ", sum: " + correct.sum + ") is maximal!");
-
}
-
}
-
}
-
}
Die von mir bereits umgesetzt Methode sieht so aus:
Java Code:
-
-
static SubSequence optimalMaxSubSequence(int[] sequence) {
-
-
/* Initialisierung */
-
int glob_max = 0;
-
int suffix_max = 0;
-
int l = 1, r = 0;
-
int sl = 1, m = 0;
-
/* Ende Intitalisierung */
-
-
while (m < sequence.length) {
-
m += 1;
-
for (int i = 0; i < sequence.length - 1; i++) {
-
if(sequence[i] + suffix_max > glob_max){
-
suffix_max += sequence[i];
-
glob_max = suffix_max;
-
l = sl;
-
r = m;
-
}
-
else if(sequence[i] + suffix_max >= 0){
-
suffix_max += sequence[i];
-
}
-
else{
-
suffix_max = 0;
-
sl = m+1;
-
}
-
}
-
}
-
return new SubSequence(0, 0, 0);
-
}
Mein Problem
Ich weiß nicht, was ich in der Methode zurück geben soll. Den Pseudocode in Java zu verfassen war ja ziemlich einfach, aber ich verstehe nicht, was es mit dem Typ SubSequence auf sich hat. Ich vermute, dass an der Stelle
Java Code:
-
return new SubSequence(0, 0, 0);
Java Code:
-
return new SubSequence(/*start, length, sum*/);
Java Code:
-
return new SubSequence(l, r, glob_max);
Wie kann ich das umsetzen? Generell ist es das erste Mal, dass ich mit solchen selber erzeugten Datentypen arbeiten soll, deswegen fehlt mir auf jeden Fall Erfahrung damit.
SubSquence
Categories: SubSquence
Inscription à :
Publier les commentaires (Atom)
0 commentaires:
Enregistrer un commentaire