Gerade durch n Punkte

F

FantastischMan

Aktives Mitglied
Entwickeln Sie einen moglichst effizienten Algorithmus, der fu ̈r eine gegebene Punktmenge P mit n Punkten mit maximal k unterschiedlichen x-Koordinaten eine Gerade findet, die durch mo ̈glichst viele Punkte aus P la ̈uf
 
H

httpdigest

Top Contributor
Wenn die Dimensionalität der Punkte bzw. Tupel = 2 ist (was von dir nicht spezifiziert ist), dann:

stackoverflow.com

What is the most efficient algorithm to find a straight line that goes through most points?

The problem: N points are given on a 2-dimensional plane. What is the maximum number of points on the same straight line? The problem has O(N2) solution: go through each point and find the number...
stackoverflow.com stackoverflow.com

Der Zusatz, dass es höchstens `k` Tupel mit unterschiedlicher x-Koordinate gibt, finde ich allerdings interessant. Wenn z.B. in einem konkreten Fall `k=0` ist, dann weisst du schon, dass die gesuchte optimale Gerade die Gleichung `x=<x>` hat (mit <x> = irgendeine der gleichen x-Koordinaten, die dann ja für alle Tupel gleich ist).
Wahrscheinlich gilt das sogar für einen Grenzwert für `k < n/2`.

Wenn `k` gross ist (oder `k = n`), könnten die Tupel immer noch auf einer Geraden liegen. Das wiederum ist dann das Problem, was vom referenzierten Stackoverflow-Artikel angesprochen wird.
 
LimDul

LimDul

Top Contributor
Mal ein paar Random Gedanken:
Unter O(n log n) sollte nicht möglich sein
Es gibt zwei Lösungsklassen:
* Einmal eine Lösung mit einer senkrechten Gerade (Sprich, x ist konstant, y ist variabel)
* Oder eine Lösung mit einer nicht senkrechten Gerade. Diese Lösung kann man in der Form y = a*x + b schreiben

Klar ist, wenn es maximale k verschiedene X-Koordinaten gibt, kann (sofern die Punkte alle paarweise verschiedenen sind), eine Lösung der zweiten Kategorie maximal k Punkte schneiden. Das heißt, wenn ich die Punkte nach x-Koordinaten gruppiere und finde, dass es zu einer X-Koordinate mindestens k Punkte gibt, dann ist diese senkrechte Gerade die beste Lösung. Nur wenn das nicht zutrifft, muss ich überhaupt prüfen, ob eine Gerade der Form y = a*x + b mehr Punkte trifft.

Mehr Ideen hab ich gerade so nebenbei nicht.
 
K

kneitzel

Gast
FantastischMan hat gesagt.:
ja danke für eure hilfe, glaube aich dass die aufgabe auch euch zu schwer ist
Zum Vergrößern anklicken....
Ja, viel zu schwer. Aber was erwartest du auch? Das hier ist doch ein Forum für Freunde der Kaffee-Sorten von Java ...

Wende Dich doch mit sowas an ein Forum, in dem auch Leute sind, die z.B. Informatik studiert haben ... evtl. findest du sogar ein Forum, in dem auch Leute aktiv sind, die an einer Uni ihr Geld verdienen ...

Ansonsten sollten wir jetzt hier On Topic werden: Die Fragen sind immer noch nicht endgültig beantwortet:
A) Einfluss der Jahreszeiten auf den Kaffeegeschmack
B) Veränderung des Kaffeegeschmacks über die letzten 20 Jahre und der Zusammenhang mit der Entwicklung des Klimas

Aber vielleicht kannst du dazu etwas beitragen anstatt uns mit Aufgaben, die viel zu schwer sind für uns Kaffeeliebhaber, zu nerven.
 
M

Mart

Gast
FantastischMan hat gesagt.:
ja danke für eure hilfe, glaube aich dass die aufgabe auch euch zu schwer ist
Zum Vergrößern anklicken....
Also ich glaube niemand ist aktiv beleidigt


um ein Beispiel zu meiner OOP2 Klausur zu nennen (sehr kurz gefasst)
es gab 17 Punkte: (war 25% der Klausur )
man musste eine vorgegebene FXML laden
Es musste Lauffähig sein
und man musste einen Eventhandler dem Button geben

als 30 Leute durchgefallen sind von 80 durch die Klausur und wir den Prof im nächsten Semester wieder gehabt haben hat er nur indirekt gesagt ::

Er kann nicht verstehen warum so viele die Aufgabe Leer gelassen haben alleine Wenn man die Main hingeschrieben hätte eine Klasse und den Methoden Namen hätte man 5 Punkte bekommen aber die meisten haben nicht mal das gebacken gekriegt ...

hätte man den Eventhandler hingeschrieben der ein Vierzeiler war und nicht wirklich schwer
hätte man 7 Punkte bekommen zusätzlich


das zuweisen des EventHandlers und die FXML laden war das schwere dafür hats halt die Restlichen 5 Punkte gegeben... die er auch nicht erwartet hätte dass die jeder hat





Dieses Forum ist für "Gedanken Blockaden lösen" da... wenn man nicht weiter kommt und wie vor einer Wand steht oder Halt wie der Dritte Teil der Aufgabe "die schweren Sachen" wo man mal doch einen größeren Anstoß an Hilfe braucht ..zumindest habe ich so den Eindruck ...

und wie du merkst ... auf das was das Forum löst gibts die wenigstens Punkte :D
 
temi

temi

Top Contributor
K

kneitzel

Gast
White_Fox hat gesagt.:
Ist das denn die Lösung? Ich habe das bisher so verstanden daß es um EINE Gerade geht (und dabei z.B. an Regression gedacht). Im Bild sehe ich aber fünf Geraden - wenn ich die Ränder des Dreiecks mal ausnehme.
Zum Vergrößern anklicken....
Du denkst an die erste Aufgabe, die zu schwer für uns war. Das ist die Lösung für die zweite, leichtere Aufgabe ...

Aber ist doch nett, dass neue User, die als Prüfer zu uns kommen, uns so noch eine weitere Chance eben ...

*scnr*
 
M

Mart

Gast
ichWeißDes hat gesagt.:
Mir ist dein Benehmen oder ob du die Rechtschreibpolizei spielen willst scheißegal. Aber der TE hat seinen Ansatz zur zweiten Aufgabe gepostet und ich habe eine Erklärung mit Lösung verlinkt. Auf meine Implementierung muss nicht zurückgegriffen werden.

Dass sich der TE nicht mehr meldet, ist schade. Ich denke, er wollte nur eine Lösung abgreifen.

Ach so, über eure Kompetenzen kann ich nicht urteilen, aber alleine der Umstand, dass ihr zwei Aufgaben nicht voneinader unterscheiden könnt, spricht nicht gerade dafür.
Zum Vergrößern anklicken....
der Thread ist halt tod nachdem der TE nicht mehr da ist und seit dem juckts keinen mehr so wirklich deswegen kommt da eher nur noch troll hier rein
 
K

kneitzel

Gast
ichWeißDes hat gesagt.:
Mir ist dein Benehmen oder ob du die Rechtschreibpolizei spielen willst scheißegal.
Zum Vergrößern anklicken....
Warum reagierst Du dann so auf diesen einfachen Spaß?
ichWeißDes hat gesagt.:
Aber der TE hat seinen Ansatz zur zweiten Aufgabe gepostet und ich habe eine Erklärung mit Lösung verlinkt. Auf meine Implementierung muss nicht zurückgegriffen werden.
Zum Vergrößern anklicken....
Das ist doch auch in Ordnung - niemand hat etwas dagegen geschrieben. (Auch wenn ich es ähnlich sehe wie @httpdiggest ... bei so einem Auftreten helfe ich der Person eher nicht mehr :) )
ichWeißDes hat gesagt.:
Dass sich der TE nicht mehr meldet, ist schade. Ich denke, er wollte nur eine Lösung abgreifen.
Zum Vergrößern anklicken....
Wenn Du das doch selbst erkannt hast: Das macht deine Reaktion auf einen Einfachen Spaß noch viel weniger verständlich!
ichWeißDes hat gesagt.:
Ach so, über eure Kompetenzen kann ich nicht urteilen, aber alleine der Umstand, dass ihr zwei Aufgaben nicht voneinader unterscheiden könnt, spricht nicht gerade dafür.
Zum Vergrößern anklicken....
Und da zeigt sich dann, dass dies der neue Account von Tobias ist?
 
K

kneitzel

Gast
Wenn Du das noch irgendwie mit Argumenten untermauern könntest ... wieso sollte mir ein Arztbesuch helfen?

Oder hoffst Du, dass ich Tipps bekomme, wie man mit Dir besser umgehen kann? :)
 
H

httpdigest

Top Contributor
Er wollte dich bestimmt nur fragen, ob du schon deine Corona Impfung von einem Arzt bekommen hattest, weil er um deine Gesundheit bei einer moeglichen Ansteckung (insbesondere durch die sich ausbreitende Delta Variante) besorgt ist. Ist ja eigentlich nett von ihm. Nur hat er seine Bedenken diesbezueglich vielleicht etwas unklar ausgedrueckt.
 
K

kneitzel

Gast
Ahh so, das ist natürlich seht nett von ihm. Da bin ich jetzt total gerührt. Toll, wie fürsorglich Leute hier sind. :)
 
K

kneitzel

Gast
ichWeißDes hat gesagt.:
Neee, der könnte kneitzels Kopf untersuchen. :) (Wenn nur Luft drin ist, muss sich keiner Sorgen machen :D )
Zum Vergrößern anklicken....
Hmm, schließt da jemand von sich auf Andere? :)

Ich frage mich, was jemand für Probleme haben muss. der sich mit irgendwas angegriffen fühlt (#30) und dann meint, so hier austeilen zu müssen.. Hast Du so wenig Selbstbewusstsein? Oder was ist gerade Dein Problem? Mir soll es egal sein - Ich finde das hier einfach nur lustig.
 

Aktuelle Jobs

Neue Themen


Oben