Rekursion Aufgabe

Aufrufe: 109     Aktiv: 1 Woche, 1 Tag her

0

Hi,

Leider verstehe hier nicht ganz, was ich einsetzen soll. Wenn ich UNKNOWN(A,1,8) aufrufe, soll es eine Zahl ausgeben. Ich weiss nicht wie ich beginnen soll bzw. welche Zahl ich einsetzen soll.

enter image description here

Hier ist mein Ansatz: enter image description here

Verstehe nicht, was ich im letzten else zurückgeben soll, kann ja nicht richtig vergleichen?enter image description here

gefragt 2 Wochen her
sayuri
Student, Punkte: 42

 
Kommentar schreiben Diese Frage melden
2 Antworten
1

Du kannst die Lösung nicht mit dem ersten Aufruf von UNKNOWN finden, sondern musst UNKNOWN immer wieder mit neuen Parametern aufrufen.

Im Prinzip wird der Ablauf der "Elternfunktion" pausiert, bis die "Kindfunktionen" einen Wert zurückgeben können.

Ich gehe davon aus, das die Indizes von 1-8 laufen und nicht wie gewohnt von 0-7 für 8 Einträge. Darauf deutet das A[1...8] hin.

Zur Vereinfachung ist: u( l, r ) => UNKNOWN( A, l, r ) und max( a, b ) die größere Zahl von a und b

Die ersten paar Aufrufe wären dann:

u( 1, 8 ) => max( u( 1, 3 ), u( 4, 8 ) ) // q=3
  u( 1, 3 ) => max( u( 1, 1), u( 2, 3 ) ) // q=1
    u( 1, 1 ) => 6
    u( 2, 3 ) => max( u( 2, 2 ), u( 3, 3 ) ) // q=2
     u( 2, 2 ) => 4
     u( 3, 3 ) => 2
    u( 2, 3 ) => max( 4, 2 ) => 4
  u( 1, 3 ) => max( 6, 4 ) => 6
//  u( 4, 8 ) geht dann analog zu  u( 1, 3 )
geantwortet 1 Woche, 3 Tage her
ds
Punkte: 30
 

Hey ds, vielen herzlichen Dank. Endlich verstehe ich es!!!

  ─   sayuri 1 Woche, 3 Tage her
Kommentar schreiben Diese Antwort melden
1

Ich habe den Algorithmus mit den gegebenen Werten mal ausgeführt. Bei mir kommt eine ArrayIndexOutOfBoundsException, da der letzte Index im Array, auf den man zugreifen kann 7 ist, die Funktion jedoch mit r=8, also einem ungültigen Index aufgerufen wird!

geantwortet 2 Wochen her
daniel.kuenkel
Schüler, Punkte: 270
 

Also funktioniert es gar nicht?

  ─   sayuri 2 Wochen her

Mit diesen Argumenten funktioniert es nicht!

  ─   daniel.kuenkel 2 Wochen her

Ich hoffe, dass ich mich nicht vertippt habe, da ich das Programm nochmal nachgeschrieben haben, um es zu testen ... jedenfalls kam bei mir eine Exception!

  ─   daniel.kuenkel 2 Wochen her

alles klar, vielen herzlichen Dank!

  ─   sayuri 2 Wochen her

habs auch versucht, aber bei mir sieht es ein bisschen anders aus...

  ─   sayuri 1 Woche, 2 Tage her

Wie sieht es bei dir aus?

  ─   daniel.kuenkel 1 Woche, 2 Tage her

Habs mal hochgeladen!

  ─   sayuri 1 Woche, 1 Tag her
Kommentar schreiben Diese Antwort melden