Informatika alapismeretek » Programozási tételek

Fejezet menü:

Össszegzés
Szélsőérték
- Érték keresése
- Hely keresése
Rendezés


- Minimum
- Beszúrásos
- Buborékos
- Cserélő
Kiválogatás
Szétválogatás
Back to top

Programozási tételek

A fejezetben ismertetett algoritmusok, programozási tételek a programozás alapköveit jelentik. A megoldandó feladat típusától függően alkalmazhatjuk nagyobb programjainkban ezen algoritmusokat, akár egy programon belül többet is.

Programírás során célszerű úgy megfogalmazni a problémát, hogy a program ne csak egy egyedi feladat megoldására legyen alkalmas, hanem egy feladatcsoport számára is használható legyen.

Összegzés

Az olyan feladatokat, melyben a sorozat elemeit valamilyen módon gyűjteni kell, összegzéses feladatoknak nevezzük.

1. Általános algoritmusa N elem esetén

Összeg : = 0

Ciklus i : = 1-től N-ig

Összeg : = összeg + i. elem

Ciklus vége

a) tömb nélkül

Osszeg : = 0;

For i : = 1 to N do

Osszeg : = osszeg + szam;

b) tömbbel

osszeg : = 0;

for i : = 1 to N do

osszeg : = osszeg + t [ i ];

2. Ha nem tudjuk előre az elemek számát

Összeg : = 0

Hozzáférés az első elemhez

Ciklus amíg van elem

Összeg : = összeg + elem

Hozzáférés a következő elemhez

Ciklus vége

a) tömb nélkül

Osszeg : = 0;

Readln (szam);

While szam <> vegjel do begin

Osszeg : = osszeg + szam;

Readln (szam);

End;

b) tömbbel

Osszeg : = 0; i : = 1;

Readln ( t [ i ] );

While t [ i ] <> vegjel do begin

Osszeg : = osszeg + t [ i ];

i : = i + 1;

Readln ( t [ i ] );

End;

vissza

Szélsőérték-kiválasztás

Minimum (maximum) érték keresése

1. Egy n elemből álló adatsorozatban

A sorozat elemeit tömbbel kezeljük, mert újra szükség lehet ezekre az értékekre - például a legkisebb elem hányadik a sorozatban. Tegyük fel, hogy a tömb legelső eleme a legkisebb adat. Meg kell vizsgálni az összes többi elemet a tömbben, össze kell hasonlítani az elsővel. Amennyiben találunk nála kisebbet, az lesz az újabb feltételezett minimumértékünk. Az összehasonlítást a tömb utolsó eleméig el kell végezni.

a) minimumérték keresés

Min : = t [ 1 ];

For i : = 2 to N do begin

If t [ i ] < min then

Min : = t [ i ];

b) maximumérték keresés

Max : = t [ 1 ];

For i : = 2 to N do begin

If t [ i ] > max then

Max : = t [ i ];

2. Minimum (maximum) érték keresése úgy, hogy nem tudjuk előre hány eleme van a sorozatnak

Tegyük fel, hogy a beolvasott számok 1 és 65534 (word típus határai lesznek a min és max változók kezdőértékei). A végjel 0 lehet, a minimum induló értékének jó a 65535, mivel ennél az értéknél biztosan találunk kisebbet, a maximum kezdőértéke pedig 0 lesz.

a) tömb nélkül

Min : = 65535; Max : = 0;

Readln (szam);

While szam <> vegjel do begin

If szam < min then min :=szam;

If szam > max then max := szam;

Readln (szam);

End;

b) tömbbel

Min : = 65535; Max : = 0; i : = 1;

Readln (t [ i ]);

While t[ i ] <> vegjel do begin

If t[ i ] < min then min := t [ i ];

If t [ i ] > max then max := t [ i ];

i : = i + 1;

Readln (t [ i ]);

End;

Minimum,- és maximumhely keresés

1. Egy n elemű adatsorozatban

a) minimumhely keresés

Min : = 1 ;

For i : = 2 to N do begin

If t [ i ] < t [min] then

Min : = i ;

End.

b) maximumhely keresés

Max : = 1 ;

For i : = 2 to N do begin

If t [ i ] > t [max] then

Max : = i ;

End.

2. Minimum (maximum) hely keresése úgy, hogy nem tudjuk előre hány eleme van a sorozatnak

Megoldás: tömbbel

Min : = 1; Max : = 1; i : = 1;

Readln (t [ i ]);

While t[ i ] <> vegjel do begin

If t [ i ] < t [min] then min := i ;

If t [ i ] > t [max] then max := i ;

i : = i + 1;

Readln (t [ i ]);

End;

vissza

Rendezés

Sokszor szükséges a tömb elemeit valamilyen szempont szerint átrendezni. Az adatokat azért tároljuk, hogy lekérdezhessük, visszakereshessük őket. Ahhoz, hogy a keresés gyorsan elvégezhető legyen, az adatokat rendezni kell. Többféle rendezési algoritmus létezik.

Minimum-kiválasztásos rendezés

Feladat: Adott n elemből álló, tetszőleges adatokat tartalmazó sorozat. Állítsuk az adatokat növekvő sorrendbe!

Kiválasztjuk a sorozat legkisebb elemét, megjegyezzük, hogy hányadik a sorban, majd felcseréljük az első elemmel. A második elemtől kezdve újra kiválasztjuk a legkisebbet és kicseréljük a második elemmel, és így tovább, amíg az utolsó elemet is a helyére nem tettük.

A megoldás lépései:

• rögzítsük 1-re annak az elemnek a sorszámát, ahova a kiválasztott legkisebb elemet írnunk kell
• a rögzített sorszámtól kezdve a sorozat végéig keressük meg a legkisebb elemet, jegyezzük meg az indexét
• cseréljük fel a minimális elemet a rögzített sorszámú elemmel
• növeljük a rögzített sorszámot 1-gyel
• ha az új rögzített sorszám megegyezik az utolsó elem indexével, akkor készen vagyunk, a sorozat rendezett

Ciklus i : = 1-től db-1-ig

Min : = t [ i ]

Index : = i

Ciklus j : = i + 1-től db-ig

Ha t [ j ] < min akkor

Min : = t [ j ]

Index : = j

Havége

Ciklusvége

t [ index ] : = t [ i ]

t [ i ] : = min

Ciklusvége

Adatszerkezet:

azonosító	típus	funkció
db	egész szám	az elemek száma
t	tömb	a sorozat elemeit tárolja
min	mint a tömb elemei	az aktuális minimum
index	egész szám	az aktuális minimum sorszáma
i	egész szám	rögzített sorszám, az aktuális minimum új helye
j	egész szám	ciklusváltozó a minimum-kiválasztáshoz

Beszúrásos rendezés

A beszúrásos rendezés hasonlít arra a módszerre, ahogy az ember leosztás után elrendezi kezében a kártyákat. Feltételezzük, hogy van egy szigorú rend, ami szerint a kártyákat sorba kell rakni. Felvesszük az első kártyát, majd felvesszük a másodikat és a helyére tesszük, és így tovább. Minden esetben megkeressük a kérdéses kártyának a helyét a már rendezett sorban, és oda beszúrjuk.

Ciklus i : = 2-től db-ig

Ha t [ i ] < t [ i -1 ] akkor Ment : = t [ i ]

j : = i

ciklus

j : = j -1

t [ j+1] : = t [ j ]

mígnem t [ j -1 ] <= ment

ciklusvége

t [ j ] : = ment

Ciklusvége

Buborékos rendezés (szomszédos elemek cseréje)

Nevét onnan kapta, hogy a megoldás során a nagyobb értékek úgy kerülnek egyre nagyobb indexű tömbelemekbe, végül a helyükre, ahogyan a folyadékban száll fel a buborék. Ha nem rendezett egy adatsorozat, akkor nyilván van olyan szomszédos elempár, amelynek sorrendje rossz. Ezt a két elemet fel kell cserélni. El kell végezni a sorozat szomszédos elempárjain az elsőtől az utolsóig az összes rossz sorrendűnél a cseréket. Mivel a cserék után is keletkezhet rossz sorrendű pár, ezért ismételjük meg a cseréket a sorozatban az első pártól az utolsóig, egészen addig, amíg el nem fogy az összes rossz sorrendű.

A megoldás lépései:

• tegyük fel, hogy nem lesz szükség cserére, a vizsgálandó párok száma n-1
• vizsgáljuk az adatokat az első pártól az utolsóig, ha a vizsgált pár első tagja a második után kellene, hogy álljon,akkor cseréljük meg őket, és jegyezzük meg, hogy szükség volt a cserére
• ha a 2. lépésben volt csere, csökkentsük a vizsgálandó párok számát 1-gyel, majd ismételjük meg az első lépéstől.

i : = db - 1

rendezett : = hamis

ciklus amíg i > = 1 és nem rendezett

rendezett : = igaz

ciklus j : = 1-től i-ig

ha t [ j ] > t [ j+1] akkor

csere : = t [ j ]

t [ j ] : = t [ j+1]

t [ j+1] : = csere

havége

ciklusvége

i : = i-1

ciklusvége

azonosító	típus	funkció
db	egész szám	az elemek száma
t	tömb	a sorozat elemeit tárolja
rendezett	logikai	a rendezettséget jelző információ
csere	mint a tömb eleme	segédváltozó a csere lebonyolításához

Cserélő rendezés

Lépések:

1. az első elem összehasonlítása az összes többivel

2. a második elem összehasonlítása az utána következőkkel

...

n-1. elem összehasonlítása az utolsóval

Ez a legkevésbé hatékony módszer. Ha két elem sorrendje nem jó, mindenképpen megcseréli azokat.

Ciklus i := 1-től n-1-ig

Ciklus j: = i +1-től n-ig

Ha t [ i ] > t [ j ] akkor

c : = t [ i ]

t [ i ] : = t [ j ]

t [ j ] : = c

Havége

Ciklusvége

Ciklusvége

vissza

Kiválogatás

Feladat : egy adott- adatokkal már feltöltött - tömb elemei közül egy másik tömbbe átemelni azokat az elemeket, amelyek adott P tulajdonsággal rendelkeznek. (pl. párosak)

A 2 tömböt egyforma méretűnek deklaráljuk, hiszen a másik tömbnek legfeljebb annyi eleme lehet, mint az adott feltöltött tömbnek.

A 2. tömb indexelésére az 1. tömb indexétől független változóra van szükség, ami 0 kezdőértékről indul, mivel eleinte üres, és csak akkor növeljük, ha P tulajdonsággal rendelkező elemet találunk.

Program

Deklaráció

a,b: tömb [1..N] egészből

i, db: egész

Algoritmus_kezd

db: = 0

ciklus i := 1-től N-ig

Ha a[ i ] páros akkor

db := db+1

b[db] := a[i]

Ha_vége

ciklus_vége

Algoritmus_vége

vissza

Szétválogatás

Feladat: egy adott - adatokkal már feltöltött - tömb elemei közül egy másik tömb elejére átemelni azokat az elemeket, amelyek P tulajdonsággal rendelkeznek, a többi elemet a vektor végén kell elhelyezni.

Két változót (e, v) vezetünk be a 2. tömb indexelésére. Az e változóval a vektor elejét, a P tulajdonságú elemeket indexeljük, ezért kezdőértéke 0. A v változóval a vektor végén elhelyezett, nem P tulajdonságú elemeket indexeljük, kezdőértéke N+1.

Deklaráció

a,b: tömb [1..N] egészből

i,e,v: egész

Algoritmus_kezd

e :=0 v := N+1

ciklus i := 1-től N-ig

Ha a[i] páros akkor

e:=e+1

b[e]:=a[i]

különben

v:=v-1

b[v] := a[i]

Ha_vége

Ciklus_vége

Algoritmus_vége

Pascal nyelven:

Var

a,b: array [1..N] of integer;

i,e,v: integer;

Begin

e :=0 ; v := N+1;

for i := 1to N do begin

if a[i] mod 2 = 0 then begin

e:=e+1;

b[e]:=a[i];

end

else begin

v:=v-1;

b[v] := a[i];

end;

end;

End.

vissza