Divide & Conquer Prinzip um Maximum eines Arrays zu berechnen

Question

Sei A[1,..,n] ein Array mit n Zahlen. Formulieren Sie einen rekursiven Divide & Conquer-Algorithmus in Pseudocode um das Maximum der Werte im Array A zu berechnen.

Mein Ansatz:

if (begin < end) {
 int middle = (int) ((begin + end) / 2);
 split(a, begin, middle);
 split(a, middle + 1, end);
 max(a, begin, middle, end);
 }

Das hier ist übernommen von Merge-Sort wie jedoch die Methode max aussehen soll um das maximum zu berechnen weiss ich nicht. Hilfe wäre toll.

LG

Answer 1

Dein Ansatz ist nicht verkehrt. Eine funktionierende Implementierung in Java sieht folgendermaßen aus:

 private static int find_max(final int[] A, int a, int b) {
    if (b - a == 1) {
       if (A[a] > A[b]) {
          return A[a];
       } else {
          return A[b];
       }
    } else if (a == b) {
    return A[a];
  }
    return Math.max(find_max(A, a, (a + b) / 2), find_max(A, (a + b) / 2 + 1, b));
 }

Die Funktion kannst Du wie folgt aufrufen:

 public static void main(final String... args) {
    final int[] array = { 1, 7, 6, 9, 1, 2, 8 };
    System.out.println(find_max(array, 0, array.length - 1));
 }

Deine Aufgabe ist es nun, daraus Pseudo-Code zu formulieren :-) Das Prinzip passt!

Comments

Danke für deine Antwort hat mir sehr geholfen hätte aber doch noch eine Frage dazu. Wie wird a inkrementiert das verstehe ich nicht? a ist immer 0 beim Aufruf wird jedoch wenn die Rekursion terminiert hat inkrementiert versteh nur nicht wie? (Erstes Teilarray)

---

a ist immer 0 beim Aufruf wird jedoch wenn die Rekursion terminiert hat inkrementiert versteh nur nicht wie?

a ist beim rekursiven Aufruf nicht immer 0. Schau Dir hierfür die folgende Codezeile an:

return Math.max(find_max(A, a, (a + b) / 2), find_max(A, (a + b) / 2 + 1, b));

Die zweite Rekursion erhält als zweiten Parameter (a) den  Wert (a + b) / 2 + 1. Auf diese Art kommt die Erhöhung von a zustande. Das Wachstum des Parameters kann durch einen einfachen Sysout dargestellt werden.

0
0
0
2
4
4
6
9

Hilft Dir das weiter?

---

Ja schön langsam verstehe ich das. Hilft mir! Ich müsste die genau Abarbeitung der Rekursionen verstehen. Die erste Rekursion ist für die erste Hälfte zuständig die zweite also für die zweite Hälfte. Das heißt die Aufrufe mit 3 mal a = 0  ist erste Rekursion danach folgt die zweite Rekursion? Wobei a = 2 noch im ersten Teilarray einen wert zurückgibt

else if (a == b)

 Steh wh am Schlauch..

LG