Foren » 30. BwInf

Einfachere Lösung für "Zaras Dritter Fehler"

    • 2 Beiträge
    2. Januar 2012 15:05:42 CET

    Hallo ihr

    Ich hab zwar dieses Mal nicht mitgemacht weil ich zu faul war ne Doku zu schreiben aber ich hab mir grad mal die Lösungen von der ersten Runde angeschaut und mich über die komplizierte Lösung mittels Wörterbuch gewundert.

    Ich bin einfach davon ausgegangen, dass Jemand beim erstellen der Zahlenreihen die kleinstmöglichen Zahlen genommen hat. Also wenn er in seinem Wort als nächstes ein N gebraucht hat, dann auch nur bis zum nächsten N gezählt hat und nicht bis zum zweiten oder weiter.

    Mein kleiner Algorithmus schaut einfach danach dass sich zwischen zwei Position nicht der Buchstabe von letzterer Position befindet.

    Findet alle Lösungen außer 7 und B. (vllt wegen nem unerheblichen Bug ka)

    Implementiert in Qt:

     

        QTextStream qout(stdout);
        QTextStream qin(stdin);
        QFile textfile("EffiBriest.txt");
        QFile keyfile("zahlenfolge0.txt"); //Ändern
        QString BuchText;
        QString KeyText;
        QStringList Keys;

        qout << "Zaras dritter Fehler\n\n" << endl;

        if (!textfile.open(QIODevice::ReadOnly | QIODevice::Text)) {
             qout << "Konnte Datei nicht öffnen";
            return 0;
         }
        BuchText = textfile.readAll();

        qout << "Buchtext geladen.\nEntferne Leer- und Satzzeichen...\n\n" << endl;

        if (!keyfile.open(QIODevice::ReadOnly | QIODevice::Text)) {
             qout << "Konnte Datei nicht öffnen";
            return 0;
          }
        KeyText = keyfile.readAll();
        Keys = KeyText.split(" ");

        int lineStart = 0;
        while (lineStart > -1) {
            int pos = lineStart;

            bool found = true;
            for (int k = 0; k < Keys.length(); k++) {
                int nextPos = pos;
                int c = 0;
                while (c < Keys[k].toInt()) {
                    if (BuchText[nextPos].isLetterOrNumber())
                        c++;
                    nextPos++;
                }
                nextPos--;
                QChar Buchstabe = BuchText[nextPos];
                QString textStelle = BuchText.mid(pos, nextPos-pos);
                if ((!textStelle.contains(Buchstabe) || textStelle.length() == 1)) {
                    qout << Buchstabe.toLower();
                } else {
                    found = false;
                    break;
                }
                pos = nextPos+1;
            }
            if (found) {
                qout << endl << "Erfolg" << endl;
                break;
            }
            qout << endl;
            lineStart = BuchText.indexOf("\n", lineStart+1);
        }

     

    MfG,

    Konrad

    • 45 Beiträge
    2. Januar 2012 15:23:37 CET
    wurde glaube ich in den Lösungen kurz erwähnt: Da es in der Aufgabe so nicht angegeben war, die Aufgabe also nicht ausschloss, dass es nicht die kleinstmögliche Zahl ist, reichte diese Lösung nicht aus.

    Paul
    • 230 Beiträge
    2. Januar 2012 15:58:34 CET
    Cooro said:

    Ich bin einfach davon ausgegangen, dass Jemand beim erstellen der Zahlenreihen die kleinstmöglichen Zahlen genommen hat. Also wenn er in seinem Wort als nächstes ein N gebraucht hat, dann auch nur bis zum nächsten N gezählt hat und nicht bis zum zweiten oder weiter.

    ja, mit dieser Vereinfachung kann man arbeiten. Das ist aber so nicht vorgegeben. Wenn Du in die Bewertungskriterien auf der Seite 36 der online verfügbaren Lösungshinweise schaust, siehst Du im vierten Punkt:

     

    Das Beispiel aus der Aufgabenstellung legt die Annahme nahe, dass Zara bei der Ver-
    schlüsselung immer die minimale Distanz zum nächsten benötigten Buchstaben wählt.
    Diese Annahme ist zwar im Nachhinein richtig, vereinfacht die Lösung aber erheblich,
    und die Verallgemeinerung eines einzelnen Beispiels ist allzu mutig.

     

     

    • 13 Beiträge
    2. Januar 2012 16:36:39 CET

    Ich habe die Aufgabe auch mit der einfacheren Lösung gelöst. Mir war wohl klar, dass in der Aufgabe nicht direkt stand, dass immer der nächste Buchstabe ausgewählt wird. Aber es wird ja oft gesagt, dass man den "BwInf-Dreisprung" bei Unklarheiten anwenden soll. Ich habe mich dann entschieden von einer minimalen Distanz auszugehen, da in allen Beispielen auch immer der nächste Buchstabe ausgewählt wurde.

     

    In den Lösungshinweisen wird behauptet, dass diese Lösung "erheblich einfacher" sei. Meiner Meinung nach, ist ein Wörterbuchabgleich keineswegs schwieriger umzusetzen. Außerdem denke ich, dass selbst wenn in der Aufgabe gestanden hätte, dass immer der nächste Buchstabe ausgewählt werden muss, die meisten eher auf die Wörterbuch-Lösung gekommen wären. Dann ist da noch von der "Verallgemeinerung eines einzelnen Beispiels" die Rede: Erstens ist es nicht ein Beispiel, sondern es trifft auf alle 12 Zahlenfolgen zu. Zweitens bestand die Aufgabe nicht darin, ein Verfahren für die allgemeine Entschlüsselung zu entwickeln, sondern in folgendem: "Ermittle für diese und alle weiteren Zahlenfolgen [...] welcher Satz [...] dahinter steckt."

     

    Aber ich bin trotzdem in die zweite Runde gekommen ;-)


    Dieser Beitrag wurde am 2. Januar 2012 16:38:19 CET von Markus Schmidt bearbeitet
    • 45 Beiträge
    2. Januar 2012 18:10:23 CET
    Ich denke schon, dass die Wörterbuchmethode etwas schwieriger ist, da man schließlich nicht davon ausgehen kann, dass eine Entschlüsselungsmethode zu 100% aus Wörtern der Wortliste besteht. Kasus und Numerus machen da gewissen Schwierigkeiten.
    • 2 Beiträge
    2. Januar 2012 23:22:12 CET
    Man könnte auch davon ausgehen, dass der Verschlüsseler einen Buchstaben nicht mehr als 5mal überspringen würde und den Algorithmus entsprechend erweitern. Da es um Geschäftsreisen geht, könnte der geheime Satz auch in einer anderen Sprache gewesen sein. Die Wörterbuchmethode ist hinsichtlich Fehleranfälligkeit, Komplexität, Speicherverbrauch und Ausführungszeit im Nachteil. Unabhängig von der Aufgabe finde ich die Idee und Implementation eines Wörterbuchvergleichs aber durchaus interessant. Nichts für ungut. :)