Seite 1 von 1

Fehlerteufel in Übung 6 und 9??

Verfasst: 9. Jul 2007 18:10
von kechler
Hallo zusammen,

ich habe mal ein paar Fragen bzw. Erratas zu oben genannten Übungen:

1.) Aufgabe 6.1 ii) Müssten da nicht Ordnung = 1 und Höhe = 5 sein?

2.) Aufgabe 6.4 c) i) für mst_erfolglos müsste es doch 89 / 17 heissen, oder?

3.) Aufgabe 9.3) Da bekomme ich für die Abfragen

optimum[o-1][s] >= optimum[o-1][s-G] + W[o]

optimum[o][s] = optimum[o-1][s-G] + W[o];

eine Nullpointer-Exception, was ja auch durchaus Sinn macht. Nun meine Frage:
Brauche ich diese Abfragen bzw. wie müssen sie geändert werden, damit der angegebene Code doch noch funktioniert?! Dieses "s-groessen" macht halt keinen Sinn...

Verfasst: 9. Jul 2007 20:44
von HerrDerFlammen
Aufgabe 6.1 ii)

stimmt schon. Diw Wurzel ist der Knoten, in dem das w steht (also der 2. von oben).

Zu mst erfolglos kann ich nix sagen, Wie berechnet die sich denn?

Re: Fehlerteufel in Übung 6 und 9??

Verfasst: 9. Jul 2007 20:49
von user
kechler hat geschrieben:3.) Aufgabe 9.3) Da bekomme ich für die Abfragen

optimum[o-1][s] >= optimum[o-1][s-G] + W[o]

optimum[o][s] = optimum[o-1][s-G] + W[o];

eine Nullpointer-Exception, was ja auch durchaus Sinn macht. Nun meine Frage:
Brauche ich diese Abfragen bzw. wie müssen sie geändert werden, damit der angegebene Code doch noch funktioniert?! Dieses "s-groessen" macht halt keinen Sinn...

Diesen Fehler hatte ich gestern auch. Die Abfrage war ja

if ((G[o] < s ) || (optimum[o - 1][s] >= optimum[o - 1][s - G[o]] + W[o]))
optimum[o][s]=optimum[o-1][s];
contains[o][s]=false;
...

falsch war:
if (G[o] < s ) || ... weil, dann würde man das Objekt nicht in den Sack lassen, dessen Größe kleiner ist als die aktuelle Rucksackgröße, was wir ja eigentlich wollen.
Dann verschwindet auch die Exception...

bei mir klappt es mit:
if ((G[o] > s ) || (optimum[o - 1][s] >= optimum[o - 1][s - G[o]] + W[o])) ...

Re: Fehlerteufel in Übung 6 und 9??

Verfasst: 10. Jul 2007 09:27
von Skullz
Zu Aufgabe 6.4) c)

Mit dem in der Musterlösung angegebenen Ergebnis habe ich auch so meine Probleme.
Vielleicht solltest du mal eine Mail an die Veranstalter schreiben, damit sie das mal klären, denn in den Vorlesungsfolien (Suchbäume) ist mir die Berechnung der erfolglosen Suche ebenso schleierhaft.

Verfasst: 10. Jul 2007 11:20
von kechler
Der Trick bei der erfolglosen Suche ist, dass man sich noch alle Null-Zeiger, die noch möglich sind, imaginär dazudenken muss. Für das zweite Beispiel in der Übung 6 würde das konkret bedeuten, dass an den Blättern "5, 11, 20, 30" noch jeweils 2 Null-Zeiger hängen. Dann führt man die Berechnung durch wie bei der erfolgreichen Suche. Hier stimmt meiner Meinung nach die MuLö auch nicht:

15 -> 1*Stufe(1)
8, 27 -> 2*Stufe(2)
5,11,20,30 -> 4*Stufe(3)
null, null, null, null, null, null, null, null -> 8*Stufe(4)

Ergibts insgesamt 49. Das durch die Anzahl der Zeiger(auch null-Zeiger) geteilt würde ich insgesamt auf 49/15 kommen?!

Hat jemand eine Idee? Sonst schreibe ich dem Veranstalter nachher einfach mal...

Verfasst: 10. Jul 2007 12:09
von Andreas T.
Zur Aufgabe 6.4 c)
i) Für mst_erfolglos würde ich vermuten, dass vergessen wurde, eine 9 (null-Zeiger von 17) zu addieren.
ii) Sieht so aus, als wäre dort zum Zähler von mst_erfolgreich 8*3 anstatt 8*4 addiert worden.

So sehe ich das momentan, bleibt wohl nichts anderes übrig, als nochmal nachzufragen...

Verfasst: 11. Jul 2007 15:02
von Skullz
@kechler

Wie die Berechnung der erfolglosen Suche vonstatten gehen soll, ist mir schon bekannt. Nur wollte ich darauf hinweisen, dass in den Vorlesungsfolien dasselbe Problem mit dem Ergebnis auftaucht. Schau dir die mal an.
Wahrscheinlich wäre eine Mail das Sinnvollste.

Verfasst: 11. Jul 2007 16:20
von Skullz
Ich nehme alles zurück.

Hätte man gleich sehr aufmerksam ins Härder-Skript geschaut, wäre das Problem gar nicht erst aufgetreten. Da gibt es nämlich eine sehr schöne Formel für die auch erfolglose Suche (Kapitel 5, Seite 39).
Da steht nämlich, dass man für die null-Knoten lediglich die Stufe des Knotens hinzuaddieren soll und nicht (Stufe + 1).

Somit ergibt sich für G6.4c)ii):
mst(auch erfolglos) = (1*1 + 2*2 + 4*3 + 8*3)/15 = (17+24)/15 = 41/15