Fehlerteufel in Übung 6 und 9??

kechler
Mausschubser
Mausschubser
Beiträge: 46
Registriert: 21. Nov 2004 22:33
Wohnort: Darmstadt

Fehlerteufel in Übung 6 und 9??

Beitrag 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...

Benutzeravatar
HerrDerFlammen
Mausschubser
Mausschubser
Beiträge: 79
Registriert: 16. Okt 2006 17:30
Wohnort: Dreieich
Kontaktdaten:

Beitrag 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?
Das Lehren soll so sein, dass das Dargebotene als wertvolles Geschenk und nicht als saure Pflicht empfunden wird.
(Albert Einstein)

Benutzeravatar
user
DON'T PANIC
Beiträge: 42
Registriert: 9. Sep 2004 18:22

Re: Fehlerteufel in Übung 6 und 9??

Beitrag 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])) ...

Benutzeravatar
Skullz
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 23. Mai 2007 16:21

Re: Fehlerteufel in Übung 6 und 9??

Beitrag 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.

kechler
Mausschubser
Mausschubser
Beiträge: 46
Registriert: 21. Nov 2004 22:33
Wohnort: Darmstadt

Beitrag 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...

Andreas T.
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 192
Registriert: 18. Okt 2006 00:18
Wohnort: Darmstadt

Beitrag 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...

Benutzeravatar
Skullz
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 23. Mai 2007 16:21

Beitrag 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.

Benutzeravatar
Skullz
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 23. Mai 2007 16:21

Beitrag 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

Antworten

Zurück zu „Archiv“