RENDEZÉSEK, TOVÁBBI PROGRAMOZÁSI TÉTELEK

Petrik tananyagtár: Rendezések, további programozási tételek Petrik Lajos Vegyipari, Környezetvédelmi és Informatikai Szakközépiskola Szoftverfejlesztő szak, 14. évfolyam, OKJ szám: 54 481 02 0010 54 04

___________________________________________________________________________

RENDEZÉSEK, TOVÁBBI PROGRAMOZÁSI TÉTELEK 1.

EGY SOROZATHOZ EGY SOROZATOT RENDELŐ TÉTELEK

1.1

Rendezések

1.1.1 Kitűzés Adott egy sorozat, és a sorozat elemein értelmezett egy “<” reláció. Rendezzük a sorozat elemeit növekvő (csökkenő) sorrendbe a megadott reláció szerint. 1.1.2 Specifikáció A: Tömb[N]:H Ef: A, N adott, “<” reláció adott. Uf: A sorozat tartalmazza az eredetileg is tartalmazott elemeit, az elemek növekvően (csökkenően) rendezettek a “<” reláció szerint. 1.1.3 Algoritmusok Megjegyzés: mivel a rendezések alapvető fontosságúak a programozásban, ezért nagyon sokféle rendezési algoritmus létezik, amelyek azonban bonyolultság és hatékonyság szempontjából eltérőek. A következőkben a legegyszerűbb rendezési algoritmusokat ismertetjük. 1.1.3.1 Közvetlen kiválasztásos rendezés Elve: ˗ Az első elemet összehasonlítjuk az utána következő elemmel, és ha az utána következő elem kisebb, akkor cserélünk. Az első elem összehasonlítását tovább folytatjuk a többi elemmel is, egészen addig, amíg a sorozat végére nem érünk. ˗ Ha a végére értünk, akkor az azt jelenti, hogy az első elem a helyére került. Ezt követően a második, harmadik elemmel járunk el ugyanígy. ˗ A legutolsó elemet már nem kell összehasonlítani, az automatikusan kerül a helyére. Szemléltető ábra:

1


___________________________________________________________________________ Algoritmus: Eljárás KozKivRend: Ciklus I:=0-től N-2-ig Ciklus J:=I+1-től N-1-ig Ha A[J]
Algoritmus: Eljárás BuborekRend: Ciklus I:=0-től N-2-ig Ciklus J:=N-1-től I+1-ig (-1-esével) Ha A[J-1]>A[J] akkor Csere(A[J-1],A[J]) Ciklus vége Ciklus vége Eljárás vége. Megjegyzés: az algoritmus 0 kezdőindexű tömbre lett megfogalmazva.

2


___________________________________________________________________________ 1.1.3.3 Minimum-kiválasztásos rendezés

Elve: ˗ Az első elemet a mögöttük lévők közül csak a legkisebbel cseréljük és csak akkor, ha az kisebb, mint az első elem. ˗ Ehhez egy minimum-kiválasztást kell alkalmazni a sorozat további részére. ˗ Miután az első elem a helyére került, ugyanígy folyatatjuk az eljárást a sorozat következő elemeivel. Szemléltető ábra:

Algoritmus: Ciklus I:=0-től N-2ig Ind:=I // Minimum-kiválasztás kezdete Ciklus J:=I+1-től N-1-ig Ha A[J]Ind Akkor csere(A[I],A[Ind]) Elágazás vége Ciklus vége Megjegyzés: az algoritmus 0 kezdőindexű tömbre lett megfogalmazva.

1.1.3.4 Beillesztéses rendezés Elve: ˗ A rendezendő elemeket a kártyalapoknál megszokott módszerrel rendezzük. ˗ Minden új elemet a már korábban rendezett elemek közé beillesztjük úgy, hogy a rendezettség megmaradjon. ˗ A beillesztés úgy történik, hogy a beillesztendő elemet jobbról balra haladva összehasonlítjuk a már rendezett elemekkel, és ha a beillesztendő elem kisebb, akkor az aktuális elemet eggyel jobbra léptetjük. ˗ Ezt mindaddig folytatjuk, amíg meg nem találjuk a beillesztendő elem helyét.

3


___________________________________________________________________________ Algoritmus: Eljárás BeillesztRendez: Ciklus I:=1-től N-1-ig J:=I-1 X:=A[I] Ciklus amíg (J>-1) és (X
1.2

Másolás, transzformálás tétele

1.2.1 Kitűzés Adott egy sorozat, a sorozat elemein értelmezett egy függvény (transzformáció). Feladat: Másoljuk a sorozat elemeinek a transzformáltjait egy másik sorozatba. 1.2.2 Specifikáció A:Tömb[1..Max]:HA N:egész / A és B elemszáma f: HA -> HB B:Tömb[1..Max]:HB Ef: A, N adott, 0<= N <= Max Uf: B adott és i  [1..N ] : ( B[ I]  f ( A[ I ]) ) / Azaz B tartalmazza az A elemeinek a transzformáltjait / 1.2.3 Algoritmus Eljárás Masol: Ciklus i:=1-től N-ig B[I]:=f(A[I]) Ciklus vége Eljárás vége 1.2.4 Feladatok -

Állítsunk elő egy egészeket tartalmazó tömb elemei alapján egy másik tömböt, amely ugyanezen számok négyzeteit tartalmazza.

-

Állítsuk elő egy tömb elemeit fordított sorrendben egy másik tömbben!

4


___________________________________________________________________________ 1.3

Kiválogatás tétele

1.3.1 Kitűzés Adott egy sorozat, a sorozat elemein értelmezett egy T tulajdonság. Feladat: Válogassuk ki a sorozat összes T tulajdonságú elemét! 1.3.2 Specifikáció A:Tömb[1..Max]:H N:egész / A elemszáma B:Tömb[1..Max]:H DB:egész / B elemszáma Ef:: A, N adott, 0<= N <= Max Uf: B adott és tartalmazza az A összes T tulajdonságú elemét, 0 <= DB <= N 1.3.3 Algoritmus Eljárás Kivalogat: DB:=0 Ciklus i:=1-től N-ig Ha T(A[I]) Akkor DB:=DB+1 B[DB]:=A[I] Elágazás vége Ciklus vége Eljárás vége 1.3.4 Feladatok -

2. 2.1

Adott egy egészeket tartalmazó tömb. Válogassuk ki belőle azokat, amelyek az elemek átlagától legfeljebb 1-el térnek el.

EGY SOROZATHOZ TÖBB SOROZATOT RENDELŐ TÉTEL Szétválogatás tétele

2.1.1 Kitűzés Adott egy sorozat, a sorozat elemein értelmezett egy T tulajdonság. Feladat: Válogassuk szét a sorozat T tulajdonságú, ill. nem T tulajdonságú elemeit!

5


___________________________________________________________________________ 2.1.2 Specifikáció A:Tömb[1..Max]:H N:egész / A elemszáma B,C:Tömb[1..Max]:H BDB,CDB:egész / B, C elemszáma Ef:: A, Uf: B, elemét; 0<= BDB

N adott, 0 <= N <= Max C adott; B tartalmazza az A összes T tulajdonságú C tartalmazza az A összes nem T tulajdonságú elemét; <=N, 0<= CDB <=N

2.1.3 Algoritmus Eljárás Szetvalogat: BDB:=0 CDB:=0 Ciklus i:=1-től N-ig Ha T(A[I]) Akkor BDB:=BDB+1 B[BDB]:=A[I] Különben CDB:=CDB+1 C[CDB]:=A[I] Elágazás vége Ciklus vége Eljárás vége Megjegyzés: a szétválogatás több (egymást kizáró) tulajdonság alapján, több vektorba is történhet. 2.1.4 Feladat -

3. 3.1

Egy személyi adatokat (név, nem, telefonszám, fizetés) tartalmazó vektor rekordjait válogassuk szét: nemek szerint ill. fizetési kategóriák szerint (0-50 000; 50-100 000; 100 001-150 000; 150 000-nél több)

TÖBB SOROZATHOZ EGY SOROZATOT RENDELŐ TÉTELEK Metszetképzés tétele

3.1.1 Kitűzés Adott két sorozat, a sorozatokon belül egy-egy elem csak egyszer szerepel. Feladat: Határozzuk meg azt a sorozatot, amely a két sorozat közös elemeit tartalmazza.

6


___________________________________________________________________________ 3.1.2 Specifikáció A,B:Tömb[1..Max]:H N,M:egész / A és B elemszáma C:Tömb[1..Max]:H L: egész / C elemszáma Ef.: A,B adott, elemeik egyediek; 0<=N<=Max , 0<=M<=Max Uf: C tartalmazza A és B közös elemeit, 0<=L<=Min(A,B) /a metszet legfeljebb annyi elemet tartalmaz, mint a kisebb elemszámú sorozat/

3.1.3 Algoritmus Elve: minden A-beli elemet keresünk a B tömbben. Ha egy A-beli megtalálható a B-ben, akkor felvesszük a közös elemek közé, a C-be. Eljárás Metszet: L:=0; Ciklus I:=1-től N-ig J:=1; / A[I] keresése B-ben Ciklus amíg J<=M és A[I]<>B[J] J:=J+1 Ciklus vége Ha J<=M / Ha A[I] megtalálható B-ben akkor L:=L+1 C[L]:=A[I] Elágazás vége Ciklus vége Eljárás vége 3.1.4 Feladat Ismerjük a bostoni, ill. a New York-i maratoni futóversenyeken célbaérkezők névsorát. Készítsük el azok névsorát, akik mindkét versenyen célba értek!

3.2

Unioképzés tétele

3.2.1 Kitűzés Adott két sorozat, a sorozatokon belül egy-egy elem csak egyszer szerepel. Feladat: Határozzuk meg azt a sorozatot, amely minden olyan elemet tartalmaz, amely legalább az egyiknek eleme.

7


___________________________________________________________________________ 3.2.2 Specifikáció A,B:Tömb[1..Max]:H N,M:egész / A és B elemszáma C:Tömb[1..2*Max]:H L: egész / C elemszáma Ef.: A,B adott; elemeik egyediek; 0<=N<=Max , 0<=M<=Max Uf: C tartalmazza az A és B sorozatok unióját, Max(A,B)<=L<=M+N Megjegyzés: a kimenő sorozat elemszáma legrosszab esetben 2*Max, ez akkor áll elő, ha A és B is Max elemet tartalmaz, és nincsen közös elemük. 3.2.3 Algoritmus Elve: először A összes elemét átmásoljuk C-be. Majd B elemeit sorra vesszük, és mindazokat, amelyek nem szerepelnek az A tömbben, szintén C-be másoljuk. Eljárás Unio: Ciklus I:=1-től N-ig /A elemeinek másolása C-be C[I]:=A[I] Ciklus vége L:=N Ciklus J:=1-től M-ig I:=1 / B[J] keresése A-ban Ciklus I<=N és B[J]<>A[I] I:=I+1 Ciklus vége Ha (I>N) / Ha B[J] nem szerepel A-ban akkor L:=L+1 C[L]:=B[J] Elágazás vége Ciklus vége Eljárás vége 3.2.4 Feladat Ismerjük a bostoni, ill. a New York-i maratoni futóversenyeken célbaérkezők névsorát. Készítsük el azok névsorát, akik legalább az egyik versenyen célba értek! 3.3

Összefuttatás tétele (UNIÓ)

Az összefuttatás rendezett sorozatok rendezett unióját (metszetét, különbségét, szimmetrikus differenciáját) állítja elő. A rendezettség miatt az összefuttatás hatékonyabb, mint az egyszerű únió, metszet tétel. Az algoritmust először unióra fogalmazzuk meg.

8


___________________________________________________________________________ 3.3.1 Kitűzés Adott két rendezett sorozat, a sorozatokon belül egy-egy elem csak egyszer szerepel. Feladat: Határozzuk meg a két sorozat rendezett unióját.

3.3.2 Specifikáció A,B:Tömb[1..Max]:H N,M:egész / A és B elemszáma C:Tömb[1..2*Max]:H L: egész / C elemszáma Ef.: A,B adottak, elemeik egyediek és növekvően rendezettek; 0<=N<=Max , 0<=M<=Max Uf: C tartalmazza az A és B sorozatok rendezett unióját, Max(A,B)<=L<=M+N 3.3.3 Algoritmus Az összefuttató algoritmus lényege (unió esetén), hogy a két bemenő sorozat aktuális elemeit összehasonlítva a kisebbik az eredménysorozatba kerül, és a kisebb elem sorozatában továbblépünk. Egyenlő elemek esetében az elem az eredménysorozatba kerül, és mindkét sorozatban lépünk. Ha az egyik sorozat elfogy, a másik maradék elemei bekerülnek az eredménysorozatba. Eljárás OsszefuttatUnio: I:=1 J:=1 L:=0 Ciklus amíg (I<=N) és (J<=M) L:=L+1 Elágazás A[I]B[J] esetén C[L]:=B[J] J:=J+1 A[I]=B[J] esetén C[L]:=A[I] /vagy C[L]:=B[J] I:=I+1 J:=J+1 Elágazás vége Ciklus vége // A megmaradó elemek másolása C-be, a két ciklus közül legfeljebb az egyik hajtódik végre!

Ciklus K:=I-től N-ig /Csak akkor fut le, ha marad elem A-ban/ L:=L+1 C[L]:=A[K] Ciklus vége

9


___________________________________________________________________________ Ciklus K:=J-től M-ig /Csak akkor fut le, ha marad elem B-ben/ L:=L+1 C[L]:=B[K] Ciklus vége Eljárás vége

3.4

Összefuttatás tétele (METSZET)

3.4.1 Kitűzés Adott két rendezett sorozat, a sorozatokon belül egy-egy elem csak egyszer szerepel. Feladat: Határozzuk meg a két sorozat rendezett metszetét, azaz, azokat az elemeket, amelyek mindkét sorozatban szerepelnek. 3.4.2 Specifikáció A,B:Tömb[1..Max]:H N,M:egész / A és B elemszáma C:Tömb[1..Max]:H L: egész / C elemszáma Ef.: A,B adottak, elemeik egyediek és növekvően rendezettek; 0<=N<=Max , 0<=M<=Max Uf: C tartalmazza az A és B sorozatok rendezett metszetét, 0<=L<=Min(A,B)

3.4.3 Algoritmus Metszet esetén az algoritmus annyiban változik, hogy csak az egyező elemek kerülnek az eredménysorozatba, és a végén a két ciklus értelemszerűen elmarad. Eljárás OsszefuttatMetszet: I:=1 J:=1 L:=0 Ciklus amíg (I<=N) és (J<=M) Elágazás A[I]B[J] esetén J:=J+1 /csak továbblép a B-ban A[I]=B[J] esetén L:=L+1 /ez a sor az uniónál az elágazás előtt volt/ C[L]:=A[I] /vagy C[L]:=B[J] I:=I+1 J:=J+1 Elágazás vége Ciklus vége Eljárás vége

10

RENDEZÉSEK, TOVÁBBI PROGRAMOZÁSI TÉTELEK

Recommend Documents