Kan iemand mij helpen dit op te lossen ?

[ThEScReW]

Hallo, mijn eerste post hier en direct al een java probleem Ik heb enkele oefenvraagstukken van java waar ik echt geen raad mee weet, graag jullie hum^

Dank

Wat doet onderstaande methode voor een in te geven string s. (bv “An”)

z = {“Jan”, “Pieter”, “Sofie”, “Liesbeth”, “Sam”, “Tom”, Stijn”, “An”, “Dieter”}
.....
public int doe (String z[ ], String s, int begin, int einde)
{
if( begin >= einde ) return;
int m = (begin+einde)/2;
if( z[m].compareTo(s) < 0 ) return doe(z, s, m+1, einde);
if( z[m].compareTo(s) > 0 ) return doe(z, s, begin, m);
return m;
}

Geef de uiteindelijke waarde van m.

 

[Palmpje]

Goh,

Dat lijkt me een binaire zoekboom. Ken geen Java en de eerste aanroep van doe() ontbreekt. Maar het lijkt me dat de index van "An" als uiteindelijk resultaat komt. Waarom... dat mag je zelf uitzoeken, Huiswerkopgave tenslotte ;-)

 

[snabbi]

Het is een zoek algoritme:

Stel je hebt al een gesorteerde lijst:

aap,boom,brand,cola,*****,groente,slang en je wilt weten waar groente staat (hoeveelste woord).

Eerste keer doorlopen:

aanroep is: z={aap,boom,brand,cola,*****,groente,slang}
s = slang
begin = 1
eind = 7 (woorden)

if( begin >= einde ) return; <<-- begin is kleiner dan eind dus we gaan verder

int m = (begin+einde)/2 <-- m = (1+7)/2 = 4

woord 4 is cola. slang komt later in het alfabet dan cola dus de compareto geeft een < 0

Wat de functie terug gaat geven is de uitkomst van:
doe(z, s, m+1, einde); (dus de aanroep wordt nu voor begin 4+1 = 5 en einde blijft 7.)

Gevolg hiervan is dat we in de volgende iteratie alleen nog maar focussen op woorden 5,6 en 7.

Tweede recursieve aanroep:
Begin is nog steeds kleiner dan eind, dus we gaan verder.

(5+7)/2 = 6.
woord 6 is groente. De s van slang zit verder dan de g van groente dus we krijgen weer de < 0 in compareto.

doe(z, s, m+1, einde); (waarbij begin wordt 6 en eind 7)

Derde recursieve aanroep:
nu zal m gelijk worden aan 13/2 afgerond 7. Woord 7 is slang. Compareto geeft nu precies 0. Daarom zal de waarde van m worden teruggegeven aan de 2de iteratie.

Tweede recursieve iteratie:
Resultaat van de formule was 7 dus hij geeft 7 terug aan de eerste iteratie.

Eerste recursieve iteratie:
Resultaat van de formule was 7 dus hij geeft 7 terug aan de aanroep van de functie.