Problem 4 Step 2c

Benutzeravatar
Dennis
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 102
Registriert: 29. Sep 2008 21:15

Re: Problem 4 Step 2c

Beitrag von Dennis »

b00m3r hat geschrieben:Hallo zusammen,

hab ein kuriosen Fehler ... meine komplette 2 läuft nur im Test 1 sagt die random mir, dass ein Intervall is present!
Hatte jemand einen ähnlichen Fehler?
Bin ziemlich ratlos :(

Hab den gleichen Fehler und häng nun schon gut 8 Std. (kumuliert) hierdran... die Einzeltests stimmen alle nur die Randoms gehen in die Hose :?:
...fragt stellvertretend für alle Freunde...

Benutzeravatar
Gnomix
Computerversteher
Computerversteher
Beiträge: 306
Registriert: 31. Okt 2005 08:44

Re: Problem 4 Step 2c

Beitrag von Gnomix »

Der Test prüft, ob alle Knoten vorhanden sind.
Wenn also "Interval is present" bei Step1.RandomTest erscheint, hat man nicht alle Knoten eingefuegt.

Ihr müßt darauf achten, dass am Anfang auf node.Intervall.start geprüft wird, ist dieses gleich, prüfe auf node.agent.
Ist auch node.agent gleich, fuege den Knoten dennoch ein, aber im linken Teilbaum.
Ersetze bei CounterInteligence.add() keinen Knoten.

Also wenn also (x,agent ) <= node, fuege in den linken Teilbaum ein.
Wenn (x,agent) > node fuege in den rechten Teilbaum ein.

Dabei kann es passieren, dass du zwei identische Intervalle mit identischen Agents einfuegst.

Benutzeravatar
Dennis
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 102
Registriert: 29. Sep 2008 21:15

Random 1 und 2 laufen :-)

Beitrag von Dennis »

Bei mir läuft test1.random und test2.random nun:

Falls es jemandem weiterhilft...

Mein Fehler war, dass add() nicht korrekt rekursiert hat.

Also mein add() hat vorher so gearbeitet, dass es geschaut hat, ob der knoten nach links oder nach rechts muss usw...
was ich dann aber falsch gemacht habe war, dass ich, obwohl ich am start schon prüfe ob "node == null" (der "Trivialfall")
und dann den Knoten einfüge - ich trotzdem beim durchwandern des Baumes am Ende immer geschaut habe ob node.left == null, und wenn ja dann mach node.left = neuerknoten.
Auf diese Weise liefen die Add Tests, auch mit Random durch, SOLANGE ich nicht rotiert habe.

Richtig wäre gewesen, dass ich statt den Knoten zu platzieren, dann einfach nochmal in die Rekursion steige, weil ja die (node == null) mechanik den Knoten auch an die richtige stelle einfügt. Auf diese Weise gingen mir dann keine Intervalle mehr verloren, weil das nächste add() dann nicht mehr auf einem durcheinandergewürfeltem Baum gearbeitet hat (sobald es viele Nodes wurden kam es da zu Ungereimtheiten).

Also mein Fazit, auch wenn in add() alles grün am Anfang war, muss das nicht heissen, dass es richtig funktioniert. Man! Da hab ich nun 12 Stunden dran gesessen und wäre wahrscheinlich auch nicht drauf gekommen, hätte ich nicht jemanden gehabt (der schon fertig ist), der mal meine Teilaufgaben bei sich reinsetzt und mir sagt, ob die Fehlerfrei arbeiten :roll:
Zuletzt geändert von Dennis am 20. Jun 2009 18:52, insgesamt 1-mal geändert.
...fragt stellvertretend für alle Freunde...

daniel herwig
Erstie
Erstie
Beiträge: 18
Registriert: 2. Okt 2007 20:41

Re: Problem 4 Step 2c

Beitrag von daniel herwig »

oh man, jetzt wurde hier so viel geschrieben, aber keiner hat den fehler dass nur testRandom durchläuft, aber die anderen 4 nicht =/

ich bin langsam echt am verzweifeln, ich sitzt jetzt schon ewigst lange an diesem kram und komm einfach nich weiter, ich kann an meinem code verändern was ich will, es läuft immer random und der rest nicht.

hat jemand nen produktiven vorschlag worans hängen könnte :?:

ich mein, der erste ia banal² einfach ne left-roation,...aber selbst das haut irgendwie nich hin ... planlos in gdi2, genau das trifft grade auf mich zu.. damn.

dumbo2
Neuling
Neuling
Beiträge: 9
Registriert: 20. Mai 2009 20:05

Re: Problem 4 Step 2c

Beitrag von dumbo2 »

Tausend Dank für den Tipp Dennis, bin ja fast schon wahnsinnig geworden.

War anscheinend genau der selbe add-Fehler wie bei dir.

Gruß Olli

Benutzeravatar
Ibliss
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 209
Registriert: 11. Apr 2008 04:08
Wohnort: Darmstadt

Re: Problem 4 Step 2c

Beitrag von Ibliss »

@daniel herwig

Weißt du was Daniel, wenn du nicht weiter kommst, dann debugger anschalten, Stift und Papier nehmen , zeichne den Baum aus dem Test und fange an Schritt für Schritt alle Änderungen im Laufe des Programms auf dem Papier zu Zeichnen. Es ist ja hart, besonders wenn es um einen RandomTest handelt, ich habe es auch so gemacht bei Problemen die mir rätzelhaft waren, und damit den Fehler entdeckt. Vielleicht suchst du den Fehler an der Falsche Stelle. Einen Fehler den du im vielleicht add() hast kommt erst beim rebalance() auf die Oberfläche.
"Honesty is the first chapter in the book of wisdom.
Alien vs Predator 2 is the movie version of that book."

daniel herwig
Erstie
Erstie
Beiträge: 18
Registriert: 2. Okt 2007 20:41

Re: Problem 4 Step 2c

Beitrag von daniel herwig »

ja ich gehe den code immer auf dem papier durch wenn ich nicht weiterkomme, nur hat mich das diesma nicht wirklich weitergebracht.

aber hab den fehler mittlerweile gefunden. danke.

Liox
Neuling
Neuling
Beiträge: 3
Registriert: 17. Jun 2009 18:14

Re: Problem 4 Step 2c

Beitrag von Liox »

Hi,
ich komme mir mittlerweile recht... grenzdebil vor :(

Ich hab quasi alles konzeptuell ausgearbeitet, aber ich hänge an 2c und komm nicht weiter, obwohl ich den Code 20fach überprüft habe. Ich glaube ich hab irgendwo nen Denkfehler, evtl. kann mir einer von euch ja helfen:

Step 1
Wenn der Baum node leer ist, erstelle einen neuen Baum mit dem Interval x und dem Knoten agent.
else
Fall 1: Das Intervall des neuen Knoten ist kleiner als das des Vaters, speichere node.left als Ausführung von add auf node.left
Fall 2: entsprechendes für Intervall Sohn > Vater für node.right
Fall 3: Intervall Sohn == Vater
Sortierung nach Agentennamen (brauch ich hier nicht weiter ausführen)

updateHeight(node); nach der Else-Schleife

Step 2a
führe height(node); aus
Wenn die Höhe des Linken Unterbaums größer ist als die Höhe des rechten Unterbaums, addiere 1 zur Höhe des Linken
Else
Umgekehrte Geschichte

Step 2b
Rotates sind beide gleich nur mit entsprechenden Abänderungen.
Struktur für Links
Speichere einen neuen Baum node2 mit dem Intervall des rechten Sohnknotens und dessen Name
Dann hab ich einfach die Teile aus dem alten Baum node genommen und sie entsprechende angehängt.
also: node2.right = node.right.right
node2.left = node;
node2.left.right=node.right.left;
updateHeight(node2.left);
updateHeight(node2);

Ich hab das auf dem Papier bei den augemahlten Bäumen aus dem Code angewandt und hab auch zwei Tests mit Rechtslinks-Rotationen gemacht (hab den alten Baum entsprechend erweitert). Funktioniert immer. :(

Step 2c
Naja, der wurde hier ja genügend besprochen.
balance aufrufen
If-Case (balance(node) >=2)
dann schau ob der BF vom rechten Unterbaum <= -1 ist
wenn ja, R-Rota auf node.right und L-Rota auf node aus,
wenn nein, R-Rota auf node
Entsprechendes für balance(node) <= -2

Fällt irgendjemandem irgendwas an meiner Ausführung auf das nicht stimmt? Bin allmöhlich wirklich am verzweifeln und hab "nur" noch 32 Stunden Zeit ^^

Benutzeravatar
DerInformator
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 24. Okt 2008 13:02
Wohnort: DA

Re: Problem 4 Step 2c

Beitrag von DerInformator »

daniel herwig hat geschrieben:oh man, jetzt wurde hier so viel geschrieben, aber keiner hat den fehler dass nur testRandom durchläuft, aber die anderen 4 nicht =/

lol ... als ich mir dein Beitrag durchgelesen habe dachte ich mir .... "das gibts doch nicht.... Random läuft aber die anderen Test nicht"

und ein paar Zeilen später ... siehe da ... ich habe das gleiche Problem :D
Random Test läuft...aber die anderen nicht :S

Was war den dein Fehler? vielleicht habe ich einen ähnlichen Denkfehler gemacht? Danke schon mal im Vorraus ^^


EDIT: habe gerade gemerkt wenn ich in rebalance nur "return null;" habe und es dann in die "add()" einbaue, bekomme ich auch den Random-Test richtig und noch mehr richtige Tests O_o

EDIT 2 : WOOOHOOO es geht :P
Zuletzt geändert von DerInformator am 20. Jun 2009 16:58, insgesamt 2-mal geändert.
"Do not go where the path may lead, go instead where there is no path & leave a trail"

Benutzeravatar
anon
Neuling
Neuling
Beiträge: 10
Registriert: 16. Mai 2009 10:21

Re: Problem 4 Step 2c

Beitrag von anon »

liox,
also dein rotate sieht komisch aus (auch wenn ich es nicht in allen einzelheiten angeschaut habe)...
guck nochmal hier:

http://en.wikipedia.org/wiki/Tree_rotation

und schau, ob das so hinkommt.
das beispiel dort ist eigentlich das gleiche wie im kommentar zu den rotate funktionen.

Liox
Neuling
Neuling
Beiträge: 3
Registriert: 17. Jun 2009 18:14

Re: Problem 4 Step 2c

Beitrag von Liox »

Ok, ich hab meinen Fehler.

Es lag nicht an der Rotation und nicht am Rebalance und nicht am Add :D
Ich hatte bei der balance Hilfsfunktion die Prüfung ob node.left.height bzw. node.right.height überhaupt existiert nicht bedacht. Dann hab ich die Verweise durch die Hilfsfunktion height(node.left) bzw height (node.right) ersetzt und es läuft. :D

OH - MEIN - GOTT XD

Benutzeravatar
DerInformator
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 24. Okt 2008 13:02
Wohnort: DA

Re: Problem 4 Step 2c

Beitrag von DerInformator »

oh neeeeeiiiiin ><

Problem 2c geht jetzt super durch (alle Tests ok) allerdings habe ich bei Test 1 jetzt auf einmal einen Fehler.... und zwar nur beim Random-Test
da steht dann so was wie >> junit.framework.AssertionFailedError: Interval is present << da .... hat jemand eine Ahnung was die Meldung bedeutet?

Oder woran das liegen könnte? (wie gesagt Test's 2a, 2b, 2c laufen alle durch ...nur Test 1 Random hapert)

EDIT: oh juhuu es geht.... ich habe einfach mal meine add() Funktion GANZ VON VORNE ^^ nochmal neu geschrieben unter berücksichtigung des Tipps von Dennis (siehe oben) Vielen Dank für den Tip Dennis!!!!!! :D
"Do not go where the path may lead, go instead where there is no path & leave a trail"

blablubb209
Neuling
Neuling
Beiträge: 9
Registriert: 19. Apr 2009 17:58

Re: Problem 4 Step 2c

Beitrag von blablubb209 »

hmm ich versteh die welt nichmehr bei mir gehen jetzt alle tests bis zur 2c außer dem 2c random test......
sagt mir balance_factor -1 0 1......, kann jemand auf anhieb sagen wo dann wahrschl mein fehler liegt :D ?
die height berechne ich wie im junit test von der 2a :D und mache sonst auch "eigentlich" alles richtig....

Benutzeravatar
DerInformator
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 24. Okt 2008 13:02
Wohnort: DA

Re: Problem 4 Step 2c

Beitrag von DerInformator »

blablubb209 hat geschrieben:hmm ich versteh die welt nichmehr bei mir gehen jetzt alle tests bis zur 2c außer dem 2c random test......
sagt mir balance_factor -1 0 1......, kann jemand auf anhieb sagen wo dann wahrschl mein fehler liegt :D ?
die height berechne ich wie im junit test von der 2a :D und mache sonst auch "eigentlich" alles richtig....
hmm...diese Fehlermeldung hatte ich noch nicht, aber ich vermute, dass es daran liegt dass du zu früh "aussteigst" ... d.h. du gibst dem schon einen AVL-Baum zurück der noch kein AVL-Baum ist... wahrscheinlich (ist aber nur meine ganz doofe Vermutung) liegt es daran, dass du rebalance() nicht richtig in add() eingefügt hast... kann aber auch an was anderem liegen ^^ sorry dass ich nicht so viel weiterhelfen konnte, aber hab auch keine wirkliche Ahnung was bei dir falsch sein könnte :(
"Do not go where the path may lead, go instead where there is no path & leave a trail"

Benutzeravatar
Gnomix
Computerversteher
Computerversteher
Beiträge: 306
Registriert: 31. Okt 2005 08:44

Re: Problem 4 Step 2c

Beitrag von Gnomix »

@blablub:
DerInformant hat recht. Der Fehler "balance_factor -1 0 1" bedeutet, dass du einen Knoten mit einem Balancefaktor hast, der nicht -1, 0 oder 1 ist, sonder höher.
Dieser Fehler tritt normalerweise dann auf, wenn du nicht alle Knoten ausbalancierst.

Antworten

Zurück zu „Archiv“