PROGRAMOZÁSI NYELVEK (GYAKORLAT)

PROGRAMOZÁSI NYELVEK (GYAKORLAT)

PROGRAMOZÁSI NYELVEK (GYAKORLAT)

A következő részben olyan szabványos algoritmusokkal fogunk foglalkozni, amelyek segítségével a későbbiekben sok hétköznapi problémát meg tudunk majd oldani.

MUNKAHELYZET- ESETFELVETÉS PROGRAMOZÁS Ezek az algoritmusok programozási nyelvtől függetlenek. Gyakorlatilag bármelyik nyelvre átültethetőek. A könnyebb megértés miatt mindegyiknek az elején található egy rövid leírás a működéséről, majd pszeudokódban is meg lesznek adva.

_________________________________________________________________________________________

SZAKMAI INFORMÁCIÓTARTALOM ALGORITMUS 1. Sorozatszámítás A sorozatszámítás során egy kezdőértéktől egy végértékig elkészítjük egy sorozat összes

elemét. Az eredményt kiíratjuk a monitorra. A következő példában 1-től n-dik elemig elkészítjük, ahol a sorozat minden eleme tízzel nagyobb az előzőnél: Eljárás Sorozatszámítás Y:=0

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

Y:=Y+10;

Ciklus vége

Ki Y

Eljárás vége

1

PROGRAMOZÁSI NYELVEK (GYAKORLAT)

2. Megszámlálás Megszámláláskor egy adott tömbben vagy intervallumban kell megszámolni, hogy egy

bizonyos tulajdonságnak hány elem felel meg. A következő példában egy n elemű T tömb azon elemeit számoljuk meg, amelyek pozitívak: Eljárás Megszámlálás DB:=0

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

Ha T[i]>0 akkor DB:=DB+1

Ciklus vége

Ki DB

Eljárás vége

3. Maximum kiválasztás Maximum, vagy minimum kiválasztáskor egy tömb vagy intervallum elemei közül kell megkeresnünk a legnagyobbat, vagy legkisebbet. A következő példában egy T nevű, n elemű tömbben keressük meg a legnagyobb elemet: Eljárás Maximumkiválasztás MAX:=T[1]

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

Ha T[i]>MAX akkor MAX:=T[i]

Ciklus vége Ki MAX

Eljárás vége

4. Eldöntés Eldöntés során egy halmaz elemeiről el kell dönteni, hogy tartalmaznak-e egy bizonyos

tulajdonsággal rendelkező elemet. A példában egy n elemű T tömbben vizsgáljuk meg, hogy tartalmaz-e negatív elemet. A végén a VAN változó logikai értéke adja meg a helyes választ: Eljárás Eldöntés

VAN:=hamis i:=1

Ciklus amíg i<=N és T[i]>=0 i:=i+1

Ciklus vége

VAN:=[i<=N]

Eljárás vége

2

PROGRAMOZÁSI NYELVEK (GYAKORLAT)

5. Keresés A keresés hasonló az eldöntéshez, de itt nem tulajdonságot, hanem egy konkrét elemet

keresünk egy halmaz elemei között. A példában egy n elemű T tömbben vizsgáljuk meg, hogy tartalmazza-e a 20-as számot. A végén a VAN változó logikai értéke adja meg a helyes választ:

Eljárás Eldöntés

VAN:=hamis i:=1

Ciklus amíg i<=N és T[i]=20 i:=i+1

Ciklus vége

VAN:=[i<=N]

Eljárás vége

6. Kiválasztás Kiválasztás során egy tömbben meg kell keresnünk egy konkrét elemet és meg kell

mondanunk, hogy hányadik elemről is van szó. A példában egy n elemű T tömbben

vizsgáljuk meg, hogy tartalmazza-e a 30-as számot. Ha igen akkor visszaadjuk a szám indexét:

Eljárás Kiválasztás i:=1

Ciklus amíg nem T[i]=30 Ciklus vége

i:=i+1

INDEX:=i Ki INDEX

Eljárás vége

7. Másolás Másolás során egy n elemű T tömb elemeit átmásoljuk egy n elemű X tömbbe. Fontos, hogy a tömbök elemszáma egyezzen, vagy a céltömb elemszáma nagyobb legyen: Eljárás Másolás

Ciklus i:=1-től N-ig X[i]:=T[i]

Ciklus vége

Eljárás vége

A másolás során persze elvégezhetünk valamilyen műveletet is az elemeken. A következő példában minden elemhez hozzáadunk 5-öt: Eljárás Másolás 3

PROGRAMOZÁSI NYELVEK (GYAKORLAT) Ciklus i:=1-től N-ig X[i]:=T[i]+5

Ciklus vége

Eljárás vége

8. Kiválogatás Kiválogatáskor egy tömbből átmásoljuk egy másik tömbbe azokat az elemeket, amelyek

megfelelnek egy kritériumnak. A példában egy n elemű T tömb negatív elemeit átmásoljuk egy X nevű tömbbe:

Eljárás Kiválogatás DB:=0

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

Ha T[i]<0 akkor DB:=DB+1 : X[DB]:=T[i]

Ciklus vége Eljárás vége

9. Szétválogatás A

szétválogatás

gyakorlatilag

egy

tömb

elemeinek

megadott

tulajdonság

szerinti

csoportosítása. Több eset is létezik: lehet két tömbbe, egy tömbbe és helyben elvégezni. A következő példák mind a három esetet bemutatják: a, Szétválogatás két tömbbe Ebben az esetben egy X tömb elemeit válogatjuk szét egy Y és egy Z tömbbe. Ha az eleme nullánál nagyobb, akkor az Y tömbbe kerül, különben a Z-be. Eljárás Szétválogatás_két_tömbbe DBY:=0 : DBZ:=0

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

Ha X[i]>0 akkor DBY :=DBY +1 : Y[DB>] :=X[i]

Eljárás vége

Ciklus vége

különben DBZ:=DBZ+1 : Z[DBZ]:=X[i]

b, Szétválogatás egy tömbbe Egy X tömb elemeit válogatjuk át egy Y tömbbe. A tömb elején lesznek azok az

elemek, amelyek nullánál nagyobbak, a végén pedig a kisebbek: Eljárás Szétválogatás_egy_tömbbe DB:=0 : DBY:=0

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

PROGRAMOZÁSI NYELVEK (GYAKORLAT) Ha X[i]>0 akkor DB :=DB +1 : Y[DB]:=X[i]

különben DBZ:=DBZ+1 : Y[N+1-DBZ]:=X[i]

Eljárás vége

Ciklus vége

c, Szétválogatás helyben Egy X tömb elemeit válogatjuk át helyben. A tömb elején lesznek azok az elemek, amik nullánál nagyobbak, a végén pedig a kisebbek: Eljárás Szétválogatás_helyben Y:=X[1] : A:=1 : B:=N

Ciklus amíg A
Ciklus amíg A
Ciklus vége

Ha A0 A:=A+1

Ciklus vége

Ha A
Ha Y>0 akkor DB:=A különben DB:=A-1 Eljárás vége

10.

Metszet

A metszet képzés gyakorlatilag a halmazműveletnek felel meg. Két tömb, X és Y, közös elemeit kiválogatjuk egy harmadik, Z tömbbe: Eljárás Metszet DB:=0

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

Ciklus amíg j<=M és X[i]<>Y[j] j:=j+1

Ciklus vége

Ha j<=M akkor DB:=DB+1 : Z[DB]:=X[i]

Ciklus vége

Eljárás vége

5

PROGRAMOZÁSI NYELVEK (GYAKORLAT)

11.

Unió

Az unió is halmazművelet. Két tömb elemeit egyesítjük egy harmadikban: Eljárás Unió Z:=X :

DB:=N

Ciklus i:=1-től M-ig j:=1

Ciklus amíg j<=N és X[j]<>Y[i] j:=j+1

Ciklus vége

Ha j>M akkor DB:=DB+1 : Z[DB]:=Y[i] Ciklus vége

Eljárás vége

12.

Összefuttatás, összefésülés

Összefutatás és összefésülés során két vagy több rendezett tömb elemeit tesszük át egy harmadikba úgy, hogy ott is rendezett marad a sorrend. a, Összefuttatás Eljárás Összefuttatás i:=1 :

j:=1 : k:=0

Ciklus amíg i<=N és j<=M k:=k+1

Elágazás

X[i]
X[i]=Y[j] esetén: Z[k]:=X[i] : i:=i+1 : j:=j+1 X[i]>Y[j] esetén: Z[k]:=Y[j] : j:=j+1

Elágazás vége

Ciklus vége

Cilkus amíg i<=N k:=k+1 : Z[k]:=X[i] : i:=i+1

Ciklus vége

Cilkus amíg j<=M

k:=k+1 : Z[k]:=Y[j] : j:=j+1

Ciklus vége

Eljárás vége b, Összefésülés

Eljárás Összefésülés

i:=1 : j:=1 : k:=0 : X[N+1]:=+

: Y[M+1]:=+ 6

PROGRAMOZÁSI NYELVEK (GYAKORLAT) Ciklus amíg i
Ha X[i]<=Y[j], akkor Z[k]:=X[i] : i:=i+1 különben Z[k]:=Y[j] : j:=j+1

Ciklus vége Eljárás vége

13.

Rendezés

A rendezési algoritmusok igen fontosak a programozásban. Nagyon sok programnak része valamilyen rendezés. Azért van szükség többféle rendezési algoritmusra, mert a problémától

függően mindig másik módszer a hatékonyabb. A következőkben a legfontosabb alap rendezésekkel ismerkedhetünk meg: a, Cserés rendezés: Az eljárás egy tömbön belül, helycserékkel oldja meg a rendezést. Eljárás Egyszerű_cserés_rendezés Ciklus i:=1-től N-1-ig

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

Ha X[j]<X[i], akkor s:=X[i] : X[i]:=X[j] : X[j]:=s

Ciklus vége

Ciklus vége

Eljárás vége

b,Buborék rendezés Az egyik legismertebb és legtöbbet használt rendezési algoritmus. A nevét az algoritmus működéséről kapta. A rendezés során először a legnagyobb (vagy legkisebb) elem kerül a

helyére. Utána pedig sorban a következő legnagyobb és így tovább. Vagyis egymás után, mint a buborékok elfoglalják az elemek a rendezett helyüket. Eljárás Buborékelvű_rendezés

Ciklus i:=N-1-től 1-ig -1-esével Ciklus j:=1-től i-ig

Ha X[j]>X[j+1], akkor s:=X[j] : X[j]:=X[j+1] : X[j+1]:=s

Ciklus vége

Ciklus vége Eljárás vége c,Minimum kiválasztásos rendezés

Az algoritmus szerint kiválasztjuk mindig a legkisebb elemet és ezt addig folytatjuk, amíg el nem fogy minden elem.

7

PROGRAMOZÁSI NYELVEK (GYAKORLAT) Eljárás Minimumkiválasztásos_rendezés Ciklus i:=1-től N-1-ig MIN:=i

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

Ha X[j]<X[MIN], akkor MIN:=j

Ciklus vége

s:=X[MIN] : X[MIN]:=X[i] : X[i]:=s

Ciklus vége

Eljárás vége d, Beillesztéses rendezés

Az algoritmus beilleszti egyenként az elemeket a rendezés szerinti megfelelő helyére. Eljárás Beillesztéses_rendezés Ciklus i:=1-től N-1-ig Y:=X[i+1] j:=i

Ciklus amíg j>0 és X[j]>Y X[j+1]:=X[j] j:=j-1

Ciklus vége

X[j+1]:=Y

Ciklus vége

Eljárás vége

14.

Logaritmikus keresés

A logaritmikus keresés, vagy bináris keresés egy olyan keresőalgoritmus, amit egy elem rendezett tömbben való keresésére használnak. A keresés intervallum felezéssekkel történik. Minden alkalommal elfelezzük a maradék elemeket és abban a félben folytatjuk a felezéses

keresést, amelyik tartalmazhatja a keresett elemet. A keresés során így egy n elemű tömbben O(log n) lépésben megtalálható a keresett elem. Az algoritmus innen kapta a nevét. Eljárás Logaritmikus_keresés A:=1 B:=N

Ciklus k:=[[A+B]/2]

Elágazás

X[k]Y esetén: B:=k-1

Elágazás vége

Mígnem A>B vagy X[k]=Y

Ciklus vége

VAN:=[A<=B]

8

PROGRAMOZÁSI NYELVEK (GYAKORLAT) Ha VAN, akkor S:=k Eljárás vége

15., Visszalépéses keresés [BackTrack] A visszalépéses keresés olyan esetekben használható, amikor a keresés fastruktúraként képzelhető el, amiben a gyökérből kiindulva egy csúcsot keresünk. Az algoritmus lényege, hogy a kezdőpontból kiindulva megtesz egy utat, és ha valahol az derül ki, hogy már nem juthat el a célig, akkor visszalép egy korábbi döntési ponthoz, és ott más utat választ. Eljárás Visszalépéses_keresés i:=1 : S[1]:=0

Ciklus amig i>=1 és i<=N

Ha VanJó(i) akkor i:=i+1: S[i]:=0 kül. i:=i-1

Ciklus vége

VAN:=[i>N]

Eljárás vége Függvény VanJó[i:szám]:logikai Ciklus

S[i]:=S[i]+1

Mignem s[i]>M[i] vagy Rendben(i,S[i])

Ciklus vége

VanJó:=(S[i]<=M[i]) Függvény vége

Függvény Rendben(i,S[i]):logikai j:=1

Ciklus amig j
Ciklus vége

ElemRendben:=(j=i) S[i]<>S[j] és |i-j|<>|S[i]-S[j]| Függvény vége

9

PROGRAMOZÁSI NYELVEK (GYAKORLAT)

Összefoglalás Milyen alapvető tömbkezelő algoritmusokat ismer? Milyen kereső algoritmusokat ismer? Ismertessen néhány rendezési módszert! Ismertesse a visszalépéses keresés lényegét!

TANULÁSIRÁNYÍTÓ A programozás tanulása során törekedjünk arra, hogy megértsük az algoritmusok működésének

minden

egyes

részletét.

Legyünk

tisztában

a

változók

feladataival,

működésével. Az algoritmusok megértése után sokkal könnyebben meg tudjuk írni a megfelelő programot rá.

A tanulás során próbáljuk meg a fent ismertetett algoritmusokat egy konkrét programozási nyelvre átültetni. Ha ez sikerült, akkor érdemes a programok bizonyos részletein változtatni és megfigyelni, hogy ez hogyan befolyásolta a program működését.

Ha valaki megszereti a programozást, akkor gyakorlatilag egy teljesen új virtuális világ fog

megnyílni előtte, ami szerintem az egyik legjobb logikai játék is a számítástechnika

világában.

10

PROGRAMOZÁSI NYELVEK (GYAKORLAT)

ÖNELLENÖRZŐ FELADATOK Ebben a részben találunk néhány feladatot, ami segít elmélyíteni a fenti ismereteket. A feladatokat itt kell megoldani a kijelölt helyen. Segítségképpen nyugodtan lapozzunk vissza kezdetben a tananyaghoz, de az lenne a végső cél, hogy teljesen önállóan tudjuk megoldani a

feladatokat!

Ha

számítógépünkön is!

itt

sikerült

megírnunk

egy

algoritmust,

akkor

próbáljuk

ki

a

1. feladat Készítsen szöveges algoritmus pszeudokód segítségével egy verseny résztvevőinek pontjai

alapján történő rendezésére! Használjon két tömböt! Az egyikben a versenyzők neve, a másikban a szerzett pontszámok szerepeljenek!

_________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________

11

PROGRAMOZÁSI NYELVEK (GYAKORLAT) 2. feladat Készítsen szöveges algoritmus pszeudokód segítségével, amely egy tömb elemei közül kiválogatja a páros számokat egy másik tömbbe!

_________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________

12

PROGRAMOZÁSI NYELVEK (GYAKORLAT) 3. feladat Készítsen algoritmust egy ön által választott programnyelven, ami megszámlálja, hogy hány prímszám van egy tömb elemei között!

_________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________ _________________________________________________________________________________________

13

PROGRAMOZÁSI NYELVEK (GYAKORLAT)

MEGOLDÁSOK

1. feladat Eljárás Feltöltés

Ciklus i:1 től 10-ig Be X[i] Be Y[i]

Ciklus vége

Eljárás Rendezés

Ciklus i:=9-től 1-ig -1-esével Ciklus j:=1-től i-ig

Ha X[j]>X[j+1], akkor s:=X[j] : X[j]:=X[j+1] : X[j+1]:=s z:=Y[j] : Y[j]:=Y[j+1] : Y[j+1]:=z Ha vége Ciklus vége

Ciklus vége

Eljárás vége

14

PROGRAMOZÁSI NYELVEK (GYAKORLAT) 2. feladat Eljárás Kiválogatás DB:=0

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

Ha (T[i]/2)=int(T[i]/2) akkor DB:=DB+1 : X[DB]:=T[i]

Ciklus vége

Eljárás vége

15

PROGRAMOZÁSI NYELVEK (GYAKORLAT) 3. feladat program PRIM;

var p,i,n:longint; k:boolean;

t:array [1..10] of longint; begin

p:=0;

for j:=1 to 10 do begin i:=2;k:=true; repeat

if t[j] mod i=0 then k:=false; i:=i+1;

until (i>Sqrt(n)) or not k;

if k then p:=p+1;

end; end.

16

PROGRAMOZÁSI NYELVEK (GYAKORLAT)

IRODALOMJEGYZÉK FELHASZNÁLT IRODALOM KUROS, A. G. : Felsőbb algebra. Budapest (Tankönyvkiadó) 1978. KNUTH, Donald, E.: A számítógép-programozás művészete I-III. Budapest (Műszaki) 1987. OBÁDOVICS J. Gyula: Matematika. Budapest (Műszaki) 1978. REIMANN József: Matematika. Budapest 1982. WIRTH, Niklaus: Algoritmusok + Adatstruktúrák = Programok. Budapest (Műszaki) 1982.

17