Tanulási útmutató
Összefoglalás
A tananyag vége felé közeledve kitekintünk a továbblépési lehetőségekre. Olyan feladatokat nézünk át, amelyek alapvetően más tantárgyak témakörébe tartoznak, de a Programozási alapismeretek tantárgy eszközkészletével tökéletesen megoldhatóak.
Ebben a leckében olyan speciális keresési feladattal foglalkozunk, ahol egy adott értékű elem megkeresése a feladat egy rendezett sorozatban.
Követelmény
A lecke végére a hallgatónak ismernie kell a különböző keresési algoritmusok filozófiáját rendezett sorozatok esetén, a megfelelő algoritmusokat értelmeznie, valamint előállítania kell tudni.
Önállóan megoldható feladatok
Keresés rendezett sorozatban
Lineáris keresés rendezett sorozatban
Ebben az esetben tehát adott egy rendezett sorozat, amelyben egy adott értékű elem sorszámát kell meghatározni, ha az benne van a sorozatban.
Bemenet
N:Egész, X:Tömb[1..N:Valami], Y:Valami,
T:Valami→Logikai
Kimenet
VAN:Logikai, SORSZ:Egész
Előfeltétel
N≥0 és RendezettE(X)
Utófeltétel
VAN ≡ (∃i(1≤i≤N): X[i]=Y) és
VAN → 1≤SORSZ≤N és X[SORSZ]=Y
Próbáljuk először a lineáris keresést alkalmazni e feladat megoldására! A feladat specialitásából következik, hogy ha egy, a keresett elemnél nagyobb értékű elemet találunk, akkor a keresett elem már biztosan nem fordulhat elő, a keresést be lehet fejezni. Emiatt a program utófeltétele a következő lesz:
Utófeltétel
VAN ≡ (∃i (1≤i≤N): X[i]=Y) és
VAN → 1≤SORSZ≤N és X[SORSZ]=Y és
∀i(1≤i<SORSZ): X[i]<Y
Keresés(N,X,Y,VAN,SORSZ):
I:=1
Ciklus amíg I≤N és X[I]<Y
I:=I+1
Ciklus vége
VAN:=(I≤N) és X[I]=Y
Ha VAN akkor SORSZ:=I
Eljárás vége.
Nézzük meg, hogy e keresést milyen hasonlítás-szám jellemez!
- Minimum: 1
- Átlag: (N+1)/2
- Maximum: N
Az átlagos hasonlítás-számban szereplő lineáris összefüggés miatt hívják e keresést lineáris keresésnek.
Logaritmikus keresés
A rendezettséget (és az indexelhetőséget) másképpen is kihasználhatjuk. Vizsgáljuk meg első lépésben a sorozat középső elemét! Ha ez a keresett elem, akkor készen vagyunk. Ha a keresett elem ennél kisebb, akkor csak az ezt megelőzőek között lehet, tehát a keresést a továbbiakban a sorozatnak arra a részére kell alkalmazni. Ha a keresett ennél nagyobb, akkor pedig ugyanezen elv alapján a sorozat ezt követő részére.
Ez a megoldás szintén az utófeltételt módosítja, szigorítja. Itt az előzővel ellentétben nem lehet tudni, hogy a megtalált érték az azonos értékűek közül az első, az utolsó, vagy pedig valamelyik középső lesz.
Utófeltétel
VAN ≡ (∃i(1≤i≤N): X[i]=Y) és
VAN → 1≤SORSZ≤N és X[SORSZ]=Y és
∀i(1≤i<SORSZ):X[i]≤Y és ∀i(SORSZ<i≤N): X[i]≥Y
Keresés(N,X,Y,VAN,SORSZ):
E:=1; U:=N
Ciklus
K:=[(E+U)/2] [E+U felének egész értéke]
Elágazás
Y<X[K] esetén U:=K-1
Y>X[K] esetén E:=K+1
Elágazás vége
amíg E≤U és X[K]?Y
Ciklus vége
VAN:=(E≤U)
Ha VAN akkor SORSZ:=K
Eljárás vége.
- Minimum: 1
- Átlag: log2(N)
- Maximum: log2(N)+1
Az átlagos hasonlítás-számban szereplő logaritmikus összefüggés miatt hívják e keresést logaritmikus keresésnek, illetve a sorozat felezésére utalva felezéses vagy bináris keresésnek.
Ennek a keresésnek is meg lehet alkotni a rokonait, mint azt tettük a lineáris kereséssel, azaz készíthetünk belőle eldöntést, kiválasztást, megszámolást, kiválogatást. Ezek közül nézzük meg a kiválogatást!
A módosított specifikáció:
Bemenet
N:Egész, X:Tömb[1..N:Valami], Y:Valami,
T:Valami→Logikai
Kimenet
VAN:Logikai, SORSZ:Egész, E,U:Egész
Előfeltétel
N≥0 és RendezettE(X)
Utófeltétel
VAN ≡ (∃i(1≤i≤N): X[i]=Y) és
VAN → 1≤E≤U≤N és ∀i (E≤i≤U): X[i]=Y és
∀i(i<E): X[i]<Y és ∀i(U<i): X[i]>Y
Nyilvánvaló, hogy az azonos értékű elemek itt mindenképpen egymás mellett fognak szerepelni, azaz a kiválogatáshoz elég megadni az első, illetve az utolsó ilyen elem sorszámát. Ezt úgy tesszük meg, hogy a logaritmikus keresés után előre, illetve hátrafelé megkeressük az utolsó megfelelő elemet.
Kiválogatás(N,X,Y,VAN,E,U):
E:=1; U:=N
Ciklus
K:=[(E+U)/2]
Elágazás
Y<X[K] esetén U:=K-1
Y>X[K] esetén E:=K+1
Elágazás vége
amíg E≤U és X[K]šY
Ciklus vége
VAN:=(E≤U)
Ha VAN akkor E:=K
Ciklus amíg E>1 és X[E-1]=Y
E:=E-1
Ciklus vége
U:=K
Ciklus amíg U<N és X[U+1]=Y
U:=U+1
Ciklus vége
Elágazás vége
Eljárás vége.
