Pseudocode Naiver Algorithmus

[s_1895]

Hey Leute, ich schreibe gerade eine HAusarbeit und bin mir nicht sicher ob mein Pseudocode so richtig ist:
Es geht darum das ich ein Wort in einem Text suchen muss und für den naiven Algorithmus ist dies doch:
pos = Position
n= länge Text ; m = länge Wort
t = Text ; w = Wort

procedure NSMAlgorithmus
pos:= 1;
while pos <= n-m + 1 do
    j :=1;
    while (j>0) and (w[j]=t[pos+j-1]) do
        j:= j+1;
    if (j=m) then print ("Vorkommen an Position", pos);
    pos:=pos+1:
wend;
end.

und wofür steht dann am Ende das wend

 

[Flown]

w(hile)end. -> Anzeige Schleifenende

 

[s_1895]

w(hile)end. -> Anzeige Schleifenende

also es soll immer um eine Position nach vorne gerückt werden wenn die zwei Buchstaben/Zeichen nicht übereinstimmen, es soll aber beim ersten Zeichen des Wortes beginnen, ich hab diesen Pseudocode abgeändert, da der Originale bei dem Letzen Buchstaben des Wortes beginnt

So wie in dem Bild soll es ablaufen

 

[kneitzel]

Macht die Prüfung j>0 in der While Schleife überhaupt Sinn? j wird ja nie negativ. Da fehlt also entweder ein setzen von j auf einen negativen Wert (Was ich so nicht machen würde) oder die Bedingung ist schlicht falsch 🙂

Und das pos = pos + 1 dürfte auch an der falschen Stelle sein. Könnte mit daran liegen, dass die Einrückung nicht korrekt ist.

Edit: Das Zweite könnte von der Aufgabe abhängen, je nachdem, was erwartet wird, wenn z.B. nach "aa" gesucht werden soll in dem Text mit "aaaa" .

 

[s_1895]

würde es so mehr Sinn ergeben?

procedure NSMAlgorithmus
pos:= 1;
while pos <= n-m + 1 do
    j :=1;
    while (w[j]=t[pos+j-1]) do
        j:= j+1;
    
    if (j=m) then print ("Vorkommen an Position", pos);
pos:=pos+1;
wend;
end.

 

[kneitzel]

Also du hast zwei While ... do aber nur ein wend. (Das war mir so genau nicht aufgefallen beim ersten Blick - sonst hätte ich den zweiten Punkt anders formuliert.)

Das ist so also schon nicht korrekt. Du brauchst also noch ein weiteres wend. Auf Grund der Einrückung wirst Du vermutlich sowas meinen:

procedure NSMAlgorithmus
    pos:= 1;
    while pos <= n-m + 1 do
        j :=1;
        while (w[j]=t[pos+j-1]) do
            j:= j+1;
        wend
        
        if (j=m) then print ("Vorkommen an Position", pos);
        pos:=pos+1;
    wend;
end.

Hast du es mal durchgespielt? Spiel es mal durch mit diesen Fällen:
Gesucht wird jeweils "das"
- ""
- "d"
- "das"
- "xdas"
- "dasx"
- "xxda"

Und achte auf die Indices. Du darfst nicht versuchen auf Zeichen zuzugreifen, die es nicht gibt.

 

[s_1895]

Jetzt müsste es doch laufen oder nicht?

 

[s_1895]

ich hab vergessen zu sagen das das erste Zeichen in diesem Beispiel 1 ist und nicht wie normalerweise 0

 

[kneitzel]

Was passiert mit der inneren while schleife, wenn das letzte Zeichen des zu suchenden Wortes korrekt war?

Welchen Wert hat j, wenn die innere while schleife verlassen wird?

 

[s_1895]

muss dann die if bedingung eventuell mit in die innere while schleife?

 

[s_1895]

oder if ( j=m+1)

 

[kneitzel]

So eine Veränderung wäre möglich. Aber was passiert denn, nachdem das letzte Zeichen geprüft wurde und es gleich ist? Dann wird j wieder eins hoch gezählt. Und dann?

 

[s_1895]

Ich steig jetzt gar nicht mehr durch

 

[kneitzel]

Ok, nehmen wir diesen Code:

        while (w[j]=t[pos+j-1]) do
            j:= j+1;
        wend

pos=1
j = 1
w = a, b, c
t = a, b, c

Was passiert?
w[1] = t[1+1-1] --> a = a
-> j = 2
w[2] = t[1+2-1] --> b = b
-> j = 3
w[3] = t[1+3-1] --> c = c
-> j = 4
w[4] = t[1+4-1] ????

w[4] gibt es nicht, t[4] gibt es nicht.

 

[Barista]

Ich steig jetzt gar nicht mehr durch

Es wäre gut, wenn Du Dich an dem Bild orientierst.

Spiel selbst den Computer und führe den Ablauf aus (so war übrigens die ursprüngliche Idee von Turing).

 

[s_1895]

Ok, nehmen wir diesen Code:

        while (w[j]=t[pos+j-1]) do
            j:= j+1;
        wend

pos=1
j = 1
w = a, b, c
t = a, b, c

Was passiert?
w[1] = t[1+1-1] --> a = a
-> j = 2
w[2] = t[1+2-1] --> b = b
-> j = 3
w[3] = t[1+3-1] --> c = c
-> j = 4
w[4] = t[1+4-1] ????

w[4] gibt es nicht, t[4] gibt es nicht.

while (m<=j) and (w[j]=t[pos+j-1]) do

meinst du dann so?

 

[kneitzel]

Das sieht deutlich besser aus. Zusammen mit #11 von Dir könnte es das gewesen sein.

Ich habe Dir eine Reihe Test-Cases genannt. Spiel die doch einfach einmal durch (mit Papier und Stift). Das ist eine ganz wichtige Übung, damit Du besser so Algorithmen im Kopf durchspielen kannst.

Und Du kannst so Pseudo-Code natürlich auch in Java umsetzen um es dann zu testen.

 

[s_1895]

procedure NSMAlgorithmus
    pos:= 1;
    while pos <= n-m + 1 do
        j :=1;
        while (m<=j) and (w[j]=t[pos+j-1]) do
            j:= j+1;
        wend
       
        if (j=m) then print ("Vorkommen an Position", pos);
        pos:=pos+1;
    wend;
end.

Tatsächlich probiere ich das immer auf Papier aus um zu gucken ob es funktioniert

Danke dir/euch
war mir eine sehr große Hilfe