Prof. Dr. Franz Schweiggert Abteilung Angewandte Informationsverarbeitung 11.01.2006
Norbert Heidenbluth Blatt 11






Allgemeine Informatik I für Mathematiker/Wirtschaftsmathematiker
(WS 2005/2006)


Abgabetermin: 18. Januar 2006

Im Mittelpunkt dieses Übungsblattes stehen diesmal Arrays. Aufgabe 23 gibt Ihnen ein Programm vor, das Arrays gebraucht, aber noch einige ``Problemzonen'' enthält, die es auszubessern gilt. In Aufgabe 24 beschäftigen wir uns mit einem berühmten Problem aus der mathematischen Literatur, das hier unter Verwendung von Arrays simuliert bzw. gelöst werden soll.

Aufgabe 23: Vor und zurück (4 Punkte)

• ``Anna hetzte Hanna.''
• ``Leg in eine so helle Hose nie'n Igel!''
• ``Trug Tim eine so helle Hose nie mit Gurt?''
• ``Eine güldne, gute Tugend: Lüge nie!''
• ``Die Liebe ist Sieger stets, rege ist sie bei Leid.''
• ``Eine treue Familie bei Lima feuerte nie.''

Wenn Sie jetzt grübeln, ob die Weihnachtsgans eventuell beim falschen Importeur gekauft wurde oder ob es an Sylvester nicht vielleicht doch ein paar harte Drinks zu viel waren, dann haben Sie wohl noch nie etwas über Palindrome gehört? Palindrome sind Wörter oder gar ganze Sätze, die vorwärts und rückwärts gelesen jeweils gleich sind.

Und damit sind wir schon mitten in dieser Aufgabe:

Auf unserem FTP-Server finden Sie das Java-Programm Palindrome1.java, das - so behauptet jedenfalls der Programmierer, der hier nicht näher genannt werden will - einen Text einliest und überprüft, ob es sich dabei um ein Palindrom handelt.

Für einfache Worte, die entweder nur aus Klein- oder Großbuchstaben bestehen (wie z.B. ``OTTO'' oder ``reliefpfeiler'') funktioniert auch alles prima. Aber als mittlerweile geübter Programmiererin fällt Ihnen natürlich sofort auf, daß dieses Programm in einem recht erbärmlichen Zustand ist. Ihre Aufgabe lautet daher:

``Verbessern Sie das gegebene Programm sukzessive, bis es die nachstehenden Kriterien erfüllt und die die eingangs zitierten Sätze als Palindrome erkennt.''

Schauen wir uns an, welche Verbesserungen hierzu notwendig sind:

• Arrays müssen stets eine feste Länge haben, welche in diesem Fall mit 100 festgelegt ist. Was passiert aber, wenn Wörter eingegeben werden, deren Länge größer ist? Probieren Sie es mal aus und treffen Sie eine Vorkehrung, damit dieser Fall kontrolliert behandelt wird.

• Die Eingabe des Textes muß mit der Eingabe von entweder zwei aufeinander folgenden CTRL-D oder der Eingabe eines newlines gefolgt von CTRL-D abgeschlossen werden. Das ist äußerst unschön! Ändern Sie das Programm dahingehend ab, daß bereits ein newline die Eingabe beendet.

• Die Groß- und Kleinschreibung sollte bei der Erkennung von Palindromen keine Rolle spielen (z.B. sollte ``Otto'' als Palindrom erkannt werden). Modifizieren Sie das Programm entsprechend!

• Weiterhin sollten jegliche Satz- bzw. Sonderzeichen (Apostroph und Co.) für die Palindrom-Auswertung keine Rolle spielen. Erweitern Sie daher Ihr Programm ein letztes Mal entsprechend!

Tips und Hinweise:

• Die letzten drei Punkte lassen sich am besten gemeinsam direkt nach der Eingabe behandeln. Denken Sie hier über die Verwendung von break und continue nach. Näheres dazu wird in den Übungen vorgestellt.
• Diese Aufgabe soll unter Verwendung eines Char-Arrays mit denjenigen Mitteln gelöst werden, die wir bislang in der Vorlesung oder den Übungen kennengelernt haben. Die Verwendung der Klasse String ist ausdrücklich nicht zulässig!

Aufgabe 24: Ein Date mit dem Praktikanten (6 Punkte)

In dieser Aufgabe kehren wir nochmals zurück in die Firma aus Aufgabe 22. Wir erinnern uns: dort gab es eine hübsche Praktikantin, und wie in der Antwort zu Feedback Nr. 84 versprochen, ist nun auch der gutaussehende Praktikant zurück aus dem Urlaub (Er war zum Surfen auf Hawaii!).

Sie sind nun also weiblich, arbeiten in der Firma und möchten sich mit dem Praktikanten für heute abend verabreden (lechz!). Dummerweise möchten das viele andere (die Anzahl derer sei $n$) in der Firma auch, aber nur eine kann die Auserwählte sein. Deshalb hat sich der Praktikant (der nicht nur gut aussieht sondern auch noch intelligent ist (hechel!)) ein Vorgehen überlegt, um die Kollegin zu finden, mit der er den Abend verbringen werden wird:

Alle $n$ ``Bewerberinnen'' müssen sich im Kreis anordnen, wobei ihre Ausgangspositionen von 1 an durchnummeriert werden. Beginnend mit Position 1 zählt der Praktikant nun immer $m$ Positionen weiter, und wer an dieser Stelle steht, muß den Kreis verlassen (und den Abend wahlweise alleine oder mit dem Informatik-Tutor aus Feedback Nr. 85 verbringen). Der Kreis wird an der Stelle geschlossen, es wird wieder $m$ Positionen weitergezählt, die dortige verlässt den Kreis und so weiter. Das geht solange, bis nur noch eine übrig ist, und das ist dann die Glückliche, die sich heute abend an dem drahtigen, braungebrannten Körper erfreuen darf (schmacht!).

Tja, und jetzt haben Sie natürlich das Problem, auf welche Position Sie sich zu Beginn des Spiels stellen müssen, damit Sie die Glückliche sind. Aber wie immer wenn's brennt kommt Ihnen die Informatik-Übung wie gerufen, denn die Aufgabe lautet nun:

``Schreiben Sie ein Java-Programm, daß Ihnen die Reihenfolge des Ausscheidens aus dem Kreis (und damit auch die Position ``der Glücklichen'', die bis zum Schluß übrig bleibt) nach obigem Algorithmus ermittelt (für einen Kreis mit $n$ Personen und Schrittweite $m$).''

Beispiel:

Nehmen wir an, es gäbe 14 Mädels (also $n=14$), die gerne mit dem Praktikanten ausgehen würden. Bei Schrittweite 4 (also $m=4$) ergibt sich dann die folgende Ausgabe:

theseus$ java PraktikantenDate
Praktikanten-Algorithmus fuer 14 Maedels und Schrittweite 4:

Als 1-tes geht die Dame von Position 4.
Als 2-tes geht die Dame von Position 8.
Als 3-tes geht die Dame von Position 12.
Als 4-tes geht die Dame von Position 2.
Als 5-tes geht die Dame von Position 7.
Als 6-tes geht die Dame von Position 13.
Als 7-tes geht die Dame von Position 5.
Als 8-tes geht die Dame von Position 11.
Als 9-tes geht die Dame von Position 6.
Als 10-tes geht die Dame von Position 1.
Als 11-tes geht die Dame von Position 14.
Als 12-tes geht die Dame von Position 3.
Als 13-tes geht die Dame von Position 10.
Die Glueckliche ist die Dame auf Position 9 :-)

Tips und Hinweise

• Für diese Aufgabe ist es wichtig, daß sie mit Hilfe eines Arrays gelöst wird, auch wenn es Möglichkeiten gibt, auf dieses zu verzichten.
• Achten Sie darauf, die Werte für $n$ und $m$ als Konstanten zu deklarieren. Schreiben Sie diese nicht ``hart verdrahtet'' in Ihr Programm! (Warum nicht?)

Viel Erfolg!