Zitat von fishb00n
Ankündigung
Einklappen
Keine Ankündigung bisher.
User helfen User - Programmieren
Einklappen
X
-
Die frage ist, muss immer die optimale lösung rauskommen? wenn nein und nur eine annäherung an ein optimum als lösung reicht, kannst du einfach stupide nacheinander mit einem wert anfangen und solange durchiterieren (werte des arrays durchlaufen), bis du nen treffer findest, der eine der gewünschten zahlen ergibt. Die beiden werte streichst du dann und schreibst sie in ein neues array. damit wirst du jedenfalls sehr schnell sehr viele treffer finden bei 500k datensätzen. allerdings kann es hier sehr oft vorkommen, dass keine optimalen paare gebildet werden.Zitat von BUSFAHRERmoin, hab vor 3 wochen mit delphi angefangen und soll jetzt folgendes programmieren:
https://www.fbi.h-da.de/fileadmin/personal/b.humm/APT_WS0910/Praktiktum/07_Praemienjagd.pdf
habe eine textdatei mit 500.000 preisen, die ich dafür benutzen soll.
ich brauche einen ansatz, wie man das ganze lösen könnte.
hab mir erstmal nen button und n richedit erstellt und bei buttonclick wird der inhalt der textdatei ins richedit geladen (habe zum testen jetzt nur 20 preise genommen, nicht 500.000).
nun weiß ich leider nicht mehr weiter.
es geht mir um die logik, nicht wie man das in programmcode umsetzt. hoffe jemand kann helfen
wenn du nicht alle kombinationen bilden willst, könnte man die daten auch vorsortieren anhand der centbeträge. Das ganze dann in ein 2-dimensionales array[n][m] wobei n dann 0-99 ist und in m dann eben die beträge eingetragen werden, die zum index passen. jetzt könntest du sehr einfach kombinationen bilden, z.b. array[1][0] + array[10][0] = ...,11 usw. (Listen könntest du natürlich auch verwenden)
müsstest allerdings dann vorher festlegen, welche möglichkeiten für bestimmte fälle bevorzugt werden sollen -> 0 + 11, 1 + 10, 2 + 9, 3 + 8 usw... und das ganze dann für alle benötigten werte festlegen. is dann ziemlich viel statische programmierung, wobei man auch das mit schleifen etwas automatisieren könnte. von der laufzeit aber wesentlich effizienter als die lösung von tobilala.
wenn du allerdings erst seit 3 wochen programmierst und das eine fh aufgabe war, dann wird wohl vorschlag 1 das richtige sein ;)
Kommentar
-
naja das beste wird wohl zu sein,
die Preise als Knoten zu defnieren und aus den Möglichkeiten Kanten zu machen.
Dann immer den Knoten mit den wenigsten Kanten auswählen, und prüfen welcher Kontaktknoten davon am wenigsten Kanten hat. Die beiden verbinden und Knoten und Kanten aus der Liste löschen. Mit dem Schritt neu anfangen, bis keine Knoten mit Kanten mehr vorhanden sind.
dürfte so ziemlich perfekt sein, ohne unendliche Möglichkeitslisten zu erzeugen.
Kann dir grad keinen Beweis dafür liefern, bin doch schon etwas zu müde, kann das mal morgen probieren.
P.S. Mathe erstes Semester direkt mit Graphentheorie eingestiegen, ist sowieso easy zu verstehen. Sind ja nichtmal gerichtete etc. sondern noch ganz einfacher Scheiß hier.
Erklärung
Knoten als Objekt erzeugen
Inhalt: Preis als Real
"Gewicht" als Int
Kanten als Liste
Liste mit allen Objekten erzeugen. Das erste Objekt mit dem Rest der List durchprobieren, wenn möglich als Kante eintragen, danach Objekt aus der großen Liste schmeißen und weitermachen.
für jedes Objekt Gewicht errechnen aus der Menge der Kanten
Liste mit allen Objekten nach kleinstem Gewicht durchsuchen, bei dem nachschauen, welcher der möglichen Knoten aus den Kanten, wiederum das kleinste Gewicht hat. Bei mehreren alles durchsuchen und halt das kleinste Paar suchen. Bei 2 gleichen Ergebnissen einfach so proggen, das das letzte Ergebnis genommen wird (halt random)
Pro-Tripp, beim löschen beider Knoten, von den betroffen anderen Knoten hier das Gewicht updaten.
Repeat nach dem kleinsten Gewicht suchen.
fertige Liste ausgeben., wenn Gewicht aller Knoten bei 0
Klein und Fein
Kommentar
-
das war ein azubi ausm zweiten lehrjahr zusammen mit nem fertig ausgebildeten.. die beiden geben uns aufgaben und unterstützen uns dabei.. vorher sollten wir n eigenes paint programm erstellen und davor nen taschenrechner.
wir haben die aufgabe nun auch gelöst, ob es der schnellste weg ist, weiß ich nicht.
wir haben 2 arrays erstellt, eins für gerade zahlen, eins für ungerade zahlen.
dann nehmen wir eine gerade zahl, addieren die nacheinander mit jeder ungeraden zahl und machen dann mit der nächsten geraden zahl weiter.
es wird ermittelt, welche zahlen die wenigsten möglichen kombinationen haben, und mit diesen wird angefangen.
bei ner liste von 5000 preisen braucht er etwa 10 sekunden zur berechnung, das ist glaube ich relativ schnell, ein anderer azubi braucht für 500 schon 1 minute.
ich wollte erst ein zweidimensionales array nehmen anstelle von 2 verschiedenen, aber mir wurde gesagt das wäre zu umständlich :/
Kommentar
-
ich hab kollegen an der fh in würzburg und hab denen mal die aufgabe gezeigt, die meinten dann, ca 75% der leute bei ihnen im 6. semester könnten das nicht lösen :DZitat von tobilalawer hat n dir die aufgabe ueberhaupt gestellt?
wage mal zu behaupten, dass sicher 50% der FH-abgaenger das nicht gescheit loesen koennen -_- .. mal die wenigen guten Info FH's aussen vor gelassen.
Kommentar
-
mir war langweilig und ich hab meinen 2. vorschlag einfach mal in c# umgesetzt, allerdings ziemlich faul und schlampig, is noch nich 100%ig auf laufzeit und effizienz optimiert, weil ich keinen nerv mehr dafür hab ;).
da ich keine testdaten habe, erzeuge ich mir mit random einfach mal 50000 beträge zwischen 0.00 und 101.00. da random gleichverteilte zufallszahlen liefert, kann man davon ausgehen, dass man ungefähr gleichviele beträge mit endungen zwischen .0 und .99 bekommt. im schnitt finde ich dann 48% treffer.
man könnte ja mal die anderen genannten lösungen implementieren und die werte vergleichen, falls ihr lust habt :D von der laufzeit her brauch ich mit meiner lösung für 50k werte ~250ms.
code: http://pastebin.com/vdNTPgf3
//achja als kleiner tipp für alle, die nachkommastellen .11, .33, .55, .77 und .99 lassen sich aus insgesamt 280 kombinationen von 2 zahlen zusammenstellen. is mir grad auch aufgefallen :D
Kommentar
-
Weil die meisten hier einfach beschränkt sind und denken FH hat Hauptschulniveau im Vergleich zu ner Uni.Zitat von purowas isn an FHs eurer meinung so schlecht? kumpel war auf der in frankfurt und hat eigentlich nur gutes erzählt :s
Mit 1,0er Abi hat halt keiner was auf ner FH zu suchen. u know?
Kommentar
-
ich hab keine schlechte meinung von fhs, im endeffekt kann jeder selbst bestimmen wie effektiv er sein studium gestaltet und man kann selbst auf der größten krüppelfh extrem viel lernen, wenn man sich hinsetzt und sachen extra macht, das sagen mir jedenfalls immer zwei kumpels die an der fh (in würzburg) informatik studieren. deshalb geb ich auch nur das wieder, was mir gesagt wurde.Zitat von purowas isn an FHs eurer meinung so schlecht? kumpel war auf der in frankfurt und hat eigentlich nur gutes erzählt :s
Kommentar
-
naja, das kannst aber auch von der uni sagen. wenn man sich nich hinsetzt und arbeitet, kriegt auch ein unistudent das ganze nich hin.Zitat von michiich hab keine schlechte meinung von fhs, im endeffekt kann jeder selbst bestimmen wie effektiv er sein studium gestaltet und man kann selbst auf der größten krüppelfh extrem viel lernen, wenn man sich hinsetzt und sachen extra macht, das sagen mir jedenfalls immer zwei kumpels die an der fh (in würzburg) informatik studieren. deshalb geb ich auch nur das wieder, was mir gesagt wurde.Zitat von purowas isn an FHs eurer meinung so schlecht? kumpel war auf der in frankfurt und hat eigentlich nur gutes erzählt :s
mal so nebenbei: ich möcht mich bisschen aufs studium vorbereiten und schonmal eine sprache lernen, hab auch schon etwas erfahrung in c++. ausbauen oder mit was anderem anfangen, was für den anfang besser ist?
Kommentar
-
es ist immer relativ schwer sich algorithmische dinge beizubringen ohne fachbücher zu lesen, genauso komplexe datenstrukturen oder mathematische problemlösungen. daher würd ich fast vorschlagen, dass du dir einfach noch bisschen tiefere c++ kenntnisse aneignest und einfach mal etwas schwierigeres programmierst (chat mit server->client, mathematischer taschenrechner, später grafisch, notenverwaltung etc).
kommt eben ganz drauf an, wo du dir wissen aneignen möchtest (datenbanken, mathematik, kommunikation etc).
es ist da auch egal, ob du c++, java, c# oder php lernst, wenn man mal eine programmiersprache kann und die konzepte dahinter versteht, muss man bei den anderen nur die libraries kennenlernen und mehr nicht. ob es nun console.writeline oder console.printline ist, macht keinerlei unterschied.
Kommentar
-
Hat aber vermutlich das Hintergrundwissen dazu in Mathe und Datenstrukturen vertiefter gehört.Zitat von puronaja, das kannst aber auch von der uni sagen. wenn man sich nich hinsetzt und arbeitet, kriegt auch ein unistudent das ganze nich hin.Zitat von michiich hab keine schlechte meinung von fhs, im endeffekt kann jeder selbst bestimmen wie effektiv er sein studium gestaltet und man kann selbst auf der größten krüppelfh extrem viel lernen, wenn man sich hinsetzt und sachen extra macht, das sagen mir jedenfalls immer zwei kumpels die an der fh (in würzburg) informatik studieren. deshalb geb ich auch nur das wieder, was mir gesagt wurde.Zitat von purowas isn an FHs eurer meinung so schlecht? kumpel war auf der in frankfurt und hat eigentlich nur gutes erzählt :s
Ne Programmiersprache brauchst du fürs Studium nicht wirklich lernen. Wenn du in c++ schon Grundlagenwissen hast, würde ich da einfach ein bisschen weiter machen.
Kommentar
Kommentar