Seite 1 von 1

Theorietestat #2b: countingRecursivePixelsOfArea2 Errata

Verfasst: 31. Mai 2017 15:56
von OAEP
In Zeile 29 sollte statt visited[heigthCoordinate][widthCoordinate] == false
eher visited[heigthCoordinate][widthCoordinate] stehen. Derzeit terminiert der Algorithmus einfach direkt mit 0.

Re: Theorietestat #2b: countingRecursivePixelsOfArea2 Errata

Verfasst: 31. Mai 2017 17:20
von invariant
Hallo,

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

Gruß

Re: Theorietestat #2b: countingRecursivePixelsOfArea2 Errata

Verfasst: 2. Jun 2017 22:09
von hallo6
Hat jemand eine Denkanstoß, wie man die Invariante wählen sollte damit der Beweis funktioniert?
Bekomme das nicht hin.

Danke für jegliche Hilfe :)

Re: Theorietestat #2b: countingRecursivePixelsOfArea2 Errata

Verfasst: 5. Jun 2017 17:57
von invariant
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ß

Re: Theorietestat #2b: countingRecursivePixelsOfArea2 Errata

Verfasst: 12. Jun 2017 15:35
von studenthoch80
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ß

Re: Theorietestat #2b: countingRecursivePixelsOfArea2 Errata

Verfasst: 12. Jun 2017 17:42
von invariant
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ß