Rekurrenz und Longest common Subsequence

Aufrufe: 227     Aktiv: 17.01.2021 um 12:08

0

Hallo zusammen,

Wie kommt man auf so seine Schreibweise bzw. was bedeutet das genau? Warum steht bei j = A7 && i =A2 eine zwei? Wie wird das berechnet?

enter image description here

enter image description here

enter image description here

enter image description here

enter image description here

Diese Frage melden
gefragt

Student, Punkte: 64

 
Kommentar schreiben
1 Antwort
0

Ich kann dir leider nicht genau sagen, wie man auf die Formel gekommen ist, aber wie man vorgeht, wenn man die Formel als richtig annimmt:

Zuerst beginnst du mit der ersten Zeile. Dort betrachtest du noch keine Buchstaben beim String der nach unten aufgelistet ist, daher ist die LCS der beiden Strings überall 0

In der zweiten Zeile betrachtest du den Buchstaben "B" des Strings der nach unten aufgelistet ist. Dann vergleichst du von links nach rechts mit dem String der nach rechts aufgelistet ist. Bei i = 1 und j = 4 stimmen die beiden Buchstaben überein, d.h bei der Formel bist du bei xi = yj, d.h. du nimmst den Wert oben links darüber und addierst 1, ( 0 + 1 = 1)

Und falls die beiden Buchstaben nicht übereinstimmen, trifft bei der Formel xi != yj zu, d.h. du musst das Maximum der Werte direkt links und direkt darüber nehmen, z.B. bei i = 4 und j = 4 musst du das Maximum von 1 und 2 nehmen, d.h. 2

Und so gehst du weiter bis ganz unten rechts, dort findest du die LCS der beiden gesamten Strings

Diese Antwort melden
geantwortet

 

Kommentar schreiben