Programozás | Programozás-elmélet » Fábián Zoltán - Programozási tételek

Összegzés tétele Általános feladat: Adott egy N elemű számsorozat. Számoljuk ki az elemek összegét! A sorozatot most és a továbbiakban is az N elemű A(N) vektorban tároljuk. Algoritmus: Eljárás S:=0 Ciklus I=1-től N-ig S:=S+A(I) Ciklus vége Eljárás vége. Eldöntés tétele Általános feladat: Adott egy N elemű sorozat és egy, a sorozat elemein értelmezett T tulajdonság. Az algoritmus eredménye: annak eldöntése, hogy van-e a sorozatban legalább egy T tulajdonsággal rendelkező elem. Algoritmus: Eljárás I:=1 Ciklus amíg I<=N és A(I) nem T tulajdonságú I:=I+1 Ciklus vége VAN:=I<=N //a VAN egy logikai változó, amely csak akkor igaz értékű, ha I<=N Eljárás vége Kiválasztás tétele Általános feladat: Adott egy N elemű sorozat, egy, a sorozat elemein értelmezett T tulajdonság, valamint azt is tudjuk, hogy a sorozatban van legalább egy T tulajdonságú elem. A feladat ezen elem sorszámának meghatározása Algoritmus: Eljárás

I:=1 Ciklus amíg A(I) nem T tulajdonságú I:=I+1 Ciklus vége SORSZ:=I Eljárás vége. A lineáris keresés tétele Általános feladat: Rendelkezésre áll egy N elemű sorozat, egy, a sorozat elemein értelmezett T tulajdonság. Olyan algoritmust kell írni, amely eldönti, hogy van-e T tulajdonságú elem a sorozatban, és ha van, akkor megadja a sorszámát. Algoritmus: Eljárás I:=1 Ciklus amíg I<=N és A(I) nem T tulajdonságú I:=I+1 Ciklus vége VAN:=I<=N Ha VAN akkor SORSZ:=I Eljárás vége. Logaritmikus keresés Általános feladat: adott egy N elemű rendezett sorozat és egy keresett elem (X). Olyan algoritmust kell írni, amely eldönti, hogy szerepel-e a keresett elem a sorozatban, s ha igen, akkor megadja a sorszámát. Kihasználjuk, hogy a vizsgált sorozat rendezett Ez alapján bármely elemről el tudjuk dönteni, hogy a keresett elem előtte vagy utána vane, vagy esetleg éppen megtaláltuk. A és F mindig annak a részintervallumnak az alsó és

felső végpontjai, amelyben a keresett elem benne lehet. Algoritmus: Eljárás A:=1 F:=N Ciklus K:=INT((A+F)/2) Ha A(K)<X akkor A:=K+1 Ha A(K)>X akkor F:=K-1 amíg A<=F és A(K)<>X Ciklus vége VAN:=A<=F Ha VAN akkor SORSZ:=K Eljárás vége. A megszámlálás tétele Általános feladat: adott egy N elemű sorozat és egy, a sorozat elemein értelmezett T tulajdonság. A T tulajdonsággal rendelkező elemek megszámlálása a feladat Algoritmus: Eljárás S:=0 Ciklus I=1-től N-ig Ha A(I) T tulajdonságú, akkor S:=S+1 Ciklus vége Eljárás vége A maximum kiválasztás tétele Általános feladat: Egy sorozat legnagyobb elemét kell megtalálni. A feladatot visszavezetjük az elemenkénti feldolgozásra: egy elem maximumát mindig tudjuk. Ha ismerjük K elem közül a legnagyobbat, és veszünk hozzá egy új elemet, akkor a maximum vagy az eddigi, vagy pedig az új elem lesz. (Minimum kiválasztásnál csak a feltételes utasítás feltétele fordul meg:

’<’ helyett ’>’ lesz) Algoritmus: Eljárás INDEX:=1 Ciklus I=2-től N-ig Ha A(INDEX) < A(I) akkor INDEX:=I Ciklus vége MAXINDEX:=INDEX Eljárás vége Ha a kérdést úgy tesszük fel, hogy mennyi a legnagyobb érték, akkor egy másik megoldást is kaphatunk: Eljárás ÉRTÉK:=A(1) Ciklus I=2-től N-ig Ha ÉRTÉK < A(I) akkor ÉRTÉK:=A(I) Ciklus vége MAXÉRTÉK:=ÉRTÉK Eljárás vége A kiválogatás tétele Általános feladat: Egy N elemű sorozat összes T tulajdonságú elemét kell meghatározni. Gyűjtsük a kiválogatott elemek sorszámait a B() vektorban. Algoritmus: Eljárás J:=0 Ciklus I=1-től N-ig Ha A(I) T tulajdonságú, akkor J:=J+1; B(J):=I Ciklus vége Eljárás vége Rendezés közvetlen kiválasztással A módszer lényege: A rendezendő számok legyenek az A vektor elemei. Az első menetben kiválasztjuk a vektor legkisebb elemét úgy, hogy az A(1)-et összehasonlítjuk A(2). A(N) mindegyikével. Ha A(1)-nél kisebb elemet találunk,

felcseréljük őket, vagyis ezt a kisebbet tesszük A(1)-be. Így a menet végére A(1) biztosan a vektor legkisebb elemét tartalmazza majd. Az eljárást A(2)-vel folytatjuk, ezt hasonlítjuk össze az A(3), , A(N) elemekkel. És így tovább N-1 lépésben a vektor rendezett lesz Algoritmus: Eljárás Ciklus I=1-től N-1-ig Ciklus J=I+1-től N-ig Ha A(J)<A(I) akkor A:=A(J) ; A(J):=A(I) ; A(I):=A Ciklus vége Ciklus vége Eljárás vége. Rendezés minimum kiválasztással A módszer lényege: A felesleges cserék kiküszöbölése érdekében két segédváltozót vezetünk be. Az ÉRTÉK tartalmazza az adott menetben legkisebb számot, az INDEX pedig annak lelőhelyét a vektorban. Algoritmus: Eljárás Ciklus I=1-től N-1-ig INDEX:=I ; ÉRTÉK:=A(I) Ciklus J=I+1-től N-ig Ha ÉRTÉK>A(J) akkor ÉRTÉK:=A(J) ; INDEX:=J Ciklus vége A(INDEX):=A(I) ; A(I):=ÉRTÉK Ciklus vége Eljárás vége. Buborékos rendezés A buborékos rendezés alapgondolata a szomszédos elemek

cseréje. Az első menetben a rendező A vektor végéről indulva minden elemet összehasonlítunk az előtte lévővel. Amennyiben rossz sorrendben vannak, felcseréljük őket. Az első menet végére a legkisebb elem biztosan a helyére kerül. Minden további menetben ismét a vektor végéről indulunk, de egyre kevesebb hasonlításra van szükségünk, mert a vektor eleje fokozatosan rendezetté válik. Algoritmus: Eljárás Ciklus I=2-től N-ig Ciklus J=N-től I-ig (-1-esével) Ha A(J-1)>A(J) akkor A:=A(J-1) A(J-1):=A(J) A(J):=A Elágazás vége Ciklus vége Ciklus vége Eljárás vége. Egyszerű beillesztéses rendezés A rendezést úgy végezzük, mintha kártyáznánk, és kezünkbe egyesével vennénk fel az asztalról a kiosztott lapokat. Az éppen felvett lapnak megkeressük a kezünkben lévő, már rendezett sorozatban a helyét úgy, hogy közben a nála nagyobbakat egy hellyel elcsúsztatjuk, végül beillesztjük a felvett lapot a neki megfelelő helyre.

N elem esetén a végső sorrend kialakításához N-1 menetre van szükség. Eredeti: 64 56 8 42 5 12 16 1. menet után: 56 64 8 42 5 12 16 2. menet után: 8 56 64 42 5 12 16 3. menet után: 8 42 56 64 5 12 16 4. menet után: 5 8 42 56 64 12 16 5. menet után: 5 8 12 42 56 64 16 . . . 15. menet után: 3 5 7 8 12 16 22 40 40 40 40 40 40 3 3 3 3 3 3 31 31 31 31 31 31 47 47 47 47 47 47 22 22 22 22 22 22 24 24 24 24 24 24 33 33 33 33 33 33 7 7 7 7 7 7 46 46 46 46 46 46 24 31 33 40 42 46 47 56 64 Algoritmus: Eljárás Ciklus J=2-től N-ig I:=J-1 ; A:=A(J) Ciklus amíg I>0 és A<A(I) A(I+1):=A(I) ; I:=I-1 Ciklus vége A(I+1):=A Ciklus vége Eljárás vége. A listás beillesztéses rendezés A módszer lényege: Egyesével vesszük sorra az elemeket, és az éppen beillesztésre váró elem helyét megkeressük egy már rendezett sorozatban. A beillesztéshez az elemek mozgatására nincs szükség, mert egy mutató vektor segítségével a rendezendő elemeket egy

listába fűzzük fel. Az A vektor minden eleméhez tartozik egy mutató, amely az adott elemet nagyság szerint követő vektorelemre mutat. A listának van egy első eleme, ez a lista feje, erre az elemre MU(0) érték mutat. A lista végét pedig úgy jelöljük, hogy az utolsó elem mutatója 0 Ha a listába új elemet szeretnénk beilleszteni, csak a megfelelő mutatókat kell átállítanunk. A rendezés algoritmusában az ME beillesztendő elem előtti elem sorszámát, MK a beillesztendő elemet követő elem sorszámát jelenti. Algoritmus: Eljárás MU(0):=1 Ciklus J=2-től N-ig MK:=MU(0) ; ME:=0 ; A:=A(J) Ciklus amíg MK>0 és A<A(MK) ME:=MK ; MK:=MU(ME) Ciklus vége MU(ME):=J ; MU(J):=MK Ciklus vége Eljárás vége Shell-módszer beszúrással A Shell-módszer nem foglalkozik egyszerre minden rendezendő elemmel, csak az egymástól adott távolságra lévőkkel. A rendezés most is több menetben történik Minden menet elején meghatározunk egy úgynevezett

lépésközt, a D-t, amely azt jelenti, hogy az adott menetben a vektor egymástól D távolságra lévő elemeit rendezzük. Az utolsó menetben, D=1 esetén a vektor rendezetté válik. Az induló lépésköz meghatározása úgy történik, hogy a rendezéshez szükséges menetek száma körülbelül log2N legyen. A további lépésközöket felezéssel kapjuk. A kisebb elemek körülbelül egyszerre haladnak a vektor elejére, a végleges helyük felé, míg a nagyobbak a vektor vége felé. A lépésköz csökkentésével ebben a nagyjából rendezett vektorban már csak kisebb korrekciókat kell végrehajtanunk. Algoritmus: Eljárás INT(LOG(N)/LOG(2)) D:=2 Ciklus I:=1 Ciklus amíg I<=D és I+D<=N Ciklus J=I+D-től N-ig (D-esével) A:=A(J) ; B:=J-D Ciklus amíg B>0 és A<A(B) A(B+D):=A(B) ; B:=B-D Ciklus vége A(B+D):=A Ciklus vége I:=I+1 Ciklus vége D:=INT(D/2) amíg D>0 Ciklus vége Eljárás vége. A szétválogatás tétele Általános feladat:

Rendelkezésre áll egy sorozat, valamint egy kijelölt eleme. Cseréljük fel úgy a sorozat elemeit, hogy az X-nél kisebbek X előtt legyenek, a nála nagyobbak pedig utána. Algoritmus: Eljárás X:=A(1) E:=1 ; U:=N Ciklus amíg E<U Ciklus amíg E<U és A(U)>=X U:=U-1 Ciklus vége Ha E>U akkor A(E):=A(U) ; E:=E+1 Ciklus amíg E<U és A(E)<=X E:=E+1 Ciklus vége Ha E<U akkor A(U):=A(E) ; U:=U-1 Elágazás vége Ciklus vége A(E):=X Eljárás vége A metszetképzés tétele Általános feladat: Rendelkezésünkre áll egy N és egy M elemű halmaz az A() és a B() vektorban ábrázolva. Készítsük el a két halmaz metszetét a C() vektorba! Algoritmus: Eljárás CN:=0 Ciklus I=1-től N-ig J:=1 Ciklus amíg J<=M és A(I)<>B(J) J:=J+1 Ciklus vége Ha J<=M akkor CN:=CN+1 ; C(CN):=A(I) Ciklus vége Eljárás vége Az unióképzés tétele Általános feladat: Rendelkezésünkre áll egy N és egy M elemű halmaz az A() és B() vektorban

ábrázolva. Készítsük el a két halmaz unióját a C() vektorba! Algoritmus Eljárás Ciklus I=1-től N-ig C(I):=A(I) Ciklus vége CN:=N Ciklus J=1-től M-ig I:=1 Ciklus amíg I<=N és A(I)<>B(J) I:=I+1 Ciklus vége Ha I>N akkor CN:=CN+1 ; C(CN):=B(J) Ciklus vége Eljárás vége Az összefuttatás tétele Általános feladat: Rendelkezésünkre állnak két rendezett sorozat elemei. Állítsunk elő belőlük egy sorozatot úgy, hogy az eredeti sorozatok minden eleme szerepeljen benne, és ez a sorozat is rendezett legyen. Tehát uniót kell előállítani úgy, hogy a rendezettség megmaradjon. A megoldásban ’ +végtelen ’ jelöli a számítógépen ábrázolható legnagyobb értéket. Az összefuttatás alapgondolata a külső rendezéseknek, amelyeknél a teljes rendezendő adatmennyiség nem fér el egyszerre az operatív tárban. Algoritmus: Eljárás I:=1 ; J:=1 ; K:=0 A(N+1):=+végtelen ; B(M+1):=+végtelen Ciklus amíg I<N+1 vagy J<M+1 K:=K+1

Elágazás A(I)<B(J) esetén C(K):=A(I) ; I:=I+1 A(I)>B(J) esetén C(K):=B(J) ; J:=J+1 A(I)=B(J) esetén C(K):=A(I) ; I:=I+1 ; J:=J+1 Elágazás vége Ciklus vége Eljárás vége