0 Daumen
289 Aufrufe

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!!

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community