Rekursion Aufgabe

Aufrufe: 257     Aktiv: 15.01.2021 um 06:52

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

Diese Frage melden
gefragt

Student, Punkte: 64

 
Kommentar schreiben
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 )
Diese Antwort melden
geantwortet

Punkte: 30

 

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

  ─   sayuri 13.01.2021 um 14:32

Kommentar schreiben

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!

Diese Antwort melden
geantwortet

Schüler, Punkte: 385

 

Also funktioniert es gar nicht?

  ─   sayuri 09.01.2021 um 22:14

Mit diesen Argumenten funktioniert es nicht!

  ─   daniel.kuenkel 09.01.2021 um 22:19

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 09.01.2021 um 22:20

alles klar, vielen herzlichen Dank!

  ─   sayuri 09.01.2021 um 22:30

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

  ─   sayuri 14.01.2021 um 21:26

Wie sieht es bei dir aus?

  ─   daniel.kuenkel 15.01.2021 um 01:34

Habs mal hochgeladen!

  ─   sayuri 15.01.2021 um 06:52

Kommentar schreiben