[Geklärt]Merge: Bug wenn i=23

Bei Postings zu Algorithmus X lassen Sie Ihren Betreff bitte mit
"X: " beginnen, bei allgemeinen Postings zu Nabla bitte mit "Nabla: ", jeweils gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Algorithmus X lassen Sie Ihren Betreff bitte mit
"X: " beginnen, bei allgemeinen Postings zu Nabla bitte mit "Nabla: ", jeweils gefolgt von einer möglichst präzisen Überschrift, danke!
knexfan0011
Neuling
Neuling
Beiträge: 2
Registriert: 19. Sep 2016 17:23

[Geklärt]Merge: Bug wenn i=23

Beitrag von knexfan0011 » 19. Sep 2016 17:32

Ich hab gerade beim Üben bei Merge eine Aufgabe mit i=23 bekommen und und laut nabla müssen die Zähler I1=12 und I2=10 sein, aber ich bin der Meinung sie müssten I1=12 und I2=11 sein, also die Länge der beiden Listen

Hier einmal meine Abgabe und die vorgeschlagene nabla Lösung:
http://prntscr.com/cjuklx

Und hier die Schritt für Schritt Lösung der letzten paar Iterationen.
http://prntscr.com/cjukxc

Hier sieht man, dass weder I1 noch I2 von Iteration 22 auf Iteration 23 erhöht werden.
Bisher galt auch immer bei Merge I1 + I2 = i, welches hier auch nicht mehr gilt.
Zuletzt geändert von knexfan0011 am 20. Sep 2016 02:55, insgesamt 1-mal geändert.

paprikawuerzung
Mausschubser
Mausschubser
Beiträge: 80
Registriert: 23. Mär 2014 23:33

Re: Merge: Bug wenn i=23

Beitrag von paprikawuerzung » 19. Sep 2016 18:59

Aus Facebook, gleicher Fall:
Die Liste l2 war nach i=22 bereits voll abgearbeitet, also wird (in i=23?) der Rest von l1 einfach an die Ausgabesequenz gehängt und man ist fertig, also ändert sich der Zeiger nicht und bleibt bei 11.

Alexj1988
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 23. Sep 2011 00:28

Re: Merge: Bug wenn i=23

Beitrag von Alexj1988 » 20. Sep 2016 01:28

Das ist das korrekte verhalten...

https://wiki.algo.informatik.tu-darmstadt.de/Merge
Variant: i_1 + i_2 increases by 1 (prior to termination); neither i_1 nor i_2 decreases.
Dann noch induktion step fall 1 und 2 mal durchlessen.


mfg Alex

knexfan0011
Neuling
Neuling
Beiträge: 2
Registriert: 19. Sep 2016 17:23

Re: Merge: Bug wenn i=23

Beitrag von knexfan0011 » 20. Sep 2016 02:53

Achso, also wenn eine Liste fertig ist, dann wird einfach der Rest der anderen Angehängt, ohne den Pointer zu erhöhen, danke

Antworten

Zurück zu „AuD: Arbeit mit Nabla“