Zahlensequenz mit einer anderen Sequenz vergleichen

[jbruenig]

Hallo,

hab hier eine Aufgabe, an der ich eine Sache nicht verstehe.

Erstmal der Code:

class CountSubsequence{
    public static void main(String[] args){
        // Testreihen
        int[] sequence = {1,2,2,2,2,4,3};
        int[] subsequence = {2,2};

        // Zaehlvariable
        int count = 0;
       
        // TODO
       
        if (sequence.length >= subsequence.length) {
       
        for(int i = 0; i < sequence.length; i++) {
            for (int j=0; j < subsequence.length && sequence[i+j] == subsequence[j]; j++) {
                if(j == subsequence.length-1) {
                    count++;
                }
            }
        }

        // Ausgabe des Ergebnisses
        System.out.println("Count: " + count);   
    }
}
}

Also, verschachtelte Schleife, zwei Sequenzen, "sequence" soll mit "subsequence" verglichen werden und dann zählt ein Zähler mit, wie oft die Subsequenz in der Sequenz vorkommt.

Die Schleife beginnt also bei i=0, i ist kleiner als die Länge der Sequenz (1<7), die innere Schleife fängt also an zu laufen.

Hier liegt dann auch mein Problem. Der erste Teil der Bedingung "j < subsequence.length" wird ja für j=0 erfüllt, das sequence[i+j] == subsequence[j] nach dem && wird aber nicht erfüllt. Warum wird dann die Anweisung "j++" trotzdem ausgeführt, und die Schleife dann nochmal für j=1 ausgeführt?, um dann bei j=2 abzubrechen und an die äußere Schleife wieder abzugeben?

Hoffe, die Frage ist so verständlich.

Liebe Grüße,

Jan

 

[max40]

mach doch mal ein

count++;
System.out.println("i="+i + " j=" + j);

Dein Programm hat noch ein Fehler, wenn deine sequence mit 2 endet: z.B.

  int[] sequence = {1,2,2,2,2,4,3,2};

 

[MoxxiManagarm]

Ehrlich gesagt verstehe ich die Frage nicht ganz. Ist das dein Code, oder der Code eines anderen den du verstehen willst?

sequence[i+j] == subsequence[j]

Wenn ich mich nicht täusche dürfte das doch irgendwann in eine IndexOutofBoundException laufen?!
Wenn i=6 und j=1, dann ist j+i=7 und den Index 7 hat deine sequence nicht.

 

[jbruenig]

Hey,

sorry für die späte Antwort!

Das ist eine Aufgabe aus einem Informatik Tutorium, ich versuche den Code zu verstehen.

Den Fehler mithilfe der Musterlösung lösen:

// TODO
11 if (sequence.length >= subsequence.length) {
12
13 for (int i = 0; i <= sequence.length−subsequence.length; i++) {

Damit gibt es dann keine Fehlermeldung mehr, warum verstehe ich allerdings nicht...
In dem Beispiel ist sequence.length ja 7, subsequence 2, also kommt da "5" raus, also wenn i zwischen 0 und 5 ist, geh in die innere Schleife.

Wenn ich mich nicht täusche dürfte das doch irgendwann in eine IndexOutofBoundException laufen?!
Wenn i=6 und j=1, dann ist j+i=7 und den Index 7 hat deine sequence nicht.

Mit der Modifikation oben ergibt das auch mehr Sinn, denn i+j ist dann maximal 6 [5+1), da ja j echt kleiner als subsequence.length sein muss.


Ich versuche meine Frage nochmal zu präzisieren:

1. Die äußere Schleife prüft, ob i <= der sequence-subsequence-Länge ist, bei i=0 ist die Bedingung erfüllt, die Anweisung wird ausgeführt (i++) --> meine erste Frage: ist i jetzt sofort = 1, also auch schon für die innere Schleife? Oder gilt das erst für den nächsten äußeren Schleifenablauf? Eigentlich ja sofort, oder?
2. Die innere Schleife überprüft erstmal, ob j < als die subsequence-Länge ist, bei j=0 erfüllt, dann wird aber noch eine zweite Bedingung überprüft (&&), ob sequence[i+j] == subsequence[j]. So, wenn man i und j jetzt gleich 0 setzt, käme da raus sequence[0] = 1 == subsequence[0] = 2, was nicht stimmt, die Anweisung (j++) wird also nicht ausgeführt, genauso wie die "if"-Schleife danach.

oder wird hier schon mit i=1 gearbeitet und es heißt dann:
sequence[1] = 2 == subsequence[0]=2, wodurch dann j auch um eins angehoben wird (j++), wodurch dann die if-Schleife ausgeführt wird, falls j=1 == subsequence.length-1=1 stimmt und dann count++ ausgeführt wird.

Hoffe mein Logikproblem ist etwas klarer geworden. Vielleicht versteh ich die Schleifenlogik einfach gar nicht, dann wäre es cool, wenn mir die jemand hier mal genau aufschreiben könnte.

Liebe Grüße,

Jan

 

[temi]

EDIT: War Blödsinn, habe nicht aufgepasst...

 

[temi]

meine erste Frage: ist i jetzt sofort = 1, also auch schon für die innere Schleife?

Beim ersten Schleifendurchlauf ist i = 0.

 

[MoxxiManagarm]

In dem Beispiel ist sequence.length ja 7, subsequence 2, also kommt da "5" raus, also wenn i zwischen 0 und 5 ist, geh in die innere Schleife.

Weil du nur den Anfang suchst von der Sequenz die du vergleichen willst. Es lohnt nicht mehr am letzten Element anzusetzen, wenn die Vergleichssequenz 2 Elemente hat.