Hallo,
ich wäre dankbar wenn mir jemand einen Lösungsansatz zur folgenden Aufgabe bieten kann... :
Gegeben sei ein n x n-Schachbrett als 2-dimensionales Array. Jedes der
Felder des Schachbretts ist mit einer Zahl beschriftet, wobei die Zahlen
paarweise verschieden sind. Ein lokales Minimum ist ein Feld so, dass jedes
seiner bis zu 8 Nachbarfelder mit einer größeren Zahl beschriftet ist.
a) Beschreiben Sie einen effizienten Algorithmus, der ein (beliebiges)
lokales Minimum bestimmt und dessen Koordinaten ausgibt. Erläu-
tern Sie, warum Ihr Algorithmus korrekt ist. (Ein \(\theta(n^2)\)) -Algorithmus
wird mit 0 Punkten bewertet! Insbesondere dürfen also nicht alle Fel-
der angeschaut werden.)
b) Schreiben Sie den Pseudo-Code zu Ihrem Algorithmus.
c) Bestimmen Sie die Anzahl an Vergleichen (in \(\theta\)-Notation), die Ihr
Algorithmus (im Worst-Case) benötigt.
Danke!!
