Budapesti M szaki F iskola Regionális Oktatási és Innovációs Központ
Távoktatás
PROGRAMOZÁSI ALAPFOGALMAK ÉS ALGORITMUSOK Segédlet
Készítette: Burián Ágnes
Villamosmérnök és m szaki menedzser szak 5. félév 1. kiadás Székesfehérvár 2002.
1
Programozási alapismeretek A programok végrehajtása A számítógépet a program m ködteti. A processzor közvetlenül csak a gépi kódú programokat tudja értelmezni. A gépi kódú program egy utasítása a m velet kódjából és a m velet operandusaiból áll. Az utasítások ugyanúgy, mint az adatok 0-k és 1-ek sorozata. A végrehajtható utasítások az operatív tárban vannak. Ha a tár egy részének tartalmát kiírjuk, nem tudjuk eldönteni, hogy program vagy adat! Utasításkészlet: a processzor által értelmezhet+ utasítások összessége. A gépi kód a leg+sibb programozási nyelv. Ma már csak szimbolikus nyelvben írjuk a programokat, ezeket a programokat a fordító program teszi át gépi kódba. A memória (operatív tár) - csak olvasható memória (ROM): kikapcsoláskor nem veszti el tartalmát, ezért olyan programokat tárolnak benne, amelyre a számítógépnek mindig szüksége van. - közvetlen elérés memória (RAM): írható, olvasható. Kikapcsoláskor elveszti tartalmát. A RAM a programozó rendelkezésére álló tár. Itt helyezkednek el a felhasználó által írt programok és az operációs rendszer felhasználó által látható részei. A tár legkisebb címezhet+ egysége a bájt, minden bájtnak önálló címe van. Az adatok általában több bájt hosszúságúak, de ugyanúgy az utasítások is. A memória közvetlen elérés tároló, mert bármely tárrekesz tartalmát a processzor egyetlen lépésben megtalálja a címe segítségével. A vezérl+egység speciális tároló rekeszei a regiszterek. Adatok tárolása a számítógépben A számítógépen az adatokat nullák és egyesek, bitek kombinációjaként (binárisan) tároljuk, dolgozzuk fel és továbbítjuk. Információs rendszereinkben viszont az adatok bet kb+l, számjegyekb+l és írásjelekb+l állnak. (karakterek) A karakterek ábrázolása számítógépen a kódjukkal történik (bináris szám)! Szabványos kódrendszerek (ASCII, EBCDIC) a számítástechnika alappillérei. A kódrendszerek lényege, hogy minden karakterhez kölcsönösen egyértelm megfeleltetéssel hozzá van rendelve egy 8 bites (bájtos) kódérték. A karaktereket a kódjukkal azonosítjuk. Gépi számábrázolás: fixpontos lebeg+pontos Fixpontos számábrázolás (egész) 2 vagy 4 bájton történik. Ha csak negatív számokat kellene ábrázolni: 0 216-1 a 2 bájtos tartomány. A negatív számokat olyan formában célszer tárolni, hogy a gépi kivonás összeadással legyen helyettesíthet+, mert akkor a számítógépnek csak az összeadást kell tudnia elvégezni. Az el+jeles egész számok ábrázolására Neumann János dolgozta ki a kettes komplemens képzés (más néven nullára történ+ kiegészítés) módszerét. Komplemens képzés: a bináris szám minden jegyét átfordítjuk a másik jegyre. Például: 0101 0001 1010 1110 (Ezt egyes komplemensnek is szokás nevezni.) Ha a komplemenshez még 1-et hozzáadunk kettes komplemens alak jön létre. Pl.: 89 = 0101 1001 1010 0110 komplemens + 1 1010 0111 kettes komplemens 2
Vegyük észre, hogy ha a számot és kettes komplemensét összeadjuk, akkor az adott méretben (példánkban 8 biten) az eredmény 0 lesz! 0101 1001 +1010 0111 10000 0000 Vessük össze ezt azzal a matematikában megismert ténnyel, hogy bármely számhoz a negatívját hozzáadva az eredmény 0 lesz! Tehát 89 kettes komplemense lesz a -89. A számítógépek többnyire a kettes komplementerképzésen alapuló eljárással végzik a kivonást. Negatív számok tárolása: láttuk az el+bbiekben, hogy az x 0 esetben -x az x kettes komplemenseként állítható el+. Lássunk egy 16 bites példát (x=12 16 biten ábrázolva): 0000 0000 0000 1010 1111 1111 1111 0101 komplemens 1111 1111 1111 0110 kettes komplemens (-x=-12) Még van egy probléma: hogyan tudjuk eldönteni, hogy egy ilyen szám pozitív-e vagy pedig egy másik pozitív szám kettes komplemense? A felírásból sehogy! Ezért megegyeztünk abban, hogy a nem negatív számok csak az alsó 15 bitet foglalják el, ilyen módon ezek kettes komplemensének legfels+ bitje 1 lesz, azaz ezek lesznek a negatív számok. A 0000 0000 kettes komplemense is 0. Az 1000 0000 negatív szám kettes komplemense : 1000 0000. Tehát a k 16 bites egész: - 32 768 k 32 767 Lebeg pontos számábrázolás (valós) A fixpontos számábrázolásnak 2 hátrányos tulajdonsága van: - kicsi az ábrázolható számtartomány - a pontosság er+sen korlátozott: ha a szám végére képzeljük a tizedespontot, az egészek közötti értékek a gép számára nem léteznek. Azaz : 1/3=0 vagy 5/3=1 stb. A lebeg+pontos számábrázolás a számok hatványkitev+s felírásán alapszik. Pl. 1800000000=1.8 109 1100011101.011=0.1100011101011 27 azaz M pk A képletben k a számrendszer alapszáma (példánkban 10 ill. 2). Hogy egyértelm legyen a felírás M<1 és a tizedesponttól jobbra álló els+ jegy nem 0. A lebeg+pontos szám a számítógépen a bináris számok hatványkitev+s alakja. Ehhez a számot ún. kettes normál alakra kell hozni. Pl. /-12.25/ = 1100.012 =0.110001 24 A szám kettes normál alakjának karakterisztikája 4 = 1002 így a szám kettes normál alakban: -0.110001 2100 Az ábrázolás a következ+ módon történik: - els+ bit a szám el+jele, - 7 biten a karakterisztika torzítva, - végül 3 bájton a mantissza. A torzítás (a negatív kitev+k miatt kell) 26=64(=100 0000) hozzáadását jelenti a karakterisztikához, így nem lesz soha negatív kitev+! A gépi nulla fogalma Az ábrázolandó szám karakterisztikája olyan kicsiny, hogy a torzítással sem lesz pozitív. A nullává váló szám nagysága tehát a karakterisztika számára rendelkezésre álló bitek számától függ. A gépi nullát úgy ábrázoljuk, hogy a karakterisztikát és a mantisszát is nullának vesszük. A véges hosszú mantissza miatt nem tudjuk az összes valós számot ábrázolni! 3
A számítógép alkalmazása Az adatok önálló, emberi beavatkozás nélküli feldolgozása a számítógép alapfeladata. A feldolgozást irányító, a gép számára végrehajtható formában adott utasítássort nevezzük programnak. Minden program algoritmusokra épül, amelyek egy adott feladat teljes vagy részbeni megoldására szolgáló m veletsort jelentenek. Az algoritmussal szemben támasztott követelmények: - Legyen egyértelm és jól meghatározott, azaz ugyanazon bemen+ adatokra minden esetben ugyanazt az eredményt szolgáltassa! - Legyen id+ben és lépésszámban véges, azaz korlátozott hosszú és végrehajtási idej ! - Legyen teljes, általános érvény , azaz különböz+ bemen+ adatokkal is oldja meg a feladatot, ne egy konkrét problémára, hanem probléma osztályra vonatkozzon! A programozás alapjai A programozás elméleti lépései el+tt ismerkedjünk meg a programozási nyelvekkel. Az összes programot így az operációs rendszert és az alkalmazásokat is programozók készítik, valamilyen programozási nyelven. Ezeket a nyelveket a számítógép processzorának nyelvéhez való közeliségük szerint szokás csoportosítani. Programozási nyelvek a) gépi nyelv: a számítástechnika +skorában egyedüli lehet+ség volt a gép bitsorozattal való programozása. b) alacsony szint (assembly) nyelv: a gépi nyelv 0 és 1 jelekb+l álló bitsorai helyett a programozó mnemonikokat (emlékeztet+ rövídítéseket, azaz azonosítókat) ír, amelyek már áttekinthet+bbé, olvashatóbbá teszik a programot. Itt már elegend+ a programozónak a számítógép fontosabb egységeit és paramétereit ismernie. Így a gép lehet+ségeit majdnem teljesen kihasználó programokat írhatunk, és bizonyos mértékben hordozhatóvá is válik a programunk. Cserében a kódsort le kell fordítani gépi nyelvre, amelyet egy assemblernek nevezett program végez el, amit az adott géptípushoz egyedi módon kapcsolódva készítenek el. c) közép szint nyelv: nagy hatékonyságú, de géptípustól függetlenebb programozási nyelvek tartoznak ide. Fordítója az ún. compiler, amely közvetlen módon állítja el+ a gépi kódot. A programozó alkalmazhatja a korszer programozási módszereket, mint a strukturáltság és az objektumorientáltság, de ismernie kell továbbra is a gép legtöbb hardver paraméterét. Ilyen nyelv például a C, amelyen Európában a programok 85%-a íródik, de ilyen a FORTH, SNOBOL és a FAST nyelv is. Az utóbbi kett+ inkább a Távol-Keleten terjedt el. d) magas szint nyelv: a programozó a legkorszer bb programozási módszereket alkalmazva készíthet segítségükkel gépfüggetlen programokat, amelyek ugyan kevésbé hatékonyak, de szabadon hordozhatóak. Vagy teljes fordítást végz+ compilert, vagy soronként értelmez+ interpretert kell használni a gépi nyelvre való lefordításhoz. El+bbi készült a PASCAL és az ADA, utóbbi a BASIC és a LOGO nyelvhez.
4
Algoritmusok Bármilyen programozási módszert alkalmazunk és bármilyen nyelven írjuk is meg a programot, el+ször meg kell terveznünk a probléma megoldására szolgáló elemi lépések sorozatát, azaz az algoritmust! Algoritmusok tervezésére, leírására, szemléltetésére többféle eszköz létezik, közülük a két legismertebb, a: - mondatszer leírás (mondatnyelv) - folyamatábra (blokkdiagram) A következ+kben ezeket az algoritmus-leírási módokat ismertetjük: a mondatszer leírást és a rajzos megadás jelöléseit. Mindkét esetben a legfontosabb algoritmus-leírási szerkezetek jelöléseit adjuk meg: 1, adat be- és kivitel; 2, értékadás; 3, utasítássorozat (szekvencia); 4, feltételes elágazás (szelekció); 5, ismétlési szerkezet (iteráció); 6, eljárás vagy függvény megadása (deklaráció); Mondatszer leírás Az anyanyelvi megfogalmazáshoz hasonló, de annál tömörebb leírási mód. Az él+nyelv pontatlanságait próbáljuk vele kizárni, de még egyszer en értelmezhet+ marad. 1, Adat be- és kivitel: BE: változók [az adatokkal szemben állított követelmények] KI: kifejezések [a kiírás formájára vonatkozó követelmények] 2, Értékadás: változó:=kifejezés Az utasítás hatására a változó felveszi a kifejezés aktuális értékét. 3, Utasítás sorozat: Egymás alá írással adjuk meg az egymás után végrehajtandó utasításokat. 4, Feltételes elágazások: a) Egyágú HA feltétel AKKOR utasítás ELÁGAZÁS VÉGE Ha a feltétel teljesül, akkor az utasítás végrehajtásra kerül, ha nem teljesül, akkor az ELÁGAZÁS VÉGE után folytatódik a program. Az utasítás helyén több utasítás is állhat. b) Kétágú Ha feltétel AKKOR utasítás1 KÜLÖNBEN utasítás2 ELÁGAZÁS VÉGE Ha a feltétel teljesül, akkor az utasítás1 kerül végrehajtásra, ha nem akkor az utasítás2. Mindkét esetben az ELÁGAZÁS VÉGE után folytatódik a program.
5
c) Többágú ELÁGAZÁS feltétel1 ESETÉN utasítás1 feltétel2 ESETÉN utasítás2 ....................
feltételn ESETÉN utasításn EGYÉB ESETBEN utasítás ELÁGAZÁS VÉGE Ha az i-edik, feltételi teljesül, akkor az utasítási kerül végrehajtásra, ha egyik feltétel sem teljesül, akkor az utasítás. Bármely esetben az ELÁGAZÁS VÉGE után folytatódik a program. (A feltételeknek egymást kizárónak kell lennie, azaz legfeljebb egy teljesülhet közülük.) 5, Ismétlési szerkezetek: a) Elöltesztel CIKLUS AMÍG feltétel ciklusmag CIKLUS VÉGE Amíg a feltétel teljesül, addig a ciklusmag végrehajtásra kerül, ha már nem teljesül, akkor a CIKLUS VÉGE után folytatódik a program. b) Hátultesztel CIKLUS ciklusmag AMÍG feltétel CIKLUS VÉGE A ciklusmag mindaddig végrehajtásra kerül, amíg a feltétel teljesül. Ha már nem teljesül, akkor a CIKLUS VÉGE után folytatódik a program. (Egyszer a ciklusmag mindenféleképpen végrehajtódik!) 6, Eljárás vagy függvény megadás: ELJÁRÁS_neve (paraméterek) utasítások ELJÁRÁS VÉGE Az eljárás vagy függvény hívása nevének és paramétereinek leírásával történik meg. A program egy kitüntetett szerep eljárás (vagy függvény), neve meghatározott: PROGRAM utasítás sorozat PROGRAM VÉGE Megjegyzés: A C programokban ennek a kitüntetett szerep eljárásnak a main() függvény felel meg, amely a belépési pont. 6
Folyamatábra (blokkdiagram) Az egyik legkorábban kialakult megadási mód. Alapjeleit maga NEUMANN dolgozta ki. Az egyes szerkezeti elemek között nyilakkal jelöljük a végrehajtási sorrendet. Ennek köszönhet+en igen vadul ugráló programok is születhetnek, minden átgondolt szerkezet nélkül. Az értékadó utasítás illetve valamilyen eljárás téglalapba, az egy vagy többágú kiválasztás rombuszba vagy lapos hatszögbe, az adatáramlás paralelogrammába, a vezérl+ utasítások körbe kerülnek. Az ismétlési szerkezeteket elrejtve tartalmazza az ábra. Csak nagy odafigyeléssel és következetességgel érhetjük el a strukturáltságot. 1. Adat be- és kivitel:
BE:
változó
KI:
kifejezés
2. M veletvégzés:
változó := kifejezés
Lehet értékadó, de másfajta utasítás is. Példánkban utasításként az értékadás szerepel: a változó felveszi a kifejezés aktuális értékét. 3. Utasítás sorozat: A nyilak által meghatározott irányban haladva kell végrehajtanunk az utasításokat. 4. Feltételes elágazás:
I utasítás1
feltétel
H utasítás2
Ha a feltétel teljesül, akk Ha a feltétel teljesül, akkor az utasítás1 kerül végrehajtásra, ha nem, akkor az utasítás2. Mindkét esetben folytatódik a program. Megfelel a kétágú feltételnek. Egyágú esetén nincs utasítás a hamis ágban. A többágú elágazás is összeépíthet+ ebb+l. 7
5. Ismétlési szerkezet: A ciklusok a feltételes elágazás segítségével készíthet+k. Például a hátul tesztel+ ciklus a következ+képpen építhet+ fel:
ciklusmag
feltétel
I
H A ciklusmag mindaddig végrehajtásra kerül, amíg a feltétel teljesül. Ha nem teljesül, akkor folytatódik a program. (Egyszer a ciklusmag mindenféleképpen végrehajtódik!) 6. Eljárás megadás:
eljárásnév
utasítások
ELJÁRÁS VÉGE
Külön blokkdiagramot készítünk számára. Az eljárás hívása az eljárásnév ovális dobozba írásával történik.
A program egy kitüntetett szerep eljárás, kezd+pontja a START, végpontja(i) a VÉGE:
8
START eljárásnév
utasítások
VÉGE
Összehasonlító példák Összefoglalásként megmutatjuk mindkét megfogalmazni egy ismert feladat megoldását.
leíró
eszköz
segítségével,
hogyan
lehet
Keressük meg 10 egymás után beírt valós szám közül a legnagyobbat! A feladatot írjuk le tömörített anyanyelvi formában: 1. olvassuk be az els+ számot, ez lesz egyben eddig a legnagyobb is, amit jelöljön m, i legyen 2, azaz i:=2; 2. olvassuk be a következ+ számot a k-ba; 3. ha a k nagyobb m-nél legyen m értéke k; 4. növeljük meg az i értékét eggyel; 5. ha kell még beolvasni, azaz i<=10, akkor vissza a 2. ponthoz; 6. írjuk ki az m értékét; 7. vége. Mondatszer leírással megadva: PROGRAM BE: m [valós szám] CIKLUS i:=2-TLL 10-IG BE: k Ha k>m AKKOR m:=k ELÁGAZÁS VÉGE CIKLUS VÉGE KI: m "a legnagyobb szám a beírtak közül" PROGRAM VÉGE
9
Folyamatábrával megadva: START
BE: m
i:=2
BE: k
i:=i+1 H
I k>m m:=k
I
i<10 H KI: m a legnagyobb"
VÉGE
Figyelem: Ezen összehasonlító példákban és a kés+bbi algoritmusoknál is az elemeket sorszámukkal azonosítjuk. Ez pedig nem ugyanaz, mint a tömbindex a C programokban: ott az els+ elem indexe nulla!
10
Adjuk össze 1-t(l 100-ig a számokat! Folyamatábra:
START eljárásnév
I:=1
N:=100
Összeg:=0
nem
igen I<=N
Ki: Összeg
I:=I+1
Összeg:= Összeg+I
VÉGE
Mondatszer leírás: PROGRAM I:=1 N:=100 ÖSSZEG:=0 CIKLUS amíg I N ÖSSZEG:= ÖSSZEG+I I:= I+1 CIKLUS VÉGE Ki: ÖSSZEG PROGRAM VÉGE 11
Adatszerkezetek Minden algoritmus-leírásnak tartalmaznia kell el+írást arra is, hogy milyen tulajdonságú adatokon végzi a m veleteket. Meg kell tehát adnunk, hogy mi az adat értékkészlete, milyen m veleteket végezhetünk a lehetséges értékekkel, valamint azokat milyen módon ábrázolva tároljuk: azaz megadjuk az adattípust. Az adatokat típusuk szerint két csoportba bonthatjuk: • elemi adat, tovább nem bontható, azaz nem rendelkezik a felhasználó által kezelhet+ kisebb részekkel, bels+ szerkezettel; • összetett adat, az egyes alkotó elemekkel külön is végezhetünk m veleteket, elemi adattípusokból felépül+ szerkezettel rendelkezik. Az elemi és az összetett adattípusokat együtt adatszerkezeteknek szokás nevezni. Az algoritmusok megadásánál megköveteltük az általánosságot a minél nagyobb problémaosztálynak való megfelelést. E cél érdekében az absztrakt adattípusok használatával az algoritmust kiterjeszthetjük, általánosabban értelmezhet+vé tehetjük. Minden konkrét algoritmushoz kialakíthatunk egy neki megfelel+ adattípust. Az elkövetkez+ekben azokat az általánosan használt adattípusokat ismertetjük a rajtuk értelmezett m veletekkel együtt, amelyek a napi munkában leggyakrabban el+fordulnak. Elemi adattípusok Egy adattípus besorolása nagyban függ attól, hogy milyen programozási nyelvvel dolgozunk. A 4 byte méret egész a magas szint nyelvekben elemi adattípus, míg a gépi kódban összetett típusként kell kezelnünk. Hasonló probléma az, hogy míg 2 byte méret egész számok szinte minden nyelvben léteznek, a magas szint nyelvekben értelmezett rajtuk az összeadás, a kivonás, a szorzás, az osztás és a maradékképzés is, addig a gépi kódban az utóbbi m velet nem. A következ+kben ezért nem biztos, hogy az éppen általunk használt nyelvre is igaz lesz a következ+ csoportosítás. Egész szám Az egész (fixpontos) számokat kettes számrendszerben, a legtöbb számítógépen 2 bájton tárolva ábrázoljuk. Az értékkészlet -32768 és 32767 közötti egész számokból áll. E korlátozás számos hiba forrása lehet; s+t bizonyos nyelvek esetében meglep+ dolgokat tapasztalhatunk: 32767+1 eredményeként 32768 helyett -32768-at kapunk! Valós szám A valós számokat lebeg+pontos módban ábrázoljuk. A valós számok értékkészletére két korlátozás érvényes: az egyik a nagyságrendi korlát, a másik a pontossági korlát. A tárolás a legtöbb nyelvben 4 bájton történik, a kettes normálalakra hozás után. A szám nagyságrendjét a 12
karakterisztika adja, míg pontosságát a mantissza. Ennek véges jegyszáma miatt valójában nem is valós számokat ábrázolunk, hanem minden valós érték helyett egy azt jól közelít+ racionális számot. Az alábbi programkészlet igen szemléletesen mutatja be ennek következményeit: PROGRAM n:=3 [n egész szám] x:=1/n [x valós szám] CIKLUS i:=1-TLL 20-IG x:=(1+n)*x-1 KI: x CIKLUS VÉGE PROGRAM VÉGE A program látszólag egyszer dolgot csinál: hússzor kiírja az egyharmad értéket. Az n jelöli a 3 egész számot, x a reciprokát, majd hússzor vesszük az n+1 x-szeresét és ezt 1-gyel csökkentjük, ez lesz az új értéke az x-nek. A mindenkori x értéket kiírjuk, azaz húsz darab egyharmad értéket kellene látnunk. A programot lefuttatva bármely konkrét nyelvre átkódolva, meglep+dve tapasztaljuk, hogy korántsem a várt eredményt kapjuk! (A jelenség oka az, hogy 1/n az egészek körében nulla!) Karakter Egy darab karakter tárolását lehet+vé tev+ adattípus, mérete 1 bájt. A karakterek ábrázolására ma már legtöbbször az ASCII kódrendszert használjuk, ami 8 bites, így az értékkészlet 0 - 255. A karakterek összehasonlítása, megel+z+ vagy rákövetkez+ karakter meghatározása, mint m veletek is e kód alapján valósulnak meg. Összetett adattípusok Az összetettebb programokban az elemi adattípusok helyett inkább az összetett adattípusokat alkalmazzák. A következ+kben megismerkedünk a leginkább használt típusokkal és néhány absztrakt szerkezettel is. Az összetett adattípusokkal végezhet+ m veletek megegyeznek az elemein végezhet+ m veletekkel. A konkrét elemtípusok helyett az ELEMTÍPUS megnevezést fogjuk használni. Tömb A legismertebb összetett típus. Gyakorlatilag mindig ezt használjuk, ha azonos típusú adatok sorozatát akarjuk kezelni. Rögzített elemszámú, bármely elemére annak sorszámával, az indexével hivatkozunk, amelynek feladata egyértelm en megadni, hogy tömbön belül az elem pontosan hol helyezkedik el. Az egyindex tömböket szokás vektornak, a kétindex tömböket mátrixnak nevezni. Az azonosításhoz szükséges indexek számát dimenziónak is nevezik. Füzér (string) A füzér vagy sztring típus egy speciális tömb típus, amelynek elemei karakterek, s hossza nem el+re meghatározott. A füzér egyes elemeire sorszámukkal lehet hivatkozni. Általában tényleges tárbeli hossza 1 bájttal nagyobb, mint a füzér karaktereinek a száma, ez a byte vagy a füzér hosszát, vagy egy speciális füzérlezáró karaktert tartalmaz. Tipikus m velete egy részének kiemelése, illetve két füzér egyesítése. 13
Elemi algoritmusok A számítógépes feladatmegoldás során az algoritmus megtervezésekor bizonyos elemi tevékenységek gyakran felmerülnek megoldandó feladatként. Az ezeket megoldó elemi algoritmusokat (programozási tételeket) mutatjuk meg a következ+kben. Az algoritmusokat mondatszer leírással adjuk meg.
Algoritmusok, amelyek egy sorozatból egy adatot állítanak el : Elemek összegzése Adott egy N elem tartalmazza.
A számsorozat. Határozzuk meg az elemek összegét! A végeredményt az S
ELJÁRÁS ÖSSZEGZÉS (A[],N,S)
S= 0 I=0 CIKLUS AMÍG I< N S= S +A[I] I=I+1 CIKLUS VÉGE ELJÁRÁS VÉGE
Lineáris keresés Adott egy N elem A sorozat, és egy, az elemein értelmezett, T tulajdonság. Döntsük el, hogy van-e olyan eleme a sorozatnak, amely rendelkezik a T tulajdonsággal, és ha van, akkor hányadik! (Ha nincs ilyen tulajdonságú elem, akkor a sorszám értéke legyen -1!) Lineáris_ keresés (A[],N,T,SORSZAM) SORSZAM=-1 I=0 CIKLUS AMÍG I < N ÉS A[I] NEM T tulajdonságú I= I+1 CIKLUS VÉGE Ha I < N akkor SORSZAM=I ELÁGAZÁS VÉGE
ELJÁRÁS
ELJÁRÁS VÉGE
Maximum kiválasztása Az el+bbi feladat egy speciális eseteként, egy adott sorozat legnagyobb (vagy esetleg legkisebb) elemének megkeresése is gyakran el+fordul. Adott N elem A számsorozatból keressük ki a legnagyobb elemet! ELJÁRÁS MAXIMUM (A[],N,MAX) MAX= A[0] I=1 CIKLUS AMÍG I < N HA MAX< A[I] AKKOR MAX=A[I] ELÁGAZÁS VÉGE I=I+1 CIKLUS VÉGE ELJÁRÁS VÉGE 14
Megszámlálás A tulajdonság el+fordulása mellett az is kérdés lehet, hogy hány elem rendelkezik ezzel az adott tulajdonsággal. Legyen adott egy N elem A sorozat és egy, az elemein értelmezett, T tulajdonság. Határozzuk meg a T tulajdonsággal rendelkez+ elemek számát! ELJÁRÁS MEGSZÁMLÁLÁS(A[],N,DB) DB= 0 I=0 CIKLUS AMÍG I < N Ha A[I] T tulajdonságú AKKOR DB= DB+1 ELÁGAZÁS VÉGE I=I+1 CIKLUS VÉGE ELJÁRÁS VÉGE PÉLDA:
Ha a sorozat: 1, 3, 5, 7 Ha a sorozat: 1, 2, 4, 8
a tulajdonság a párosság, a tulajdonság a párosság,
akkor DB=0. akkor DB=3.
Algoritmusok, amelyek egy sorozatból egy másik sorozatot állítanak el : Kiválogatás Egy sorozat elemei közül azokat válogatjuk ki egy új sorozatba, amelyek megfelelnek egy adott tulajdonságnak. Legyen adott egy N elem A sorozat és egy, az elemein értelmezett, T tulajdonság. Gy jtsük ki a B sorozatba az A sorozat T tulajdonságú elemeit! A készül+ sorozat elemszáma DB lesz. (Ha az A sorozatban nincs T tulajdonságú elem, akkor DB 0 lesz!) ELJÁRÁS KIVÁLOGATÁS (A[],N,T,B[],DB) DB=0 I= 0 CIKLUS AMÍG I < N HA A[I] T tulajdonságú AKKOR B[DB]=A[I] DB=DB+1 ELÁGAZÁS VÉGE I=I+1 CIKLUS VÉGE ELJÁRÁS VÉGE
Rendezések Gyakran a rendezett elemekkel való m veletvégzés sokkal hatékonyabb, mint rendezetlen elemek esetében. Ezért nagyon fontosak a sorozat elemeit más sorrendbe el+állító algoritmusok. A kívánt rendezési irány lehet növekv+ vagy csökken+ Valamennyi ismertetésre kerül+ rendezési algoritmusban a növekv( sorrend elérése a cél. A többféle rendezési módszer közül a legismertebbek algoritmusát adjuk meg. A rendezéseket mindig helyben, új sorozat létrehozása nélkül kell megoldani. Ha két sorozattag között a reláció nem a kívánt rendezettség szerinti, akkor a tagok felcserélésére van szükség. 15
Két elem cseréjét a következ+kben az alábbi módon jelöljük: EGYIK A csere megvalósításához egy segéd változót használunk: EGYIK
MÁSIK
jelentése tehát:
MÁSIK.
segéd= egyik egyik= másik másik= segéd
Minimum-elven alapuló rendezés A minimumkereséses rendezés lényege az, hogy egy adott intervallumban - amely kezdetben a teljes sorozat - megkeressük a legkisebb elemet, s azt tesszük az els+ helyre. A következ+ lépésben eggyel sz kítjük az intervallumot (megnöveljük a sorozat alsó határát jelöl+ indexet), és ismét a legkisebb elemet visszük el+re. Végül a rendezend+ adatok elfogynak, a sorozat végére érünk. A mindenkori legkisebb elem keresése lineáris módszerrel történik. (Ha a kívánt sorrend a csökken+ rendezettség, akkor a maximum-elv rendezési algoritmust használjuk, ami csak a relációban különbözik.) ELJÁRÁS Minimum_elv (A[], N) I=0 CIKLUS AMÍG I < N-1 J=I+1 CIKLUS AMÍG J < N HA A[I] > A[J] AKKOR A[I] A[J] ELÁGAZÁS VÉGE J=J+1 CIKLUS VÉGE I=I+1 CIKLUS VÉGE ELJÁRÁS VÉGE
Buborék rendezés A buborék rendezés mindig két szomszédos elemet vizsgál, s ha azok a kívánt rendezettségnek nem megfelel+ relációban vannak, felcseréli +ket, majd tovább lépve újabb elempárt vizsgál. Az elejét+l a végéig ismételten végigpásztázva az egész sorozatot, eljutunk a rendezett állapotig, amikor már nincs szükség cserére. A bels+ ciklus egy lefutása után a legnagyobb elem az utolsó helyre kerül. ELJÁRÁS BUBORÉK_ELV(A[],N) I=1 CIKLUS AMÍG I < N J=0 CIKLUS AMÍG J < N-I HA A[J] > A[J+1] AKKOR A[J] ELÁGAZÁS VÉGE J=J+1 CIKLUS VÉGE I=I+1 CIKLUS VÉGE ELJÁRÁS VÉGE
A[J+1]
16
Javított buborékos rendezés Ha a buborékos rendezésnél egy teljes bels+ ciklus lefutása alatt egyetlen csere sem volt, akkor a sorozat már rendezett. Ilyenkor feleslegesek a további összehasonlítások. A CSERE változó jelzi azt, hogy a bels+ ciklusban kellett-e cserélni. A bels+ ciklus indulása el+tt, el+készítésként, a változót nullázzuk, és csak akkor lesz újra 1 az értéke, ha cserére volt szükség. Tehát, ha az összes szomszédos elem-pár a kívánt rendezettségnek megfelel+ relációban van, akkor a CSERE változó értéke 0 marad. ELJÁRÁS JOBB_BUBORÉK(A[],N) CSERE = 1 CIKLUS AMÍG CSERE ==1 CSERE = 0 J=0 CIKLUS AMÍG J
A[J+1] AKKOR A[J]
A[J+1] CSERE =1
ELÁGAZÁS VÉGE
J=J+1 CIKLUS VÉGE CIKLUS VÉGE ELJÁRÁS VÉGE
Tovább javított buborékos rendezés Mivel a bels+ ciklus egyszeri lefutása után a legnagyobb elem az utolsó helyen áll, ezt az elemet már felesleges vizsgálni. Ebben az algoritmusban a bels+ ciklus minden alkalommal eggyel kevesebb elemre fut le, mert a DB változót a bels+ ciklus befejez+dése után csökkentjük. ELJÁRÁS LEGJOBB_BUBORÉK(A[],N) CSERE = 1 DB = N CIKLUS AMÍG CSERE == 1 CSERE = 0 J=0 CIKLUS AMÍG J< DB -1 HA A[J]>A[J+1] AKKOR A[J]
A[J+1]
CSERE =1 ELÁGAZÁS VÉGE
J=J+1 CIKLUS VÉGE DB = DB-1 CIKLUS VÉGE ELJÁRÁS VÉGE
17
