Benötige unbedingt Hilfe für einen Code
-
Guten Abend,
ich soll ein d-näres Heap programmieren und stecke nun seit fast eine Woche mit dem Code fest. Problem ist die BubbleDown-Funktion.
Bin gerade im 2. Semester Informatik und hatte zuvor noch nie programmiert. Selbst zu Schulzeiten nicht. Bin also blutige Anfängerin. Der Code ist nicht gerade optimal oder sehr 'schön'. Und leider auch nicht wirklich funktionsfähig. Nun will ich das Ding aber zum Laufen bringen und wäre wirklich um jede kleinste Hilfestellung dankbar!
inline void BubbleDown( T A[], const uint N, uint p, const uint D ) { typedef typename T::key_type K; /// TODO Anfang int k = 1; int child = (p * D) + k; int minChild = child; int maybeChild; int count = 0; bool done = false; while(!done && (p <= ((N-2)/D))) { for(int i=1; i<=D; ++i) // Kinder zählen <-- wahrscheinlich klappt so nicht... { child = (p * D) + i; count ++; } if(count = D) // 1. Fall: p hat genau D Kinder { for(k = 2; k <= D; ++k) // Index des kleinsten Kindes finden { maybeChild = child; if(A[maybeChild].Key() < A[minChild].Key()) { minChild = maybeChild; } } if(A[p].Key() <= A[minChild].Key()) // Probe, ob wirklich kleiner als p done = true; else // falls ja: Tausche beide { swap(A[p], A[minChild]); p = minChild; // p ist nun eine Ebene tiefer } } if(count < D) { maybeChild = count; while(maybeChild > 1) { if(A[maybeChild].Key() < A[minChild].Key()) { minChild = maybeChild; } --maybeChild; } if(A[p].Key() <= A[minChild].Key()) done = true; else { swap(A[p], A[minChild]); done = }false; } } /// TODO Ende }
-
Ich geh jetzt mal nicht auf die Logik ein (weil ich keinen Plan habe was die Funktion machen soll.
inline void BubbleDown( T A[], const uint N, uint p, const uint D ) )Die Integer müssen nicht const sein. Du kannst eh nur die lokalen Variablen ändern.
for(int i=1; i<=D; ++i) { child = (p * D) + i; count ++; }count ist danach immer gleich D, da die Schleife genau D mal durchlaufen wird.
if(count = D) // 1. Fall: p hat genau D Kinder {macht das selbe wie
count = D; if(count != 0) {Und selbst wenn du das fixt, D ist wie gesagt immer gleich count...
done = ;}false;Syntaxfehler bei Instanzierung des Templates. Du willst
done = false; }
-
Danke! Die Funktion war so vorgegeben. Mein Job beschränkt sich zwischen den Todos.
Vom Prinzip hat man einen linksvollständigen Baum, in dem jeder Knoten D Kinder hat. An einem Knoten p ist die Heapeigenschaft verletzt. Ziel ist es nun, diese wieder herzustellen. Dabei muss ich den Kindknotem von p mit dem kleinsten Schlüssel finden und diesen mit p tauschen. Anschließend muss überprüft werden, ob p an der 'neuen' Stelle die Heapeigenschaft erfüllt oder verletzt und evtl. p solange nach unten tausche, bis ein heap wieder entstanden ist.
Wie mache ich es denn, wenn ich die Kinder von p zählen will? Tipp war eine Hilfsvariable m = c_1(p) zu deklarieren. Innerhalb der Hauptschelife soll man dann feststellen, ob p genau D Kinder hat, indem man aus der Menge (c_1(p)...c_D(p)) den Index desjenigen Kindes findet, der A[i].Key() minimiert. Dann soll man überprüfen, ob A[i].Key() wirklich kleiner als A[p].Key() ist. Falls nein: Abbruch. Falls ja, p = i und m neuberechnen.
Wenn man auf dem letzten Level ist, kann es sein, dass p weniger als D Kinder hat - hier muss man die Anzahl der Kinder ermitteln.
Weiß denn jemand, wie ich mithilfe des m's i bestimmen kann und wie man die Anzahl der Kinder ermitteln kann?
-
Dazu bräuchte der, der es für Dich lösen soll, viel mehr Kontext: die genaue Aufgabenstellung und vor allem den ganzen restlichen Code und welche Anforderungen T erfüllen muss (.Exists()?) und 200€ Taschengeld.
Ups, linksaufgefüllt, na, dann haste ja schon alle Daten übergeben kriegt. Komischer Tipp, von dem Du redest, der passt eher nicht.
Die Art der Fragestellung, das falsche Forum, der Mädchenname, Dein bisheriger Code, die Aussicht, daß Du damit einen akademischen Abschluss bekommst und den Arbeitsmarkt beeinflusst, sagen wir lieber mal 500€ fürs Anschauen.Bin gerade im 2. Semester Informatik und hatte zuvor noch nie programmiert. Selbst zu Schulzeiten nicht.
Dann rate doch mal, was Du jetzt machen solltest.
Im zweiten Semester also und hast noch kein Programmierbuch durchgearbeitet. Müßtest jetzt bequem das vierte durch haben. Also ran an den Feind und den Programmiergrundlagenschein im nächsten Jahr nochmal versuchen. Dann macht's auch viel mehr Spaß und dann wirste auch eher 11 Zeilen bauen statt 70.
-
der es für Dich lösen soll
Es soll keiner für mich lösen - das will ich allein. Ich dachte nur, man hätte ein paar Hinweise.
falsche Forum
Dann schieb mich ins Richtige.
der Mädchenname
Und?! Qualifiziert mich das ab?
dein bisheriger Code
Ja, dafür lernt mal ja. Schätze du bist auch nicht als Programmiergenie auf die Welt gekommen, oder?!
Und ja, ich lerne es gerade. Und ja: Man mag es kaum glauben, dazu werden sogar Bücher zu Rande gezogen. Dennoch fehlt einem einfach die Routine und schlichtweg Übung, um einen einigermaßen anständigen Code zu fabrizieren. Jaja, wahrscheinlich kommt jetzt: "Übung macht den Meister". Ach was?! Wirklich?!
Das Lernen soll mir keiner abnehmen. Es war lediglich die Frage nach ein paar konstruktiven Hinweisen.
-
MissMarshall schrieb:
der Mädchenname
Und?! Qualifiziert mich das ab?
Ja. Dies ist das Internet. Normalerweise ist jeder anonym unterwegs, sogar das Geschlecht ist verborgen. Wenn jemand ausdrücklich sein Geschlecht zum Ausdruck bringt, dann werden wir hellhörig, denn dann will er damit höchstwahrscheinlich was erreichen. Und noch wahrscheinlicher ist, dass die Information auch noch falsch ist.
~(Du magst vielleicht die große Ausnahme sein, die wirklich so naiv ist. Aber bis das Gegenteil bewiesen ist, hält dich der Großteil der Leser nun für einen fetten alten Mann, der irgendwie auf hilfsbedürftiges Mädchen machen will.)~
Allgemein:
http://www.tty1.net/smart-questions_de.html
-Wähle das Forum sorgfältig
-Verwende aussagekräftige, genaue Betreffzeilen
-Selbsterniedrigung ist kein Ersatz für nicht gemachte Hausaufgaben
-Stelle eine deutliche Frage
-Poste keine Hausaufgaben
-Vermeide aussagenlose Fragen
-Kennzeichne deine Fragen nicht als Wichtig, auch wenn sie es für dich sind
-Umgang mit Grobheit
-Nicht wie ein Loser reagierenNatürlich kann nicht jeder immer sich an alles halten. Aber du wirst überrascht sein, wie gut und schnell du Hilfe bekommst, wenn du dir Mühe mit deinen Fragen und deinem Auftreten gibst. Wenn du es nicht tust, passiert das, was du hier erlebst. Also relativ nutzlose Antworten bis hin zu Anfeindungen (wobei volkard geschickt direkte Anfeindungen in dem was er schreibt vermeidet, auch wenn du dich (wahrscheinlich zurecht*) angegriffen fühlst).
*: Das heißt nicht, dass er Unrecht hat. Er sagt die Wahrheit und die tut eben manchmal weh. Sei ihm dankbar, falls er dich damit aufgerüttelt hat.
-
Das war sehr konstruktiv.
Ich empfehle wirklich, daß Du Programmieren lernst, und zwar deutlich über das bescheidene Maß hinaus, was gerade reicht, im Grundlagenschein eine 4 zu erbeuten. Das ganze Info-Studium fällt mit solidem Programmierhintergrund erheblich leichter. Dazu ist auch wichtig, daß Du gute Bücher benutzt, ich denke, daran krankt es schon. (Rieche ich gerade das C/C++-Kompendium?)Im Moment rennste nur gegen eine Wand.
inline void BubbleDown( T A[], const uint N, uint p, const uint D ) { typedef typename T::key_type K; /// TODO Anfang int k = 1;//lokaler int child = (p * D) + k;//erst recht int minChild = child;//erst rechter int maybeChild;//unnötig int count = 0;//lokaler, pEnd wäre besser bool done = false;//unnötig und pascaloid while(!done && (p <= ((N-2)/D)))//darum pEnd {//wenn man dann noch erzwänge, daß pEnd nicht zu groß werden könnte… for(int i=1; i<=D; ++i) // Kinder zählen <-- wahrscheinlich klappt so nicht... //nee, berechnen statt zählen //und sich am besten nicht wirklich auf die Kinderzahl fixieren { child = (p * D) + i;//tut nix count ++;//hättest du direkter haben können } if(count = D) // 1. Fall: p hat genau D Kinder//== { for(k = 2; k <= D; ++k) // Index des kleinsten Kindes finden {//warum gehts bei 2 los maybeChild = child;//nicht von k abhängig if(A[maybeChild].Key() < A[minChild].Key())//warum nicht k? { minChild = maybeChild;//dito } }//schlecht eingerückt if(A[p].Key() <= A[minChild].Key()) // Probe, ob wirklich kleiner als p//oder evtl minchild zu beginn auf p setzen, eine überlegung wert. done = true;//dafür hat uns der herr return geschenkt else // falls ja: Tausche beide { swap(A[p], A[minChild]); p = minChild; // p ist nun eine Ebene tiefer } } if(count < D)//ganz unnötige fallunterscheidung { maybeChild = count;//wie oben while(maybeChild > 1)//schlicht unfug { if(A[maybeChild].Key() < A[minChild].Key())//die zeile ist doch bestimmt geklaut { minChild = maybeChild; } --maybeChild;//oh! damit hab ich nicht gerechnet. } if(A[p].Key() <= A[minChild].Key()) done = true;//siehe oben else { swap(A[p], A[minChild]); done = }false; } } /// TODO Ende }Ok, ich erkenne, was Du machen willst, na wenigstens etwas. Aber die konstruktiven Tipps müßten quasi jede Zeile reparieren, das heißt also Neuschreiben. Kannst mir viel erzählen, aber nicht, daß diese Aufgabe zur Zeit für Dich sinnvoll wäre.
Hab das Gefühl, Du hast auch keinen Bock mehr. Hoffentlich nur Folge schlechter Bücher, denn unvermeidbar sinkt die Motivation mit jeder Stunde, die man nicht weiterkommt.
Hier mein Gegenvorschlag. Um nicht zu viel zu verraten, habe ich einen noch nicht lauffähigen Entwurf genommen und die Buchstaben und EInrückungeb gelöscht.
inline void BubbleDown(T A[], const uint N, uint p, const uint D) { typedef typename T::key_type K; /// TODO Anfang (;;){ =::(-,*+-); =; (=;<;++) ([].()<[].()) =; ([].()<=[].()) ; ::([],[]); =; } /// TODO Ende }So, das war aber jetzt konstruktiv für die ganze Woche.
-
Vielleicht hilft Dir auch der Artikel zu binären Heaps weiter?
-
SeppJ schrieb:
Normalerweise ist jeder anonym unterwegs, sogar das (...) hilfsbedürftiges Mädchen machen will
Mhh.. nagut. Wusste nicht, dass man so zwischen den Zeilen ließt, aber ich werde es mir für die Zukunft merken. Wollte nicht den Eindruck erwecken, auf einen "Weibchen-Bonus" aus zu sein. (Und ja, ich bin eine derartige naive Ausnahme...)
volkard schrieb:
Ich empfehle wirklich, daß Du Programmieren lernst, und zwar deutlich über das bescheidene Maß hinaus, was gerade reicht, im Grundlagenschein eine 4 zu erbeuten.
Ja und ja. Nur zwischen programmieren lernen und beherrschen liegen nun mal Welten. Unser Studium ist vorwiegend theoretisch ausgerichtet. Die Praxis wird eher als "ferner liefen" behandelt. Programmiereinführungsveranstaltungen etc pp. gab's nie und wird's auch nicht geben. Einen Grundlagenschein musste man nicht machen. Ist alles nicht so schlimm, Selbststudium bringt einen nicht um. Doch geht's nicht von heute auf morgen.
volkard schrieb:
Das ganze Info-Studium fällt mit solidem Programmierhintergrund erheblich leichter. Dazu ist auch wichtig, daß Du gute Bücher benutzt, ich denke, daran krankt es schon. (Rieche ich gerade das C/C++-Kompendium?)
Das glaube ich Dir gerne, dass das alles viel leichter fällt und auch Spaß macht.
Naja, ich habe nun mal bis jetzt nur Einführungsbücher durchgearbeitet. Klar, die geben auch nicht mehr her als eine Grundlagenbasis. Dass das nicht reicht, ist mir schon klar.volkard schrieb:
Kannst mir viel erzählen, aber nicht, daß diese Aufgabe zur Zeit für Dich sinnvoll wäre.
Doch ist es. Ich will das Ding zum Laufen bringen.
volkard schrieb:
Hab das Gefühl, Du hast auch keinen Bock mehr. Hoffentlich nur Folge schlechter Bücher, denn unvermeidbar sinkt die Motivation mit jeder Stunde, die man nicht weiterkommt.
S. oben.
Und glaube mir das einfach, wenn ich Dir das so sage: Ich will es zum laufen bringen. Hätte ich keinen Bock, würde ich nicht um Hilfe bitte und hätte hingeschmissen. Und nochmal: Es soll mir keiner lösen.volkard schrieb:
Hier mein Gegenvorschlag.(..)
Danke Dir.
Ich versuche mich dran.if(count < D)//ganz unnötige Fallunterscheidung // Wieso? Die Kinderanzahl der letzten Ebene kann < D sein. Muss ich den Fall nicht berücksichtigen? { maybeChild = count;//wie oben while(maybeChild > 1)//schlicht unfug { if(A[maybeChild].Key() < A[minChild].Key())//die zeile ist doch bestimmt geklaut // Nein. { minChild = maybeChild; } --maybeChild;//oh! damit hab ich nicht gerechnet. }Jester schrieb:
Vielleicht hilft Dir auch der Artikel zu binären Heaps weiter?
Ja. Danke.
-
MissMarshall schrieb:
Wieso? Die Kinderanzahl der letzten Ebene kann < D sein. Muss ich den Fall nicht berücksichtigen?
Würde ihn vorher berücksichtigen, da wo die Kinderanzahl berechnet wird.
Dann kannste später ohne Fallunterscheidung bis zur Kinderanzahl laufen.
Oder geh immer von allen Kindern aus, prüfe aber in der Schleife "if(child>=N) break;" oder so. Ok, das bräuchte man zwar nur in der untersten Ebene prüfen, aber die Mehrkosten würde ich zunächst zahlen, damit der Code erstmal kurz bleibt.
-
SeppJ schrieb:
Ja. Dies ist das Internet. Normalerweise ist jeder anonym unterwegs, sogar das Geschlecht ist verborgen
Und daher nennst du dich "SeppJ"? SCNR
