A. függelék: programozási tételek

A programozási tételek olyan általános algoritmusok, melyekkel programozás során gyakran találkozunk, érdemes tehát jól megtanulni õket. A következõ algoritmusok általában tömbökkel foglalkoznak, legyen tehát T egy N elemû tömb (1..N). Az algoritmusokat általános formában adjuk meg, de Pascal programmá kódolásuk sehol nem okoz nehézséget. Alaposan nézd át õket, és pontosan értsd meg a mûködésüket!

1. Összegzés

Az algoritmus feladata egy tömb elemeinek összegzése. Könnyen átírható pl. szorzatra s:=1 kezdõértékkel, és a + jel * jelre cserélésével.

s:=0 Ciklus i:=1..N s:=s+T[i] Ciklus vége Ki: s

2. Megszámolás

Az algoritmus megszámolja, hogy a tömbben hány, adott tulajdonságú elem van. Legyen most a tulajdonság az, hogy a szám negatív-e (természetesen ez akármilyen más feltétellel helyettesíthetõ).

s:=0 Ciklus i:=1..N Ha T[i]<0 akkor s:=s+1 Ciklus vége Ki: s

3. Eldöntés

Az algoritmus eldönti, hogy van-e a tömbben adott tulajdonságú elem. Amint talál egyet, a ciklus leáll, hiszen fölösleges lenne tovább futnia. Ha a ciklus azért állt le, mert túlléptünk a tömb utolsó, vizsgált elemén is, akkor nem volt benne keresett elem. A kérdés legyen az, hogy van-e 50 az elemek között.

i:=1 Ciklus amíg i<=N és T[i]<>50 i:=i+1 Ciklus vége Ha i<=N akkor ki: "volt 50"

Figyeljük meg, hogy az i<=N feltétel megelõzi T[i] vizsgálatát. Mi történik ugyanis, ha i elérte az N+1-et? Az elöltesztelõs ciklus feltétele még utoljára kiértékelésre kerül. Ekkor azonban a T tömb N+1-ik elemére hivatkozunk, ami programhiba, ha T csak N-elemû. A Pascal képes úgy kiértékelni a logikai kifejezéseket, hogy AND-del összekapcsolt két kifejezés esetén ha az elsõ hamis, a másodikat már figyelmen kívül hagyja (hamis AND akármi = mindenképpen hamis). Ez gyorsítja a logikai kifejezések kiértékelését, és esetünkben megelõzi, hogy a második, hibát okozó részfeltételre sor kerüljön. (Ugyanígy mûködik az igaz OR akármi típusú feltételek kiértékelése). Ez a kiértékelési mód megfelelõ fordítási direktívával kikapcsolható, ekkor mindenképpen kiértékelésre kerül az összes részfeltétel. Olyan programnyelvnél, amely mindenképpen kiértékeli az összes részfeltételt, az algoritmus jó mûködéséhez T tömböt N+1-elemûnek kell deklarálni.

Itt felhasználjuk az alkalmat, hogy egy hasznos programozástechnikai trükkre hívjuk fel a figyelmet. Az i<=N feltételt a ciklus minden lépésben ellenõrzi, és ez valamelyest lassítja a program futását. Ha biztosak lennénk benne, hogy szerepel az 50 az elemek között, nem lenne szükség erre a feltételre. A gyorsított algoritmus ezért bele teszi az 50-et a tömbbe utolsó utáni segédelemként (úgynevezett fiktív elem): ha elõbb nincs is 50, a ciklus biztosan leáll az N+1-ik elemnél.

T[N+1]:=50 i:=1 Ciklus amíg T[i]<>50 i:=i+1 Ciklus vége Ha i<=N akkor ki: "a tömbben van 50"

4. Kiválasztás

Az algoritmus megadja, hogy a tömbben egy bizonyos elem hol (hányadik helyen) van. Az algoritmus csak akkor mûködik, ha biztosan van ilyen elem! Legyen a keresett elem az 50.

i:=1 Ciklus amíg T[i]<>50 i:=i+1 Ciklus vége Ki: i

5. Keresés

Az elõzõnél biztonságosabb algoritmus: megadja, hogy van-e olyan elem, és ha igen, hányadik. (Majdnem megegyezik az eldöntéssel.) Ha i>N, akkor nem létezik a keresett elem.

a) lineáris avagy soros keresés (figyelem! Gyorsítható a 3. pontban leírtak szerint!)

i:=1 Ciklus amíg i<=N és T[i]<>50 i:=i+1 Ciklus vége Ha i<=N akkor ki: "a tömbben van 50, az", i ,". helyen"

Nagy tömbben ez a keresés lassú (legrosszabb esetben az egész tömböt végig kell vizsgálni). Gondoljunk a szótározásra: ahhoz, hogy megtaláljunk egy szót, nem kell a szótárat szavanként végignézni. Ez azért lehetséges, mert a szótár ABC-ben rendezett. A leggyorsabb mód: nyissuk ki a szótárat középen. Az elsõ szóra ránézve megál lapítható, hogy a keresett szó a szótár elsõ, vagy második felében található. Így máris megfeleztük a számításba vehetõ szavak listáját. A fél szótáron megismételjük az elõzõ mûveletet, egészen addig, míg meg nem találjuk a keresett szót. A következõ algoritmus nagyon gyors: pl. egy 1024-elemû tömbben 11 lépésben biztosan megtalálja a keresett elemet. T tömb növekvõen rendezett, és keressük megint az 50-et. Az algoritmus egyáltalán nem nyilvánvaló, érdemes konkrét esetre eljátszani a mûködését.

b) bináris vagy felezéses keresés (e a vizsgálandó rész elsõ, u az utolsó, k a középsõ elemének helyét jelöli)

e:=1 u:=N k:=int((e+u)/2){ (e+u)/2 egészrésze }
Ciklus amíg T[k]<>50 és e<=u Ha T[k]<50 akkor e:=k+1 különben u:=k-1 k:=int((e+u)/2) Ciklus vége Ha T[k]=50 akkor ki: "a tömbben van 50, a ",k ,". helyen"

6. Kiválogatás

Ez az algoritmus egy tömb bizonyos tulajdonságú elemeit teszi egy másik tömbbe. db változó számolja, hogy a másik tömbbe hány elem került, és válogassuk ki a negatív számokat. Az eredmény B tömbben lesz (deklarációnál B tömböt N elemûre kell választani, hacsak nem tudjuk elõre, hány negatív szám van T-ben).

db:=0 Ciklus i:=1..N Ha T[i]<0 akkor db:=db+1 B[db]:=T[i] Ciklus vége

7. Szétválogatás

A feladat hasonló az elõzõhöz, de a feltételnek nem megfelelõ elemeket is egy újabb tömbbe kell elhelyezni (tehát kétfelé válogatjuk az eredeti tömböt).

a) szétválogatás két tömbbe

dbb:=0 dbc:=0 Ciklus i:=1..N Ha T[i]<0 akkor dbb:=dbb+1, B[dbb]:=T[i] különben dbc:=dbc+1, C[dbc]:=T[i] Ciklus vége

Memóriafoglalás szempontjából a két tömböt használó a) algoritmus nem hatékony: mindkét tömböt N elemûre kell deklarálni, de a két tömbben összesen csak N elem van. Használhatunk egy tömböt is, akkor annak elsõ felébe tesszük a negatív számoghat, a második felébe (hátulról kezdve a feltöltést) a többit.

b) szétválogatás egy tömbbe

db:=0 veg:=N+1 Ciklus i:=1..N Ha T[i]<0 akkor db:=db+1, B[db]:=T[i] különben veg:=veg-1, C[veg]:=T[i] Ciklus vége

8. Metszet

A feladat most két tömb (A[1..N] és B [1..M]) azonos elemeinek kiválogatása C tömbbe. A feladat csak úgy értelmezhetõ pontosan, ha az egyes tömbökben egy elem nem szerepel kétszer. Mivel a metszet halmazmûvelet, ez a feltétel elég magától értetõdõ. Az algoritmus lényege: menjünk végik A tömb elemein, és válogassuk ki azokat (kiválogatás), melyek szerepelnek B-ben (eldöntés). Így a feladat a korábbi tételekre visszavezethetõ. C maximális elemszáma N és M közül a kisebbik.

db:=0 Ciklus i:=1..N j:=1 Ciklus amíg j<=M és B[j]<>A[i] j:=j+1 Ciklus vége Ha j<=M akkor db:=db+1, C[db]:=A[i] Ciklus vége

9. Únió

A feladat A és B tömb összes elemét C tömbbe tenni de (mivel C halmazt jelképez) minden elem csak egyszer szerepelhet benne. A legkézenfekvõbb megoldás: tegyük be C-be A összes elemét, majd B-bõl azokat, melyek nem szerepelnek A-ban. C elemszáma legfeljebb N+M.

a) kiválogatás és eldöntés

Ciklus i:=1..N C[i]:=A[i] Ciklus vége db:=N Ciklus j:=1..M i:=1 Ciklus amíg i<=N és B[j]<>A[i] i:=i+1 Ciklus vége Ha i>N akkor db:=db+1, C[db]:=B[j] Ciklus vége

Az algoritmus sokkal hatékonyabb, ha A és B tömb rendezett. Ekkor az eldöntés csak addig fut, amíg a kérdéses elemnél nagyobbat nem talál a másik tömbben. Végsõ soron az algoritmus mindig a kisebb elemet tartalmazó tömbben lép a következõ elemre, így megtalálja az egyezõ elemeket (és így azok csak egyszer kerülnek C tömbbe), másrészt C tömb is rendezett lesz.

b) összefuttatás (únió rendezett tömbökkel)

i:=1, j:=1, db:=0 Ciklus amíg i<=N és j<=M Elágazás: Ha A[i]<B[j] akkor db:=db+1, C[db]:=A[i] i:=i+1 Ha A[i]=B[j] akkor db:=db+1, C[db]:=A[i] i:=i+1, j:=j+1 Ha A[i]>B[j] akkor db=db+1, C[db]:=B[j] j:=j+1 Elágazás vége Ciklus vége Ciklus k:=i..N db:=db+1, C[db]:=A[k] Ciklus vége Ciklus k:=j..M db:=db+1, C[db]:=B[k] Ciklus vége

Az utolsó két ciklusra azért volt szükség, mert miután i vagy j kifutottak a megfelelõ tömbbõl, a másik tömbben még maradnak feldolgozatlan elemek, melyket át kell másolni C tömbbe. Az algoritmusban találkozunk a többszörös elágazással, melynek mindig csak egy ága hajtódik végre. Ez kiváltható egymásba skatulyázott
Ha ... akkor ... különben Ha ... akkor ... különben ...feltételekkel, de az algoritmus jobban olvasható és érthetõ a többszörös elágazás használatával.

10. Maximumkiválasztás

A feladat megadni T tömb maximális elemét. Megadhatjuk magát az elemet (ebbõl nem derül ki, hogy az elem hányadik), és megadhatjuk az elem pozícióját a tömbben (ebbõl viszont kiderül, melyik az az elem). A második esetben ugyanannyi munkával több információhoz jutunk.

m:=1 Ciklus i:=2..N Ha T[i]>T[m] akkor m:=i Ciklus vége Ki: m, T[m]

Érdemes megfigyelni az algoritmus elvét. m a pillanatnyilag talált legnagyobb elem helyét mutatja. Ahogy haladunk a tömbben, m vagy marad, vagy belekerül az eddigieknél még nagyobb elem pozíciója. m tehát a tömb addig vizsgált szeletében mindig a legnagyobb elemre mutat.

11. Rendezés

Mint látható, a rendezett tömbökkel meggyorsítható a programok mûködése (elsõsorban a keresés).

a) maximumkiválasztásos rendezés

Az elv: kiválasztjuk a tömb legnagyobb elemét, és berakjuk a tömb végére (vagyis kicseréljük az utolsó elemmel). Ezt az eljárást ismételjük a maradék tömbre (az utolsó elem most már a helyén van, ahhoz nem kell nyúlni). i változó adja meg, hogy hányadik elem fog a helyére kerülni. A Csere(i,m) eljárás kicseréli a tömb i. és m. elemét. (Emlékeztetõ: x:=T[i], T[i]:=T[m], T[m]:=x.)

Ciklus i:=N..2 m:=1 Ciklus j:=2..i Ha T[j]>T[m] akkor m:=j Ciklus vége Csere(i,m) Ciklus vége

b) buborékos rendezés

Az algoritmus elve: végigmegy a tömbön, és ha szomszédos elemeknél rossz a sorrend, megcseréli õket. Ez a csere, mint egy buborék, végighalad a tömbön, és a legnagyobb elemet biztosan a tömb végére teszi. i változó ismét azt jelzi, hányadik elem kerül a helyére. Az algoritmus az elõzõnél több cserét használ, de csak a szomszédos elemeket cseréli (ez hasznos lehet bizonyos gyakorlati megvalósításoknál).

Ciklus i:=N..2 Ciklus j:=1..i-1 Ha T[J]>T[J+1] akkor Csere(j,j+1) Ciklus vége Ciklus vége

c) beillesztéses rendezés

Az algoritmus bonyolultabb az elõzõeknél, viszont gyorsabban mûködik, mivel cserék helyett félcseréket alkalmaz. Az elv: induljunk ki egy 1-elemû tömbbõl, ez nyilván rendezett. Vegyünk hozzá egy új elemet, és illesszük be a rendezett tömbbe, mégpedig úgy, hogy addig léptessük eggyel elõre a tömb elemeit, míg meg nem találjuk az új elem helyét. Így minden lépésben rendezett tömböt kapunk. i változó mutatja az újonnan beillesztendõ elem helyét (az új elemet m-ben tároljuk).

Ciklus i:=2..N m:=T[i] j:=i-1 Ciklus amíg m<T[j] és j>0 T[j+1]:=T[j] j:=j-1 Ciklus vége T[j+1]:=m Ciklus vége

Következõ fejezet
Elõzõ fejezet
Tartalomjegyzék
Honlap