Fehler in der Lösung zur Übungsaufgabe

mg_92
Neuling
Neuling
Beiträge: 4
Registriert: 21. Sep 2013 15:25

Fehler in der Lösung zur Übungsaufgabe

Beitrag von mg_92 »

Erst mal eine Frage vorweg:

Ist die Behandlung der Sequenz laut Induction Base im Wiki als erste Iteration anzusehen oder geschieht dies vor der Iteration.

Ich habe es so verstanden, dass dies vor der Iteration passiert. Somit ist in Aufgabe 3 zu dem Algorithmus "Pivot partitioning by scanning", meiner Meinung nach, so einiges falsch:

1) Bevor die erste iteration anfängt wird i3 schon auf die 18 gesetzt, da die ersten zwei Elemente auf denen i3 steht ja schon korrekt einsotiert sind.
Somit komm ich dann schon nach 4 Iterationen FAST auf das Ergebnis, das in der Lösung erst nach 5 Iterationen erlangt wird. Außerdem müsste in der Lösung die 40 mit der 23 vertauscht werden, da die 23 nie berührt wird und somit sich nicht verändert.

2) i2 muss auf der 9 stehen nicht auf der 40. Erst nach der 5 (bzw. in der Lösung die 6. )Iteration eins hochgesetzt werden auf m2.


Desweitern ist in der Aufgabe 5 zu dem Algorithmus "Dijkstra", meiner Meinung nach, ein Fehler. Und zwar:

Die Kante von 1 nach 2 ist falsch. Da die Kante von 4 nach 2 den Wert 5*2+4=14 hat. Die Kante von 1 nach 2 den Wert (5*1+4)+(5*1+2)=16. Da 14<16 gilt müsste die Kante von 4 nach 2 genommen werden.

Irgendwie nicht sehr hilfreich die Übung, wenn so viele Fehler drin sein sollten.

MfG mg

CJo
Neuling
Neuling
Beiträge: 8
Registriert: 6. Sep 2013 15:25

Re: Fehler in der Lösung zur Übungsaufgabe

Beitrag von CJo »

Soweit ich das verstanden habe geschieht die Induction Base vor der 1. Iteration.
Zu 1. stimme ich dir zu, habe auch nach 5 Iterationen bereits das Ergebnis.

sbechtel
Mausschubser
Mausschubser
Beiträge: 56
Registriert: 17. Apr 2013 19:13

Re: Fehler in der Lösung zur Übungsaufgabe

Beitrag von sbechtel »

Soweit ich das verstanden habe geschieht die Induction Base vor der 1. Iteration.
Ditto!

Zu Aufgabe 1 habe ich das selbe auch schon geschrieben (dort wird ebenfalls i=5 als der Zustand nach der 6. Iteration beschrieben) und jemand hat ebenfalls geantwortet, dass als 1. Iteration die Induktionsbasis angesehen wird/wurde. Wie gesagt, ich sehe das auch nicht so. Eine offizielle Stellungnahme wäre deshalb hilfreich!

biz
Erstie
Erstie
Beiträge: 19
Registriert: 4. Okt 2010 13:10

Re: Fehler in der Lösung zur Übungsaufgabe

Beitrag von biz »

Hallo,

bei mir beendet der Algorithmus auch nach 5 Iterationen. Mein S sieht dabei so aus:

Code: Alles auswählen

S = ( 18, 1, 1, 14, 9, 7, 7, 9, 3, 0, 22, 23, 42, 40, 30, 35, 54)
                                    ^   ^                       ^
                                   i1   i2                      i3
                                   m1   m2                  

dann ist i= 5, i1 = m1, i2 = m2, und i3 = n+1, also genau die Abbruchbedingung. Eine 6te Iteration findet nicht statt.


edit: i3 leicht angepasst
Zuletzt geändert von biz am 22. Sep 2013 16:26, insgesamt 2-mal geändert.

sbechtel
Mausschubser
Mausschubser
Beiträge: 56
Registriert: 17. Apr 2013 19:13

Re: Fehler in der Lösung zur Übungsaufgabe

Beitrag von sbechtel »

mg_92 hat geschrieben:Da 14<16 gilt
Nicht in Z5 :mrgreen:

oek
Erstie
Erstie
Beiträge: 21
Registriert: 11. Sep 2013 08:42

Re: Fehler in der Lösung zur Übungsaufgabe

Beitrag von oek »

Also ich habe auch die selbe Reihenfolge wie biz nur zeigt i3 doch noch auf die 54 also auf n und noch nicht auf n+1 oder?
Somit ist der Algorithmus noch nicht beendet und man müsste noch den Step 3.1 und 3.3 der Implementation des Induction Steps durchführen oder irre ich mich?

mg_92
Neuling
Neuling
Beiträge: 4
Registriert: 21. Sep 2013 15:25

Re: Fehler in der Lösung zur Übungsaufgabe

Beitrag von mg_92 »

oek hat geschrieben:... zeigt i3 doch noch auf die 54 also auf n und noch nicht auf n+1 oder?
Somit ist der Algorithmus noch nicht beendet und man müsste noch den Step 3.1 und 3.3 der Implementation des Induction Steps durchführen oder irre ich mich?
Ich würde sagen das i3 niemals am ende einer Iteration auf die 54 zeigen wird, da die 54 richtig sortiert ist und dann sowohl in Induction Step 2 als auch im Induction Step 3 jeweils die indizes soweit hochgezählt werden bis sie ihre Endposition erreicht haben ODER sie auf einem falschen Element stehen. Da die 54 richtig ist wird i3 sofort weiter auf n+1 gesetzt.

oek
Erstie
Erstie
Beiträge: 21
Registriert: 11. Sep 2013 08:42

Re: Fehler in der Lösung zur Übungsaufgabe

Beitrag von oek »

mg_92 hat geschrieben:
oek hat geschrieben:... zeigt i3 doch noch auf die 54 also auf n und noch nicht auf n+1 oder?
Somit ist der Algorithmus noch nicht beendet und man müsste noch den Step 3.1 und 3.3 der Implementation des Induction Steps durchführen oder irre ich mich?
Ich würde sagen das i3 niemals am ende einer Iteration auf die 54 zeigen wird, da die 54 richtig sortiert ist und dann sowohl in Induction Step 2 als auch im Induction Step 3 jeweils die indizes soweit hochgezählt werden bis sie ihre Endposition erreicht haben ODER sie auf einem falschen Element stehen. Da die 54 richtig ist wird i3 sofort weiter auf n+1 gesetzt.
Stimmt du hast recht das hab ich ganz vergessen. Also hab ich es genauso wie biz und der Algo terminiert nach i=5 :mrgreen:

biz
Erstie
Erstie
Beiträge: 19
Registriert: 4. Okt 2010 13:10

Re: Fehler in der Lösung zur Übungsaufgabe

Beitrag von biz »

oek hat geschrieben:Also ich habe auch die selbe Reihenfolge wie biz nur zeigt i3 doch noch auf die 54 also auf n und noch nicht auf n+1 oder?
Somit ist der Algorithmus noch nicht beendet und man müsste noch den Step 3.1 und 3.3 der Implementation des Induction Steps durchführen oder irre ich mich?
Oh, du hast Recht. Mein i3 ist leicht verrutscht, es sollte auf die Positon nach der 54 zeigen. Hab das mal korrigiert.

biz
Erstie
Erstie
Beiträge: 19
Registriert: 4. Okt 2010 13:10

Re: Fehler in der Lösung zur Übungsaufgabe

Beitrag von biz »

Hi,

da in der Musterlösung zur Übungsaufgabe die Lösung zur Aufgabe 7 fehlt ist hier noch meine Lösung dazu.
Ich bin mir allerdings nicht sicher ob ich das "rekursiv löschen" richtig verstanden, habe da bei mir auch alle Kinder der Knoten <15 oder >45 gelöscht werden.

Code: Alles auswählen

    public static int remove(BinaryTree node){
        if( node == null) return 0;
        int r = 0;
        if(node.left == null){
            //do nothing
        }else if( node.left.key < 15 || node.left.key > 45){
            node.left = null;
            r++;
        }else{
            r += remove(node.left);
        }
        
        if(node.right == null){
            //do nothing
        }else if( node.right.key < 15 || node.right.key > 45){
            node.right = null;
            r++;
        }else{
            r += remove(node.right);
        }
        return r;
    }

Antworten

Zurück zu „Archiv“