M
margitbrunner
Gast
Hallo, ich bin totaler anfänger mit jave (1.semester) und wir müssen die folgende aufgabe programmieren. leider hab ich davon nicht viel ahnung. bitte bitte helft mir.
ihr könnt mir gerne auch eine mail schreiben: ###########
Aufgabe 1: Punktepaare in Einfach
In dieser Aufgabe sollen Sie ein Programm schreiben, das aus einer Menge von Punkten im R2 dasjenige Punktepaar mit dem kürzesten Abstand bestimmt. Es wird auf saubere (objekt-orientierte) Programmierung wertgelegt.
Ein weiteres Lernziel ist die Benutzung der Java-Bibliothek. Unter anderem werden Sie eine generische Klasse zum Sortieren von Objekten verwenden.
Der Algorithmus
Eine naive Lösung für dieses Problem ist das Vergleichen der Abstände sämtlicher Punktepaare - was einen Aufwand von O(n2) bedeutet (n = Anzahl der Knoten), weil man alle möglichen Paare vergleichen müsste.
Mittels eines sogenannten Divide-and-Conquer Algorithmus lässt sich das Problem allerdings in O(n log n) lösen.
Idee
Bei diesem Algorithmus wird das Feld mit den Punkten solange rekursiv in Teilfelder Fi zerteilt, bis jedes Teilfeld nur noch 2 oder 3 Punkte enthält.
Anschliessend kann für jedes Teilfeld Fi das lokale Punktepaar pFi mit dem kleinsten Abstand bestimmt werden. Aus ihnen wird das minimale Punktepaar pFmin bestimmt.
Allerdings sind nun Punktepaare von Punkten, die in verschiedenen Teilfeldern liegen, noch nicht berücksichtigt. Im obigen Beispiel ist das dichteste Punktepaar genau so ein Fall (rot eingezeichnet).
Um diese zu bearbeiten, bildet man für jede Trennlinie Tj zweier Teilfelder Fn und Fm die Menge P der Punkte aus Fn, die dichter oder gleich dicht an Tj liegen, als der Abstand vom kürzesten bisher berechneten Punktepaar pFmin beträgt und die analoge Menge Q der Punkte aus Fm, die dichter oder gleich dicht an Tj liegen.
Anschliessend berechnet man für jede Trennlinie Tj das Punktepaar pTj = (p, q), p E P, q E Q, mit dem kürzesten Abstand und bildet das Minimum pTmin.
Aus den Punktepaaren pFmin und pTmin kann man nun dasjenige mit dem kürzesten Abstand bestimmen.
Eine ausführlichere (und weniger formellastige) Beschreibung finden Sie hier (ab Seite 465).
Schema der Implementierung
Der Algorithmus kann etwas abgewandelt komplett in einer Rekursion implementiert werden:
1. Das Ausgangsfeld wird rekursiv in Teilfelder zerteilt, bis jedes Teilfeld nur noch 2 oder 3 Punkte enthält. Dazu wird in jedem Rekursionsschritt das aktuelle Teilfeld so in zwei neue Teilfelder aufgeteilt,
dass die neuen Teilfelder jeweils die Hälfte der Punkte des aktuellen Teilfelds enthalten.
2. Gelangt man bei der Teilung zu einem Teilfeld F, das nur noch 2 oder 3 Punkte enthält, führt man folgende Berechnungen durch:
a) das lokale Punktepaar pF mit dem kleinsten Abstand berechnen
b) pF zurückgeben
3. Bei der Rückkehr aus einem rekursiven Aufruf erhält jedes Teilfeld F , das mehr als 3 Punkte besitzt, von den beiden Teilfeldern
Fn und Fm, in die es sich aufgeteilt hat, deren Punktepaare pFn und pFm mit dem jeweils kürzesten Abstand.
a) das Punktepaar aus pFn und pFm mit dem kürzesten Abstand wird bestimmt - wir nennen es pTEMP.
b) die Punkte in F bestimmen, die näher oder gleich nah an der Trennlinie zwischen Fn und Fm liegen, als der Abstand von pTEMP beträgt-
die ermittelten Punkte links von der Trennlinie werden als Menge P bezeichnet, die rechts der Trennlinie als Menge Q.
c) nun berechnet man das Punktepaar pT = (p, q), p E P, q E Q, mit dem kürzesten Abstand, das die Trennlinie überschneidet.
d) dasjenige Punktepaar aus pTEMP und pT mit dem kleinsten Abstand wird zurückgegeben
Nach diesem Schema sollen Sie ihre Lösung programmieren.
Eingabe-Umgebung
Ihr Programm gibt die Eingabeaufforderung »points> « aus, liest ein Kommando ein und führt es aus. Beachten Sie das Leerzeichen hinter dem >!
Im initialen Zustand hat das Programm eine leere Ebene.
Die Punkte der Punktemenge, welche untersucht werden soll, werden einzeln im Format x y eingegeben, wobei x und y ganzzahlig sein müssen.
Durch die Eingabe einer leeren Zeile wird das Einlesen von Punkten beendet, die Berechnung ausgeführt und das Ergebnis ausgegeben.
Anschliessend geht das Programm in den initialen Zustand über. Die Ausgabe des Abstandes soll auf zwei Stellen hinter dem Komma abgerundet werden. Hierfür kann die Methode String. verwendet werden. Das geschieht durch den Aufruf String."0.00"
Durch die Eingabe des Kommandos help oder h wird ein Hilfetext mit Hinweisen zur Bedienung ausgegeben.
Durch die Eingabe des Kommandos quit oder q wird das Programm beendet
Bei fehlerhaften Eingaben wird eine sinnvolle Meldung der Form »Error! ...« ausgegeben. Das Programm soll hier nicht abbrechen, sondern die bisher eingelesenen Punkte bewahren und auf weitere Eingaben warten.
Mehrfach-Eingaben desselben Punkts sollen mit einer Meldung der Form »Error! ...« behandelt werden. Auch hier soll das Programm die bisher eingelesenen Punkte bewahren und auf weitere Eingaben warten.
Der Algorithmus funktioniert nur mit mindestens 2 angegebenen Punkten. Wurden weniger Punkte eingegeben, muss eine Fehlermeldung erfolgen und in den initialen Zustand übergegangen werden.
Beispiele
> java Shell
points> 56 77
points> 23 2
points> 2345 45
points> 3 88
points>
Distance: 54.13
Point Pairs: (3, 88) - (56, 77)
points> quit
> java Shell
points> 56 77
points> 23 2
points> 2345 45
points> 29
Error! Unbekanntes Kommando \'29\' .
points> 3 88
points>
Distance: 54.13
Point Pairs: (3, 88) - (56, 77)
points> quit
> java Shell
points> 12 43
points> 57 777
points> 2126 32
points> 4 6
points> 5 367
points> 47 87
points> 24576 221
points> 66 567
points> 842 45
points> 36 66
points> 7 200
points> 98 786
points> 423 45
points> 21 67
points> 2 3
points> 2 4
points> 7 8
points> 7 9
points> 887 667
points> 33 880
points> 845 5343
points> 95 5
points> 66 807
points> 97 642
points> 89 89
points> 53 76
points>
Distance: 1.0
Point Pairs: (2, 3) - (2, 4), (7, 8) - (7, 9)
points> quit
Hinweise zur Implementierung
Allgemeines
Ihr Programm soll sauber separiert werden, d.h. zB. dass nur in der Shell Eingaben eingelesen oder Ausgaben getätigt werden dürfen.
Schreiben Sie Ihr Programm lesbar und verständlich - beachten Sie dazu die bekanntgegebenen Richtlinien.
In dieser Aufgabe muss auch eine Datei Tests.txt abgegeben werden, welche Ihre eigenen Testfälle enthält. Bei einer fehlenden oder stark ungenügenden Testfallbeschreibung wird das Programm höchstens noch mit Funktionalität = 3 bewertet.
Wichtig: Fehlermeldungen müssen mit dem Wort Error! anfangen, sonst werden sie nicht erkannt!
Zu implementierende Klassen
Implementieren Sie eine Klasse Field, die eine Punktemenge verwaltet. Diese Klasse erhält eine Methode shortestDistance, welche den Algorithmus ausführt. Jedes Teilfeld und das Ausgangsfeld werden durch je ein Objekt dieser Klasse repräsentiert.
Die shortestDistance -Methode liefert ein Objekt der Klasse ShortestDistance zurück, die eine Distanz sowie dazugehörige Punktepaare enthält - mehrere Punktepaare können denselben kürzesten Abstand haben!
Die Reihenfolge der Ausgabe bei mehreren Ergebnissen ist egal.
Punkte sollen durch Objekte einer Klasse Point dargestellt werden.
Zudem benötigen Sie eine Klasse Shell, welche Benutzereingaben einliest, die entsprechenden Kommandos ausführt und das Ergebnis ausgibt.
Für das rekursive Aufteilen der Punktemenge empfiehlt es sich, dass die Punkte eines Felds sortiert sind. Da die Punkte in einer beliebigen Reihenfolge eingegeben werden können, müssen sie vor der Ausführung des Divide-and-Conquer Algorithmus sortiert werden (aus Performance-Gründen). Dazu sollen Sie ein Objekt der generischen Klasse java.util.ArrayList oder java.util.LinkedList verwenden. Das Sortieren erfolgt mittels eines der in der Vorlesung kennen gelernten Sortierverfahren Ihrer Wahl. Dabei sollen Sie Punkte nach ihrer x-Koordinate sortieren; Punkte die dieselbe x-Koordinate haben, nach der y-Koordinate.
Das Instantiieren erfolgt mittels der Anweisung
ArrayList<Point> list = new ArrayList<Point>();
Ein gute, allerdings sehr tief gehende Einführung zu Generics gibt es hier.
Zusammenfassung der geforderten Schnittstellen
Zusammenfassend noch einmal die zu implementierenden Klassen und Methoden auf einen Blick. Weitere benötigte Klassen, Methoden und Felder sind zu ergänzen:
class Shell {
public static void main(String[] args) {...}
...
}
class Field {
ArrayList<Point> points; // oder LinkedList
ShortestDistance shortestDistance(){...}
...
}
class ShortestDistance {...}
class Point {...}
[edit by stevg] e-mail adresse entfernt
ihr könnt mir gerne auch eine mail schreiben: ###########
Aufgabe 1: Punktepaare in Einfach
In dieser Aufgabe sollen Sie ein Programm schreiben, das aus einer Menge von Punkten im R2 dasjenige Punktepaar mit dem kürzesten Abstand bestimmt. Es wird auf saubere (objekt-orientierte) Programmierung wertgelegt.
Ein weiteres Lernziel ist die Benutzung der Java-Bibliothek. Unter anderem werden Sie eine generische Klasse zum Sortieren von Objekten verwenden.
Der Algorithmus
Eine naive Lösung für dieses Problem ist das Vergleichen der Abstände sämtlicher Punktepaare - was einen Aufwand von O(n2) bedeutet (n = Anzahl der Knoten), weil man alle möglichen Paare vergleichen müsste.
Mittels eines sogenannten Divide-and-Conquer Algorithmus lässt sich das Problem allerdings in O(n log n) lösen.
Idee
Bei diesem Algorithmus wird das Feld mit den Punkten solange rekursiv in Teilfelder Fi zerteilt, bis jedes Teilfeld nur noch 2 oder 3 Punkte enthält.
Anschliessend kann für jedes Teilfeld Fi das lokale Punktepaar pFi mit dem kleinsten Abstand bestimmt werden. Aus ihnen wird das minimale Punktepaar pFmin bestimmt.
Allerdings sind nun Punktepaare von Punkten, die in verschiedenen Teilfeldern liegen, noch nicht berücksichtigt. Im obigen Beispiel ist das dichteste Punktepaar genau so ein Fall (rot eingezeichnet).
Um diese zu bearbeiten, bildet man für jede Trennlinie Tj zweier Teilfelder Fn und Fm die Menge P der Punkte aus Fn, die dichter oder gleich dicht an Tj liegen, als der Abstand vom kürzesten bisher berechneten Punktepaar pFmin beträgt und die analoge Menge Q der Punkte aus Fm, die dichter oder gleich dicht an Tj liegen.
Anschliessend berechnet man für jede Trennlinie Tj das Punktepaar pTj = (p, q), p E P, q E Q, mit dem kürzesten Abstand und bildet das Minimum pTmin.
Aus den Punktepaaren pFmin und pTmin kann man nun dasjenige mit dem kürzesten Abstand bestimmen.
Eine ausführlichere (und weniger formellastige) Beschreibung finden Sie hier (ab Seite 465).
Schema der Implementierung
Der Algorithmus kann etwas abgewandelt komplett in einer Rekursion implementiert werden:
1. Das Ausgangsfeld wird rekursiv in Teilfelder zerteilt, bis jedes Teilfeld nur noch 2 oder 3 Punkte enthält. Dazu wird in jedem Rekursionsschritt das aktuelle Teilfeld so in zwei neue Teilfelder aufgeteilt,
dass die neuen Teilfelder jeweils die Hälfte der Punkte des aktuellen Teilfelds enthalten.
2. Gelangt man bei der Teilung zu einem Teilfeld F, das nur noch 2 oder 3 Punkte enthält, führt man folgende Berechnungen durch:
a) das lokale Punktepaar pF mit dem kleinsten Abstand berechnen
b) pF zurückgeben
3. Bei der Rückkehr aus einem rekursiven Aufruf erhält jedes Teilfeld F , das mehr als 3 Punkte besitzt, von den beiden Teilfeldern
Fn und Fm, in die es sich aufgeteilt hat, deren Punktepaare pFn und pFm mit dem jeweils kürzesten Abstand.
a) das Punktepaar aus pFn und pFm mit dem kürzesten Abstand wird bestimmt - wir nennen es pTEMP.
b) die Punkte in F bestimmen, die näher oder gleich nah an der Trennlinie zwischen Fn und Fm liegen, als der Abstand von pTEMP beträgt-
die ermittelten Punkte links von der Trennlinie werden als Menge P bezeichnet, die rechts der Trennlinie als Menge Q.
c) nun berechnet man das Punktepaar pT = (p, q), p E P, q E Q, mit dem kürzesten Abstand, das die Trennlinie überschneidet.
d) dasjenige Punktepaar aus pTEMP und pT mit dem kleinsten Abstand wird zurückgegeben
Nach diesem Schema sollen Sie ihre Lösung programmieren.
Eingabe-Umgebung
Ihr Programm gibt die Eingabeaufforderung »points> « aus, liest ein Kommando ein und führt es aus. Beachten Sie das Leerzeichen hinter dem >!
Im initialen Zustand hat das Programm eine leere Ebene.
Die Punkte der Punktemenge, welche untersucht werden soll, werden einzeln im Format x y eingegeben, wobei x und y ganzzahlig sein müssen.
Durch die Eingabe einer leeren Zeile wird das Einlesen von Punkten beendet, die Berechnung ausgeführt und das Ergebnis ausgegeben.
Anschliessend geht das Programm in den initialen Zustand über. Die Ausgabe des Abstandes soll auf zwei Stellen hinter dem Komma abgerundet werden. Hierfür kann die Methode String. verwendet werden. Das geschieht durch den Aufruf String."0.00"
Durch die Eingabe des Kommandos help oder h wird ein Hilfetext mit Hinweisen zur Bedienung ausgegeben.
Durch die Eingabe des Kommandos quit oder q wird das Programm beendet
Bei fehlerhaften Eingaben wird eine sinnvolle Meldung der Form »Error! ...« ausgegeben. Das Programm soll hier nicht abbrechen, sondern die bisher eingelesenen Punkte bewahren und auf weitere Eingaben warten.
Mehrfach-Eingaben desselben Punkts sollen mit einer Meldung der Form »Error! ...« behandelt werden. Auch hier soll das Programm die bisher eingelesenen Punkte bewahren und auf weitere Eingaben warten.
Der Algorithmus funktioniert nur mit mindestens 2 angegebenen Punkten. Wurden weniger Punkte eingegeben, muss eine Fehlermeldung erfolgen und in den initialen Zustand übergegangen werden.
Beispiele
> java Shell
points> 56 77
points> 23 2
points> 2345 45
points> 3 88
points>
Distance: 54.13
Point Pairs: (3, 88) - (56, 77)
points> quit
> java Shell
points> 56 77
points> 23 2
points> 2345 45
points> 29
Error! Unbekanntes Kommando \'29\' .
points> 3 88
points>
Distance: 54.13
Point Pairs: (3, 88) - (56, 77)
points> quit
> java Shell
points> 12 43
points> 57 777
points> 2126 32
points> 4 6
points> 5 367
points> 47 87
points> 24576 221
points> 66 567
points> 842 45
points> 36 66
points> 7 200
points> 98 786
points> 423 45
points> 21 67
points> 2 3
points> 2 4
points> 7 8
points> 7 9
points> 887 667
points> 33 880
points> 845 5343
points> 95 5
points> 66 807
points> 97 642
points> 89 89
points> 53 76
points>
Distance: 1.0
Point Pairs: (2, 3) - (2, 4), (7, 8) - (7, 9)
points> quit
Hinweise zur Implementierung
Allgemeines
Ihr Programm soll sauber separiert werden, d.h. zB. dass nur in der Shell Eingaben eingelesen oder Ausgaben getätigt werden dürfen.
Schreiben Sie Ihr Programm lesbar und verständlich - beachten Sie dazu die bekanntgegebenen Richtlinien.
In dieser Aufgabe muss auch eine Datei Tests.txt abgegeben werden, welche Ihre eigenen Testfälle enthält. Bei einer fehlenden oder stark ungenügenden Testfallbeschreibung wird das Programm höchstens noch mit Funktionalität = 3 bewertet.
Wichtig: Fehlermeldungen müssen mit dem Wort Error! anfangen, sonst werden sie nicht erkannt!
Zu implementierende Klassen
Implementieren Sie eine Klasse Field, die eine Punktemenge verwaltet. Diese Klasse erhält eine Methode shortestDistance, welche den Algorithmus ausführt. Jedes Teilfeld und das Ausgangsfeld werden durch je ein Objekt dieser Klasse repräsentiert.
Die shortestDistance -Methode liefert ein Objekt der Klasse ShortestDistance zurück, die eine Distanz sowie dazugehörige Punktepaare enthält - mehrere Punktepaare können denselben kürzesten Abstand haben!
Die Reihenfolge der Ausgabe bei mehreren Ergebnissen ist egal.
Punkte sollen durch Objekte einer Klasse Point dargestellt werden.
Zudem benötigen Sie eine Klasse Shell, welche Benutzereingaben einliest, die entsprechenden Kommandos ausführt und das Ergebnis ausgibt.
Für das rekursive Aufteilen der Punktemenge empfiehlt es sich, dass die Punkte eines Felds sortiert sind. Da die Punkte in einer beliebigen Reihenfolge eingegeben werden können, müssen sie vor der Ausführung des Divide-and-Conquer Algorithmus sortiert werden (aus Performance-Gründen). Dazu sollen Sie ein Objekt der generischen Klasse java.util.ArrayList oder java.util.LinkedList verwenden. Das Sortieren erfolgt mittels eines der in der Vorlesung kennen gelernten Sortierverfahren Ihrer Wahl. Dabei sollen Sie Punkte nach ihrer x-Koordinate sortieren; Punkte die dieselbe x-Koordinate haben, nach der y-Koordinate.
Das Instantiieren erfolgt mittels der Anweisung
ArrayList<Point> list = new ArrayList<Point>();
Ein gute, allerdings sehr tief gehende Einführung zu Generics gibt es hier.
Zusammenfassung der geforderten Schnittstellen
Zusammenfassend noch einmal die zu implementierenden Klassen und Methoden auf einen Blick. Weitere benötigte Klassen, Methoden und Felder sind zu ergänzen:
class Shell {
public static void main(String[] args) {...}
...
}
class Field {
ArrayList<Point> points; // oder LinkedList
ShortestDistance shortestDistance(){...}
...
}
class ShortestDistance {...}
class Point {...}
[edit by stevg] e-mail adresse entfernt
