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 A
0 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
