Programmieren mit Harald R. Haberstroh

Implementieren Sie in einem Paket recursion Klassen mit Testmethoden für folgende Aufgabenstellungen:

1. Fakultät: 0! = 1, 1! = 1, n! = n * (n -1)
2. Fibonaccizahlen: fib(0) = 0, fib(1) = 1, fib(n) = fib(n - 1) + fib(n - 2)
3. McCarthys 91: f(n) = n-10, wenn n > 100 bzw. f(f(n+11)) für allen anderen n.
4. Bestimmen Sie ob eine Zahl gerade oder ungerade ist, in dem Sie zwei indierekt rekursive Funkionen boolean istUngerade(int n) und boolean istGerade(int n) verwenden.
5. Implementieren Sie den Euklidischen Algorithmus zum Finden des größten gemeinsamen Teilers zweier Zahlen.

Floodfill

Aus Wikipedia: Floodfill bzw. Flutfüllung ist ein Begriff aus der Computergrafik. Es ist ein einfacher Algorithmus, um Flächen zusammenhängender Pixel einer Farbe in einem digitalen Bild zu erfassen und mit einer neuen Farbe zu füllen.

Ausgehend von einem Pixel innerhalb der Fläche werden jeweils dessen Nachbarpixel darauf getestet, ob diese Nachbarpixel auch die alte Farbe enthalten. Jedes gefundene Pixel mit der alten Farbe wird dabei sofort durch die neue Farbe ersetzt.
Zwei Varianten des Algorithmus sind gängig:

1. Es werden jeweils die vier benachbarten Pixel oben, unten, links und rechts vom Ausgangspunkt untersucht.
   
2. Es werden jeweils die acht benachbarten Pixel oben, unten, links, rechts, oben-links, oben-rechts, unten-links und unten-rechts vom Ausgangspunkt untersucht.
   

Legen Sie ein neues Package floodfill an und Erstellen Sie die beiden Klassen Grafik und Logik mit dem unten angegebenen Source-Code (Dank an W. Schermann).

• floodfill.Grafik.java (enthält die Grafik-Funktionen und main())
• floodfill.Logik.java (enthält die Logik, sie müssen die Methode run() erweitern)

Speichern Sie die folgenden beiden Bilder in einem Ordner images im Ordner des Projektes.

Implementieren Sie in der Logik eine rekursive Funktion zum Füllen eines Bildabschnittes (In 4 Richtungen und alternativ in 8 Richtungen). Rufen Sie die rekursive Funktion aus der Funktion run aus auf. Sie können folgende Funktionen der Grafik-Klasse verwenden.

public Color getColor(int x, int y) //Bildfarbe abfragen
public void setColor(int x, int y, Color c) //Bildfarbe ändern

Der Algorithmus ist hoch-rekursiv. Daher besteht ein hohes Risiko, dass der Algorithmus zu einem Stack-Überlauf führt. (Z.B. beim Hintergrund)

Um die Übung ohne trotzdem komplett testen zu können kann die Stack-Größe in Java verändert werden. In Eclipse kann dies bei den Argumenten der Virtual-Machine in den Run-Konfigurationen eingestellt werden. Mit -Xss5M wird der Stack-Speicher auf 5 Megabyte gesetzt.

Beachten Sie die eventuellen "Fehler" beim Füllen mit dem Algorithmus für 8 benachbarte Pixel.

Labels: Aufgabe, Java, POS1-2

# Eingestellt von Harald R. Haberstroh @ 09:43 0 Kommentare

Implementieren Sie in Java eine Simulation des Philosophenproblems (Aufgabenstellung über den Link).

Zeigen Sie das Auftreten eines Deadlocks.

Entwickeln Sie eine Lösung ohne Deadlock.

Labels: algorithmen, Aufgabe, Informatik, Java, POS1-3

# Eingestellt von Harald R. Haberstroh @ 09:01 0 Kommentare

Ergänzen Sie IntList um eine Methode int search(int value), welche den Index der Zahl value liefert, wenn sie im Array vorhanden ist und -1, wenn die Zahl nicht vorhanden ist.

Implementieren Sie die Methode so, dass sie im unsortierten Fall einfach sequentiell sucht und im sortierten Fall eine binäre Suche durchführt. Sie benötigen also eine Methode, die prüft, ob das Array in IntList sortiert ist.

Schreiben Sie eine zusätzliche Methode int[] getDuplicates(), welche ein Array mit allen Duplikaten liefert, also alle Zahlen, die mehr als einmal vorhanden sind.

void removeDuplicates() soll alle Duplikate entfernen, sodass jede Zahl nur einmal vorkommt.

Die beiden letzten Methoden können in Abhängigkeit der Sortierung (ja oder nein) unterschiedlich implementiert werden.

# Eingestellt von Harald R. Haberstroh @ 09:01 0 Kommentare