Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Aufgabe 4.5
Hallo,
wir hätten da eine Frage zu Teilaufgabe a).
Wir sollen ja die eukllidische Distanz zwischen p und einem weiteren Punkt herausfinden.
Zu Beginn wird angenommen, dass p und pd die kleinste Distanz haben.
Ist also ps leer habe ich schon einmal meinen Basisfall, dass wenn ps leer ist, so gebe ich pd aus.
Wenn allerdings ps (zweidimensionales Array) gefüllt ist, so muss ich doch eigentlich : ps - p (Startpunkt) machen.
Nur wie rechnet man bitte mit Arrays ?
Die kann man doch nicht einfach von einander abziehen.
Vorallem sind sie auch noch verschieden in ihren Dimensionen.
Hilfe wäre sehr nett, wir kommen einfach nicht weiter.
Schau dir den Anfang der main()-Funktion an. Jede Zeile in deinem zweidimensionalen Array ist ein eigener Punkt.
Die Distanz musst du für jeden Punkt einzeln berechnen. Dadurch haben deine Arrays dann auch die gleiche Dimension. Und richtig, du kannst nicht einfach zwei Arrays subtrahieren. Schau dir dazu mal die Funktion distance() an.
Also ich sehe da kein Problem => man muss garnichts abziehen! (Erklärts mir wenns falsch ist, ich bin auch erstie)
Selbst wenn man den Punkt aus pd (Enthält ja auch die Distanz) auch in ps hat, macht das keinen Unterschied, da
explizit auch pd als Ergebnis rauskommen kann, wenn es keinen Punkt mit kürzerer Distanz in ps gibt, oder je nachdem wie man das regelt, nur einen/mehrere Punkt/e mit der gleichen Distanz wie pd.
(Explizit: “In allen anderen Fällen liefert die Methode einen Punkt aus ps und pd zusammen mit dessen Distanz zurück…”)
Okay vielen Dank, die distance Methode würde mir das zwar alles ausrechnen, aber man kann ja kein zweidimensionales Array da reinpacken, zumindest spuckt er bei uns nur Fehler aus…
Rein logisch betrachtet müsste ich da doch dann distance mit den Arrays ps und p berechnen oder nicht ?
Und halt noch die Stelle angeben an für ps, welche Zahl aus dem Array er mit p berechnen soll.
Außerdem verwirrt mich der Satz in der Aufgabenstellung etwas :
“In allen anderen Fällen liefert die Methode einen
Punkt aus ps und pd zusammen mit dessen Distanz zurück, der die minimale euklidische
Distanz zu p hat.”
Was genau ist damit gemeint ?
Ich verstehe das so:
pd ist ein Punkt, z.b. A
ps enthält eine Liste von Punkten: B, C, D
Du sollst jetzt denjenigen Punkt aus der Menge {A, B, C, D} („aus ps und pd zusammen“) finden, der möglichst nahe bei p liegt.
Das stimmt so nicht. Du musst die Punkte in ps mit dem gegebenen Punkt p verrechnen.
Die Distanz zwischen einem Punkt lässt sich mit der bereits implementierten Methode distance(double[] p1, double[] p2) berechnen.
Ein Beispiel:
double[] punktEins = {1,1};
double[] punktZwei = {5,4};
double abstand = distance(punktEins, punktZwei); //abstand hat also den Wert 5Damit du den Abstand in den Punkt speichern kannst, benutzt die Methode
appendDistance(double[] array, double d)Allerdings solltest du hier darauf achten, dass die Methode einen Rückgabewert hat. Und der Rückgabewert ist ein neues Array, in dem eben die Distanz hinzugefügt wurde.
Ein Beispiel:
double[] punktEins = {1,1};
double[] punktZwei = {5,4};
double abstand = distance(punktEins, punktZwei); //abstand hat also den Wert 5
punktEins = appendDistance(punktEins, abstand); //punktEins hat nun die Form: {1,1,5} Ja, da hast du recht. Der Punkt p und das Array mit den Punkten ps haben unterschiedliche Dimensionen. Es ist so, dass in dem zwei-dim-Array ps ein-dim-Array gespeichert ist. Quasi ein Array aus Arrays. Und diese ein-dim-Arrays in ps repräsentieren deine Punkte. Wenn du zum Beispiel das erste Array eines zwei-dim-Arrays haben möchtest, dann sieht das so aus:
double[][] einZweiDimArray = {{1,2,3},{4,5,6,7}};
double[] einEinDimArray = einZweiDimArray[0]; //das ist also die erste Zeile, also {1,2,3}Ich hoffe, dass hilft euch weiter.
Vielen vielen Dank.
Das hat uns wunderbar weitergebracht 
Konnte jetzt schon einmal die a) lösen.
Morgen geht es dann an die Teilaufgabe b) und c).
Challo und jutn Abend,
dazu hätt ich auch noch ne Frage. Ich hab a) zwar, aber nicht rekursiv und ich wüsste net wie.
Bei mir hab ich des iterativ, weil ich net weiß, wie genau man die Parameter handhaben muss, damit man auf den Basisfall ps.length == 0 kommt.
Dange scho mal;
Es gibt die Methode skipFirstPoint(); sie braucht einen double etc… somit kann man der Reihe nach eine Stelle überspringen bis man an ps.length-1 angelangt ist.
zwei weitere Fragen aus dem Thread Aufgabe 4.5 c) - #3 von bor1 - Algorithmen und Datenstrukturen - FSI Informatik Forum :
#1 von na02zijy
#2 von mir
Frage vom gleichen Kaliber:
Wenn ein Array ps mehrere Punkte doppelt hat. D.h. z.B. ps ={{p_1,p_2},{p_1,p_2},{p_3,p_2},{p_3,p_2},{p_4,p_2},{p_4,p_2}}.
Welchen soll er zurückgeben? Alle haben den gleichen minimalen Abstand. Ich gebe den erst gefunden aus. Wie ist es richtig?
Antwort im oben erwähnten Forum von DerBaer
Danke im Vorraus
Wie bereits erwähnt, gibt es dafür die Methode
skipFirstPoint(double[][] ps)Eine beispielhafte Anwendung dafür:
double[][] zweiDimArray = { {1,2,3} , {4,5,6,7} , {8,9} };
double[][] verkuerztesArray = skipFirstPoint(zweiDimArray); //der Inhalt von diesem Array lautet: { {4,5,6,7} , {8,9} }Genau so greifst du dir einen Punkt aus ps und verkürzt dann ps um eine Stelle.
Die Frage von na02zijy kann ich nicht beantworten, da ich die Testcases nicht kenne. Ich denke mal aber, dass es keine Rolle spielen dürfte. Wäre gut, wenn das ein Übungsleiter/-tutor bestätigt.
Zitat aus der Aufgabenstellung:
Verdammt…
Somit ist Teilaufgabe a) also doch nicht gelöst 
Hab das gleiche Problem wie Zyrotilk.
Ich versteh nicht ganz, wie ich hier die Rekursion einbauen sollte.
Ohne Rekursion hatte ich es ja schon, allerdings mit einer haut es mir alles durcheinander, dass gar nichts mehr ausgegeben wird.
Ich bin am verzweifeln…
Die ganze Arbeit gestern war mal wieder umsonst 
Ich hätte zur 4.5 b) ne Frage und zwar heißt es ja, dass closestPoint nicht rekursiv ist…heißt dass ich nur in closestPoint nicht closestPoint verwenden darf oder?
Jup
Die Rekursion ersetzt letztendlich die Schleife der iterativen Variante.
Wenn du dir die Signatur der rekursiven Methode mal ansiehst:
closestPointHelper(double[] p, double[] pd, double[][] ps)Der Punkt p ist der Punkt, für den der näheste Punkt gesucht werden soll. Du hast einen festen Punkt und siehst die von diesem Punkt aus die Entfernungen zu allen anderen Punkten an und wählst die kleinste. In jedem rekursiven Aufruf wird also einer der anderen Punkte mit diesem verglichen.
pd enthält laut Angabe den aktuellen nähesten Punkt zu p. Beim rekursiven Aufruf musst du also darauf achten, dass du closestPointHelper auch wirklich mit dem (eventuell neuem) nähesten Punkt aufrufst.
Bleibt noch ps und die Regel, dass Rekursion nur dann möglich ist, wenn das Teilproblem beim rekursiven Aufruf verkleinert wird. Aus dieser Punktliste kannst du dir mit einem entsprechenden Arrayzugriff einen Punkt rausholen, den du mit p vergleichen willst. Das Verkleinern der Punktliste hat gaku ja bereits beschrieben.
Hey,
ich hätte noch eine Frage zu 4.5 c), wollte aber keinen neuen Thread aufmachen, weil ja hier bereits einer vorhanden ist
Und zwar: Ich hab’ das rekursive Prinzip, wie die Aufgabe gelöst werden soll, verstanden. Dennoch kann ich einen einzigen Teil davon nicht umsetzen:
wenn ich die Methode closestPoint aufrufe und somit die minimale Distanz eines fixen Punktes mit einem anderen zurückgegeben bekomme,
muss ich die ja irgendwie abspeichern, um danach im erneuten rekursiven Aufruf vergleichen zu können, ob die neue minimale Distanz, die sich aus closestPoint ergibt,
kleiner ist, als die des letzten rekursiven Aufrufes.
Sitze an der Frage bereits 2 Tage lang und komme einfach nicht auf den richtigen Weg.
Würde mich freuen, wenn mir jemand zumindest einen Ansatz liefern kann.
Vielen Dank im Voraus!
Dein Lösungsweg bisher scheint korrekt zu sein.
Ein Beispiel:
Gegeben ist die Liste mit den Punkten: [ (1,1) , (1,3) , (1,4) ]
So, wir wissen:
d( (1,1) , (1,3) ) = 2
d( (1,3) , (1,4) ) = 1
d( (1,1) , (1,4) ) = 3
Das weiß aber noch nicht dein Programm.
Was du bisher machst ist das folgende:
Nehme die obige Liste und suche mir vom ersten Punkt aus den Punkt mit der kürzesten Distanz.
Als Resultat erhälst du den Punkt (1,3)
Und jetzt zu der Lösung deines Problems.
Vom Punkt (1,1) hast du bereits die kürzeste Distanz, jetzt brauchst du sie vom nächsten Punkt. Also kannst du ja die Restliste betrachten und das gleiche nochmal machen wie oben.
Richtig, du musst Ergebnisse vergleichen. Das tust du nachdem du zwei Punkte berechnet hast. Mehr möchte ich nicht verraten.
Bei mir gibt es ein ähnliches Problem.
Allerdings läuft es bei mir so, dass die Werte, die durch closestPoint in der Methode closestPair aufgerufen werden nur den Punkt an sich zweimal rausgeben mit einer Distanz von 0.
Also beispielsweise so :
[8.0, 9.0, 8.0, 9.0, 0.0]
Das soll er aber ja nur machen wenn ps nur 1 Wert enthält.
Bei mir sind aber 3 im Array
Brichst du die Rekursion früh genug ab? closestPair([array mit zwei punkten]) ist bereits der Basisfall. Du kannst diesen Aufruf nicht auf closestPair([array mit nur einem punkt]) zurückführen.