Texte entschlüsseln

Die mit polyalphabetischer Verschlüsselung kodierten Texte (bei Verwendung eines Alphabets) lassen sich meist sehr einfach über die Häufigkeitsverteilung der Buchstaben in Texten entschlüsseln.

Texte in deutscher Sprache haben etwa folgende Verteilung (nach deutscher Wikipedia) als double-Feld. Umlaute sind als ae, ue, oe gezählt:

double [] haeufigkeiten = new double[256];

        haeufigkeiten['a'] = 0.0651;
        haeufigkeiten['b'] = 0.0189;
        haeufigkeiten['c'] = 0.0306;
        haeufigkeiten['d'] = 0.0508;
        haeufigkeiten['e'] = 0.1740;
        haeufigkeiten['f'] = 0.0166;
        haeufigkeiten['g'] = 0.0301;
        haeufigkeiten['h'] = 0.0476;
        haeufigkeiten['i'] = 0.0755;
        haeufigkeiten['j'] = 0.0027;
        haeufigkeiten['k'] = 0.0121;
        haeufigkeiten['l'] = 0.0344;
        haeufigkeiten['n'] = 0.0253;
        haeufigkeiten['m'] = 0.0978;
        haeufigkeiten['o'] = 0.0251;
        haeufigkeiten['p'] = 0.0079;
        haeufigkeiten['q'] = 0.0002;
        haeufigkeiten['r'] = 0.0700;
        haeufigkeiten['s'] = 0.0727;
        haeufigkeiten['t'] = 0.0615;
        haeufigkeiten['u'] = 0.0435;
        haeufigkeiten['v'] = 0.0067;
        haeufigkeiten['w'] = 0.0189;
        haeufigkeiten['x'] = 0.0003;
        haeufigkeiten['y'] = 0.0004;
        haeufigkeiten['z'] = 0.0113;
        haeufigkeiten['ß'] = 0.0031;

Implementieren Sie ein Programm, welches mit Hilfe dieser Verteilung einen verschlüsselten Text entschlüsselt: die Zeichen im verschlüsselten Text werden gezählt und dann mit den am besten passenden Buchstaben obiger Verteilung ersetzt. Der verschlüsselte Text sollte möglichst lang sein (mehr als 1000 Zeichen).

Man kann den Algorithmus noch verbessern, indem die Buchstabenhäufigkeit von Anfangs- und Endbuchstabe mit berücksichtigt wird oder ein Wörterbuch verwendet wird.

Sixteen-Puzzle lösen

Wir betrachten folgendes Geduldsspiel:

Das Spielbrett enthält 8 rote und 8 grüne Steine. Ein Feld in der Mitte ist frei.

Ziel des Spiels ist es die grünen und roten Steine auszutauschen.

Folgende horizontalen und vertikalen Züge sind dabei möglich:

• Ein zum leeren Feld angrenzender Stein darf in das leere Feld verschoben werden.
• Ein Stein darf über einen anderen Stein (egal welche Farbe) in das leere Feld springen.

Hier drei gültige aufeinanderfolgende Spielzüge:

Implementieren Sie ein Programm mit rekursivem Backtracking, das eine Lösung für dieses Problem findet. Beachten Sie, das ein Hin- und Herschieben von Steinen zu unendlichen Zugfolgen führt. Dies kann durch beschränkte Tiefensuche gelöst werden: Bei 50 Zügen wird die Suche abgebrochen (es gibt Lösungen mit weniger Zügen).

Das Spiel habe ich hier gefunden. Dort kann man es mit einem JavaScript-Programm spielen. Den Ursprung des Spiels habe ich leider nicht herausgefunden.

Goldbachsche Vermutung überprüfen

1742 hat Christian Goldbach eine Vermutung aufgestellt, nach der jede ungerade Zahl größer als fünf als Summe dreier Primzahlen dargestellt werden kann.

Die nach ihm benannte Goldbachsche Vermutung lautet in einer stärkeren, heute gebräuchlichen Version:

Jede gerade natürliche Zahl (größer als zwei) kann als Summe zweier Primzahlen repräsentiert werden.

4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, …

Die Summe muß nicht eindeutig sein: 5 + 5 = 3 + 7 = 10 .

Die Vermutung wurde bisher nicht bewiesen. Sie wurde für alle Zahlen bis 10¹⁸ (Stand 2007) bestätigt.

Implementieren Sie ein Programm, daß für alle geraden Zahlen bis zu einer Obergrenze, zwei Primzahlen findet, deren Summe gleich der Zahl ist.

Zyklische Zahlen berechnen

Eine natürliche Zahl n mit i Dezimalstellen ist eine zyklische Zahl, wenn das Produkt alle Zahlen von 1 bis i mit n eine Zahl ergibt, deren Dezimalstellen sich aus einer zyklischen Verschieben der Stellen von n ergeben.

1 ist eine zyklische Zahl. 142857 ist die nächst größere zyklische Zahl (1 * 142857 = 142857, 2 * 142857 = 285714, …)

Schreiben Sie ein Programm, welches alle zyklischen Zahlen von 1 bis einer Obergrenze findet.

Man muß führende Nullen zulassen!

Um diese Aufgabe zu lösen müssen Sie Dezimalstellen zyklisch verschieben.