Methoden Zweifach rekursive Methode - Addition

[triban1337]

Hey Leute ich brauche eure Hilfe,
Heute habe ich in der Uni eine Übungsaufgabe bekommen bei der ich nicht so recht weiß wie ich anfangen soll. Und zwar soll ich eine Zweifach rekursive Methode [ int summe(int[] v, int von, int
bis) ] programmieren welche die Summe der Werte im Feld "v" von Index "von" bis Index "bis" berechnet. Wenn der Basisfall erreicht wird der zugehörige Wert zurückgeliefert, sonst wird der Indexbereich in zwei möglichst gleich große Teilbereiche zerlegt, die Funktion ruft sich selbst für jeden
dieser beiden Teilbereiche auf und verarbeitet die Ergebnisse. Zudem soll ich eine Applikation programmieren, die eine Folge ganzer Zahlen auf der Kommandozeile übergeben bekommt, diese in einem Feld speichert, das komplette Feld mit der Methode summe addiert und das Ergebnis ausgibt.

Als Hinweis wurde mir dieser Code gegeben:

class Summe {
    public static void main (String[] args) {
	int n = args.length;
	if ( n == 0) {
	    System.out.println("Aufruf: Summe <zahl1> ... <zahlN>");
	    return; // verlasse Methode sofort
	}
	int[] z = new int[n];
	for (int i = 0; i < n; i++)
	    z[i] = Integer.parseInt(args[i]);
	int s = 0; 
	for (int i = 0; i < n; i++)
	    s = s + z[i];
	System.out.println("Summe: " + s);
    }
}

Vielen vielen Dank im Vorraus,
Triban

 

[Flown]

Ähm was ist deine konkrete Frage dazu?

 

[triban1337]

Wie ich anfangen soll ich weiß nichts mit zweifach rekursiv anzufangen

 

[Flown]

Ich wollt dir eigentlich mal mit einem Pseudocode aushelfen, aber das wäre zu einfach, da schon alles dastehen würde.
Darum helf ich dir mit Prosa aus:

Überprüfe ob die Differenz "von" und "bis" kleiner gleich 1 ist, wenn
... ja dann gib das Element an der Stelle "von" des Arrays zurück
... wenn nein, bestimme die Mitte von "von" und "bis" und starte die Rekursion mit den neuen Parameter "von" ... Mitte und Mitte bis "bis" und addiere das Ergebnis. Gib das Ergebnis zurück!

 

[triban1337]

ja aber ich würde nur "If" benutzen, also iwie so:

---------------------------------------------------------

if differenz kleiner/gleich 1 {

system.out.println(Element an der Stelle "von" des Arrays)

} else {

mitte von "von" und "bis" bestimmen

Methodenaufruf(NeuerParameter)
}

-------------------------------------------------------------

so hatte ich es im kopf natürlich mit den richtigen befehlen. Und voher die Zahlen in einen Array einlesen und die Methode aufrufen.

 

[Flown]

Ja zweifach rekursiv heißt nur das du dann zweimal die selbe Methode in der Methode aufrufst. Das heißt einmal mit dem unteren und einmal mit dem oberen Bereich!

Jetzt hast du deinen Pseudocode soweit gebracht, jetzt übersetz es in Java und dann helf ich dir gerne wieder weiter.

 

[triban1337]

Ich kapier es einfach garnicht.. ich bekomme es nicht hin versuche es schon seit 10:00Uhr könntest du mir evtl ein Grundgerüst geben ? Ich weiss nicht wie ich das Feld "v" bzw das Array "v" in 2 etwa gleich große hälften Teilen soll..

 

[Flown]

Du hast dir doch selbst ein Grundgerüst gegeben, wo liegt das Problem?

if(bis - von <= 1) {
  //gib v an der Stelle "von" zurueck
} else {
  int mid = (von + bis) >> 1;
  return /* Methode (von bis mitte) + Methode (mitte bis "bis") */
}

Wow und das ist genau das gleiche was du oben hattest!

 

[triban1337]

Ja das ist das was ich geschrieben habe als Java-Code aber ich bekomme die Aufgabe damit einfach nicht gelöst..

 

[Flown]

public static int sum(int[] v, int von, int bis) {
   if(bis - von <= 1) {
    return ???;
   } else {
    int mid = (von + bis) >> 1;
    return sum(v, ???, ???) + sum(v, ???, ???);
   }
}

Also wenns jetzt nicht klappt, dann fang gaaaanz von vorne mit Grundlagen an!

 

[LimK]

Hallo,
dieselbe Aufgabe war auch dieses Jahr dran. So zur Info die Aufgabe kommt in der Informatik 1 Übung an der Uni Göttingen dran. *SPOILER ALARM für diejenigen, die diese Aufgabe selber lösen wollen!*


Jetzt zu meiner Frage. Ich habe diese Aufgabe gelöst, weiß aber nicht warum sie funktioniert haha Habe alles selber programmiert aber ich habe durch rumprobieren am Basisfall(Endbedingung), viel gelernt wie eine Rekursion funktioniert bzw. wann sie nicht funktioniert. Jedoch konnte ich nicht an der Logik verstehen warum im if-return v[von] UND v[bis] als summe ausgegeben werden muss. Ich hatte am Anfang nur v[bis] angegeben und daher bemerkt dass das erste Feld vom Array nicht mitsummiert wurde. Kann mir das jemand erklären? Es muss einfach sooo banal logisch sein aber irgendwie liege ich gerade etwas flach...

 

[LimK]

Ach funktioniert doch nicht... haha da war ich wohl zu voreilig...