Evergreens der Informatik

Permutationen/Anagramme bilden

Beispiel: "abtis" ist ein Anagramm zu "basti". Wie findet man alle Anagramme? Nun, man kann ja jeden Buchstaben als ersten nehmen. Dann bildet man alle Permutationen der übriggebliebenen Buchstaben, und hängt den herausgewählten davor. Das macht man nun mit allen Buchstaben des Ausgangswortes, und schon hat man alle Anagramme. Der Algorithmus verwendet also Rekursion.

Die Frage nach dem Anagramm einer Zeichenkette ist zugleich die Frage nach den Permutationen einer Menge. Dabei werden im übrigen auch gleiche Buchstaben als unterscheidbare Elemente aufgefaßt. Das führt dazu, daß bei Wörtern mit doppelten Buchstaben (z. B. Anagramm) mehrere gleiche Wörter in der Liste der Ergebnisse auftauchen. Vor einigen Jahren fand ein Wettbewerb statt, in dem das längste deutsche Wort ohne einen wiederkehrenden Buchstaben gesucht wurde. Der Gewinner war "Heizölrückstoßabdämpfung". Zahl der Anagramme ist 24! = 6.204484 * 1023, also überlegen Sie es sich, bevor Sie Ihr Programm damit füttern...

Wie das ganze in Pascal aussieht, zeigt die Datei anagramm.pas.

Potenzmenge

Spätestens seit Viagra... nein, lassen wir das! Die Potenzmenge einer Menge ist die Menge aller möglichen Teilmengen. Beispielsweise ist die Potenzmenge von {a,b,c} = {{},{a},{b},{c},{a,b},{b,c},{a,c},{a,b,c}}. Um die Potenzmenge zu bestimmen, nimmt man sich das erste Element der Menge heraus. Man unterscheidet dann die Teilmengen ohne dieses und die mit ihm. Erstere sind die Potenzmenge der übrigen Elemente, letztere auch, nur das das herausgegriffene noch vor jede davorgestellt wird. Also:

Pot(abc) = Pot(bc) + Pot(bc) mit jeweils a davor.

Alles klar? Hatte ich auch nicht mit gerechnet... die Lösung ist zu finden in der Datei potenzmenge.pas.

Das 8-Damen-Problem

Kann man auf einem Schachbrett (8x8 Felder) 8 Damen so hinstellen, daß keine Dame eine andere bedroht, und wenn ja, wie?

Eins vorweg: Man kann. Die möglichen Stellungen bestimmt ein Programm durch systematisches Ausprobieren. Dabei geht man von folgender Überlegung aus: Wenn zwei Damen in einer Reihe stehen, bedrohen sie sich. Also darf in jeder Reihe maximal eine Dame stehen, und da es 8 Damen und 8 Reihen gibt... Man plaziert also in einer Reihe eine Dame so, daß sie die schon plazierten Damen nicht bedroht (z. B. in die erste noch freie Spalte), und versucht dann, die Dame in der nächsten Reihe zu plazieren, wo sich die gleiche Problematik ergibt, usw. Genau, ein rekursiver Algorithmus.

Das Programm beginnt also, in dem es die erste Dame plaziert und für jede Spalte die gleiche Routine - nur für die zweite Dame - aufruft. Dort geht es genauso weiter. Die Positionen der Damen werden in einem Array gespeichert. Bleibt nur noch zu klären, wie man feststellt, ob sich zwei Damen bedrohen? Das tun sie

  1. wenn sie in der gleichen Spalte stehen (x1 = x2)
  2. wenn sie in einer Diagonale stehen (|x1-x2| = |y1-y2|)

Damit haben wir alles zusammen, um das Programm zu schreiben. Der Quelltext ist hier: 8damen.pas

Ein Neger mit Gazelle...

Ein Palindrom ist ein Wort (oder ein Satz), das rückwärts gelesen genau gleich lautet, wie z. B. "ANNA" (ich habe eine überwältigende Phantasie, nicht?). Um zu erkennen, ob ein Wort ein Palindrom ist, geht man es buchstabenweise bis zur Mitte durch und schaut, ob auf der "gegenüberliegenden" Seite der gleiche Buchstabe seht. Wenn man einen Fehler findet, kann man natürlich vorzeitig aussteigen. Wie sieht es bei ungerader Buchstabenzahl aus? Nun, der mittlere Buchstabe ist auf jeden Fall korrekt, also teilen wir beim Errechnen der Mitte durch zwei und runden ab. Wie schön, daß div das ohnehin macht...

palindrom.pas

In Worten: ...

Manchmal liest man etwas wie z. B. "Hier wurde jetzt schon 13, in Worten dreizehn Mal eingebrochen...". Seltsamerweise kommt so etwas weniger häufig mit Zahlen wie 45307 vor, aber hier springt der Computer ein. Damit ist der Einsatzzweck erklärt.

Man führt das Problem auf zweistellige Zahlen (0 - 99) zurück. Die Hunderter sind dann auf Einer-Stellen zurückzuführen (einhundert - neunhundert), die Tausender auf Hunderter (Dreihunderttausend). Wie kommt man von einer Zahl auf ihre (beispielsweise) Hunderter-Stellen, und auf das, was dann noch kleiner ist? So: 

Hunderter := Zahl div 100;
Kleiner := Zahl mod 100;

Bei 345 ist jetzt Hunderter = 3 und Kleiner = 45. Das "kleinere" muß dann natürlich noch in Zehner und Einer zerlegt werden.

Quelle für maximal 6-stellige Zahlen: zahlen.pas

Die Türme von Hanoi

Ein echter Klassiker! Für den Fall, daß Sie das Spiel nicht kennen, hier eine kurze Beschreibung: Auf einer bestimmten Anzahl Stangen (meist sind es 3) können Scheiben (mit einem Loch in der Mitte) gestapelt werden; diese Scheiben haben alle unterschiedliche Größen. Am Anfang liegen alle Scheiben auf einer Stange, zuunterst die größte, dann die nächstkleinere usw. bis ganz oben, wo die kleinste liegt. Ziel des Spiels ist es, die Scheiben auf eine andere Stange zu transportieren, so daß sie am Ende wieder die gleiche Reihenfolge haben. Dabei müssen folgende Regeln eingehalten werden:

Wenn man z. B. 2 Scheiben auf Stab 1 hat, die man auf Stab 3 befördern will (wir gehen von 3 Stangen aus), geht man in folgenden Schritten vor:

  1. Bewege die oberste Scheibe von Stab 1 nach Stab 3
  2. Bewege die neue oberste Scheibe von Stab 1 nach Stab 2
  3. Bewege die Scheibe von Stab 2 nach Stab 3

Fertig. Ebenfalls noch recht leicht ist die Sache mit 3 Scheiben, von da an wird es komplizierter.

Die Türme von Hanoi gelten als das Beispiel für rekursive Programmierung. Tatsächlich macht der rekursive Ansatz das zunächst doch recht komplex wirkende Problem sehr einfach. Wir wollen als die n-te Scheibe auf einem Turm die n-te von oben betrachten. Wir werden nun eine Funktion schreiben, mit der wir die n-te Scheibe von Turm a nach Turm b bewegen können, inklusive der darüberliegenden n-1 Scheiben. Wenn uns das gelingt, besteht die ganze Aufgabe nur noch darin, diese Funktion für die unterste Scheibe und den Start- und Zielturm aufzurufen. Wie jedoch funktoniert diese Funktion? Die Bewegung der Scheibe selber wäre ja trivial, doch was machen wir mit den darüberliegenden? Nun, wir haben ja noch Turm c, bewegen wir sie doch vorübergehend darauf, und wenn wir die Scheibe n dann nach b gelegt haben, bewegen wir sie allesamt nach b weiter. Dazu benötigen wir eine Funktion, mit der wir einen ganzen Stapel bewegen können - und die haben wir gerade geschrieben :-)

Nun ist klar, worin hier die Rekursion besteht. Der Abschluß der Rekursion besteht natürlich in dem Fall, daß n = 1 ist, also keine weiteren Scheiben auf n liegen. Da wir, je tiefer wir in die Rekursion einsteigen, immer nur kleinere Scheiben bewegen, müssen wir auch keine Angst haben, daß eine größere Scheibe auf eine kleinere geraten könnte. Ein kleiner Trick noch, der bei 3 Türmen gerne verwendet wird, um den Ausweichturm zu berechnen: Die Summe der Turmnummern 1 + 2 + 3 = 6, daher ist bei gegebenen Türmen a und b dann c = 6 - a - b.

Das Beispielprogramm ist in der Datei hanoi.pas zu finden.