# Helft mir bitte beim Programm erstellen



## margitbrunner (28. Jan 2008)

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


----------



## Jango (28. Jan 2008)

So, wie es aussieht müsstest du erstmal lernen, wie man ordentlich in ein Forum postet!
Wir machen keine Hausaufgaben.


----------



## Quaxli (28. Jan 2008)

Es ist auch immer schlimm, daß die Prof's immer Hausaufgaben stellen, deren Themen nie vorher dran waren


----------



## Leroy42 (28. Jan 2008)

*Jango zustimm*


----------



## stev.glasow (28. Jan 2008)

jop
versuch's selbst zu lösen und stell dann konkrete fragen oder such dir nen anderes forum. *geschlossen*
[edit]
ich machs doch mal wieder auf, falls noch was eigenes kommt.


----------



## seid nicht so gemein (28. Jan 2008)

ich finde wenn der oder die arme so verzweifelt ist dann sollte man ihr auch helfen


----------



## stev.glasow (28. Jan 2008)

hm jo aber ne ^^ du hast vergessen deine ip-adresse zu wechseln, bevor du dich als jemand anders ausgibst.

kein bock haben, einen auf mitleid machen um die leute auszunutzen und uns dann noch verarschen wollen. reicht jetzt wah.

p.s. ich hab auch zu vielen dingen kein bock, aber entweder ich steh dann dazu, las es sein und leb mit den konsequenzen und geh nich irgendwelchen leuten aufn brenner oder ich überwinde mich.


----------

