Theorietestat #2b: countingRecursivePixelsOfArea2 Errata

OAEP
Neuling
Neuling
Beiträge: 4
Registriert: 31. Mai 2017 15:50

Theorietestat #2b: countingRecursivePixelsOfArea2 Errata

Beitrag von OAEP » 31. Mai 2017 15:56

In Zeile 29 sollte statt visited[heigthCoordinate][widthCoordinate] == false
eher visited[heigthCoordinate][widthCoordinate] stehen. Derzeit terminiert der Algorithmus einfach direkt mit 0.

invariant
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 6. Mai 2017 19:01

Re: Theorietestat #2b: countingRecursivePixelsOfArea2 Errata

Beitrag von invariant » 31. Mai 2017 17:20

Hallo,

Das ist korrekt, die Offenen Übungsaufgaben werden so schnell wie möglich korrigiert.

Gruß

hallo6
Erstie
Erstie
Beiträge: 14
Registriert: 4. Mai 2017 10:36

Re: Theorietestat #2b: countingRecursivePixelsOfArea2 Errata

Beitrag von hallo6 » 2. Jun 2017 22:09

Hat jemand eine Denkanstoß, wie man die Invariante wählen sollte damit der Beweis funktioniert?
Bekomme das nicht hin.

Danke für jegliche Hilfe :)

invariant
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 6. Mai 2017 19:01

Re: Theorietestat #2b: countingRecursivePixelsOfArea2 Errata

Beitrag von invariant » 5. Jun 2017 17:57

Hallo,

gleich vorneweg - ist nicht ganz so einfach also nicht verzweifeln ;)

Überlegen Sie sich vielleicht zuerst wie ihr Induktionsparameter aussehen könnte.
Was ändert sich bei ihren Eingabeparametern in jedem Rekursionsschritt? (Stichwort Variante)
Zum einen ändern sich x oder y zum anderen wird die Anzahl der besuchten Elemente um eins erhöht.

Jetzt meine Empfehlung an dieser Stelle:

Beschreiben wir die Menge der Pixel im Canvas als C und die Menge der besuchten Pixel in in visited (also die für die visitied = true) als V, dann könnten wir folgendes machen:

Der rekursive Aufruf mit |C\V| >= 0 liefert das korrekte Ergebnis.

An dieser Stelle sollten wir noch überlegen, was das korrekte Ergebnis ist:

Der Algorithmus soll die Anzahl der Pixel zurückgeben, die die selbe Farbe haben. Dabei betrachtet der rekursive Aufruf aber nur die Elemente die nicht schon in visited auf true gesetzt waren. Da ein Pixel nur auf true gesetzt wird, wenn er die richtige Farbe hat ist das die Anzahl der Pixel die nach dem rekursiven Aufruf zusätzlich auf true gesetzt wurden also |V'\V| (Wenn V' an dieser Stelle die Menge der Pixel bezeichnet, die nach dem rekursiven Aufruf besucht wurden).


Mit dem Rest des Beweises würde ich Sie an dieser Stelle gerne alleine lassen.

Ich hoffe die Antwort hat geholfen.

Gruß

studenthoch80
Neuling
Neuling
Beiträge: 9
Registriert: 15. Mai 2017 16:16

Re: Theorietestat #2b: countingRecursivePixelsOfArea2 Errata

Beitrag von studenthoch80 » 12. Jun 2017 15:35

Hallo,

ich habe den Unterschied zwischen V' und V noch nicht richtig verstanden.

In der Hörsaalübung vom vergangenen Freitag gab es eine ähnlich Aufgabe, ColoringCanvasInBackgroundColor2Recursive.

Dort steht in der Lösung "V ist die Menge der besuchten Pixel im Eingabeparameter visited". Und zu V' "Menge der Pixel, die im Eingabeparameter visited nach dem rekursiven Aufruf auf true gesetzt sind..."

Ich verstehe den Unterschied nicht.

Kann mir einer helfen?

Danke & Gruß

invariant
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 6. Mai 2017 19:01

Re: Theorietestat #2b: countingRecursivePixelsOfArea2 Errata

Beitrag von invariant » 12. Jun 2017 17:42

Hallo,

stellen Sie sich das folgendermaßen vor:

Ihr rekursiver Aufruf erhält als Eingabeparameter visited - in diesem Array sind gewisse Pixel auf true gesetzt, das sind die besuchten Pixel V.
Nachdem ihr rekursiver Aufruf terminiert wurden u.U. weitere Pixel besucht - in visited auf true gesetzt - das entspricht V'.

Der Unterschied zwischen V' und V sind also, dass in V' zusätzlich die Elemente enthalten sind, die im rekursiven Aufruf besucht wurden.

Hoffe das hat weitergeholfen.

Gruß

Antworten

Zurück zu „Archiv“