Wörter suchen - Programmieraufgaben.ch

Wörter suchen (Algorithmen)

Laden Sie die gepackte Wortliste herunter. (Es handelt sich um eine leicht modifizierte Rechtschreibkorrektur des Browsers "Firefox".)

Überlegen Sie die Vor- und Nachteile einer linearen Suche im Gegensatz zu einer binären Suche. Lösen Sie damit die folgenden Aufgaben:

Schreiben Sie ein Programm, das alle Wörter der Datei ausgibt, bei welchen der folgende Wortanfang gegeben ist: "Distanz", "Erdbi", "Finanzind".
Schreiben Sie ein Programm, das ermittelt, welche der folgenden Wörter in der Liste vorkommen: "Darmlymphgefäß", "Fahrplanabschnitt", "Formamid".
Schreiben Sie ein Programm, das alle Wörter anzeigt, welche die folgende Wortendung aufweisen: "gulierung", "dcomputer", "chsdor".

Dateien:

deutsch.zip

0 Kommentare

Bitte melde dich an um einen Kommentar abzugeben

import java.io.*;
import java.util.*;

public class WoerterSuchen {
    public static void main(String[] args) {
        new WoerterSuchen().top();
    }

    final String VERZEICHNIS = "/home/user/Desktop";

    List<String> wortListe;

    void top() {
        wortlisteLaden("deutsch.txt");
        wortAnfangLinear();
        wortAnfangBinaer();
        wortExaktLinear();
        wortExaktBinaer();
        wortEndeLinear();
    }

    void wortAnfangLinear() {
        String[] suchWoerter = { "Distanz", "Erdbi", "Finanzind" };
        for (String wort : wortListe) {
            for (String suchWort : suchWoerter)
                if (wort.toLowerCase().startsWith(suchWort.toLowerCase())) {
                    System.out.println("WortAnfangLinear gefunden: " + wort);
                }
        }
    }

    void wortAnfangBinaer() {
        String[] suchWoerter = { "Distanz", "Erdbi", "Finanzind" };
        for (String suchWort : suchWoerter) {
            int suchIndexUntergrenze = 0;
            int suchIndexObergrenze = wortListe.size() - 1;
            int suchIndexMitte = (suchIndexObergrenze + suchIndexUntergrenze) / 2;

            while (!gefundenWortAnfang(suchIndexMitte, suchWort)) {
                if (indexMitteZuGrossWortAnfang(suchIndexMitte, suchWort)) {
                    suchIndexObergrenze = suchIndexMitte;
                } else {
                    suchIndexUntergrenze = suchIndexMitte;
                }
                suchIndexMitte = (suchIndexObergrenze + suchIndexUntergrenze) / 2;
            }
            alleInDerNaeheAusgeben(suchIndexMitte, suchWort);
        }
    }

    void alleInDerNaeheAusgeben(int suchIndexMitte, String suchWort) {
        while (wortListe.get(suchIndexMitte).toLowerCase().startsWith(
                suchWort.toLowerCase())) {
            suchIndexMitte = suchIndexMitte - 1;
        }
        suchIndexMitte = suchIndexMitte + 1;
        while (wortListe.get(suchIndexMitte).toLowerCase().startsWith(
                suchWort.toLowerCase())) {
            System.out.println("WortanfangBinaer gefunden: "
                    + wortListe.get(suchIndexMitte));
            suchIndexMitte = suchIndexMitte + 1;
        }
    }

    boolean indexMitteZuGrossWortAnfang(int suchIndexMitte, String suchWort) {
        String wortInMitte = wortListe.get(suchIndexMitte);
        if (wortInMitte.toLowerCase().startsWith(suchWort.toLowerCase())) {
            return false;
        }
        return wortInMitte.toLowerCase().compareTo(suchWort.toLowerCase()) > 0;
    }

    boolean indexMitteZuGrossExakt(int suchIndexMitte, String suchWort) {
        String wortInMitte = wortListe.get(suchIndexMitte);
        if (wortInMitte.toLowerCase().equalsIgnoreCase(suchWort.toLowerCase())) {
            return false;
        }
        return wortInMitte.toLowerCase().compareTo(suchWort.toLowerCase()) > 0;
    }

    boolean gefundenWortAnfang(int suchIndexMitte, String suchWort) {
        return wortListe.get(suchIndexMitte).startsWith(suchWort);
    }

    boolean gefundenExakt(int suchIndexMitte, String suchWort) {
        return wortListe.get(suchIndexMitte).equalsIgnoreCase(suchWort);
    }

    void wortEndeLinear() {
        String[] suchWoerter = { "gulierung", "dcomputer", "chsdor" };
        for (String wort : wortListe) {
            for (String suchWort : suchWoerter)
                if (wort.toLowerCase().endsWith(suchWort.toLowerCase())) {
                    System.out.println("WortEndeLinear gefunden: " + wort);
                }
        }
    }

    void wortExaktBinaer() {
        String[] suchWoerter = { "Darmlymphgefäß", "Fahrplanabschnitt",
                "Formamid" };
        nextWort: for (String suchWort : suchWoerter) {
            int suchIndexUntergrenze = 0;
            int suchIndexObergrenze = wortListe.size() - 1;
            int suchIndexMitte = (suchIndexObergrenze + suchIndexUntergrenze) / 2;

            while (!gefundenExakt(suchIndexMitte, suchWort)) {
                // Abbruch falls nicht vorkommt!
                if (suchIndexObergrenze == suchIndexUntergrenze) {
                    continue nextWort;
                }
                if (indexMitteZuGrossExakt(suchIndexMitte, suchWort)) {
                    suchIndexObergrenze = suchIndexMitte;
                } else {
                    if (suchIndexUntergrenze < suchIndexMitte) {
                        suchIndexUntergrenze = suchIndexMitte;
                    } else {
                        suchIndexUntergrenze = suchIndexMitte + 1; // Abrundungsfehler
                    }

                }
                suchIndexMitte = (suchIndexObergrenze + suchIndexUntergrenze) / 2;
            }
            System.out.println("WortExaktBinaer gefunden: "
                    + wortListe.get(suchIndexMitte));
        }
    }

    void wortExaktLinear() {
        String[] suchWoerter = { "Darmlymphgefäß", "Fahrplanabschnitt",
                "Formamid" };
        for (String wort : wortListe) {
            for (String suchWort : suchWoerter)
                if (wort.equalsIgnoreCase(suchWort)) {
                    System.out.println("WortExaktLinear gefunden: " + wort);
                }
        }
    }

    void wortlisteLaden(String dateiname) {
        wortListe = new ArrayList<String>();
        FileReader fr = null;
        String vollerDateiname = VERZEICHNIS + "/" + dateiname;
        try {
            fr = new FileReader(vollerDateiname);
            BufferedReader br = new BufferedReader(fr);
            String aktuellesWort;
            while (null != (aktuellesWort = br.readLine())) {
                wortListe.add(aktuellesWort.trim());
            }
            Collections.sort(wortListe);
            fr.close();
        } catch (FileNotFoundException e) {
            System.err.println("Datei nicht gefunden: " + vollerDateiname
                    + " (" + e + ")");
            e.printStackTrace();
        } catch (IOException e) {
            System.err.println("Dateifehler: " + e);
            e.printStackTrace();
        }
    }

} // end of class WoerterSuchen

/*----------------------------------------------------------*\
| Der einfachheit halber wurde die wortliste bearbeitet,     |
| über html geladen und liegt als wortarray $dictionary vor. |
\*----------------------------------------------------------*/

// wortanfänge
let list = ['Distanz', 'Erdbi', 'Finanzind'];
for (let l in list)
  console.log(`${list[l]}~:
    ${dictionary.filter(wrd => wrd.startsWith(list[l])).join(', ')}`);

// vorkommen
list = ['Darmlymphgefäß', 'Fahrplanabschnitt', 'Formamid'];
for (let l in list)
  console.log(`${list[l]}:
    ${dictionary.includes(list[l])}`);

// wortenden
list = ['gulierung', 'dcomputer', 'chsdor'];
for (l in list)
  console.log(`~${list[l]}:
    ${dictionary.filter(wrd => wrd.endsWith(list[l])).join(', ')}`);
                                                             // lissalanda@gmx.at

Lösung von: Lisa Salander (Heidi-Klum-Gymnasium Bottrop)

// NET 6.x | C# 10.x | VS-2022

var path = @"C:\...\deutsch.txt";
if (!File.Exists(path)) return;
var data = File.ReadAllLines(path);

void Print<T>(IEnumerable<T> t1, IEnumerable<T> t2, Func<T, T, bool> func) =>
    t1.SelectMany(x => t2.Select(y => (f: x, s: y))).Where(x => func(x.f, x.s)).ToList().ForEach(x => Console.WriteLine(x));

Print(data, new List<string> { "Distanz", "Erdbi", "Finanzind" }, (a, b) => a.StartsWith(b));
Print(data, new List<string> { "Darmlymphgefäß", "Fahrplanabschnitt", "Formamid" }, (a, b) => a.Contains(b));
Print(data, new List<string> { "gulierung", "dcomputer", "chsdor" }, (a, b) => a.EndsWith(b));

Lösung von: Jens Kelm (@JKooP)

// C++ 14 | VS-2022

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <fstream>

using str = std::string;
using vstr = std::vector<str>;

inline const bool ends_with(const str& lhs_, const str& rhs_) {
    if (rhs_.size() > lhs_.size()) return false;
    return std::equal(rhs_.rbegin(), rhs_.rend(), lhs_.rbegin());
}

inline const bool starts_with(const str& lhs_, const str& rhs_) {
    return lhs_.rfind(rhs_, 0) == 0;
}

inline const bool contains(const str& lhs_, const str& rhs_) {
    return lhs_.find(rhs_) != str::npos;
}

template<typename T, typename F>
const auto print(const T& t1_, const T& t2_, const F& f_) {
    for (const auto& e2 : t2_) {
        std::cout << e2 << ":\n";
        for (const auto& e1 : t1_)
            if (f_(e1, e2))
                std::cout << e1 << "\n";
        std::cout << "\n";
    }
    std::cout << "====================\n\n";
}

inline const auto get_data(const str& path) {
    str line;
    vstr output{};
    std::ifstream input(path);
    if (!input) {
        std::cerr << "Pfad (" << path << ") nicht gefunden!\n\n";
        return output;
    }
    while (std::getline(input, line))
        output.push_back(line);
    return output;
}

int main() {
    const str path{ "C:\\...\deutsch.txt" };
    const auto data{ get_data(path) };
    const vstr start{ "Distanz", "Erdbi", "Finanzind" };
    const vstr contain{ "Darmlymphgefäß", "Fahrplanabschnitt", "Formamid" };
    const vstr end{ "gulierung", "dcomputer", "chsdor" };

    print(data, start, starts_with);
    print(data, contain, contains);
    print(data, end, ends_with);
}

Lösung von: Jens Kelm (@JKooP)

wortanfang=[ "Distanz", "Erdbi", "Finanzind"]
vorkommen=["Darmlymphgefäß", "Fahrplanabschnitt", "Formamid"]
wortendung=["gulierung", "dcomputer", "chsdor"]
with open("deutsch.txt") as datei:
    liste = [wort.rstrip() for wort in datei]
#Vorkommen   
for x in range(len(vorkommen)):
    try:    
        liste.index(vorkommen[x])
        print(vorkommen[x])
    except:   
        continue
#Wortanfang
for wort in liste:
    for x in range(len(wortanfang)):
       if wortanfang[x] in wort:
            print(wort)
#Wortendung
for wort in liste:
    for x in range(len(wortendung)):
        standort=wort.rfind(wortendung[x])
        if standort==-1:
            continue
        if standort+len(wortendung[x])==len(wort):
            print(wort)

Lösung von: Name nicht veröffentlicht

Verifikation/Checksumme:

Diskussion: Um binär zu suchen, muss ein Index bekannt sein. Für die Wortendungen bleibt unter anderem die lineare Suche oder eine sortierte Tabelle nach den Spiegelbild-Wörtern (Umkehrung: "Hallo" -> "ollaH").

Zeit:	2
Schwierigkeit:	k.A.
Webcode:	9nz3-nf8o
Autor:	Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

Programmieren lernen

Web-Code:

Wörter suchen (Algorithmen)

Dateien:

0 Kommentare

5 Lösung(en)

Verifikation/Checksumme:

Aktionen

Bewertung

Meta