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.

Texte verschlüsseln

Eine sehr einfache Verschlüsselungsmethode ist die polyalphabetische Verschlüsselung: jedem Buchstaben des Alphabets wird genau ein anderer Buchstabe des Alphabets zugeordnet. Die Zuordnung muss bijektiv sein.

Man betrachte z.B. die Verschlüsselung, bei der jeder Buchstabe des lateinischen Alphabets (ohne Umlaute oder ß) durch den vorherigen Buchstaben ersetzt wird:
b -> a, c -> b, …, z -> y, a -> z

Aus IBM wird dann HAL.

Implementieren Sie ein Programm, das eine Zeichenkette polyalphabetisch verschlüsselt. Die Zuordnung soll als char-Feld gegeben sein. Groß- und Kleinschreibung soll ignoriert werden.

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.

Durchschnitt einer Zahlenfolge berechnen

Gegeben sei ein Feld mit double Werten.

Schreiben Sie ein Java-Programm, das den Durchschnitt der Werte in dem Feld berechnet.