Stringproblem durch Rekursion lösen

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Stringproblem durch Rekursion lösen

    Hallo Leute, ich habe ein riesen Problem.
    Und zwar besteht das Problem darin, diese Aufgabe mit Java zu lösen. Könnt ihr mir weiterhelfen wie man da vorgeht?

    Aufgabenstellung:
    Ein typisches Problem in der Informatik ist die Berechnung der Ahnlichkeit von zwei
    Wortern. Entsprechende Algorithmen werden z. B. bei der automatischen Rechtschreibkorrektur
    angewendet, um Korrekturvorschlage zu unterbreiten. Dabei wird das falsch geschriebene Wort mit allen bekannten Wortern in einem Worterbuch verglichen und
    die ahnlichsten Worter als Korrektur vorgeschlagen.
    Implementieren Sie einen Algorithmus, der die Ahnlichkeit bzw. Distanz zwischen zwei
    Strings berechnet. Die Ahnlichkeit von zwei Strings s1 und s2 entspricht den minimalen
    Kosten, die benotigt werden, um s1 in s2 zu transformieren. Hohe Kosten bedeuten dabei
    eine geringe Ahnlichkeit der beiden Strings. Folgende rekursiv denierte Funktion soll
    dafur implementiert werden:
    public static int berechneMinKosten(String s1, String s2, int pos1, int pos2)

    Diese Funktion bekommt als Eingabe zwei Strings s1 und s2, sowie die Position pos1
    innerhalb des ersten Strings und die Position pos2 innerhalb des zweiten Strings. Als
    Ausgabe liefert die Funktion die minimalen Kosten zuruck, die entstehen wenn man s1
    ab der Position pos1 in den String s2 ab Position pos2 transformieren will.
    Die minimalen Kosten werden wie folgt berechnet:
    Die Rekursion wird abgebrochen, wenn sowohl pos1 als auch pos2 uber die maximale
    Läange des Strings hinausgelaufen sind. In dem Fall sind die minimalen Kosten
    als 0 deniert.
    Wenn die beiden Buchstaben an pos1 und pos2 identisch sind, dann sind die
    minimalen Kosten deniert als berechneMinKosten(s1, s2, pos1+1, pos2+1).
    Wenn die beiden Buchstaben an pos1 und pos2 unterschiedlich sind, dann sind
    die minimalen Kosten deniert als das Minimum von
    berechneMinKosten(s1, s2, pos1+1, pos2)+1 und
    berechneMinKosten(s1, s2, pos1, pos2+1)+1.

    Fur Ihre Implementierung der Funktion berechneMinKosten(s1, s2, pos1, pos2)
    mussen Sie auerdem noch uberlegen, wie Sie mit dem Fall umgehen, wenn entweder nur
    pos1 oder nur pos2 uber die maximale Lange des jeweiligen Strings hinausgelaufen sind.
    Uberlegen Sie auerdem, wie die rekursive Funktion anfangs aufgerufen werden muss, um
    die minimalen Transformationskosten fur zwei beliebige Strings zu berechnen. Benutzen
    Sie diese letzte Uberlegung um zusatzlich noch folgende Funktion zu implementieren:
    public static int berechneMinKosten(String s1, String s2)
    Nutzliche Funktionen:
    Folgende Funktionen für Strings sind hilfreich fur die Implementierung der Aufgabe:
    s.length() liefert die Lange des Strings s zuruck.
    s.charAt(pos) liefert den Buchstaben an Position pos im String s zurüuck. Der
    erste Buchstabe eines Strings hat dabei die Position 0.

    Hoffe ihr könnt mir da weiterhelfen. Sage schon mal vielen Dank im Voraus.
    Gruß, leon

    Quellcode

  • leon2906 schrieb:

    Und zwar besteht das Problem darin, diese Aufgabe mit Java zu lösen.

    Aha. Mit einer anderen Programmiersprache wäre es für dich also ohne Probleme lösbar?
    Könnt ihr mir weiterhelfen wie man da vorgeht?

    Jupp: Sich auf den Hosenboden setzen und selber mal über eine Lösung nachdenken, anstatt auf vorgekaute Lösungen zu hoffen. Wenn du sowas ähnliches wie einen Lösungsansatz hast, kannst du ja noch mal wiederkommen.