Ein Anfang is gesucht.

[Guest]

Hallo,

ich sitze vor der selben Aufgabe wie hier!

Ich will keine Lösung, denn davon kann man nix lernen... ich würde nur gerne einen Tipp/Rat haben wie ich das Problem am besten in viele kleine aufspalten kann und dann nach und nach mich durchhangeln kann...

Wer kann mir helfen?
Sollte ich vll. erst mal mit der Shell beginnen?

Danke schon mal ;-)

 

[ARadauer]

ja beginn mit der Shell und programmier mal das Feld, dann versuchst du den "naiven algorythmus" zu schreiben. das ist einfach.

dann machst du eine rekursion die das feld so lange aufteilt bis 2 oder 3 elemente drin sind.
Der Rest des Teile und Herrsche Algorythmus wird eh beschrieben....

btw: ist euerer Lehrer so schlecht, oder seits ihr es? du gehst in passau zur schule oder? das ist die 4. Anfrage für diese Aufgabe!

 

[Guest]

Hm, das ist eine gute Frage aber ich finde dass das alles viel zu schnell manchmal geht und dann viele einfach keine Chance haben mitzukommen...deshalb glaub ich auch kommen hier so viele Anfragen...
Und ich verstehe auch dass hier keine Lösungen gepostet werden, denn so kann man nix lernen und steht nächstes mal wieder vor dem selben Problem oder checkt den code nicht aber wenn man noch nie geproggt hat dann is so ne Aufgabe doch ziemlich schwer...

Danke mal für deinen Tipp werd mcih jetzt mal wieder dran sitzen und meld mich dann wenn ich mal was habe... vll. kannst mir ja dann wieder weiterhelfen weil ich glaube dass ich das nicht so von heute auf morgen hinbekomme

Danke!

 

[ARadauer]

mhn stimmt,
irgendwie finde ich die übung einwenig schwierig fürs 1. semester

das wichtigste ist, dass man sich vor einem komplexen problem nicht fürchten darf. Aus einer Menge von Punkte den kürzesten Abstand zu finden ohne das man jeden mit jedem vergleicht, ist sicher nicht einfach, aber man kann das Problem ja zerlegen. In der Programmierung geht es eigentlich meistens darum, ein komplexes Problem in einfache Probleme zu zerlegen.

Und der Algorythmus ist auch beschrieben:

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

Schritt für Schritt, dann schaffst du das schon.

 

[Guest]

...dann machst du eine rekursion die das feld so lange aufteilt bis 2 oder 3 elemente drin sind.
Der Rest des Teile und Herrsche Algorythmus wird eh beschrieben...

Also ich sitz an der selben Aufgabe und mir ist nich ganz klar wie ich das Feld so aufteilen kann, dass zum Schluss alle Teilfelder berücksichtigt werden. Man muss ja einen Rekursions-Fall haben in dem eine Anweisung erfolgt wo ich einmal die Funktion mit der linken Hälfte und einmal mit der rechten Hälfte aufrufen muss. Aber wie verknüpfe ich diese beiden Aufrufe miteinander so, dass beide ausgeführt werden?

Gruß
El Rey