Verständnisprobleme bei Arrays

[juliaa]

Hallo zusammen,
ich habe folgenden code, kann aber leider nicht nachvollziehen was das Programm wann macht um auf das Ergebnis zukommen..

class Klausur {
		
		public static void main (String[] args){
			   
		int []array = new int [] {0,5,1,2,7,4,3,9};
		System.out.println ("MAX: "+arraymax(array,0,array.length-1));
		}
		public static int arraymax (int []array, int untergrenze, int obergrenze){
			if (obergrenze-untergrenze<=1){
				return Math.max (array[obergrenze],array[untergrenze]);
				
			}
	else {
		return Math.max (arraymax(array,untergrenze,(obergrenze+untergrenze)/2),arraymax (array,(obergrenze+untergrenze)/2+1,obergrenze));
	}
		}

}

meine Hauptprobleme
1. Welche bedeutung hat das array.length-1 hier? heißt es das nacheinander von rechts nach links die Zahlen des Arrays in der rekursion als Obergrenze eingesetzt werden??
2. Welche Schritte macht das Programm genau in der if- und else- Bedingung?
Ich möchte gerne das System des Programms verstehen damit ich es auch selber auf andere Beispiele anwenden kann, es wäre super wenn mir jemand helfen könnte.
Gruß
Julia

 

[Timothy Truckle]

1. Welche bedeutung hat das array.length-1 hier? heißt es das nacheinander von rechts nach links die Zahlen des Arrays in der rekursion als Obergrenze eingesetzt werden??

Nein.
Die Methode

arraymax

erwartet gültige Indexe. Die fangen in Java bei 0 an.

Array.length

gibt dagegen die Anzahl der Elemente an, die beginnt mit 1. In einem Array mit der Länge 3 gibt es also die Indexe 0, 1 und 2 (bitte nachzählen).
Der höchste gültige Index in einem Array ist damit Array.length -1 (weil 3-1=2 ist). Das hat mit der Richtung, in der das Array durchlaufen wird noch n ichts zu tun.

2. Welche Schritte macht das Programm genau in der if- und else- Bedingung?

Das

if

stellt fest, ob die Indexe in der "richtigen" Reihenfolge übergeben wurden, d.h. ob der erste kleiner als der zweite ist. Wenn das so ist wird der höchste Wert in diesem Abschnitt des Arrays ermittelt.

Wenn nicht wird scheinbar der höchste Wert außerhalb des Abschnittes ermittelt...

bye
TT

 

[hüteüberhüte]

Hi juliaa,

    public static void main(String[] args) {
        int[] array = new int[]{0, 5, 1, 2, 7, 4, 3, 9};
        // Array-Deklaration und -Initialisierung

        System.out.println("MAX: " + arraymax(array, 0, array.length - 1));
        // Ausgabe des Aufrufs von arraymax auf der Standardausgabe
        // (und String-Konkatenation)
    }

    /**
     * Rekursive Methode, die mit dem linken und rechten Teilarray
     * erneut aufgerufen wird, und das Maximum bestimmt.
     * 
     * @param array
     * @param untergrenze
     * @param obergrenze
     * @return Maximum des Arrays array zwischen unter- und obergrenze (inklusive)
     */
    public static int arraymax(int[] array, int untergrenze, int obergrenze) {
        if (obergrenze - untergrenze <= 1) {
            return Math.max(array[obergrenze], array[untergrenze]);
        } else {
            return Math.max(
                    arraymax(array, untergrenze, (obergrenze + untergrenze) / 2),
                    arraymax(array, (obergrenze + untergrenze) / 2 + 1, obergrenze) );
        }
    }

meine Hauptprobleme
1. Welche bedeutung hat das array.length-1 hier? heißt es das nacheinander von rechts nach links die Zahlen des Arrays in der rekursion als Obergrenze eingesetzt werden??

array.length-1

gibt den Index des letzten Array-Elements zurück.

arraymax "halbiert" diesen Bereich und ruft erneut auf, mit dem "linken" und "rechten Bereich".

2. Welche Schritte macht das Programm genau in der if- und else- Bedingung?
Ich möchte gerne das System des Programms verstehen damit ich es auch selber auf andere Beispiele anwenden kann, es wäre super wenn mir jemand helfen könnte.

Sagen wir, ein Array beinhaltet 6 Elemente:

Aufruf 1: 0 bis 5,---Rückgabe max(max(max(array[0], array[1]), max(array[2], array[2])), max(max(array[3], array[4]), max(array[5], array[5])) ),
Aufruf 2: 0 bis 2,--Rückgabe max(max(array[0], array[1]), max(array[2], array[2])),
Aufruf 3: 0 bis 1, Rückgabe max(array[0], array[1]),
Aufruf 4: 2 bis 2, Rückgabe max(array[2], array[2]),
Aufruf 5: 3 bis 5,--Rückgabe max(max(array[3], array[4]), max(array[5], array[5])),
Aufruf 6: 3 bis 4, Rückgabe max(array[3], array[4]),
Aufruf 7: 5 bis 5, Rückgabe max(array[5], array[5]).

Verstehst du jetzt durch dieses Beispiel, wie Rekursion funktioniert?

liebste Grüße LIIII

 

[hüteüberhüte]

Das ganze hätte man auch etwas einfacher formulieren können:

    public static int arraymax2(int[] array, int from) {
        if (from == array.length - 1) {
            return array[from];
        }
        return Math.max(array[from], arraymax2(array, from + 1));
    }

Von der Laufzeit her beißt sich da nichts.

Wenn du mehr erfahren möchtest, google mal nach "divide and conquer top down approach". Dann gelangst du z.B. zu so einer schlauen Seite (nicht ironisch gemeint):

Top-Down Algorithms: Divide-and-Conquer

In this section we discuss a top-down algorithmic paradigm called divide and conquer . To solve a given problem, it is subdivided into one or more subproblems each of which is similar to the given problem. Each of the subproblems is solved independently. Finally, the solutions to the subproblems are combined in order to obtain the solution to the original problem.

Divide-and-conquer algorithms are often implemented using recursion. However, not all recursive functions are divide-and-conquer algorithms. Generally, the subproblems solved by a divide-and-conquer algorithm are non-overlapping.

Grüßle