Algorithmen, Datenstrukturen und Programmieren I

WS 2001/2002

1. Welches Ergebnis liefern die folgenden Operationen? Geben Sie zunächst einen “educated guess” an und überprüfen Sie diesen dann mittels einer selbstgeschriebenen Java-Applikation.

  a) x = 7 + 3 * 6 / 2 - 1;
 b) x = 2 % 2 + 2 * 2 - 2 / 2;
  c) x = (3 * 9 * (3 + (9 * 3 / (3))));

2. Stellen Sie analog zu Beispiel 1.) fest, welchen Wert jeweils die Variablen a, b am Ende der angegebenen Anweisungsfolge hat, wenn beide zunächst mit dem Wert 1 initialisiert wurden.

  a) b = a++;
 b) b = a--;
  c) b = ++a + b--;
 d) a = b /= 3;
  e) a = (--a + 1) == b ? 4 : 3;
  f) b = a != b++ ? b++ : ++a;
  g) b = a++ == b ? b++ : b * a--;
 h) a /= ++b % (a + 2);

3* Nehmen Sie an, die boolean-Variablen r, s seien mit true bzw. false initialisiert. Welchen Wert haben die folgenden Ausdrücke? Testen Sie Ihre Meinung wieder mit einem Programm.

  a) r && s || (r || s)
 b) r = r || s ? r : s;
  c) r || (r && s) && (r || s)
 d) s = r ? r : (r || s);
  e) r = (!s && r) ? true : !r;
  f) s = true ? !s : !r;

Fertigen Sie vor dem Codieren der folgenden Beispiele jeweils einStruktogramm an!

4. Bekanntlich ist n! = n · (n − 1) · (n − 2) … 3 · 2 · 1.

a) Schreiben Sie eine Applikation, die eine ganze Zahl n von der Tastatur einliest und n! ausgibt.

b) Schreiben Sie ein Programm, das mit Hilfe der Formel

e = 1 + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + …

die Zahl e berechnet. Der Benutzer soll eingeben können, wie viele Terme der Summe berechnet werden sollen.

5. Schreiben Sie ein Programm, das (untereinander) die folgenden Muster ausgibt:

*           *********        *********               *
**          ********          ********              **
***         *******            *******             ***
****        ******              ******            ****
*****       *****                *****           *****
******      ****                  ****          ******
*******     ***                    ***         *******
********    **                      **        ********
*********   *                        *       *********

* darf dabei nur als System.out.print('*'); angegeben werden. Ansonsten sollten Sie zur Ausgabe nur System.out.print(' '); und

System.out.print(); verwenden.

Fertigen Sie vor dem Codieren der folgenden Beispiele jeweils ein Struktogramm an!

6. Benutzen Sie das Sieb des Eratosthenes, um alle Primzahlen ≤ 999 zu bestimmen und auszudrucken:

a) Legen Sie einen Array mit 1000 boolean Elementen an und initialisieren Sie alle Elemente mit true.

b) Beginnend mit Array-Index 2 soll das Programm für jedes Array-Element, das auf true steht eine Schleife durchlaufen, in der alle Elemente, deren Index ein Vielfaches dieses Index ist, auf false gesetzt werden.

Nachdem dieser Prozeß abgeschlossen ist, sind die Primzahlen ≤ 999 genau die Indizes der verbleibenden true-Elemente. Diese sollen dann formatiert ausgegeben werden.

7* Schreiben Sie eine Applikation, die eine Folge von 10 ganzen Zahlen von der Tastatur einliest und sie aufsteigend sortiert wieder ausgibt.

Fertigen Sie vor dem Codieren der folgenden Beispiele jeweils ein Struktogramm an!

8* Schreiben Sie eine Applikation Zahlenraten, bei der der Benutzer eine vom Computer intern ermittelte (Integer-) Zufallszahl zwischen 0 und 999 durch Eingaben über die Tastatur herausfinden soll. Zufallszahlen generiert man mit Hilfe der Methode Math.random(), die eine Zufallszahl vom Typ double im Wertebereich [0, 1) retourniert. Die Deklaration

z = (int) (1000*Math.random());

liefert also eine zufällige Integer-Zahl zwischen 0 und 999. Das Programm soll nach jedem Tipp des Users zu hoch!, zu niedrig! oder richtig! ausgeben. Ein- und Ausgabe des Programmes sollten über ein JOptionPane-Objekt, wie im Beispiel Eingabe Swing.java gezeigt, erfolgen.

9. Die Folge der Fibonacci Zahlen

0, 1, 1, 2, 3, 5, 8, 13, 21, …

beginnt mit den Zahlen 0 und 1 und hat nach Definition die Eigenschaft, dass jedes Folgenglied die Summe der beiden Vorgänger ist. Schreiben Sie ein Programm, das die ersten n Fibonacci-Zahlen in einer Tabelle ausgibt, wobei n vom Benutzer eingegeben werden soll.

10. Türme von Hanoi. Die Priester eines fernöstlichen Klosters stehen vor folgender Aufgabe: Auf einem Pflock sind Scheiben (mit einem Loch in der Mitte) der Größe nach aufgeschichtet (wobei die größten Scheiben unten liegen). Es stehen zwei weitere Pflöcke zur Verfügung. Das Ziel der Priester ist es, die Scheiben von Pflock 1 nach Pflock 3 zu transportieren (mit Pflock 2 als Zwischenlager), wobei sie sich allerdings an folgende Regeln zu halten haben:

• Es darf in jedem Arbeitsschritt nur eine Scheibe bewegt werden.

• Niemals darf eine größere auf eine kleinere Scheibe gelegt werden.

Schreiben Sie eine Applikation, die den Benutzer zur Eingabe der Scheibenzahl auffordert und eine Lösungsstrategie etwa in der Form

1 -> 3
1 -> 2
3 -> 2
...

ausgibt.

Hinweise: Am besten löst man dieses Problem rekursiv, mittels folgender Überlegung: Um n Scheiben von Pflock 1 nach Pflock 3 zu transportieren, kann man wie folgt vorgehen:

a) Bewege n − 1 Scheiben von Pflock 1 nach Pflock 2, wobei Pflock 3 als Zwischenlager dient.

b) Lege die letzte (größte Scheibe) von Pflock 1 nach Pflock 3.

c) Bewege die n−1 Scheiben von Pflock 2 nach Pflock 3, wobei Pflock 1 als Zwischenlager dient.

Somit kann man den Fall von n Scheiben auf den von n − 1 Scheiben reduzieren und der Fall n = 1 ist ohnehin trivial.

Schreiben Sie eine rekursive (also sich selbst aufrufende) Methode turm, die vier int Parameter übernimmt:

(a) Die Gesamtzahl der Scheiben.

(b) Die Zahl des Pflocks, auf dem die Scheiben zu Beginn liegen.

(c) Die Zahl des Pflocks, auf dem die Scheiben am Ende liegen sollen.

(d) Die Zahl des Pflocks, der als Zwischenlager dienen soll.

Mit Hilfe dieser Methode ist die Applikation dann leicht zu implementieren (man kann den Benutzer sogar Anfangs- und Endstapel aussuchen lassen, wenn man möchte). Schreiben Sie unbedingt zuerst ein Struktogramm!

11* a) Implementieren Sie eine Klasse Komplex, die die Durchführung der Grundrechnungsarten und die formatierte Ausgabe komplexer Zahlen ermöglicht.

b) Schreiben Sie eine Applikation, um die Funktionalität ihrer Klassendefinition zu überprüfen.

12* Schreiben Sie eine Applikation, die einen String einliest und mittels einer rekursiven Methode stringReverse (mit Rückgabewert void) in umgekehrter Reihenfolge wieder ausgibt. Der Methode stringReverse soll als Parameter ein Character-Array, der den String enthält, übergeben werden.

Hinweis: Sorgen Sie dafür, dass das letzte Zeichen des Character-Arrays ein ’\0’ ist und definieren Sie zwei Instanzvariablen i,j, die mit 0 initialisiert sind sowie eine Instanzvariable s (ein Character-Array derselben Länge wie der eingelesene String). stringReverse( char b[]) arbeitet dann wie folgt:

  • Falls b[i] == '\0': return;

• Sonst: Erhöhe i um 1 und rufe stringReverse(b) auf.

  • s[j++] = b[--i];

Fertigen Sie ein Struktogramm an und testen Sie zuerst von Hand, ob der Algorithmus funktioniert.

13. Definieren Sie eine von Angestellter abgeleitete Klasse Chef, die Datenfelder zur Speicherung der Vertragsdauer und der geleiteten Abteilungen enthält. Stellen Sie Methoden zur Änderung und Ausgabe dieser Daten zur Verfügung. Modifizieren Sie die Klasse PersonalVerwaltung so, daß für alle Angestellten (also auch für Chef) schon bei der Eingabe Monats- bzw. Stundenlohn und Stundenzahl festgelegt werden können. Nach Eingabe aller Angestellten soll außerdem eine gezielte Abfrage der Daten der einzelnen Angestellten möglich sein: Zuerst sollen die Namen und Nummern aller Angestellten ausgegeben werden. Danach sollen durch Eingabe der Angestellten-Nummer alle Daten des jeweiligen Angestellten abgerufen werden können, solange der User weitere Daten abrufen will. Verwenden Sie für die Entscheidung, welche Methoden zur Ausgabe der Daten verwendet werden sollen, den instanceof-Operator.

14. Schreiben Sie ein JApplet, das mittels dreier JTextFields drei Zahlen einliest. Nach Eingabe der dritten Zahl (und Drücken von Enter) sollen in nicht-editierbaren JTextFields Summe, Produkt, Mittelwert, Minimum und Maximum der Zahlen ausgegeben werden.

15. Wandeln Sie das Beispiel “Zahlen sortieren” in ein JApplet um. Die Beschreibung der Eingaben soll über JLabels erfolgen, das Einlesen der Zahlen über JTextFields und die Ausgabe in einer JTextArea.

16* Schreiben Sie eine Applet-Version des Programmes ‘Zahlenraten’ mit folgender Funktionalität: Zunächst soll in einer nicht editierbaren Text Area eine kurze Erklärung des Spieles gegeben werden. Die Eingaben des Users sollen in ein TextField erfolgen. Falls die Eingabe höher ist als die vom System vorbereitete Zufallszahl, soll die Farbe des Applets auf rot wechseln und in einem nicht-editierbaren TextField sollen die Worte ‘zu hoch’ erscheinen. Andernfalls soll die Farbe auf ‘blau’ gesetzt werden und ‘zu niedrig’ in das Textfeld geschrieben werden. Falls der User die Zahl errät, soll im Textfeld ‘Richtig!!’ erscheinen und das Eingabe-Textfeld soll uneditierbar gesetzt werden. Durch Drücken eines Buttons soll ein neues Spiel begonnen werden können.

17. Schreiben Sie ein Applet, das es dem User erlaubt, durch Mausbewegung Rechtecke zu zeichnen: Die linke obere Ecke des Rechteckes soll an der Stelle sein, an der die linke Maustaste gedrückt wird. Dann soll der User durch Ziehen (dragging) des Mauscursors und anschließendes Loslassen die rechte untere Ecke des Rechteckes bestimmen können. In der Statuszeile soll die Fläche des jeweiligen Rechteckes angezeigt werden. Benutzen Sie zum Zeichnen der Rechtecke die Graphics-Methode drawRect, deren Parameterliste Sie am besten der Online-Doku entnehmen sollten.

18. Schreiben Sie ein JApplet, in dem mit Hilfe des geeigneten Layout-Managers 100 JButtons in einem 10x10-Feld angeordnet sind. Beim Klicken auf einen JButton soll dieser sowie seine vier direkten Nachbarn (ohne die diagonalen Nachbarn) vom Applet entfernt werden.

19. Schreiben Sie ein Applet, in welchem ein Frame-Fenster geöffnet wird. Dieses soll mit einem Menu versehen werden. Mit Hilfe dieses Menüs soll der User auswählen können, ob (im Frame) ein Rechteck, eine Ellipse oder ein Kreis gezeichnet werden soll. Außerdem soll das Applet-Fenster eine CheckboxGroup beinhalten, mit welcher der User die Farbe des gezeichneten Objekts bestimmen kann.

20. Schreiben Sie ein Applet, in dem mit Hilfe des geeigneten Layout-Managers 100 Buttons in einem 10x10-Feld angeordnet sind. Beim Klicken auf einen Button soll dieser sowie seine vier direkten Nachbarn (ohne die diagonalen Nachbarn) vom Applet entfernt werden (d.h. Aufgabe 19 in AWT anstatt Swing).

21. a) Wandeln Sie eines der bisher geschriebenen Applets in ein Programm um, das sowohl als Applet als auch als Applikation laufen kann.

b) Wandeln Sie zwei Ihrer JApplets in Applikationen um, die als Unterklassen von JFrame implementiert sind.

22. Modifizieren Sie zwei Ihrer bisher geschriebenen Applikationen, die User-Eingaben erfordern so, daß diese mittels try und catch Exception-Handling verwenden. Definieren und verwenden Sie dazu eigene Unterklassen von Exception.

23. Schreiben Sie eine Applikation, die die gleichen Aufgaben wie das in der Vorlesung besprochene Beispiel WriteFile erfüllt. Die Ein- und Ausgabe soll jedoch über GUI-Komponenten erfolgen.