15. Rekurzió III

Keresések rekurzív megvalósítása:

• Tegyük fel, hogy a sorozatunk nem rendezett
• Ha az első elem nem felel meg a keresett elemnek (Y) akkor hívjuk meg újra a függvényt, de már csak a második elemtől az utolsó elemig.
• E jelöli a vizsgálandó sorozatrész első elemét, U pedig az utolsó elem indexét
• A függvény visszatérési értéke legyen 0 ha Y nem található a sorozatban. Ha létezik ilyen elem, akkor X-beli indexét kell visszaadni annak az elemnek, melynek értéke megegyezik Y-nal.

Pszeudokód:

Függvény Keresés(X, E, U, Y)

Ha E>U akkor

return(0)

különben

Ha X[E]=Y akkor

return(E)

különben

return(Keresés(X,E+1,U,Y))

Elágazás vége

Elágazás vége

Függvény vége

Logaritmikus keresés:

Ebben az esetben tegyük fel, hogy növekvően rendezett a sorozatunk

Pszeudokód:

Függvény Keresés(X, E, U, Y)

Ha E>U akkor

return(0)

különben

K<-Egészrész((E+U)/2)

Elágazás

X[K] = Y esetén

return(K)

X[K]<Y esetén

return(Keresés(X, K+1,U,Y))

X[K]>Y esetén

return(Keresés(X,K-1,U,Y))

Elágazás vége

Elágazás vége

Függvény vége

Felhasznált Irodalom: Sergyán Szabolcs – Programozás I – 10. előadás diasor

Kommentek

comments

Powered by Facebook Comments