Im folgenden Beispiel ruft sich ein JavaScript rekursiv auf.
Dazu wurde folgendes "Problem" gewählt: Bevor sich die T9-Algoritmen auf Mobiltelefonen verbreitet hatten, war es bei manchen
Radiosendern ein beliebtes Spiel, dem Hörer eine Zahl zu geben. Der Hörer muß dann auf seiner Handytastatur
nachsehen und die Buchstaben, die den Ziffern zugeordnet sind, so wählen, dass ein
sinnvolles Wort entsteht. Die Tabelle rechts zeigt die übliche Belegung der Tastatur
mit Ziffern und Buchstaben.
Um das richtige Wort aus den Zahlen herauszufinden, muss man einfach alle Buchstabenkombinationen erstellen, die mit
den gegebenen Ziffern möglich sind und dann die sinnvollen Worte heraussuchen.
Das Skript hilft so auch, zu vorgegebenen PINs passende Wörter zu suchen, mit denen man sich die
PIN merken kann, indem man das Wort statt der PIN auf der Handy-Tastatur eintippt.
Mathematisch geht es darum, alle Permutationen (= möglichen Kombinationen) herauszufinden,
die sich aus den Buchstaben ergeben.
1
2 ABC
3 DEF
4 GHI
5 JKL
6 MNO
7 PQRS
8 TUV
9 WXYZ
*
0
#
Praktisch habe ich das so umgesetzt: Für die erste Ziffer der PIN, z.B. die 5, gibt es drei mögliche
Buchtstaben, nämlich J, K und L. Das Programm bestimmt diese drei Buchstaben, trennt aus der
PIN die 5 heraus und ruft sich selbst dreimal auf, um mit der verbliebenen PIN die neuen
Varianten zu berechnen.
Beim rekursiven Aufruf wird in jedem Schritt die PIN um eine Ziffer verkleinert und die
Buchstabenkombination gleichzeitig um ein Zeichen vergrößert. Sobald die PIN aufgebraucht ist,
bricht die Rekursion ab und die Buchstabenkombination wird ausgegeben.
Beliebige Zahl, führende Nullen werden berücksichtigt
Anmerkungen
Das Script arbeitet in exponentieller Zeit (durchschnittlich 3n, mit
n als Anzahl der Ziffern in der bearbeiteten PIN)
Das Array ZeichenListe enthält die Zuordnung der Buchstaben zu
den Ziffern auf dem Handy. Die Buchstaben, die zu Ziffer 0 gehören, werden durch den ersten
String in ZeichenListe festgelegt. Die Zuordnung kann beliebig geändert oder um weitere
Zeichen ergänzt werden.
Funktions-Demo
In das Eingabefeld eine Zahl eingeben und den Button klicken.
Code
// Liste der Zeichen, wie sie den Ziffern auf der Tastatur eines Telefons zugeordnet
// ist. Die 0 steht am Anfang (+), dann kommt die 1 (Leerzeichen), dann die 2 (abc) ...
// ein anderes Zeichenlayout (z.B. 1 = ABC, wie auf älteren Telefonen zu sehen) kann
// über diese Variable eingestellt werden
var ZeichenListe = new Array("+"," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz");
function Umwandeln(PIN)
{
// Prüft, ob eine Zahl eingegeben wurde
if (isNaN(PIN.value)) { return alert("Bitte geben sie nur Ziffern ein") }
var Zahl = PIN.value
// Anzahl der möglichen Kombinationen berechnen
var Kombinationen = 1
for(var Pos = 0;Pos < Zahl.length;)
{ Kombinationen *= ZeichenListe[Zahl.substring(Pos, ++Pos)].length }
// Neues Browserfenster für die Ausgabe öffnen
NeuesFenster = open("","","scrollbars,resizable,menubar,width=250");
Seite = NeuesFenster.document;
Seite.writeln("<HTML><HEAD></HEAD><BODY><H1>Variationen Ihrer PIN</H1>")
Seite.writeln(Kombinationen + " Kobinationsmöglichkeiten<P><FONT FACE=\"monospace\">")
// Aufruf der Berechnung
Zeichen(Zahl, "");
// Ausgabe in neues Browserfenster abschließen
Seite.writeln("</FONT></BODY></HTML>")
NeuesFenster.focus();
Seite.close();
}
function Zeichen(Zahl, Text)
{ // Falls tiefste Verschachtelungsebene erreicht, dann
// Buchstabenkombination in das neue Browserfenster ausgeben
if (Zahl.length == 0) { return Seite.writeln(Text + "<BR>"); }
// Erstes Zeichen der PIN holen
var Ziffer = Zahl.substring(0,1);
// Erstes Zeichen aus dem Rest der PIN entfernen
Zahl = Zahl.substring(1);
// Alle Buchstaben, die 'Ziffer' entsprechen nehmen, und einzeln
// in einen rekursiven Aufruf schicken.
for(var Pos = 0; Pos < ZeichenListe[Ziffer].length;)
{ Zeichen (Zahl, Text + ZeichenListe[Ziffer].substring(Pos, ++Pos)); }
} // -->