ALGORITMIZÁLÁS ALAPJAI. Tömösközi Péter

ALGORITMIZÁLÁS ALAPJAI

Tömösközi Péter

MÉDIAINFORMATIKAI KIADVÁNYOK

ALGORITMIZÁLÁS ALAPJAI

Tömösközi Péter

Eger, 2011

Lektorálta: CleverBoard Interaktív Eszközöket és Megoldásokat Forgalmazó és Szolgáltató Kft.

A projekt az Európai Unió támogatásával, az Európai Szociális Alap társfinanszírozásával valósul meg.

Felelős kiadó: dr. Kis-Tóth Lajos Készült: az Eszterházy Károly Főiskola nyomdájában, Egerben Vezető: Kérészy László Műszaki szerkesztő: Nagy Sándorné

Kurzusmegosztás elvén (OCW) alapuló informatikai curriculum és SCORM kompatibilis tananyagfejlesztés Informatikus könyvtáros BA, MA lineáris képzésszerkezetben TÁMOP-4.1.2-08/1/A-2009-0005

AZ ALGORITMIZÁLÁS ALAPJAI

Tartalom 1. Bevezetés ....................................................................................................................... 9 1.1 Célkitűzés .......................................................................................................... 9 1.2 A tananyag tartalma ........................................................................................ 10 1.3 A tananyag tömör kifejtése ............................................................................. 10 1.4 Kompetenciák és követelmények .................................................................... 10 1.5 Tanulási tanácsok, tudnivalók ......................................................................... 10 2. Az algoritmusok jellemzői és leírásuk ...................................................................... 11 2.1 Célkitűzés ........................................................................................................ 11 2.2 Tartalom .......................................................................................................... 11 2.3 A tananyag kifejtése ˙...................................................................................... 11 2.3.1 Az algoritmus .................................................................................. 11 2.3.2 Mit jelent az, hogy elemi lépés? ...................................................... 13 2.3.3 Az algoritmusok jellemzői ............................................................... 15 2.3.4 Algoritmusok megadása .................................................................. 16 2.4 Összefoglalás................................................................................................... 31 2.5 Önellenőrző kérdések ...................................................................................... 31 3. Adatok, adatszerkezetek ............................................................................................ 32 3.1 Célkitűzés ........................................................................................................ 32 3.2 Tartalom .......................................................................................................... 32 3.3 A tananyag kifejtése ........................................................................................ 32 3.3.1 Adat ................................................................................................. 32 3.3.2 A literálok ........................................................................................ 33 3.3.3 A változók ....................................................................................... 34 3.3.4 Összetett adatok, adatszerkezetek .................................................... 37 3.3.5 A tömb ............................................................................................. 38 3.3.6 További homogén adatszerkezetek .................................................. 42 3.3.7 A rekord ........................................................................................... 46 3.3.8 A fájl ................................................................................................ 47 3.4 Összefoglalás................................................................................................... 47 3.5 Önellenőrző kérdések ...................................................................................... 47 4. Adatsorhoz egy adatot rendelő eljárások 1. ............................................................. 48 4.1 Célkitűzés ........................................................................................................ 48 4.2 Tartalom .......................................................................................................... 48 4.3 A tananyag kifejtése ........................................................................................ 48 4.3.1 A tömbfeltöltés ................................................................................ 48 4.3.2 Az összegzés .................................................................................... 50 4.3.3 Az eldöntés ...................................................................................... 52 4.3.4 A megszámlálás ............................................................................... 54 4.3.5 A kiválasztás .................................................................................... 57 4.3.6 A szélsőérték-kiválasztás ................................................................. 57 5

AZ ALGORITMIZÁLÁS ALAPJAI 4.4 4.5

Összefoglalás................................................................................................... 59 Önellenőrző kérdések ...................................................................................... 60

5. Adatsorhoz egy adatot rendelő eljárások 1. – Keresések ........................................ 61 5.1 Célkitűzés ........................................................................................................ 61 5.2 Tartalom .......................................................................................................... 61 5.3 A tananyag kifejtése ........................................................................................ 61 5.3.1 A teljes keresés ................................................................................ 61 5.3.2 A strázsás keresés ............................................................................ 62 5.3.3 A lineáris keresés ............................................................................. 63 5.3.4 A bináris (logaritmikus) keresés ...................................................... 63 5.3.5 Sztring keresése sztringben – mintaillesztés.................................... 66 5.4 Összefoglalás................................................................................................... 68 5.5 Önellenőrző kérdések ...................................................................................... 68 6. Adatsorhoz adatsort rendelő eljárások 1. ................................................................ 69 6.1 Célkitűzés ........................................................................................................ 69 6.2 Tartalom .......................................................................................................... 69 6.3 A tananyag kifejtése ........................................................................................ 69 6.3.1 Kiválogatás ...................................................................................... 69 6.3.2 Az összefuttatás ............................................................................... 72 6.4 Összefoglalás................................................................................................... 74 6.5 Önellenőrző kérdések ...................................................................................... 75 7. Adatsorhoz adatsort rendelő eljárások 2. – Rendező eljárások ............................. 76 7.1 Célkitűzés ........................................................................................................ 76 7.2 Tartalom .......................................................................................................... 76 7.3 A tananyag kifejtése ........................................................................................ 77 7.3.1 Két elem cseréje egy vektorban ....................................................... 77 7.3.2 Rendezés közvetlen kiválasztással .................................................. 77 7.3.3 A buborékrendezés .......................................................................... 78 7.3.4 Rendezés szélsőérték-kiválasztással ................................................ 79 7.3.5 A beszúró rendezés .......................................................................... 81 7.3.6 Shell módszere................................................................................. 82 7.3.7 A gyorsrendezés .............................................................................. 83 7.4 Összefoglalás................................................................................................... 87 7.5 Önellenőrző kérdések ...................................................................................... 87 8. Példák az eljárások alkalmazására ........................................................................... 89 8.1 Célkitűzés ........................................................................................................ 89 8.2 Tartalom .......................................................................................................... 89 8.2.1 Példák a tételek alkalmazására ........................................................ 89 8.3 Összefoglalás................................................................................................. 117 8.4 Önellenőrző kérdések .................................................................................... 117 9. Algoritmusok hatékonysága .................................................................................... 118 9.1 Célkitűzés ...................................................................................................... 118 6

AZ ALGORITMIZÁLÁS ALAPJAI 9.2 9.3

9.4 9.5

Tartalom ........................................................................................................ 118 A tananyag kifejtése ...................................................................................... 118 9.3.1 Algoritmusok műveletigénye ........................................................ 118 9.3.2 Aszimptotikus jelölések ................................................................. 119 Összefoglalás................................................................................................. 121 Önellenőrző kérdések .................................................................................... 121

10. Alprogramok............................................................................................................. 122 10.1 Célkitűzés ...................................................................................................... 122 10.2 Tartalom ........................................................................................................ 122 10.3 A tananyag kifejtése ...................................................................................... 122 10.3.1 Az alprogramok célja, jellemzői, fajtái.......................................... 122 10.3.2 Formális és aktuális paraméterek................................................... 125 10.3.3 A rekurzió ...................................................................................... 126 10.3.4 Hatókör, élettartam ........................................................................ 127 10.4 Összefoglalás................................................................................................. 128 10.5 Önellenőrző kérdések .................................................................................... 128 11. Dinamikus adatszerkezetek ..................................................................................... 129 11.1 Célkitűzés ...................................................................................................... 129 11.2 Tartalom ........................................................................................................ 130 11.3 A tananyag kifejtése ...................................................................................... 130 11.3.1 A halmaz ........................................................................................ 130 11.3.2 A lista............................................................................................. 136 11.3.3 A verem ......................................................................................... 138 11.3.4 Sor.................................................................................................. 139 11.3.5 Fa ................................................................................................... 139 11.3.6 A háló ............................................................................................ 142 11.4 Összefoglalás................................................................................................. 143 11.5 Önellenőrző kérdések .................................................................................... 143 12. Összefoglalás ............................................................................................................. 144 12.1 A kurzusban kitűzött célok összefoglalása.................................................... 144 12.2 Tartalmi összefoglalás ................................................................................... 144 12.3 A tananyagban tanultak részletes összefoglalása .......................................... 144 12.3.1 Bevezetés ....................................................................................... 144 12.3.2 Az algoritmusok jellemzői és leírásuk........................................... 144 12.3.3 Adatok, adatszerkezetek ................................................................ 145 12.3.4 Adatsorhoz egy adatot rendelő eljárások 1. ................................... 145 12.3.5 Adatsorhoz egy adatot rendelő eljárások 2. Keresések.................. 145 12.3.6 Adatsorhoz adatsort rendelő eljárások 1. ....................................... 145 12.3.7 Adatsorhoz adatsort rendelő eljárások 2. Rendező eljárások ........ 145 12.3.8 Példák az eljárások alkalmazására ................................................. 145 12.3.9 Az algoritmusok hatékonysága ...................................................... 145 12.3.10 Alprogramok ............................................................................... 146 12.3.11 Dinamikus adatszerkezetek......................................................... 146 12.4 Zárás .............................................................................................................. 146 7

AZ ALGORITMIZÁLÁS ALAPJAI 12.5 Egyéb ............................................................................................................ 146 13. Kiegészítések ............................................................................................................. 147 13.1 Irodalomjegyzék ............................................................................................ 147 14. Ábrajegyzék .............................................................................................................. 148 15. Médiaelemek ............................................................................................................. 150 16. Tesztek ....................................................................................................................... 151 16.1 Próbateszt ...................................................................................................... 151 16.2 Záróteszt A. ................................................................................................... 155 16.3 Záróteszt B. ................................................................................................... 158 16.4 Záróteszt C. ................................................................................................... 162

8


1. BEVEZETÉS Az algoritmizálás alapjai című kurzusban elemi algoritmusokkal, azok jellemzőivel és lehetséges felhasználási területeikkel ismerkedünk meg. Algoritmusok segítségével egyszerűbb és bonyolultabb problémákat oldhatunk meg. Hétköznapi szavakkal az algoritmus valamilyen probléma vagy feladat megoldásának lépéseit határozza meg. Ha ezeket a lépéseket a megfelelő sorrendben hajtjuk végre, azzal megadjuk egy probléma vagy feladat egy lehetséges megoldását. Az algoritmus kifejezést értelmezhetjük úgy is, hogy egy olyan számítási eljárást, amely valamilyen bemenetből (bemenő adatból vagy bemenő adatok sorozatából) a lépések végrehajtásával valamilyen kimenetet állít elő. Sokan tévesen hiszik azt, hogy az algoritmizálás és a programozás kifejezések lényegében azonos tevékenységeket jelölnek. Kétségtelen, hogy helyes programok készítéséhez általában ismernünk kell különféle algoritmusokat. Azonban egyrészt algoritmusokat konkrét programozási nyelv ismerete nélkül is megadhatunk. Gondoljunk elemi matematikai feladatokra: pl. ismerjük egy síkidom oldalainak hosszát, és szeretnénk kiszámítani a kerületét és területét. Bemenő adatok az oldalak hosszúságai, kimenő adatok a síkidom kerülete és területe. A megoldáshoz bizonyos síkidomok esetében egyszerű képleteket alkalmazhatunk, néha azonban, például a terület kiszámítása csak több lépésben valósítható meg (pl. egy sokszöget először háromszögekre bontunk, és a háromszögek területének összegét kiszámítva kapjuk meg a síkidom területét). Másrészt léteznek olyan programozási nyelvek is, amelyek használatakor a programozónak nem kell ismernie a feladat megoldásának lépéseit, vagyis a megoldás algoritmusát. Ezekben a nyelvekben a megoldást maga a programozási nyelv keresi meg. Az ilyen nyelveket deklaratív programozási nyelveknek nevezzük. Deklaratív nyelveket használva a programozónak azt kell megadnia, hogy mit szeretne megoldani, és nem azt, hogy hogyan. Ezzel szemben az imperatív nyelvekben a programozó a feladat megoldásának algoritmusát ülteti át az adott programozási nyelvbe, figyelembe véve a nyelv szintaxisát és eszközrendszerét. A programozó változókat használ. Ezek segítségével eléri és módosítani tudja a memóriában tárolt adatokat, a probléma megoldásának algoritmusát ő adja meg. Az imperatív nyelveket szokás procedurális nyelveknek is nevezni. Az algoritmus tehát többféle módon értelmezhető és megadható: absztrakt módon (pl. matematikai eszközökkel), számítógépes programként stb. Aki algoritmusokkal foglalkozik, az egyben adatokkal, adatszerkezetekkel is foglakozik. Ez az algoritmus kifejezés fenti értelmezéséből is adódik, hiszen az algoritmus a fentiek szerint egy olyan számítási eljárás, amely bemenő adatokból kimenő adatokat állít elő. A kurzus másik célja, hogy a különböző problémák megadásához használható adatok és adatszerkezetek jellemzőit is bemutassa. Kijelenthetjük tehát, hogy ha valaki programozással, vagy az informatika sok más területével (pl. adatbázis-kezelés, számítógép-hálózatok, térinformatika, kriptográfia stb.) kíván foglalkozni, szüksége lesz alapvető algoritmizálási ismeretekre is. 1.1

CÉLKITŰZÉS

A kurzus célja az algoritmusokkal, illetve adatokkal, adatszerkezetekkel kapcsolatos alapvető ismeretek bemutatása, és felhasználási lehetőségeik áttekintése. 9

AZ ALGORITMIZÁLÁS ALAPJAI Az algoritmizálás önálló tudomány. A jegyzet azonban olyan hallgatók számára készült, akik csak érintőlegesen foglalkoznak ezzel a tárggyal, ezért a jegyzet elkészítésekor nem volt célunk, hogy algoritmuselméleti és -helyességi kérdésekkel is foglalkozzunk. A jegyzet csak elemi algoritmusok bemutatását és felhasználásuk lehetséges módjait tárgyalja.

1.2 A TANANYAG TARTALMA 1. Bevezetés 2. Az algoritmusok jellemzői, az algoritmusokkal szemben támasztott követelmé-

nyek. A Böhm–Jacopini-tétel, vezérlési szerkezetek az algoritmusokban 3. Algoritmusok megadásának eszközei 4. Adatok és adatszerkezetek jellemzői 5. Adatsorhoz egy adatot rendelő algoritmusok 6. Adatsorhoz adatsort rendelő algoritmusok 7. Rendező algoritmusok 8. Alprogramok 9. Dinamikus adatszerkezetek 10. Feladatok és megoldásaik

1.3 A TANANYAG TÖMÖR KIFEJTÉSE A kurzusban elemi algoritmusokkal, az ún. programozási tételekkel ismerkedünk meg. Ahogyan a bevezetőből már kiderült, az algoritmusok megadása és a programozás kifejezések különböző tevékenységeket jelölnek, de az algoritmusok legfőbb alkalmazási területe az informatikában a programozás. Emiatt szükséges, hogy az elemi algoritmusokon túl megismerkedjünk néhány programozási nyelv alapvető jellemzőivel is, hogy a különböző eszközökkel felírt algoritmusokat a gyakorlatban is ki tudjuk próbálni. Ehhez nyújt segítséget a 10. fejezet. Hangsúlyozzuk azonban, hogy nem célunk a programozási nyelvek teljes eszközrendszerének bemutatása, hiszen ez nem egy programozás tankönyv. 1.4

KOMPETENCIÁK ÉS KÖVETELMÉNYEK

A kurzus teljesítéséhez előfeltételként alapvető informatikai ismeretek szükségesek. A tananyag megértéséhez ismerni kell a Neumann-elv alapvető pontjait, a processzor és a memória szerepét, illetve az adattárolás alapjait.

1.5 TANULÁSI TANÁCSOK, TUDNIVALÓK A tananyag megértéséhez feltétlenül szükséges a definíciók pontos ismerete. Nagyon fontos, hogy megértse a második és harmadik fejezet minden részét, és csak ezután kezdjen a konkrét algoritmusok tanulmányozásához.

10


2. AZ ALGORITMUSOK JELLEMZŐI ÉS LEÍRÁSUK 2.1

CÉLKITŰZÉS

Ebben a fejezetben az algoritmusokkal és az algoritmizálással, algoritmuskészítéssel kapcsolatos alapvető fogalmakkal ismerkedünk meg. Megismerjük az algoritmus szó értelmezését, az algoritmusokkal szemben támasztott követelményeket, és az algoritmusok pontos megadásának különböző eszközeit.

2.2 TARTALOM − − − 2.3

Az algoritmus kifejezés értelmezése Algoritmusok jellemzői és algoritmusokkal szemben támasztott követelmények Algoritmusleíró eszközök és jellemzőik

A TANANYAG KIFEJTÉSE ˙

Ebben a fejezetben az algoritmizálás alapjainak tárgyalásához szükséges fogalmakkal és eszközökkel ismerkedünk meg. 2.3.1

Az algoritmus

A köznyelvben az algoritmus szó valamilyen műveletsort, tevékenységet jelent, amelylyel egy probléma megoldását adjuk meg. Lényegében minden tevékenységünkkel algoritmusokat követünk: minden mozdulatsorunk, de még a gondolkodásunk is algoritmizálható. Ahhoz, hogy valamit megoldjunk, algoritmust használunk, legyen az munka, játék, hobbi vagy sport. Algoritmust követünk egy étel készítésekor (recept), egy lapraszerelt bútor összerakásakor (útmutató rajz), vagy ha szeretnénk hibát bejelenteni vagy információhoz jutni valamilyen közüzemi szolgáltatónál („kérem, telefonja billentyűzete segítségével válasszon az alábbi menüből”), hogy csak néhány példát említsünk. A továbbiakban az algoritmust olyan számítási műveletként értelmezzük, amely valamilyen bemeneti (input) adatból vagy adatsorból egy vagy több kimeneti (output) adatot állít elő. Egy algoritmus elemi lépések meghatározott sorrendű véges sorozata. Ez a megfogalmazás matematikai szempontból nem kellően pontos. Megjegyzésként említjük meg, hogy egy absztraktabb értelmezés szerint az algoritmus egy Turing-gépre írt program. A Turing-gép egy absztrakt automata, tehát nem egy valós, fizikai gépre kell gondolnunk, hanem egy matematikai módszerre, a valós digitális számítógépek egy nagyon leegyszerűsített modelljére.

11


1. kép

A Turing-gép vázlata

A Turing-gép egy olyan gép, amelyhez egy végtelen hosszúságú papírszalag tartozik. Ezen a szalagon cellákban jeleket találunk, minden cellában egy-egy jelet. A Turing-gép nyilvántartja az aktuális cella pozícióját. Minden lépésben lehetőség van beolvasni az aktuális cella tartalmát, lehetőség van az előző és a következő pozícióra léptetni az olvasófejet, lehetőség van az aktuális cella tartalmát egy másik jelre változtatni. A gép minden lépésnél valamilyen belső állapotban van (a belső állapotok száma véges sok), az egyes cellák értékei ezeket a belső állapotokat megváltoztathatják. A gép tehát minden lépésben beolvassa az aktuális cella tartalmát, megváltoztat(hat)ja belső állapotát, megváltoztat(hat)ja a jelet a cellában, aztán elmozdul(hat). Ez a folyamat kétféle kimenetet eredményezhet: − a gép terminális (leálló) belső állapotba kerül és megáll (ez a szabályos lefutás), − sosem kerül stop állapotba, végtelen ideig fut. A belső állapotok megváltoztatása a gép vezérlőegységének feladata. Az, hogy egy állapotból milyen állapotba válthat a gép, egyrészt függ a szalagon található jelektől, másrészt attól, hogy az automata működése milyen utasításokkal van leírva. A Turing-gép fogalmának bevezetésével absztrakt definíció adható az algoritmusra: Egy probléma megoldására adott utasítások sorozata akkor algoritmus, ha létezik olyan vele ekvivalens Turing-gép, amely minden megoldható bemenet esetén megáll. A Turing-gép megalkotása Alan Turing (1912–1954) brit matematikus nevéhez fűződik. A gép fogalmát egy 1936-ban megjelent cikkében vezeti be. Turing bebizonyította, hogy minden speciális automata leírható véges hosszúságú utasítássorozattal. Ez az eredmény nagy hatással volt Neumann János (1903–1957) munkásságára, illetve a mai korszerű digitális számítógépek fejlődésére.

12


2. kép

3. kép 2.3.2

Alan Turing

Neumann János

Mit jelent az, hogy elemi lépés?

Erre a kérdésre többféle dolog határozhatja meg a választ. Ha abból indulunk ki, hogy azért adunk meg egy feladathoz algoritmust, hogy abból azután számítógépes programot készítsünk, az elemi lépések nagyságát meghatározhatja az adott programozási nyelv eszközrendszere. Köztudott, hogy a futtatott program utasításait a memória tárolja, a futáshoz szükséges adatokkal együtt. A program utasításait a processzor hajtja végre. A processzor csak egyféle programot tud végrehajtani, olyat, amelyet az ő saját utasításkészletén írtak. Minden processzortípusnak egyedi jellemzői vannak, így egyedi a különböző processzorok utasításkészlete is. A processzorok saját utasításkészletén írott programokat nevezzük gépi kódnak. A gépi kód lényegében bináris számjegyek sorozataként írható fel, egy-egy utasítás egy 8, 16, 24 stb. jegyű bináris jelsorozat. Egy ilyen gépi kódú utasítás önmagában általában nem túl látványos hatást eredményez (pl. beír egy memóriaterületre egy 1 bájtos számot, vagy növeli/csökkenti egy memóriacellában található szám értékét stb.) főleg, ha ún. magasszintű programozási nyelvek utasításaihoz hasonlítjuk őket. A gépi kódú prog13

AZ ALGORITMIZÁLÁS ALAPJAI ramozás tehát azért nehéz, mert nagyon elemi szintű utasítások állnak csak rendelkezésünkre, másrészt pedig az emberi szem számára lényegében olvashatatlan egy ilyen kód: kevés olyan ember van, aki számára egy több ezer bináris számjegyből álló sorozatot gépi kódként azonnal meg tud érteni. A számítástechnika hőskorában azonban ez volt az egyetlen lehetséges programozási módszer. Az első eszköz, amely kicsit barátságosabbá tette a programozást, az assembly nyelv volt. Ez lényegében a gépi kód egy olvashatóbb jelölésmódját jelenti, amelyben az utasításokat bináris számjegyek helyett 2-3 betűs szavak, rövidítések, ún. mnemonikok jelölik. Lássunk egy példát: gépi kód 10110000 01100001 assembly MOV AL, 061h Az utasítás jelentése: „tedd a hexadecimális 61 értéket a processzor AL regiszterébe!” A processzorok azonban közvetlenül az assembly nyelvet sem értik, ahhoz tehát, hogy egy ilyen nyelven írott programot futtatni tudjunk, az assembly nyelvű kódot gépi kódra kell fordítani. Az ilyen fordítóprogramokat nevezzük assemblernek. Az 1950-es évektől kezdtek megjelenni az ún. magas szintű programozási nyelvek1. Ezek közös jellemzője, hogy közelebb állnak az ember beszélte (általában angol) nyelvhez, mint a gépi kódhoz. Magas szintű programozási nyelven való programozáshoz nem (feltétlenül) szükséges ismernünk a számítógép hardverének (elsősorban a processzor és a memória) felépítését, sőt, sok magas szintű programozási nyelvben nincs is eszközünk arra, hogy közvetlenül nyúljunk a memóriához vagy a processzorhoz. A magas szintű programozási nyelvekben különböző adattípusokat és adatszerkezeteket, illetve összetett utasításokat használhatunk. (A nagyságrend érzékeltetéséhez: gépi kódban egy utasítással beírhatunk egy adatot egy bizonyos memóriacímre, míg egy erre alkalmas magas szintű programozási nyelvben például egyetlen utasítás segítségével a képernyő felbontásához igazítva és a videokártya sajátosságait figyelembe véve lejátszhatunk egy videoállományt.) Kissé pontatlanul az alábbi megállapításokat tehetjük: − mivel a magas szintű programozási nyelvek sokkal több kész eszközt adnak a programozó kezébe, a magas szintű programozási nyelveken egyszerűbb a programozás; − mivel gépi kódban a programozó közvetlenül programozza a processzort, sokkal hatékonyabb kódok írhatók gépi kódban, mint amilyen gépi kódot a magas szintű programozási nyelvek fordítóprogramjai állítanak elő.

1

Az első magas szintű nyelv a FORTRAN volt, melynek leírását 1954-ben tette közzé az IBM. Az első gyakorlatban használt programozási nyelv tíz évvel korábban készült, Konrad Zuse készítette 1944-ben Plankalkül néven a Z4 jelű számítógépéhez.

14

AZ ALGORITMIZÁLÁS ALAPJAI Mindkét állításban van igazság, de ennél azért lényegesen összetettebb kérdésről van szó. A laikus számára egy magas szintű programozási nyelven írott kód is lehet éppen anynyira értelmezhetetlen, mint egy gépi kódú, másrészt a programozási nyelvek fordítóprogramjai egyre fejlettebbek, és az új fordítók képesek lehetnek közel olyan hatékonyságú gépi kód előállítására, mint amilyet egy gépi kódban jártas programozó készít. Összefoglalva: az elemi lépés pontos meghatározása többféle tényezőtől függhet. Általában elmondhatjuk, hogy elvárjuk az elemi lépésektől, hogy − függetlenek legyenek, vagyis egy elemi lépés ne legyen felírható más elemi lépések sorozataként, − a probléma szempontjából legyenek fontosak, célszerűek és hatékonyak (relevancia). 2.3.3

Az algoritmusok jellemzői

A 2.3.1 fejezetben kijelentettük, hogy az algoritmus elemi lépések meghatározott sorrendű véges sorozataként értelmezhető. Az elemi lépések „nagysága” az előző részben írottak alapján függhet például attól, hogy milyen programozási nyelven akarjuk implementálni a kódot. (Az implementáció kifejezés azt jelenti, hogy az algoritmust egy konkrét programozási nyelv utasításkészletére írjuk át, más szavakkal konkrét programozási nyelvi megvalósítást értünk alatta.) Lássunk egy példát: a tankönyvekből unásig ismert „hétköznapi” algoritmus a teafőzés algoritmusa. Ha a teafőzés algoritmusát gépi kódra akarjuk alkalmazni, képletesen szükségünk lesz két hidrogén- és egy oxigénatomra, amelyekből némi munkával vizet hozhatunk létre. Hasonlóképp szükségünk lesz másféle atomokra és molekulákra, amelyekből teafüvet, cukrot, citromlevet stb. készítünk. Az összetevőkből azután energia közlésével (melegítés) és keveréssel előállítható a kívánt ital. Ezzel szemben a mai modern magas szintű, pl. objektumorientált programozási nyelvek mindegyikében (képletesen) létezik tea objektum, amelyet a programozónak nem kell létrehoznia, mert készen kapja azt, ha szüksége van rá. (A teafőzés – telefonálás, levél feladása postán, bevásárlás stb. – algoritmusának megadása a legtöbb, kezdőknek szóló algoritmizálás-tankönyv kedvelt bevezető példája: „Írjuk le egy hétköznapi tevékenység – pl. teafőzés, telefonálás stb. – algoritmusát!”. Az ilyen feladatokra azonban nem lehet algoritmust adni, ugyanis nem egyértelműek. Nem tudjuk, hogy otthon a konyhában vagy a Mount Everesten állunk-e éppen. Nem tudjuk, hogy milyen eszközök állnak rendelkezésünkre a teafőzéshez, illetve van-e nálunk mobiltelefon, vagy fülkét kell keresnünk, és ha igen, merre induljunk. Nem tudjuk, hány főnek készül a tea, és így tovább. Összefoglalva: nyitott feladatok megoldására nem lehet algoritmust adni. Az egyértelműség elengedhetetlen: amíg nem tudjuk pontosan megfogalmazni, mi a feladat, addig a megoldást sem tudjuk megadni.) Az elemi lépések meghatározott sorrendjére vonatkozó követelmény nem igényel magyarázatot. Egy feladatot csak úgy tudunk megoldani, ha a lépéseket a megfelelő sorrendben hajtjuk végre. A végesség is nyilvánvaló követelmény. Az általunk tárgyalt algoritmusok lépéseinek elemszáma mindig véges. (Megjegyzés: a végesség többféle módon értelmezhető. Jegyzetünkben a végesség lépések leírására vonatkozik– ez az ún. statikus végesség –, és nem a végrehajtásukra. Ha egy algoritmus öt egymás utáni utasításból áll, és az ötödik utasítás az,

15

AZ ALGORITMIZÁLÁS ALAPJAI hogy „ugorj vissza az 1. utasításra”, akkor az algoritmus véges számú lépésből áll, tehát statikusan véges, hiszen öt lépést definiáltunk, a végrehajtás viszont végtelen.) Egy algoritmust determináltnak nevezzük, ha ugyanazon bemenetek esetén ugyanazt a kimenetet állítja elő (azonos kezdőállapotok mellett). 2.3.4

Algoritmusok megadása

2.3.4.1 LNKO Tekintsünk egy egyszerű példát, a legnagyobb közös osztó (LNKO) kiszámításának egy lehetséges algoritmusát. Általános iskolában úgy tanultuk, hogy az a és b természetes számok legnagyobb közös osztója az a c természetes szám, amely osztója a-nak és b-nek is, és az ilyen számok közül a legnagyobb. A c nem feltétlenül különbözik a-tól és/vagy b-től: LNKO(6;12) = 6, LNKO(25;25) = 25. Az LNKO kiszámítására az iskolában azt a módszert tanultuk, hogy megkeressük a és b prímtényezőit, majd azokat a prímtényezőket, amelyek mindkét szám felbontásában megtalálhatók, a legkisebb hatványon összeszorozzuk. Ennél a módszernél van egy lényegesen egyszerűbb, bár kevésbé hatékony megoldás. Ehhez csak a kivonás műveletét kell ismernünk, és meg kell tudnunk határozni két szám közötti relációkat (<, =). Az eljárás lényege az, hogy a két szám közül a kisebbiket addig vonjuk ki nagyobbikból, míg végül a két szám egyenlő nem lesz2. Lássunk egy példát: Legyen a = 42, b = 30. Készítsünk egy táblázatot, melyben nyomon követhető a műveletsorozat! a b művelet 42 30 a = a – b (mivel a a nagyobb, azt csökkentjük b-vel) 12 30 b=b–a 12 18 b=b–a 12 6 a=a–b 6 6 A műveletsorozat végén a = b = 6 lett az eredmény, ezért LNKO(42;30) = 6. Próbáljuk meg leírni, mit csináltunk! 1. Add meg a két számot! 2. Ha a egyenlő b-vel, akkor megvan az LNKO, megállhatsz. 3. Különben, ha a nagyobb, mint b, akkor csökkentsd a értékét b-vel. Ha pedig b na-

gyobb, mint a, akkor b értékét csökkentsd a-val! 4. Menj vissza a 2. pontra.

2

Ennél hatékonyabb eljárás az ún. euklideszi algoritmus. Vegyük észre, hogy egy egész számból egy nála kisebb egész szám többszöri kivonásának műveletsorozata helyettesíthető egyetlen egészosztás művelettel. Pl.: 23 – 4 – 4 – 4 –4 – 4 = 3, a 23-ból 5-ször vontuk ki a 4-et, maradt a 3, vagyis 23 = 5 ∙ 4 + 3. Egyszerűbben leírva: 23 : 4 = 5, maradék: 3. Az euklideszi algoritmusban az a és b számok különbsége helyett osztásuk maradékát képezzük (a nagyobbat elosztjuk a kisebbel és a kapott maradékkal számolunk tovább). Ugyanazt az eredményt fogjuk kapni, mint a kivonások sorozatával, de sokkal kevesebb lépésben.

16

AZ ALGORITMIZÁLÁS ALAPJAI Ez a leírás nagy vonalakban megfelelő, de azért vannak vele problémák. Egyrészt terjengős, másrészt csak azok értik, akik beszélnek magyarul, és nem is teljesen egyértelmű. (A 3. pontban a Ha pedig… érthető úgy is, hogy abban az esetben, ha 3. pont első mondata nem volt igaz, de úgy is, ha igaz volt.) Adjuk meg ennél pontosabban az algoritmust!

2.3.4.2 A Böhm–Jacopini-tétel Figyeljük meg a fenti példában, hogy az eljárásban három különböző strukturális (más szóval vezérlési) szerkezet található. a) Egyrészt az a és b értékét felváltva, egymás után változtatjuk. Annak nincs jelentősége, hogy az a csökkentése után a b, vagy ismét az a értékét kell-e csökkenteni, de a kivonások mindig egymás után és nem egyszerre történnek. (Csak azután hajtom végre pl. a harmadik kivonást, ha a másodikat már befejeztem.) Azt mondjuk, hogy ezek a műveletek szekvenciát alkotnak. b) Előfordulhat olyan eset, hogy úgy ér véget az algoritmus, hogy az eredeti értékeken egyáltalán nem kell változtatnunk. Ha a két eredeti, bemenő számadat egyenlő, akkor nincs semmi tennivalónk, kiválasztjuk az egyiket és az lesz az LNKO. Így a 2. pont azonnal egy döntést igényel tőlünk: kell-e bármit is csinálnunk, vagy készen vagyunk? Mivel a végrehajtás során többször is sorra kerül a 2. tevékenység, ez lesz az a pont, amely végül megállítja a végrehajtást. (Bármely két természetes számnak van legnagyobb közös osztója. „Legrosszabb” esetben ez a szám az 1, ha a két szám relatív prím.) Azt mondjuk, hogy a 2. művelet egy elágazás vagy szelekció. Az ilyen esetekben mindig két vagy több lehetséges végrehajtási lépés (végrehajtási ág) közül választunk ki egyet és azt hajtjuk végre. A 3. pontban is elágazásokat látunk. c) Az egész eljárás egy műveletsorozat ismétlése. Addig kell ismételve kivonnunk a nagyobbik számból a kisebbiket, amíg egyenlők nem lesznek. Az ilyen ismétlő szerkezet neve ismétlés vagy iteráció. (A programozási nyelvekben az ismétlés neve ciklus, és ciklusutasításokkal valósítható meg. Minden magas szintű programozási nyelv ismer legalább egyféle ciklusszerkezetet, de általában többet is.) Az 1966-ban két olasz matematikus, Corrado Böhm (1923–) és Giuseppe Jacopini cikke3 mutatja be azokat a kutatási eredményeket, amelyeket azóta az algoritmusok strukturált leírásának egyik alaptételeként használunk. A tételt Böhm–Jacopini-tételnek nevezik: Bármely algoritmust leírhatunk három alapstruktúra segítségével: szekvenciával, iterációval és szelekcióval.

3

C. Böhm, G. Jacopini: Flow diagrams, Turing Machines and Languages with only Two Formation Rules, Comm. of the ACM , 9(5). 1966, pp. 366–371.

17


4. kép

18

Az eredeti cikk első oldala


5. kép

Corrado Böhm

A következőkben az algoritmusok pontos megadásának és leírásának néhány eszközét ismerjük meg.

2.3.4.3 Mondatszerű leírónyelv, pszeudonyelv A mondatszerű leírónyelv (pszeudonyelv, pszeudokód) a magyar (angol stb.) nyelv szavainak, kifejezéseinek segítségével, illetve szimbólumok (→, ← stb.) használatával írja le az algoritmus vezérlési szerkezeteit, végrehajtandó műveleteit. Jól definiált, kizárólagos szabvány nem létezik rá. A hazai és nemzetközi szakirodalom gyakorlatában kialakult egyfajta szintaxis kisebb-nagyobb eltéréseket mutat a különböző szerzők, kiadók műveiben. Jegyzetünkben minden algoritmust ezzel a leíró eszközzel mutatunk be. Kötetünkben a vezérlési szerkezetek jelölésére is magyar szavakat, kifejezéseket fogunk használni, de ebben a fejezetben bemutatjuk a további elterjedt jelölésmódokat is. Bevezetésként lássunk egy konkrét példát. Tekintsük a korábban leírt LNKO kiszámításának egy lehetséges, mondatszerű leírónyelven megadott algoritmusát. eljárás LNKO be: A, B ciklus, amíg A ≠ B ha A > B, akkor A = A – B különben B = B – A // harmadik eset nincs elágazás vége ciklus vége ki: A eljárás vége Figyeljük meg a vezérlési szerkezeteket! Az eljárás lényegében három fő részből áll. Az első rész az input (be: A, B), a második rész a számítást végzi, a harmadik rész pedig az output (ki: A). Az eljárás kimenete természetesen lehetne a B változó is, hiszen a ciklus lefutása után A és B egyenlők.

19

AZ ALGORITMIZÁLÁS ALAPJAI A középső rész ciklusa addig fut, amíg a két változó értéke egyenlő nem lesz. Ha a bemenő értékük eredetileg is egyenlő (pl. A = B = 17), nincs tennivalónk, hiszen az LNKO is ez a szám lesz. A ciklus belsejében egy szelekciót látunk. Ha A nagyobb B-nél, akkor A értékét csökkentjük B-vel, ha nem nagyobb, akkor a B értékét csökkentjük A-val. Egyenlők nem lehetnek, mert ha egyenlők lettek volna, már kiléptünk volna a ciklusból. Ezt jelöltük is az algoritmusban egy kommenttel. A komment (megjegyzés) a programozónak és nem a fordítóprogramnak szól. A kommentek jelölésére a különböző programozási nyelvek másmás módszert alkalmaznak. Jegyzetünkben mi a kommenteket // (per-per) jel mögé fogjuk írni és minden esetben kurzívan szedjük. Az A = A – B utasítás egy értékadás, amely az egyik legfontosabb típusa a végrehajtható utasításoknak az algoritmusokban és az imperatív nyelven írott programokban. A változó értéket kap, vagyis a változóhoz rendelt memóriaterületre a változó típusának megfelelő reprezentációban eltároljuk a változó értékéhez rendelhető bitkombinációt. Az értékadás bal oldalán mindig egy változó áll, a jobb oldalon pedig egy kifejezés, amelynek kiértékelhető értéke van. A kiértékelhetőség azt jelenti, hogy az algoritmus adott pontján a kifejezésben szereplő összes változó deklarált és rendelkezik értékkel, illetve a kifejezésben szereplő operandusok és operátorok, illetve esetleges zárójelek értelmezhető műveletet alkotnak és a művelet elvégzésekor egyértelmű értéket adnak. A kifejezés lehet konstans, vagy állhat operandusokból, operátorokból és zárójelekből. Operandus lehet konstans vagy változó, operátor lehet az adott adattípuson értelmezhető műveleti jel (pl. számok esetében +, –, *, /). Zárójelezésre a különböző programozási nyelvekben jellemzően kerek zárójelet () szoktunk használni. A zárójelek egymásba ágyazhatók. A kifejezések megadása a programozási nyelvekben leggyakrabban infix alakban történik, azaz az operátorok az operandusok között vannak elhelyezve. Jegyzetünkben a változók nevét nagybetűsen szedjük. Ez eltérhet a szakirodalmakban szokásos szabályoktól, és nem követi az egyes magas szintű programozási nyelvekben használt de facto szabványokat, illetve konvencionális jelölésmódot. (Magas szintű forráskódokban nagybetűs szedéssel az ún. nevesített konstansokat (Pascal), más néven szimbolikus állandókat (ANSI C) vagy konstansokat (C#) szokás jelölni. A változók nevében csak kisbetűket szoktak alkalmazni, kivéve akkor, ha a változó neve több szóból áll. Mivel szóköz – néhány ritka példától eltekintve – a programozási nyelvek egyikében sem fordulhat elő azonosítóban, az aláhúzás jelnek (_) pedig egyes nyelvekben speciális a funkciója, megszokott, hogy a több szóból álló változóneveket szóköz nélkül egybeírjuk, de a szókezdő betűket nagyra cseréljük, kivéve az elsőt: pl. elemekSzáma, ügyfélNeve, ellenőrzőSzámjegy, legnagyobbKözösOsztó stb.) Jegyzetünk azonban nem konkrét programozási nyelvhez készült. Az algoritmusok átírását ez a jelölésmód nem befolyásolja, de átíráskor figyelembe kell venni az adott nyelv szintaxisának szabályait (pl. a magyar ékezetes karakterek sok nyelvben nem használhatók azonosítókban). Példák értékadásra: A = 17 B = A * 2 C = (A + B) / (A – B) KÉTPI = 6.28 SZÖVEG = "hétfő" 20

AZ ALGORITMIZÁLÁS ALAPJAI Az A = A – B értékadás azért tűnhet speciálisnak, mert az egyenlőség bal és jobboldalán is szerepel az A változó. Ennek programozástechnikai szempontból semmilyen jelentősége nincs, mert az értékadás jobboldala egy kiértékelhető kifejezés, és a kiértékelés után kapott érték kerül a bal oldalon lévő változóba. A jegyzetben a vezérlési szerkezetek megadására a következő leírónyelvi utasításokat fogjuk használni: input: be: , , ... output: ki: , , ... elágazás: ha logikai kifejezés, akkor utasítás1 [különben utasítás2] elágazás vége A logikai kifejezés olyan kifejezés, amelynek logikai értéke {IGAZ, HAMIS} van. Ilyen kifejezéseket összehasonlító operátorokkal (<, ≤, >, ≥, =, ≠) és logikai operátorokkal (NEM, ÉS, VAGY), illetve zárójelekkel adhatunk meg. Abban az esetben, ha a megadott logikai kifejezés értéke igaz, akkor az utasítás1-et hajtjuk végre. Ha a logikai kifejezés értéke hamis, és adtunk meg különben-ágat, akkor az utasítás2-t hajtjuk végre. Az utasítás1 és utasítás2 bármilyen utasítás lehet: végrehajtható utasítás, újabb elágazás, ciklus stb. Ahol utasítás szerepel, ott bármilyen utasítássorozat is megadható. A különben-ágon jelölt szögletes zárójelek ([ ]) azt jelentik, hogy a vezérlési szerkezetben ez a rész opcionális, tehát nem kötelező megadni. A különböző programozási nyelvek általában nem csak kétirányú feltételes elágazást kezelnek, hanem ún. esetszétválasztó elágazásokat, más szóval többirányú elágazást is (Pascal: CASE … OF; C, C#, Java: switch). Jegyzetünkben ezektől eltekintünk, és minden algoritmusban csak kétirányú feltételes elágazást fogunk használni. előfeltételes vagy elöltesztelő ciklus: ciklus, amíg logikai kifejezés utasítások ciklus vége A logikai kifejezésnek itt is egy logikai értéke van, tehát kiértékelhető kifejezés, ez a ciklus feltétele. A ciklusmagban lévő utasításokat addig ismételjük, amíg a ciklusfejben megadott ciklusfeltétel igaz. Ha az első lefutás előtt a ciklusfeltétel hamis, akkor a ciklus 21

AZ ALGORITMIZÁLÁS ALAPJAI magja egyszer sem fut le, ilyenkor üres ciklusról beszélünk. Az előfeltételes ciklus válhat végtelenné, ha a ciklusmagban nem gondoskodunk arról, hogy a ciklusfeltétel egyszer hamissá váljon. Ilyenkor a ciklusból sosem lépünk ki. Ez szemantikai hiba. (A ciklus végtelenné válása nem azonos a fajta szerinti végtelen ciklussal. A végtelen ciklus olyan ciklus, amelynek sem a fejében, sem a végében nem adunk meg feltételt sem az ismétlésre, sem a befejezésre. Az ilyen ciklusokból a ciklusmagban elhelyezett befejeztető/kiugró – pl. EXIT – utasításokkal lehet kilépni. Ilyen végtelen ciklusokat alkalmaznak pl. operációs rendszerekben, de jegyzetünk tárgyába ezek a ciklusok nem tartoznak bele, így használatukat kerülni fogjuk.) végfeltételes, utófeltételes vagy hátultesztelő ciklus: ciklus utasítások amíg logikai kifejezés A hátultesztelő ciklus feltételét a ciklus végében helyezzük el. Ez a feltétel lehet pozitív vagy negatív, vagyis jelentheti az ismétlés (a ciklusban maradás) vagy a kilépés feltételét is. Jegyzetünkben minden esetben a ciklusban maradás feltételét fogjuk megadni az ilyen ciklusoknál. Ez a ciklusszerkezet lényegesen eltér az előfeltételes ciklustól annyiban, hogy ez a ciklus nem lehet üres. Ha a ciklus feltétele az első lefutás előtt hamis (tehát kiléptet a ciklusból), a ciklusmag egyszer akkor is lefut. A ciklus magja egyszer mindenképpen lefut, mert csak az első lefutás után értékeljük ki a ciklus feltételét. Ha a ciklusmagban nem gondoskodunk arról, hogy a ciklusmagot úgy változtassuk meg, hogy kiléptessen a ciklusból, akkor a végfeltételes ciklus is válhat végtelenné. számláló ciklus (előírt lépésszámú ciklus): ciklus = kezdőérték-től végérték-ig utasítások ciklus vége A számláló ciklusban az első lefutás előtt a változó (ciklusváltozó) felveszi a kezdőértéket, majd az utasítások végrehajtódnak. Ezután a ciklusváltozó értéke automatikusan megnő eggyel, és ha az aktuális érték még nem haladja meg a végértéket, akkor a mag ismét lefut. A ciklus addig ismétel, amíg a ciklusváltozó értéke meg nem haladja a végértéket. A különböző programozási nyelveket összehasonlítva a számláló ciklus szintaxisa jelentősen különböző lehet. Vannak nyelvek, amelyek a fenti szintaxisú ciklust nem ismerik, de hasonlót igen (pl. C, C#, Java). Vannak nyelvek, amelyek ismerik a fenti szerkezetet, de a lépésköz csak ±1 lehet (pl. Pascal). Vannak nyelvek, amelyekben megadható lépésköz (pl. különböző BASIC-ek). Az egyes programozási nyelvekben a végérték helyett célszerűbb a határ kifejezést használnunk, mert ha megadhatunk lépésközt, akkor nem biztos, hogy a ciklusváltozó fel is veszi a határként megadott értéket. Pl. ha a kezdőérték 5, a lépésköz 3, a határ 12, akkor a 22

AZ ALGORITMIZÁLÁS ALAPJAI ciklusváltozó által felvett értékek a következők: 5, 8, 11. A 12-t nem veszi fel, vagyis végértékről itt nem beszélhetünk. Jegyzetünkben a számláló ciklusoknál általában nem jelölünk lépésközt. Ahol nem jelölünk, ott a lépésköz mindig +1 lesz. Abban az egy-két esetben, ahol mégis jelölni fogjuk, a lépésköz –1 lesz. A számláló ciklus is lehet üres, ha a megadott kezdőértéktől a megadott irányban a végértékig (határig) nincs egyetlen felvehető érték sem. Ilyen ciklusokat azonban a jegyzetünkben nem fogunk használni. iterátor (bejáró) ciklus: // C# foreach (elem in adatszerkezet) { utasítások } // Java for (változó : adatszerkezet) { utasítások } // PHP foreach ($adatszerkezet as $változó) { utasítások } // Javascript for (változó in adatszerkezet) { utasítások } Ezt a ciklusszerkezetet az „újabb” programozási nyelvek gyakran alkalmazzák. A lényege, hogy a ciklus az adatszerkezet összes elemére lefut. A fejben megadott változó felveszi az adatszerkezet összes értékét és a ciklus magja az összes értékre lefut. Az adatszerkezet lehet tömb, de más is (az egyes nyelvekben eltérő típusú adatszerkezetek támogatottak). Tömb esetén nem kell kezelnünk az elemek indexét, és nem kell tudnunk azt sem, hogy hány elemű a tömb, mert a vezérlési szerkezet helyettünk kezeli ezeket. Mivel ez a vezérlési szerkezet csak bizonyos programozási nyelvekben fordul elő4, és jegyzetünk a legtöbb algoritmust vektorok alkalmazásával adja meg, melyekben egyszerű 4

A fentieken kívül találkozhatunk vele például az ActionScript, az Ada, az Objective C, a Delphi, a Perl, a Python, a Ruby és a Visual Basic .NET nyelvekben.

23

AZ ALGORITMIZÁLÁS ALAPJAI az elemek elérése az indexükkel, a jegyzet további részében nem fogjuk alkalmazni az itertor ciklust. Amint arról korábban már szóltunk, ez a jelölésmód részben önkényes, de a szakirodalomban általában használt szabályokat követi. Példaként bemutatunk az LNKO-algoritmusra egy másik szimbólumrendszert alkalmazó peszudokóddal megadott változatot is, ez inkább hasonlít a nemzetközi szakirodalomban alkalmazotthoz: LNKO

1a←x 2b←y 3 while a ≠ b 4 do if a > b 5 then a ← a – b 6 else b ← b – a 7 print a Ebben a pszeudokód-szintaxisban értékadás, feltételes elágazás (if … then … else) és kétféle ciklus (while … do és for ← létezik. Végrehajtható utasításként egyedül az értékadásnak van saját szimbóluma: ← kifejezés. Minden egyéb műveletet szövegesen kell leírni, ennek nyelve és szintaxisa a különböző irodalmakban eltérő (általános az angol nyelv). A fenti példában nem input és output műveletet írtunk, hanem a-nak és b-nek x és y kezdőértéket adtunk. Ez nem befolyásolja az algoritmus átírhatóságát, a lényeg, hogy az a és b változók valahonnan kezdőértéket kapjanak. Az input és output utasítások egyébként is nagyon különböző módon vannak implementálva a különböző programozási nyelvekben. Vannak olyan nyelvek, amelyekben kulcsszavakkal történik az I/O, de jellemzőbb, hogy az I/O utasítások nem képezik a nyelv részét, hanem unitokban vagy osztályokban vannak definiálva.

2.3.4.4 Folyamatábra, D-diagram Folyamatábrákkal grafikus módon írhatók le az algoritmusok. A folyamatábrák síkidomokból, illetve az azokat összekötő nyilakból állnak. A végrehajtási sorrendet a nyilak határozzák meg. A síkidomok alakja jelöli az egyes vezérlési szerkezetek és végrehajtható utasítások típusát. Folyamatábrákkal nemcsak informatikai algoritmusoknál találkozhatunk. Minden olyan esetben szívesen alkalmazzák őket, amikor valamilyen műveletsort írnak le, és lényeges, hogy az egyes lépések milyen sorrendben kövessék egymást. (Ez végül is az algoritmusok lényege.) Találkozhatunk folyamatábrákkal lapra szerelt bútorok összeállítási útmutatójában, minőségellenőrzési feladatoknál, vészhelyzeti útmutatóban stb. Ezek a folyamatábrák azonban gyakran elég kuszák a sok nyíl miatt. Informatikai algoritmusok megadásánál nagyon fontos az egyszerűség, az áttekinthetőség és az egyértelműség, ezért az ilyen algoritmusok megadásához ún. D-diagramokat használunk. A D betű Dijkstra5 nevére utal, aki 5

Edsger Wybe Dijkstra (1930–2002) holland matematikus, informatikus. Számos fontos és máig használt algoritmus és módszer kidolgozója (pl. Dijkstra-algoritmus a legrövidebb út meghatározásához egy adott csomópontból irányított gráfokban, Dijkstra-szemaforok többszálú programokban a szálak szinkronizálásához).

24

AZ ALGORITMIZÁLÁS ALAPJAI elsőként adott egy szűkebb jelölési rendszert a folyamatábrák megadására. A jelölési rendszer legfontosabb szabálya, hogy minden síkidomnak egyértelműen csak egy továbblépési ága van. Ez alól egyedül a program végét jelölő szimbólum a kivétel, amely megállítja a vezérlést.

6. kép

Edsger Wybe Dijsktra

Az alábbiakban a folyamatábrák D-diagram-elemeit mutatjuk be. A folyamatábra kezdő szimbóluma a startszimbólum, utolsó eleme pedig a stopszimbólum. Mindkettőt ellipszis jelöli. A startszimbólumnak nincs megelőző, a stopszimbólumnak nincs rákövetkező eleme.

7. kép

Start- és stopszimbólum folyamatábrában

A szekvencia egyes lépéseit téglalapok jelölik. A lépések sorrendjét a nyilak jelölik ki.

25


8. kép

Szekvencia D-diagram

A szekvencia a végrehajtható utasítások lépéseinek meghatározott sorrendű sorozata. Előfordul azonban olyan eset, amikor az algoritmus felírásához, vagy megértéséhez nem szükséges minden egyes végrehajtható lépést teljes részletességgel elemeznünk. Például ha egy olyan algoritmust készítünk, amely tartalmazza egy adatbázis feltöltését, illetve az egyes lehetséges lekérdezések eljárásait is, akkor nem biztos, hogy az adatrögzítés minden egyes lépését szükséges részletesen szerepeltetni a folyamatábrában. (Ha a dokumentációban szerepel, hogy milyen adatokat kell rögzítenünk, ezek milyen adattípusúak, hol kell őket tárolni stb., akkor szinte biztos, hogy szükségtelen ezeket az információkat a folyamatábrában újra szerepeltetni.) Ilyen esetekben ahelyett, hogy részletesen kifejtenénk a lépéseket, egyetlen síkidommal jelöljük a nem elemi lépést az algoritmusban. Ez egy téglalap, melynek rövidebb oldalait dupla vonallal jelöljük.

9. kép

26

Szekvencia nem elemi utasítással

AZ ALGORITMIZÁLÁS ALAPJAI Az input és output utasítások jelölésére külön síkidom, a paralelogramma szolgál.

10. kép

Input és output

Az elágazások jelölésére sarkára állított négyszöget (négyzet, rombusz, deltoid stb.) használunk. Az elágazásba egy irányból léphetünk be, de két lehetséges irányban léphetünk ki belőle. Az elágazást jelölő négyszögbe kerül a feltétel. Ha a feltétel igaz, akkor az egyik ágat, ha hamis, akkor a másik ágat kell választanunk.

11. kép

Elágazás D-diagram

A feltételes ciklus jelölésére nincs külön síkidom, elágazás és szekvencia, illetve az őket összekötő nyilak segítségével írjuk fel őket.

27


28

12. kép

Előfeltételes ciklus D-diagram

13. kép

Végfeltételes ciklus D-diagram


2.3.4.5 Struktogram Szintén grafikus algoritmusleíró eszköz. A szakirodalomban találkozhatunk vele Nassi– Shneiderman-diagram6 (NSD), illetve Chapin-ábra7 (Chapin chart) néven is.

14. kép

Isaac „Ike” Nassi és Ben Shneiderman

15. kép

Ned Chapin

6

Isaac „Ike” Nassi és Ben Shneiderman (1947–) informatikusok által 1972/73-ban kifejlesztett eszköz. I. Nassi and B. Shneiderman: Flowchart Techniques for Structured Programming. In: ACM SIGPLAN Notices, Volume 8, Number 8 (August 1973), pp.12–26. 7 Ned Chapin: New Format for Flowcharts. In: Software – Practice and Experience, Volume 4, Number 4 (October-December 1974), pp. 341–357.

29

AZ ALGORITMIZÁLÁS ALAPJAI A struktogramok a különböző tevékenységeket téglalapokkal jelölik. Maga az algoritmus is egy tevékenység, így ezt is egy téglalap jelöli. Az algoritmus lépéseit ezen a téglalapon belül elhelyezett kisebb téglalapok jelentik. Szekvencia:

16. kép

Szekvencia a struktogramban

Az elágazás lépésének téglalapját több síkidomra bontjuk. Ha a feltétel igaz, akkor az igaz ághoz tartozó téglalap lépését hajtjuk végre, ha hamis, akkor pedig a hamis ághoz tartozó lépést.

17. kép

Elágazás a struktogramban

A ciklus jelölésére az adott téglalapon belül elhelyezett kisebb téglalap szolgál. A belső téglalapba kerül a ciklus magja, alá/fölé pedig az ismétlés feltétele. Fölé akkor, ha a ciklus előfeltételes, alá pedig akkor, ha a ciklus végfeltételes.

18. kép

30

Ciklusok a struktogramban


2.4 ÖSSZEFOGLALÁS Az algoritmusok egy feladat, probléma megoldásának lépéseit, vagyis a megoldás módszerének pontos leírását adják. Az algoritmusokkal szemben támasztott követelményekről a lecke elején már olvashattunk, de a lecke végigolvasása után leszögezhetjük, hogy a legfontosabb követelmények a pontosság és az egyértelműség. A leckében bemutatott algoritmusleíró eszközöket a szakirodalomban használt szabályok alapján ismertettük, de kisebb-nagyobb eltérések a különböző szakirodalmak jelölésmódjában előfordulhatnak. A legfontosabb követelmény itt is az, hogy egyértelműen és pontosan értelmezhető legyen az egyes lépések feladata és a lépések közötti sorrend.

2.5 ÖNELLENŐRZŐ KÉRDÉSEK Értelmezze az algoritmus fogalmát! Milyen követelményeket fogalmazhatunk meg az algoritmusokkal szemben? 2. Mutassa be az algoritmusleíró eszközöket! Milyen módon adhatók meg a vezérlési szerkezetek a különböző algoritmusleíró eszközökben? 3. Hasonlítsa össze az elő- és végfeltételes ciklusokat! Milyen ciklus lehet üres? Milyen ciklus válhat végtelenné? 4. Adja meg néhány, eddigi (közép- és felsőfokú) tanulmányai során megismert művelet, tevékenység algoritmusát! Milyen körülményekre kell figyelnie? 1.

31


3. ADATOK, ADATSZERKEZETEK 3.1

CÉLKITŰZÉS

Ebben a leckében az algoritmusokban, illetve a programokban használt adatok megjelenési formáiról, adattípusokról és adatszerkezetekről fogunk beszélni. A lecke célja, hogy megismerjük az elemi és az összetett adatok tárolási és feldolgozási lehetőségeit, az adattípusok és az adatszerkezetek jellemzőit. Algoritmusok készítésénél fontos felismernünk, hogy milyen adattípus vagy adatszerkezet a legalkalmasabb az adott probléma megoldásához. 3.2 − − − − − − − − −

TARTALOM Az adat A literál A változó Az adatok jellemzői, adattípusok Összetett adatok kezelésének lehetőségei Adatszerkezetek jellemzői Homogén adatszerkezetek: tömb, halmaz, sor, verem, lista, fájl A rekord adatszerkezet Adatok és adattípusok megjelenése a különböző programozási nyelvekben, példák

3.3 A TANANYAG KIFEJTÉSE 3.3.1

Adat

Tágabb értelemben minden jel adatnak tekinthető. Az adatok segítségével információt közölhetünk, a kommunikációban az adat hordozza az ismereteket, de nem önmagában. Információvá akkor válhat egy adat, ha az új ismeretként értelmezhető. Az adatok eszerint olyan jelsorozatok, amelyek alkalmasok arra, hogy emberi vagy gépi kommunikációban információkat közvetíthessenek. Ehhez a jeleknek érzékelhetőknek, észlelhetőknek, feldolgozhatóknak és megérthetőknek kell lenniük. Szűkebb értelemben, és a számítástechnikában általában az adatok számokkal leírt dolgokat jelentenek. Közismert, hogy a számítógépek az adatok tárolásakor lényegében minden dolgot kettes számrendszerű, azaz bináris jelsorozatokká alakítanak. Azért éppen binárissá, mert a kettes számrendszerben mindössze kétféle jelet használunk, a 0-t és az 1-et. Kétféle számjegyhez sokkal egyszerűbb egyértelműen megkülönböztethető fizikai állapotokat rendelni, mintha többféle számjegyhez kellene ugyanezt megtennünk. Ugyanakkor tudjuk azt is, hogy bármilyen adat átalakítható kettes számrendszerbeli jelsorozatokká. A természetes számok egyszerű konverzióval, az előjeles, esetleg nem egész számok különböző algoritmusokkal8, a szöveges adatok különféle karakterkódolások9 alkalmazásával, 8

Az érdeklődők számára javasoljuk, hogy önállóan ismerkedjenek meg a fixpontos és lebegőpontos aritmetika alapjaival. Ezekről az első látásra kissé talán bonyolult eljárásokról számos irodalomban olvashatunk.

32

AZ ALGORITMIZÁLÁS ALAPJAI hangok, álló- és mozgóképek pedig digitalizálással. A digitalizálás nem egyetlen eljárást jelent, a különböző médiumtípusok esetén számos eljárás ismeretes. Ezek ismertetése azonban nem tartozik jegyzetünk tárgykörébe. Most lássuk, hogy milyen módon fordulhatnak elő adatok algoritmusainkban, programjainkban. 3.3.2

A literálok

A programokban, algoritmusokban előforduló számokat, karaktereket és szövegeket literáloknak nevezzük. Literálok lehetnek például: 42, –173.51, "c", "szerda", "1989. október 23." Ezek olyan adatok, amelyek önmagukat jelentik, értékük, típusuk, jelentésük állandó. Nem tudjuk, hogy minek a mennyiségét jelöli a 42 jelsorozat, de mindenki számára nyilvánvaló, hogy ez egy kétjegyű, decimális (tízes számrendszerbeli) egész.10 Nem tudjuk, hogy milyen halmaz számosságát jelenti (pl. milyen tárgyból van negyvenkettő), de tudjuk, hogy ez az összes negyvenkét elemű halmaz közös tulajdonsága, és a nagyságrendjét is érzékeljük: több mint öt, de kevesebb, mint százhúsz. Hasonló a helyzet a –173.51 esetében, ez nagy valószínűséggel egy negatív, véges tizedes törtet, vagyis egy racionális számot jelöl. Azt ebben az esetben sem tudjuk, hogy pontosan milyen dolognak a mérőszámáról van szó, de valószínűleg mindenki egy mennyiségre gondol, ha ezt a jelsorozatot látja. A "c" egy latin betű, a magyar ábécé negyedik betűje, a fizikában a fény vákuumbeli sebességét jelölik vele. Ha egy üres lapon önmagában látjuk ezt a jelet, valószínűleg nem tulajdonítunk neki jelentést, azon túl, hogy ez egy c betű. Hasonlóképp a "szerda", amely egy karaktersorozat és magyar nyelven a hét egyik napjának neve, illetve az utolsó példa, amely egy dátum. (Számunkra azért fontos, mert akkor kiáltották ki a harmadik magyar köztársaságot, egy külföldi számára azonban valószínűleg jelentéktelen napról van szó). A számliterálok mennyiségeket, a karakterliterálok betűket (pontosabban karaktereket, vagyis a kódtábla egy-egy elemét) jelölnek, a szövegliterálok pedig karaktersorozatokat. Ezek az adatok csak önmagukat jelentik, az értékük változatlan, de alkalmasak arra, hogy műveleteket végezzünk velük, illetve rajtuk. A különböző programozási nyelvekben eltérő szabályok vonatkozhatnak a literálok megadására. Számliterálokban számjegyek, előjel és tizedespont állhat. A különböző programozási nyelvekben használhatunk tízestől eltérő alapszámú számrendszerbeli számliterálokat is, tehát nemcsak decimális, hanem pl. bináris, oktális vagy hexadecimális számliterálokat is. A karakteres literálok megadása is különbözhet az egyes programozási nyelvekben. Ezeket vagy aposztrófok (’’), vagy macskakörmök ("") között kell megadnunk (Pascalban pl. minden karakter- és sztringliterált aposztrófok között, a C-szerű nyelvekben 9

Járjunk utána, hogy milyen kódtáblákon alapuló karakterkódolási eljárások használatosak ma. Járjunk utána az ASCII kódrendszer, illetve az azon alapuló más kódrendszerek (pl. ISO-8859 szabványcsalád kódolásai) jellemzőinek. Járjunk utána, hogy mi a jelentősége a UNICODE szabványnak, és mit jelent az UTF-8 kódolás, amely a UNICODE rendszer egyik gépi megvalósítása! 10 Valójában ez egyáltalán nem ennyire egyértelmű. Önmagát tekintve ez a jelsorozat még azt sem garantálja, hogy egy mennyiségről van szó. Elképzelhető, hogy ez egy kétszavas üzenet, amelynek első szavát a 4, második szavát a 2 helyettesíti. Ahhoz, hogy ezt megfejtsük, szükségünk van egy szótárra, egy kulcsra, egy kódtáblára. Mindemellett azonban valószínű, hogy mindannyiunk számára inkább az a természetes, hogy a 42 jelsorozat egy pozitív egész számot jelent, tízes számrendszerben.

33

AZ ALGORITMIZÁLÁS ALAPJAI a karakterliterálokat aposztrófok, a sztringliterálokat macskakörmök között, míg a különböző BASIC-nyelvjárásokban mindkét literáltípust általában macskakörmök között). Jegyzetünk mondatszerű leírónyelven megadott példáiban mi minden karakter- és sztringliterált macskakörmök között fogunk megadni. 3.3.3

A változók

A 2.3.4 fejezetben bemutatott LNKO-példában használtunk két jelet, a-t és b-t, hogy számokat helyettesítsünk velük. A feladat kiírásában azt is jelöltük, hogy ezek a szimbólumok természetes számokat jelölnek, vagyis meghatároztuk, hogy milyen értékkészletből vehetnek fel értékeket. Hasonló eszközöket általános iskolás korunktól kezdve használtunk matematika, fizika és egyéb természettudományos tanórákon. Minden matematika érettségin találkozhatunk ilyen jellegű feladatokkal: Oldja meg az alábbi másodfokú egyenletet x Z esetén!

3x 2

7 x 15 0

A fenti egyenletben található x szimbólum egy (pontosabban nulla, egy vagy két) számot jelöl. Azt, hogy milyen értéke(ke)t vehet fel, az x Z szabállyal kikötöttük. Az x1 és x 2 gyököket ki tudjuk számítani a másodfokú egyenlet megoldó képletével, de mivel ezek jelen esetben nem egészek, azt mondjuk, hogy ennek az egyenletnek a megadott értelmezési tartományban nincs megoldása. A 2.3.4 fejezet példájában az a és b, illetve a fenti példában x tekinthetők változóknak. A változó egy olyan eszköz, amely valamilyen értéket helyettesít. Ez az érték nem állandó, meg is változhat, innen származik az eszköz elnevezése. Az LNKO-példában a és b értékét többször csökkentettük, tehát a vagy b az algoritmus végrehajtása során minden lépés után új értéket kapott, egészen addig, amíg egyenlők nem lettek. Az értékük tehát változott, de a végrehajtás egy adott pillanatában mindig egy konkrét értéket jelöltek. Imperatív programozásban a változóknak nagyon fontos szerepe van. A programozó ezen eszközök segítségével tudja elérni, illetve megváltoztatni a memóriában tárolt adatokat. Éppen ezért a változók az algoritmizálásban is fontos szerepet kapnak. A változók olyan programozási eszközök, amelyek négy fontos jellemzővel rendelkeznek.

3.3.3.1 A név A változó neve egy azonosító. Minden programozási nyelv világosan definiálja, hogy egy változó milyen nevet kaphat, azaz milyen karaktersorozatból állhat az azonosítója. Általában elmondható, hogy a programozási nyelvek többsége szerint az azonosító egy olyan karaktersorozat, amely betűvel kezdődik és betűvel vagy számjeggyel folytatódhat. Ez a definíció nem tűnik bonyolultnak, de ha figyelembe vesszük, hogy a különböző programozási nyelvek milyen jeleket tekintenek betűknek, akkor máris nehezebb kérdéssel állunk szemben. Nem célunk a különböző programozási nyelvek szintaktikai szabályrendszerének összehasonlítása, ezért itt csak annyit írunk a kérdésről, hogy míg a régebbi programozási nyelvek többnyire ASCII-kódolást használtak, ezért elsősorban az angol ábécé huszonhat kis- és nagybetűjét tekintettét betűnek, a mai programozási nyelvek jelentős része UNICODE kódolású, így nemcsak az angol nyelvben használt jelek tekinthetők ben34

AZ ALGORITMIZÁLÁS ALAPJAI nük betűnek. Fontos kérdés továbbá az, hogy a kis- és nagybetűk azonos jelentésűek-e (vagyis különbséget tesz-e kis- és nagybetűk között a nyelv, ha azonosítóban használjuk őket), és még számos további kérdés. Az azonosítókban használható számjegyek egyértelműen csak decimális számjegyek lehetnek. Az algoritmusok nem feltétlenül (sőt, többnyire nem) kapcsolhatók egyetlen programozási nyelvhez, ezért az algoritmusokban használt változók elnevezései nem minden esetben követik az egyes nyelvek szabályrendszerét. Ezzel kapcsolatosan részletesebb leírást adtunk a 2.3.4.3 fejezetben.

3.3.3.2 Jellemzők A változók legfontosabb jellemzői az adattípusuk, illetve hogy a program egyes részeiben hogyan viselkednek. Az adattípus egy értékhalmazhoz rendelt név. A viselkedéssel, mint jellemzővel kapcsolatosan említendő fogalmak a láthatóság és az élettartam, de mivel ez elsősorban programozási kérdés, jelen jegyzetben csak érintőlegesen tárgyaljuk. A változók adattípusa elsősorban azt határozza meg, hogy az értéküket milyen értékkészletből vehetik fel. A numerikus típusú változók értékei számok lehetnek. Ez tág fogalom, hiszen a matematikában is különböző számhalmazokat ismerünk: természetes számok, egészek, racionálisak, irracionálisak, valós számok, komplex számok. A különböző programozási nyelvekben általában többféle numerikus típus rendelhető változókhoz. Minden nyelv támogatja az egész és a valós típusokat, és jellemzően nincs külön típus az irracionális számokra. Ha végiggondoljuk, ez logikus. Az irracionális számok halmazában olyan számok találhatók, amelyek nem írhatók fel két egész szám hányadosaként. Ezeket a számokat végtelen tizedes törtként írhatnánk fel, pontos leírásuk azonban nyilvánvalóan lehetetlen, hiszen végtelenek. Ezeket a számokat csak bizonyos pontossággal tudjuk megadni. Közismerten ilyen számok a π, az e, a 2 , és folytathatnánk. (A számegyenesen több irracionális szám van, mint racionális. Ennek a tételnek a bizonyítása természetesen nem tartozik jegyzetünk tárgykörébe.) Ha pontosan akarnánk megadni az értéküket, végtelen számjegyet kellene megadnunk, a számítógép memóriájában vagy háttértárán pedig végtelen számjegyet kellene eltárolnunk. Az informatikai tárolóeszközök tárolókapacitása folyamatosan nő, de végtelen – természetesen – soha sem lesz. Így bármekkora merevlemezen tárolnánk is egyetlen irracionális számot, csak bizonyos pontossággal tehetnénk meg azt. Az informatikában az adattárolás jellemzően a véges mennyiségek körében alkalmazott tudomány. Természetesen más kérdés az, hogy mely elméleti vagy alkalmazott tudományoknak van szüksége az irracionális számok nagy pontosságú tárolására, és egzakt módon mit jelent a nagy pontosság kifejezés. Numerikus típusokon kívül a legtöbb programozási nyelv támogat karakteres típusokat (karakter, karakterlánc), sok nyelvnek van saját típusa a logikai értékek tárolására, míg más nyelvekben a logikai értékek numerikus értékekkel vannak reprezentálva. Elemi adattípusoknak nevezzük az elemi adatok tárolására szolgáló típusokat. Elemi adatok azok az adatok, amelyeket nem lehet, vagy az adott feladat szempontjából nem érdemes kisebb részekre bontani. A személyes adataink között elemi adat például a nemünk, vagy a születési évünk (bár az évszázad, mint ennek része akár külön adatként is értelmezhető lehet). Elemi adat a lakhelyünk irányítószáma, vagy a címünkből házszám.

35

AZ ALGORITMIZÁLÁS ALAPJAI Összetett adatoknak nevezzük azokat az adatokat, amelyek elemi adatokból épülnek fel. Személyi adataink közül jellemzően ilyen a lakcím, hiszen az felbontható irányítószámra, helységnévre, közterület nevére és típusára, házszámra, emeletre, ajtóra stb. Összetett adat lehet egy név is, ha szükséges, hogy külön kezeljük a vezetéknevet és a keresztneve(ke)t. Az összetett adatok kezelésére a programozási nyelvekben és algoritmusainkban adatszerkezeteket használunk. Ha egy változónak megadtuk az adattípusát, kijelöltük, hogy milyen értékkészletből vehet fel értékeket. Emellett azonban két további dolgot is meghatároztunk. Az adattípus meghatározza azt is, hogy milyen műveletek végezhetők az adott adaton. Numerikus adatokon végezhetők pl. alapműveletek, néhány kivétellel (pl. nullával való osztás), míg keresztnevek hányadosának kiszámítása értelmezhetetlen művelet. A másik dolog inkább programozási kérdés. Az adattípus meghatározásával eldől az is, hogy az adott adatot milyen reprezentációban találhatjuk meg a memóriában. Az egész számokat fixpontos számábrázolással alakíthatjuk a memóriában tárolható alakúra. Valós számokat lebegőpontos számábrázolás segítségével alakíthatunk tárolható formátumúvá. Szövegek tárolásához kódtáblákat használunk: a szöveget karakterekre bontjuk, és a karakterek kódját tároljuk a memóriában. A típus tehát a tárbeli reprezentációt is meghatározza. Az algoritmizálás témakörétől azonban ez utóbbi kérdés viszonylag távol esik.

3.3.3.3 A tárbeli cím Az adatokat a memória tárolja. A memóriában minden egyes tárcímen egybájtos adatokat tárolhatunk. A tárcímek ún. szegmentált címzéssel adhatók meg. A memóriát ilyen módon nagyon bonyolult feladat kezelni. Magunknak kell megoldani az egyes adattípusok és adatszerkezetek reprezentálását, és magunknak kell nyilvántartani azt is, hogy az egyes adatainkat milyen memóriaterületen tároljuk, illetve hogy az egyes memóriaterületeken milyen adatok érhetők el.

19. kép

36

A változók tárbeli címe

AZ ALGORITMIZÁLÁS ALAPJAI A magas szintű, elsősorban procedurális nyelvekben a változók azért alapvető jelentőségűek, mert segítségükkel a szegmentált memóriakezelés nélkül is tudunk adatokat kezelni. Változók segítségével lényegében az egyes memóriaterületeknek adhatunk nevet. A magas szintű nyelvekben ha egy változót deklarálunk (megadjuk nevét és típusát), akkor a nyelv automatikusan lefoglal egy az adott változó számára megfelelő méretű memóriaterületet. Ha ezután a változónak értéket adunk, az adott érték a választott típusnak megfelelő reprezentációban bekerül a megadott címre, ha a változó értékét szeretnénk felhasználni, akkor pedig a rendszer a változóhoz rendelt memóriaterületről olvassa ki az ott tárolt adatot, és alakítja az adott típusnak megfelelő kódolás felhasználásával a programozó által értelmezhető formátumúra.

3.3.3.4 Az érték A deklarációtól kezdve minden változó rendelkezik címkomponenssel. Mivel a memóriában nincsenek üres területek (lehet, hogy egy tárcímen 0-s érték van tárolva, de az a cella sem üres!), a számítógép bekapcsolásától kezdve a memória minden területén van valamilyen adat, a változók a deklaráció pillanatától kezdve értékkel is rendelkeznek. Régebbi programozási nyelvekben ez azt is jelentette, hogy ha a programozó deklarált egy változót, de annak nem adott értéket, akkor a változó értéke nemdeterminisztikus volt, vagyis az érték bármilyen „memóriaszemét” lehetett. Egyes nyelvekben ezt a problémát automatikus kezdőérték-adással orvosolták: a deklaráció pillanatában a változó valamilyen nullás kezdőértéket kapott (0-s numerikus érték, üres karakterlánc stb.). Más nyelvekben egy változó értékét csak akkor használhatjuk fel, ha mi magunk adtunk már neki értéket. 3.3.4

Összetett adatok, adatszerkezetek

Személyes adataink között tipikusan összetett adat a lakcímünk, hiszen ez elemi adatokra bontható. Összetett adat iskolai osztálynévsor, egy könyv adatai egy irodalomjegyzékben stb. Az összetett adatok tárolására és feldolgozására a magas szintű programozási nyelvekben adatszerkezeteket használhatunk. Adatszerkezetekkel ezért algoritmusok kapcsán is fontos foglalkoznunk. Az adatszerkezetek csoportosításának kétféle alapja lehetséges.

3.3.4.1 Az adatszerkezetek fajtái a tárolt elemek típusa szerint Vizsgálnunk kell, hogy az adott adatszerkezetet alkotó elemi adatok típusa megegyezőe, vagy az adatszerkezetben különböző típusú elemi adatok találhatók. Ha az adatszerkezetet alkotó elemi adatok azonos típusúak, akkor homogén adatszerkezetről beszélünk, ha az adattípusok különböz(het)nek, akkor pedig inhomogén vagy heterogén adatszerkezetet használunk. Homogén adatszerkezetek pl. a tömb, halmaz, sor, verem, lista, fa, háló, fájl, heterogén adatszerkezet pedig a rekord. A sztring (karakterlánc) tekinthető elemi adatnak és adatszerkezetnek is. Vannak olyan programozási nyelvek, amelyekben nem létezik ez az adattípus. Azokban a nyelvekben, amelyek támogatják a sztring típust, létezik eszköz a karakterlánc elemeinek (vagyis az egyes karaktereknek) az elérésére is. Ebből a szempontból a sztring értelmezhető egy karakterekből álló homogén adatszerkezetként (pl. tömb) is.

37

AZ ALGORITMIZÁLÁS ALAPJAI A rekord adatszerkezetben az egyes elemi adatokat mezőknek nevezzük. A mezők típusa eltérő lehet. A rekord adatszerkezet alapvető szerepet tölt be az ún. relációs adatbáziskezelő rendszerekben.

3.3.4.2 Az adatszerkezetek fajtái a tárolt elemek száma szerint Attól függően, hogy az adatszerkezet elemeinek száma változhat-e a program vagy az algoritmus végrehajtása során, beszélhetünk statikus és dinamikus adatszerkezetekről. A statikus adatszerkezetek elemszáma a létrehozás (deklaráció) pillanatában eldől, a végrehajtás során ez a tulajdonság nem változtatható meg. Tipikusan statikus adatszerkezet a tömb, amelynek elemszámát a deklarációkor kell megadnunk. Programozási nyelvtől függően fordítási vagy futásidőben a rendszer lefoglalja a megfelelő méretű memóriaterületet (a memóriaterület az elemi adatok helyfoglalásától és az elemszámtól függ), ezért nem tudjuk megváltoztatni az elemszámot.11 Arra van lehetőségünk, hogy egy 100 eleműre deklarált tömbnek csak az első harminc elemét dolgozzuk fel, de tudnunk kell, hogy a maradék hetven elem számára is foglalt helyet a rendszer, és az elemszám így statikus. Dinamikus adatszerkezeteknél a fordító vagy futtató rendszer nem foglal állandó méretű memóriaterületet. Az ilyen adatszerkezetek elemszáma futásidőben változhat. Ezeknél az adatszerkezeteknél gyakori az az eljárás, hogy létrehozunk egy üres (egyetlen elemet sem tartalmazó) adatszerkezetet, és futásidőben bővítjük vagy csökkentjük egy-egy elemmel. Dinamikus adatszerkezet például a lista, a sor, a verem, a különböző gráfok, illetve a fájl. Ismét hangsúlyozzuk, hogy ez a jegyzet programozással és algoritmizálással csak érintőlegesen foglalkozó hallgatók számára készült, ezért az adatszerkezetek áttekintésekor sem célunk a teljesség 3.3.5

A tömb

A tömb homogén, statikus, és ún. asszociatív adatszerkezet. Az asszociativitás azt jelenti, hogy az egyes elemek eléréséhez ún. indexeket használunk. A tömb minden egyes eleme kap egy (vagy több) indexet, ez(ek) általában egész szám(ok). Az egyes programozási nyelvekben nemcsak számok lehetnek tömbindexek, de mi minden példában nemnegatív egészeket fogunk használni.

3.3.5.1 A tömbök dimenzióinak száma Attól függően, hogy egy elem eléréséhez hány indexet kell megadnunk, beszélhetünk a tömbök dimenziószámáról. Az egydimenziós tömbök esetében (melyeket vektoroknak is nevezünk) az egyes elemek egy indexszel érhetők el. A tömbelemek elérésére az indexeket 11

A tömb a legismertebb és leggyakrabban használt homogén, statikus adatszerkezet, minden magas szintű programozási nyelv ismeri és támogatja. Számos nyelvben van lehetőségünk arra, hogy újradefiniáljuk a tömb méretét, vagyis megváltoztassuk az elemszámot futásidőben. Vannak olyan programozási nyelvek, amelyek tömbnek nevezett adatszerkezetében különböző típusú adatok tárolhatók. Ebben a jegyzetben nem célunk a különbségek teljes körű feltárása, sem pedig eldönteni, hogy valóban tömb-e az az adatszerkezet, amelyet egy adott nyelv annak nevez. A jegyzetben ezért mi ragaszkodni fogunk ahhoz a definícióhoz, hogy a tömb statikus, homogén adatszerkezet. Így is fogjuk használni.

38

AZ ALGORITMIZÁLÁS ALAPJAI szögletes zárójelben fogjuk jelölni (TÖMBNÉV[INDEX]). A legtöbb magas szintű programozási nyelv is követi ezt a jelölésmódot.

20. kép

Egydimenziós tömb (vektor)

A kétdimenziós tömb (mátrix) esetében egy elem eléréséhez két indexet kell megadnunk. A kétdimenziós tömbök felfoghatók úgy is, mint n sorból és m oszlopból álló táblázatok.

21. kép

Kétdimenziós tömb (mátrix)

Lényegtelen, hogy a mátrixot n×m-es vagy m×n-es táblázatnak tekintjük-e, tehát nincs jelentősége, hogy egy elem elérésekor először az oszlopindexet, majd a sorindexet, vagy először a sorindexet és ezután az oszlopindexet adjuk-e meg, de minden esetben azt a sorrendet kell követnünk, amelyet a deklarációkor eldöntöttünk Az iskolai órarend esetében először általában az oszlopindexet tekintjük, majd a sorindexet („pénteken a harmadik óra”, nem pedig „a harmadik óra pénteken”). Az órarend 39

AZ ALGORITMIZÁLÁS ALAPJAI tárolásához érdemes ezért egy öt oszlopból és hat vagy hét sorból álló tömböt deklarálnunk. A torpedójátékban, vagy a sakkban is egy mező jelöléséhez először az oszlop, majd a sorindexet adjuk meg. Ha torpedójátékot, vagy sakkprogramot készítünk, a játéktábla tárolásához használhatunk olyan mátrixot, amelynek deklarációjakor először az oszlopok, majd a sorok számát adjuk meg. (A sakknál különösen kell figyelnünk az indexekre, mert a sakktábla sorainak és oszlopainak száma azonos.) Hangsúlyozzuk, hogy nincs erre szabvány vagy kötelező szabály, de a programokban, algoritmusokban nem a fenti megoldást szoktuk követni. Mátrixoknál az elemek eléréséhez általában sorindex, oszlopindex sorrendben szoktuk megadni az indexeket. Ebben a jegyzetben mi minden esetben ezt a sorrendet fogjuk követni. A háromdimenziós tömbök esetében képzeljük azt, hogy ezek lapokból állnak, a lapokon pedig mátrixok vannak. Egy elem eléréséhez meg kell adnunk a lapindexet, majd a sorindexet, végül az oszlopindexet.

22. kép

Háromdimenziós tömb

A négydimenziós tömb elképzelhető úgy, mint egy olyan mátrix, amelynek egyes elemei is mátrixok. Az ötdimenziós tömb lapokból áll, az egyes lapokon olyan mátrixok vannak, amelyeknek az elemei is mátrixok, és így tovább.

40


23. kép

Magasabb dimenziószámú tömbök

A dimenziók száma elvben nem korlátozott, de egyrészt az egyes programozási nyelvek általában adnak felső korlátot, másrészt a gyakorlatban háromnál nagyobb dimenziószámú tömböket nem szoktunk használni.

3.3.5.2 A tömbindexek értelmezési tartománya Vannak olyan programozási nyelvek, amelyekben a tömbindex nemcsak szám lehet, hanem például karakter is, Ebben a jegyzetben mi minden esetben számokat fogunk használni. Vannak olyan programozási nyelvek, amelyekben a programozó maga döntheti el, hogy a tömbök egyes indexei milyen tartományból vehetnek fel értékeket, míg más nyelvekben deklarációkor nem az indexek által felvehető értékek tartományát, hanem a tömb elemszámát kell megadnunk. Ezekben a nyelvekben az indexelés mindig 0-tól kezdődik. Régebbi, algoritmusokkal foglakozó könyvekben gyakori volt az a sajnálatos szokás, hogy a tömb első elemének 1-es indexet adtak. Programozási nyelvekben ez egyedül a BASIC nyelvekre jellemző szokás volt, de a ma használatos BASIC változatokban (Visual Basic .NET, Visual Basic for Applications) van lehetőségünk arra, hogy a tömbelemeket 0-tól kezdjük indexelni. A programozói gyakorlatban a BASIC nyelv jelentősége csekély más nyelvekével szemben (C, C++, C#, Java stb.), és ezekben a nyelvekben minden esetben 0-val kezdődik a tömbelemek indexelése, mert a programozónak a tömb elemeinek számát, és nem az indexek által felvehető értékek tartományát kell megadnia. Ezek figyelembe vételével ebben a jegyzetben minden esetben 0-val kezdjük a tömbelemek indexelését. Az első elem indexe 0, a második elem indexe 1, a harmadik elem indexe 2 és így tovább. Egy n elemű tömb utolsó elemének indexe így n–1.

41

AZ ALGORITMIZÁLÁS ALAPJAI 3.3.6

További homogén adatszerkezetek

A következőkben felsorolásszerűen bemutatunk néhány gyakran alkalmazott adatszerkezetet és főbb jellemzőiket. A 11. fejezetben részletesebben szólunk ezekről az adatszerkezetekről és használatukról.

3.3.6.2 A halmaz A halmaz adatszerkezet ún. struktúra nélküli adatszerkezet. Az elemek között nem tudunk sorrendet kijelölni, nem tudjuk megmondani, hogy egy elemnek melyik elem a megelőzője és melyik a rákövetkezője. Az adatszerkezetbe tudunk elemeket rögzíteni és elemeket kivonni belőle, illetve meg tudjuk mondani, hogy egy adott adat eleme-e a halmaznak. A halmaz adatszerkezetnek egy elem vagy eleme, vagy nem, minden elem vagy egyszer, vagy nullaszor található meg benne. A halmaz adatszerkezet hasonlít a matematikában használt halmazokhoz, de az elemszáma nem lehet végtelen. Nem minden programozási nyelvben létezik halmaz adattípus, de a programozó készíthet saját reprezentációt, például tömb segítségével. Az ún. multihalmaz adatszerkezet lehetővé teszi, hogy egy elemet többször is elhelyezzünk a halmazban.

24. kép

25. kép

42

Halmaz

Multihalmaz


3.3.6.2 Sor Az adatszerkezetet gyakran említik FIFO néven is, amely az angol First In First Out kifejezés rövidítése. Ennek az adatszerkezetnek az a jellemzője, hogy egymás után bővítjük adatokkal, de legelőször azt az adatot dolgozhatjuk fel, amelyet először helyeztünk el benne. Úgy képzelhető el ez az adatszerkezet, mint egy alagút, benne az adatok az autók. Az autók az alagútban nem előzhetik meg egymást, vagyis az az autó fog először kijönni az alagútból, amelyik bement a másik végén.

26. kép

Sor (FIFO)

Ezt az adatszerkezetet használja a pl. billentyűzetpuffer. Ha valamiért a billentyűzetről bejövő adatok nem dolgozhatók fel azonnal, az adatok egy pufferbe kerülnek, amíg megtörténik a feldolgozásuk. Természetesen azt az adatot kell először feldolgozni, amelyik először bekerült a pufferbe, vagyis a feldolgozás sorrendjének meg kell egyeznie az adatbevitel sorrendjével.

3.3.6.3 A verem Ezzel az adatszerkezettel kapcsolatban gyakran találkozhatunk a LIFO rövidítéssel, amelynek feloldása az angol Last In First Out kifejezést jelenti. Ennek az adatszerkezetnek az a jellemzője, hogy a benne tárolt adatok közül azt dolgozhatjuk fel először, amelyet utoljára helyeztünk el benne. Képzeljünk el egy dobozt, amelyikbe azonos méretű könyveket rakunk egymás után. A dobozban a könyvek csak egymásra kerülhetnek, egymás mellett nem férnek el. Azt a könyvet fogjuk tudni először kivenni, amelyet utoljára tettünk a dobozba.

27. kép

Verem (LIFO) 43


3.3.6.4 A lista A lista adatszerkezetnek az a jellemzője, hogy minden elemnek (az első és az utolsó kivételével) van megelőzője és rákövetkezője. A listában tehát az elemek rendezettek. A lista bárhol bővíthető és bárhonnan törölhető belőle elem. Nem szabad összekevernünk a lista adatszerkezetet az ún. láncolt lista tárolási módszerrel. A láncolt lista tárolási módszernél minden elem tartalmaz egy adartrészt és egy mutató részt. Az adatrész tárolja az adatot, a mutató pedig megmondja, hogy a többi elem közül melyik az adott elem rákövetkezője. Kétirányban láncolt lista esetén egy elem nem csak a következő, hanem az előző elemre mutató mutatót is tartalmaz. Az utolsó elem következő elemre mutató mutatója egy speciális elemre, a NIL-re mutat. A NIL elemnek nincs adattagja, sem pedig előző és következő elemre mutató mutatótagja sem. Ciklikus lista esetén az utolsó elemnél a következő elemre irányuló mutató az első elemre mutat. Ciklikus lista is lehet kétirányban láncolt, ekkor az első elem előző elemre mutató mutatója az utolsó elemre mutat. A láncolt listákhoz tartozik még egy speciális elem, a fej. Ez az elem nem tartalmaz adattagot, csak egy mutatót, amely a lista belépőelemére (a kijelölt első elemre) mutat. A láncolt listába bárhová beszúrhatunk adatot, ehhez megfelelő memóriaterületet kell lefoglalnunk, majd be kell állítanunk a beszúrt elem, az azt megelőző (és esetleg a rákövetkező) elem mutatóit. Még egyszer hangsúlyozzuk, hogy a lista adatszerkezet és a láncolt lista tárolási módszer két különböző dolog. Lista reprezentálható láncolt listával, de reprezentálható vektorral is. Bármilyen adatszerkezet reprezentálható láncolt listával, ekkor szétszórt tárolásról beszélünk. Ekkor az adatszerkezet elemei – melyek logikailag valamilyen sorrendben állnak egymás után – a memória egymástól független részein, szétszórva vannak eltárolva. Folytonos tárolás esetén az adatszerkezet egyes elemei fizikailag is egymást követően vannak eltárolva a memóriában.

28. kép

Láncolt listák

3.3.6.5 Fa, bináris fa A fa adatszerkezet megfelel a matematikában használatos fa gráfoknak. Ez egy hierarchikus adatszerkezet, ahol minden egyes elemnek pontosan egy szülő, és tetszőleges számú utódeleme lehet, kivéve a gyökérelemet és a levélelemeket. A gyökérelem a gráf kezdőeleme, ennek az elemnek nincs szülője. A levélelemeknek nincs utódeleme. A gráfban az elemeket csomópontoknak nevezzük, őket élek kötik össze. Bináris fákban minden elemnek 0, 1 vagy két rákövetkezője lehet. A szigorú értelemben vett bináris fák minden elemének 0 vagy 2 rákövetkezője van.

44

AZ ALGORITMIZÁLÁS ALAPJAI Fák esetében az elemek beszúrása és törlése függ a fa típusától. Egy általános fába bárhová beszúrhatunk elemet, de csak levélelemként. Bináris fák esetén bonyolultabb a kérdés, hiszen a beszúrás után is bináris fának kell maradnia az adatszerkezetnek. A bináris fáknak és általában a fa adatszerkezeteknek a számítástechnikában nagyon fontos szerepük van. Egy mindenki által jól ismert példa a háttértárakon megjelenő könyvtárszerkezet, amely szintén egy fa struktúra.

29. kép

Fa, bináris fa, szigorúan bináris fa

3.3.6.6 A háló A háló olyan gráf, amelyben az elemeknek bármennyi megelőző és rákövetkezője lehet. Ha két elem között van kapcsolat, akkor ők egymásnak kölcsönösen megelőzői és rákövetkezői. Egy elemnek akár saját maga is lehet a megelőzője vagy a rákövetkezője.

45


30. kép

Háló

Közismert az ún. utazó ügynök probléma. Egy gráf csúcsai városok, a közöttük található élek pedig útvonalak két város között. Az éleket súlyozzuk, „költséggel” látjuk el. A költség lehet távolság, vagy meredekség (hegyvidéki utak esetében), esetleg a fizetendő ár, ha útdíjas az út vagy tömegközlekedéssel közlekedünk. A feladat az, hogy találjuk meg a legolcsóbb (legrövidebb, legkisebb szintkülönbségű stb.) utat A-ból B-be. Ezt a problémát háló adatszerkezettel (is) lehet reprezentálni.

31. kép

Háló

Megjegyezzük, hogy az ilyen jellegű feladatok megoldására nincs általános érvényű algoritmus. Nem tudunk olyan műveletsort definiálni, amely bármilyen gráfban azonnal megadja az optimális útvonalat. A megoldást keresni kell, ehhez a gráfot valamilyen algoritmussal be kell járni, és meg kell találni az optimális megoldást. Ez bonyolultabb gráfok esetében akár megoldhatatlan feladat is lehet, ezért az ilyen feladatoknál gyakran alkalmaznak mesterséges intelligenciában használt megoldásokat. 3.3.7

A rekord

A rekord heterogén adatszerkezet. A rekordban tárolt elemi adatokat mezőknek nevezzük. A mezők típusának nem kell egyezőnek lennie, ezért a rekord heterogén adatszerkezet. A rekord adatszerkezet nagyon fontos szerepet tölt be a relációs adatbázis-kezelő rendszerekben. Ezekben az adatokat táblák segítségével tároljuk, a táblákban pedig az egyes adatelemek a rekordok (egyed, tuple). Absztrakt megközelítésben: a táblák az azonos 46

AZ ALGORITMIZÁLÁS ALAPJAI egyedtípusok tárolására szolgálnak, ezekben az egyes egyed-előfordulások a rekordok. A rekordok mezői az egyedek tulajdonságait írják le. A rekord egyes mezőinek típusai a tulajdonságtípusok, míg a rekordokban tárolt mezők egyes értékei a tulajdonságelőfordulások.

32. kép 3.3.8

Rekord

A fájl

Fájlokról háttértárakon tárolt adatok esetében beszélünk. A fizikai tárolás, vagyis a reprezentáció attól függ, hogy milyen háttértáron tároljuk az adatot. A fájlokban logikailag összefüggő adatokat tárolunk, de a tárolásuk fizikailag lehet szétszórt is (gondoljunk pl. a mágneses elvű háttértárakon természetes lemeztöredezettségre, fragmentációra). A programozási nyelvek megkülönböztetik a logikai és a fizikai fájl fogalmát. A fizikai fájl a háttértáron tárolt bitkombináció, a logikai fájl az az adatszerkezet, amelyet a program során manipulálunk. Ez az adatszerkezet épül fel adatelemekből (adattagokból). A program a logikai fájlon keresztül fér hozzá a fizikai háttértár-tartalomhoz. A szerkezet nélküli (szeriális) állomány olyan állomány, amelynek nincs szerkezete. A benne tárolt adatok (rekordok) sorrendje tetszőleges. Ha keresni akarunk benne, csak teljes keresést alkalmazhatunk. A szekvenciális állományban a rekordok elsődleges kulcsa alapján rendezettek az adatok. A direkt és random állományok esetén egy függvény segítségével kölcsönösen egyértelmű (direkt állomány) vagy csak egyértelmű (random) leképezést hozunk létre az állomány rekordjainak azonosítója és a háttértáron elfoglalt helye között.

3.4 ÖSSZEFOGLALÁS Ebben a fejezetben az algoritmusokban előforduló adatokról esett szó. Az adatok lehetnek literálok, vagy megjelenhetnek változókon keresztül. A problémamegoldásban az algoritmusok mellett az adatszerkezetek ismerete is rendkívül fontos. Egy feladatot akkor tudunk sikerrel megoldani, ha felismerjük, és ki tudjuk választani a megoldáshoz legalkalmasabb adattípusokat vagy adatszerkezetet is.

3.5 ÖNELLENŐRZŐ KÉRDÉSEK Milyen jellemzői vannak egy változónak? 2. Mutassa be az elemi és az összetett adatok jellemzőit! 3. Hasonlítsa össze a statikus és dinamikus, illetve homogén és inhomogén adatszerkezeteket! 4. Eddigi tanulmányai során hol találkozott már fa és bináris fa adatszerkezettel? Ne csak az informatikára gondoljon! (Pl. családfa) 1.

47


4. ADATSORHOZ EGY ADATOT RENDELŐ ELJÁRÁSOK 1. 4.1

CÉLKITŰZÉS

Ebben a leckében olyan algoritmusokkal ismerkedünk meg, amelyek adatsorozatból (egy vektor elemeiből) egy adatot állítanak elő. A leckében szereplő algoritmusok egyszerűek, de feltétlenül szükségesek ahhoz, hogy megértsük a későbbi, bonyolultabb eljárásokat. Az alábbi algoritmusok bemutatásánál az adatokat vektorok tárolják. Fontos azonban megjegyeznünk, hogy ezek az algoritmusok – általában – kismértékű átalakítással más adatszerkezetek esetén is helyesen működnek

4.2 TARTALOM − − − − − −

Tömb feltöltése adatokkal Összegzés (összeg, szorzat, számtani közép) Eldöntés Megszámlálás Kiválasztás Szélsőérték-kiválasztás


A tömbfeltöltés

Ahhoz, hogy adatokkal dolgozhassunk, természetesen először is adatokra van szükségünk. A lecke további részében található algoritmusokat vektorokon mutatjuk be, ezért ebben a részben a vektorok feltöltését tekintjük át. Tegyük fel, hogy deklaráltuk az n elemű a vektort. A vektor feltöltésének algoritmusa: eljárás TÖMBFELTÖLTÉS ciklus I = 0-tól (N – 1)-ig be: A[I] ciklus vége eljárás vége Ezt az algoritmust akkor használhatjuk, ha a vektort inputról (pl. billentyűzetről) akarjuk feltölteni. A harmadik sor be: A[i] utasítása helyett írható pl. értékadás is, ha a vektor elemeit pl. egy másik tömb értékeinek felhasználásával akarjuk megadni. A fenti algoritmusban nem szerepel deklaráció, ahogy az ezt követő algoritmusokban sem. A deklaráció a programozási nyelvek eszköze a változó típusának és tárbeli helyfoglalásának végrehajtására. Mivel jegyzetünk az algoritmusokról szól, és az alkalmazott adatszerkezetek bázistípusa, illetve elemszáma indifferens az algoritmusok szempontjából, a deklarációkat nem jelöljük az algoritmusokban.

48

AZ ALGORITMIZÁLÁS ALAPJAI Lássunk példákat különböző programozási nyelveken! Feltételezzük, hogy az A tömböt már deklaráltuk az alábbi eljárásokat tartalmazó programrészekben, a ciklusváltozó deklarációját viszont jelöljük.

Turbo Pascal, Free Pascal procedure tombfeltoltes; var i : integer; begin for i := 0 to (n – 1) do begin write(’Kérem a(z) ’, str(i), ’. adatot:’); readln(a[i]); end; end;

ANSI C void tombfeltoltes() { int i; for (i = 0; i < n; ++i) { puts("Kérem a következő számot:"); scanf("%d", &a[i]); } }

C# void tombfeltoltes() { int i; for (i=0; i < n; ++i) { System.Console.WriteLine("Kérem a(z) {0}. adatot:", i); a[i] = System.Console.ReadLine(); } } A Pascalban mindegy, hogy a ReadLn() eljárás paramétere milyen típusú. Az ANSI C példában azt feltételezzük, hogy az A tömb egészeket tartalmaz. Ha nem, akkor a scanf() függvény paraméterében a %d konverziós karaktert %c-re, %f-re stb. kell cserélni. A C# példában azt feltételeztük, hogy az A tömb sztringeket tartalmaz. Ha nem, akkor az a[i] = System.Console.ReadLine(); értékadás helyett ehhez hasonlót kell írni: a[i] = int.Parse(System.Console.ReadLine()); – egész típusú elemek esetén –, vagy más módon 49

AZ ALGORITMIZÁLÁS ALAPJAI kell gondoskodni az input adat konvertálásáról (pl. a Convert osztály megfelelő metódusainak használatával), mert a ReadLine() függvény visszatérési értéke String. 4.3.2

Az összegzés

Az összegzés tétele egy vektor elemeinek összegét (szorzatát, számtani közepét stb.) adja meg. Feltételezzük, hogy a vektor elemei numerikus típusúak. Feladat: Adott az N elemű A vektor. Keressük az elemei összegét (szorzatát, számtani közepét). eljárás ÖSSZEGZÉS1 ÖSSZEG = 0 ciklus I = 0-tól (N – 1)-ig ÖSSZEG = ÖSSZEG + A[I] ciklus vége ki: ÖSSZEG eljárás vége Lássunk egy példát! Tegyük fel, hogy bevásárlás után szeretnénk a pénztárblokk adatait ellenőrizni. A TÉTEL tömbben tároltuk a vásárolt termékek árait, és szeretnénk ellenőrzésként kiszámítani a végösszeget. sorszám TÉTEL 1 427 2 1271 3 57 4 983 5 234

I – 0 1 2 3 4

TÉTEL[I] ÖSSZEG – 0 427 427 1271 1698 57 1755 983 2738 234 2972

Az algoritmus elején az ÖSSZEG változó felveszi a 0 kezdőértéket. Ekkor az I változó, illetve a TÉTEL tömb I-edik eleme még nem értelmezett adat. Az első lépésben I felveszi az 0-ás értéket, a TÉTEL tömb I-edik (nullás indexű, tehát első) eleme a 427. Ezt hozzáadjuk az ÖSSZEG változó aktuális értékéhez (0), így az ÖSSZEG új értéke 427 lesz. A második lépésben I felveszi az 1-es értéket, a TÉTEL tömb I-edik (egyes indexű, tehát második) értéke az 1271. Ezt hozzáadjuk az ÖSSZEG változó aktuális értékéhez (427), így az ÖSSZEG új értéke 1698 lett. Így folytatjuk, amíg a ciklus le nem fut az I = (N – 1) (azaz I = 4) értékre is. Az utolsó összeadás után az ÖSSZEG változó értéke a vektor elemeinek összege lesz. Az algoritmus helyes összeget ad, de vegyük észre, hogy van benne egy felesleges lépés. Ha otthon, számológéppel ellenőriznénk az adatokat, biztosan nem így kezdenénk el. Az első tételt nem a nullához adnánk, hanem az lenne az első lépés, hogy az első tételhez hozzáadnánk a másodikat, majd az első kettő részösszegéhez a harmadikat és így tovább.

50

AZ ALGORITMIZÁLÁS ALAPJAI Abban az esetben, ha egy vektor összes elemének összegét keressük, az ÖSSZEG változó kezdőértékének beállíthatjuk a tételek közül az elsőt, és a ciklust a második elemtől indíthatjuk. eljárás ÖSSZEGZÉS2 ÖSSZEG = A[0] ciklus I = 1-től (N – 1)-ig ÖSSZEG = ÖSSZEG + A[I] ciklus vége ki: ÖSSZEG eljárás vége Hogyan lesz az összegből átlag? Nyilván úgy, hogy elosztjuk az elemek számával. Ha tudjuk, hogy N > 0, akkor az eljárás kimenete lehet ez is: ki: ÖSSZEG / N Ha elemek szorzatát keressük, akkor a ciklus magjában lévő művelet legyen ez: SZORZAT = SZORZAT * A[I] Ekkor persze fontos, hogy a SZORZAT változó kezdőértéke ne legyen 0 (kivéve, ha a vektor első eleme éppen nulla). Az összegzés algoritmusát alkalmazzuk akkor is, ha egy vektornak csak bizonyos elemeit szeretnénk összegezni, ekkor viszont feltételes összegzést alkalmazunk. Feladat: a TÉTELEK vektorban tároljuk egy háztartás bevételeit és kiadásait. A bevételek pozitív, a kiadások negatív előjelűek. Mennyi a háztartás teljes bevétele, teljes kiadása és jelenlegi egyenlege? eljárás PÉLDA1 BEVÉTEL = 0 KIADÁS = 0 ciklus I = 0-tól (N – 1)-ig ha TÉTEL[I] > 0 akkor BEVÉTEL = BEVÉTEL + TÉTEL[I] különben KIADÁS = KIADÁS + TÉTEL[I] elágazás vége ciklus vége ki: BEVÉTEL, KIADÁS, BEVÉTEL – KIADÁS eljárás vége

51


Turbo Pascal procedure pelda1; const bevetel : real = 0; kiadas : real = 0; var i : integer; begin for i := 0 to (n – 1) if tetel[i] > 0 then bevetel := bevetel + tetel[i] else kiadas := kiadas + tetel[i] writeln(bevetel, kiadas, bevetel – kiadas); end;

C# void pelda1() { double bevetel = 0, kiadas = 0; int i; for (i = 0; i < n; ++i) if (tetel[i] > 0) bevetel += tetel[i]; else kiadas += tetel[i]; System.Console.WriteLine(’{0}, {1}, {2}’,bevetel, kiadas, bevetel – kiadas); } 4.3.3

Az eldöntés

Adott egy N elemű A vektor és egy T tulajdonság, amely értelmezhető a tömb elemeire (páros, nemnegatív, osztható öttel, hosszabb tíz karakternél, van benne ’k’ betű stb.). Kérdés: van-e az A vektornak T tulajdonságú eleme? Ez tipikusan az a tétel, amelyben nem célszerű a vektor összes elemét vizsgálni. Elegendő csak addig keresnünk T tulajdonságú elemet, míg a legelsőt meg nem találjuk, hiszen nem kérdés, hogy hány darab T tulajdonságú elem van, ezek milyen indexekkel érhetők el stb. Ha a vektor legelső eleme T tulajdonságú, megállhatunk, és az eljárás jelezheti, hogy igen, van ilyen elem. A legkedvezőtlenebb eset az lehet, ha a tömb valamennyi elemét megvizsgáltuk, de egyik sem volt T tulajdonságú. Ezt az jelzi, hogy az I ciklusváltozó értéke N lesz. N. indexű eleme nincs a tömbnek, hiszen 0-tól kezdődik az indexelés, így az utolsó elem indexe (N – 1).

52

AZ ALGORITMIZÁLÁS ALAPJAI eljárás eldöntés I = 0 ciklus, amíg (I < N) és (A[I] nem T tulajdonságú) I = I + 1 ciklus vége ha I < N, akkor ki: "Igen, van T tulajdonságú elem" különben ki: "Nem, nincs T tulajdonságú elem" elágazás vége eljárás vége Figyeljük meg a ciklusfejben szereplő feltételt. Ez a feltétel lényegében a továbblépés feltétele. Ha az éppen vizsgált index még a tömb lehetséges indexe (I < N), és az aktuális indexű elem nem olyan, amilyen keresek (A[I] nem T tulajdonságú), akkor léphetek a következő elemre. A ciklusból két ok miatt léphetünk ki: vagy az (I < N) feltétel válik hamissá, vagy az (A[I] nem T tulajdonságú) feltétel. Mivel az I értéke egyesével növekszik, az (I < N) feltétel csak úgy válhat hamissá, ha (I = N) teljesül. Ha ez az eset következik be, az azt jelenti, hogy I < N esetén egyetlen olyan elemet sem találtunk, amely T tulajdonságú lett volna, vagyis a vektornak nincs a keresett tulajdonságnak megfelelő eleme. Ha az (A[I] nem T tulajdonságú) feltétel válik hamissá, vagyis az I indexű elemre nem igaz, hogy nem T tulajdonságú, az azt jelenti, hogy találtunk egy T tulajdonságú elemet. Konkrét feladatok esetében a legnagyobb hibalehetőséget a ’nem T tulajdonságú’ feltétel leírása jelentheti, ha a T tulajdonság összetett. Matematikai logikával kapcsolatos tanulmányainkból emlékszünk az alábbi azonosságokra:

( P Q) ( P Q)

P P

Q Q

Lássunk egy példát. A SZÁMOK vektorban természetes számokat tárolunk. Kérdés: van-e közöttük olyan szám, amelyik 5-nél nagyobb, de 10-nél kisebb? T: SZÁMOK[I] > 5 és SZÁMOK[I] < 10 T: SZÁMOK[I] ≤ 5 vagy SZÁMOK[I] ≥ 10 eljárás példa2 I = 0 ciklus, amíg (I < N) és (SZÁMOK[I] ≤ 5 vagy SZÁMOK[I] ≥ 10) I = I + 1 ciklus vége ha I < N akkor ki: "Igen, van olyan szám közöttük, amelyik 5–10 közé esik" különben ki: "Nem, nincs ilyen szám." elágazás vége eljárás vége 53


Turbo Pascal procedure pelda2; var i : integer; begin i := 0; while (i < n) and ((szamok[i] <= 5 or szamok[i] >= 10) do i := i + 1; if i < n then writeln("Igen, van ilyen szám.") else writeln("Nem, nincs ilyen szám."); end;

C# void pelda2() { int i; for (i=0; i < n && (szamok[i] <= 5 || szamok[i] >= 10); ++i) ; if (i < n) System.Console.WriteLine("Igen, van ilyen szám."); else System.Console.WriteLine("Nem, nincs ilyen szám."); } 4.3.4

A megszámlálás

Adott az N elemű A vektor és egy T tulajdonság. Kérdés: hány T tulajdonságú eleme van A-nak? A válasz megadásához most az A valamennyi elemét meg kell vizsgálnunk. Az I ciklusváltozó felveszi 0 és (N – 1) között az összes lehetséges tömbindexet, és ha az I indexű elem T tulajdonságú, akkor eggyel növeljük a DB számláló értékét. eljárás megszámlálás DB = 0 ciklus I = 0-tól (N – 1)-ig ha A[I] T tulajdonságú, akkor DB = DB + 1 elágazás vége ciklus vége ki: DB eljárás vége

54

AZ ALGORITMIZÁLÁS ALAPJAI Lássunk egy példát. Ismerjük egy 15 fős iskolai csoport tanulóinak nemét és magasságát cm-ben. Számítsuk ki a fiúk átlagos magasságát!

NEM MAGASSÁG

0 F

1 F

2 N

3 N

4 N

5 F

6 F

7 N

8 F

9 N

10 11 12 13 14 F N N F F

178

192

167

159

164

169

182

177

165

170

170

173

164

181

172

eljárás példa3 ÖSSZEG = 0 DB = 0 ciklus I = 0-tól 14-ig ha NEM[I] = "F", akkor DB = DB + 1 ÖSSZEG = ÖSSZEG + MAGASSÁG[I] elágazás vége ciklus vége ha DB > 0, akkor ki: ÖSSZEG / DB különben ki: "Az adatok között nem szerepelt egy fiú magassága sem" elágazás vége eljárás vége A megoldásban egy feltételes összegzést és egy megszámlálást láthatunk. Mivel a megoldásban az adatok tárolására tömböt használunk, a nemek és a magasságok nem tárolhatók egy adatszerkezetben, hiszen különböző típusúak az adatok. Ezért két külön vektorban tároljuk őket. A logikailag összetartozó (vagyis egyazon személyre vonatkozó) adatokat az indexek kötik össze. A csoport harmadik tagjának neme NEM[2], magassága pedig MAGASSÁG[2]. Ebben a példában nem használhatjuk azt a megoldást, hogy az ÖSSZEG változó kezdőértékének a MAGASSÁG tömb 0. elemét választjuk, mert nem lehetünk biztosak abba, hogy a csoport tagjai között az első személy éppen fiú. A konkrét példában az, de más iskolai csoportok esetében ez egyáltalán nem biztos. Hasonlóképp: habár ebben a konkrét példában látjuk, hogy az adatok között szerepelnek fiúk adatai is, az adatok pontos ismerete nélkül ebben nem lehetnénk biztosak. Emiatt az összegzés és a megszámlálás után szükséges azt is ellenőriznünk, hogy volt-e T tulajdonságú elem az adatok között, vagyis jelen esetben szerepel-e legalább egy fiú adata, mert ha nem, akkor kiíráskor nullával osztanánk. Lássuk a példa Turbo Pascal és C# nyelvű kódjait! Ezekben a kódrészletekben az eddigiektől eltérően megadjuk a vektorok adatait is.

55


Turbo Pascal procedure pelda3; const osszeg : integer = 0; db : integer = 0; nem : array[0..14] of char = (’F’, ’F’, ’N’, ’N’, ’N’, ’F’, ’F’, ’N’, ’F’, ’N’, ’F’, ’N’, ’N’, ’F’, ’F’); magassag : array[0..14] of integer = (178, 192, 167, 159, 164, 169, 182, 177, 165, 170, 170, 173, 164, 181, 172); var i : integer; begin for i := 0 to (n – 1) do if nem[i] = ’F’ then begin db := db + 1; osszeg := osszeg + magassag[i]; end; if db > 0 then writeln(osszeg / db) else writeln(’Nincs közöttük fiú.’); end;

C# void pelda3() { char[] nem = new char[] {’F’, ’F’, ’N’, ’N’, ’N’, ’F’, ’F’, ’N’, ’F’, ’N’, ’F’, ’N’, ’N’, ’F’, ’F’}; int[] magassag = new int[] {178, 192, 167, 159, 164, 169, 182, 177, 165, 170, 170, 173, 164, 181, 172}; int osszeg = 0, db = 0, i; for (i = 0; i < n; ++i) if (nem[i] == ’F’) { ++db; osszeg += magassag[i]; } if (db > 0) System.Console.WriteLine(osszeg / double(db)); else System.Console.WriteLine(’Nincs közöttük fiú.’); }

56


A kiválasztás

Adott az N elemű A vektor és egy X elem, melyről biztosan tudjuk, hogy eleme A-nak. Kérdés: hányas indexű eleme A-nak X? A megoldás lényege, hogy biztosan tudjuk, hogy a keresett elem megtalálható A-ban. Az I ciklusváltozó kezdőértékét beállítjuk 0-ra, majd egyesével növelve értékét sorra megvizsgáljuk a tömb elemeit. A vizsgálatot addig folytatjuk, míg megtaláljuk X-et A-ban. Nem kell azt vizsgálnunk, hogy esetleg elfogytak-e az elemek, és a keresés sikertelen, mert a tétel előfeltételei között szerepelt, hogy a keresett elem biztosan megtalálható a vektorban. eljárás kiválasztás I = 0 ciklus, amíg A[I] ≠ X I = I + 1 ciklus vége ki: I eljárás vége Viszonylag erős követelmény az az előfeltétel, hogy a keresett elem biztosan szerepeljen a vektorban. Ezért ezt a tételt általában más tételekkel együtt szoktuk alkalmazni. Nemcsak konkrét X elemre, de T tulajdonságú elemre is felírható ez a tétel, ha biztosan tudjuk, hogy van T tulajdonságú elem egy adatsorban. Ez esetben nem konkrét értéket keresünk, hanem egy bizonyos tulajdonságú elemet. Ez a tulajdonság lehet konkrét, csak az adott adatsorra értelmezhető jellemző, de lehet általános is. A következő tétel(ek)ben általános jellemzőnek megfelelő elemeket keresünk: minden adatsoron értelmezhető szélsőérték, kereshetünk legkisebb és legnagyobb elemet.12 4.3.6

A szélsőérték-kiválasztás

A szélsőérték-kiválasztást maximumkiválasztáson mutatjuk be, de ez az eljárás nagyon könnyen alakítható minimumkiválasztássá. Maximumkiválasztásnál azokra a kérdésekre kell válaszolnunk, hogy a vektor összes eleme közül keressük a legnagyobbat, vagy a vektornak csak valamilyen feltételnek megfelelő elemeit vonjuk be a kiválasztásba. A másik kérdés az, hogy ha a maximális érték többször is előfordul, melyik előfordulás indexét szeretnénk megkapni. 12

Legkisebb és legnagyobb elemet nemcsak számok között kereshetünk. Mivel a szöveges adatok kódolásához kódtáblázatokat használnak a programozási nyelvek, a szöveges adatok is numerikus adatként vannak tárolva. Így értelmezhetünk sztringek közötti relációkat (kisebb, nagyobb, egyenlő stb.). Fontos, hogy sztringek összehasonlításakor a legtöbb programozási nyelv case sensitive, vagyis a kis- és nagybetűket határozottan megkülönböztetik, és a nagybetűk kódja kisebb, mint a kisbetűké. (A legtöbb magas szintű programozási nyelv így kezeli a karakterláncok összehasonlítását, de van kivétel, pl. az Adobe Director nevű multimédia szerzői rendszerének programozási nyelve, a Lingo nem case sensitive, még a sztringek összehasonlításában sem.) Továbbá a kódtáblákban az alfabetikus karakterek között sajnos csak az angol ábécé betűire igaz az, hogy betűrend szerint követik egymást. A magyar ékezetes magánhangzók helye a kódtáblákban nem követi a betűrendbe sorolás magyar szabályait, ezért magyar ékezetes karaktereket tartalmazó karakterláncoknál az összehasonlító operátorok segítségével közvetlenül nem tudunk betűrendbe sorolást végezni.

57

AZ ALGORITMIZÁLÁS ALAPJAI Az alábbi eljárásban a vektor összes elemének figyelembe vételével a maximális elem indexét keressük. Ha több előfordulása is van, az első előfordulás indexét keressük. eljárás maximumkiválasztás1 MAXINDEX = 0 ciklus I = 1-től (N – 1)-ig ha A[I] > A[MAXINDEX], akkor MAXINDEX = I elágazás vége ki: MAXINDEX eljárás vége Figyeljük meg, hogy az eljárásban abból a kezdőfeltételből indulunk ki, hogy a vektor legnagyobb eleme az első elem. Ezt követően a második elemtől az utolsó elemig mindet összehasonlítjuk az eddig legnagyobbnak tekintett elemmel, és ha az aktuális indexű elem nagyobb, mint az eddig legnagyobbnak gondolt, akkor megjegyezzük ennek indexét. A további hasonlításoknál ezt az új indexet vesszük figyelembe. Az eljárásban tehát a MAXINDEX változó az eddig megvizsgált elemek közül jegyzi meg a legnagyobbnak az indexét. Mint fent jeleztük, ez az eljárás a vektor összes elemének figyelembe vételével keresi a legnagyobbnak az indexét. Ha a maximális elemnek több előfordulása is van a vektorban, ez az eljárás az első előfordulás helyét adja meg.

33. kép

Szélsőérték többszöri előfordulása egy vektorban

Az eljárásban az elágazás feltételében található > (nagyobb) relációt < (kisebb) jelre cserélve az eljárás minimális elemet keres. Ebben az esetben szintén minden elem figyelembevételével, és ha több minimáliselem-előfordulás is van a vektorban, akkor a legelsőt találjuk meg. Abban az esetben, ha a szélsőérték-előfordulások közül az utolsónak az indexére vagyunk kíváncsiak, akkor a > és < relációkat ≥ (nagyobb vagy egyenlő) és ≤ (kisebb vagy egyenlő) relációra kell cserélnünk. Feladat: A 4.3.4 fejezetben megadott adatok figyelembe vételével keressük a legmagasabb lány magasságát. Ennél a feladatnál nem vehetjük figyelembe az összes adatot, hiszen vannak fiúk is a tanulócsoportban. Minden esetben az alábbi algoritmust kell alapul vennünk, ha feltételezzük, hogy az adatsorban szerepelhetnek olyan adatok is, amelyek nem felelnek meg a feladat kiírásának. (Ennél a feladatnál azt kell feltételeznünk, hogy a csoportban nemcsak lányok vannak.) Mivel tudjuk vagy feltételezzük, hogy nem minden adatot kell majd figyelembe vennünk, ebben a feladatban nem élhetünk azzal a kezdőfeltételezéssel, hogy az első adat a 58

AZ ALGORITMIZÁLÁS ALAPJAI legnagyobb, mert lehet, hogy a konkrét esetben az első adat nem is lányé. (A fenti adatsorban valóban nem lányé az első adat.) Természetesen nem hasonlíthatjuk hozzá a többi adatot. Ha az az eset következne be, hogy nincs egyetlen lány sem, aki magasabb, mint az első tanuló (aki fiú) magassága, akkor az algoritmus végül rossz adatot szolgáltatna. Egy olyan lány magasságát kapnánk meg, amely valójában az első fiú magassága. Ilyenkor szükségünk van még egy segédváltozóra, ennek kezdőértéke lesz az, amelyet az első összehasonlításkor alapul veszünk. Ennek az értéknek viszont olyannak kell lennie, hogy az első összehasonlításkor biztosan felülíródjon. Ha maximumot keresünk, ennek a segédváltozónak olyan kezdőértéket adjunk, amelynél az első valós elem mindenképpen nagyobb, legyen az bármilyen kicsi is. Ha minimumot kell keresnünk, a segédváltozó kapjon olyan kezdőértéket, hogy az első összehasonlításnál ez az érték mindenképpen nagyobb legyen, mint az első valós érték, legyen az bármilyen nagy is. Maximumkiválasztásnál ezt az értéket –∞-nek, minimumkiválasztásnál +∞-nek fogjuk jelölni. Ilyen értéket a programozási nyelvek nem támogatnak, ezért a konkrét nyelvi implementációkban kellően nagy vagy kellően kicsi értékkel helyettesítsük őket! A MAXINDEX (vagy MININDEX) változó értékét pedig –1-re állítjuk. A tömbnek nincs –1-es indexű eleme, ez az index tehát egy fiktív elemé. Ez jelöl(het)i a kiválasztás végén, hogy találtunk-e egyet is a kijelölt tulajdonságú elemek között, amely lehet minimum vagy maximum. eljárás példa4 MAX = –∞ MAXINDEX = –1 ciklus I = 0-tól 14-ig ha NEM[I]=’N’ és MAGASSÁG[I] > MAX, akkor MAX = MAGASSÁG[I] MAXINDEX = I ciklus vége ki: MAGASSÁG[MAXINDEX] eljárás vége A fenti eljárás végén a kiíratásnál használhattuk volna a MAX változót is, hiszen ugyanazt az értéket tárolja, mint a MAGASSÁG[MAXINDEX]. Gyakori eset azonban, hogy nem ugyanabból a vektorból kell megadnunk a végeredményt, amelyben kerestünk. Ha például tárolnánk a tanulók neveit, akkor kérdezhettük volna a legmagasabb lány nevét is: NÉV[MAXINDEX].

4.4 ÖSSZEFOGLALÁS Ebben a leckében olyan elemi algoritmusokkal ismerkedtünk meg, amelyek adatsorból egy adatot állítanak elő. Az itt szereplő eljárások körét önkényesen választottuk ki, ebben a leckében szerepelhetett volna több eljárás is.

59


4.5 ÖNELLENŐRZŐ KÉRDÉSEK Keressen olyan hétköznapi tevékenységeket, amelyben szélsőérték-kiválasztás alkalmazható! 2. Gyorsítja-e a szélsőérték-kiválasztást, ha tudjuk, hogy az adatsor rendezett? 3. Általános esetben van-e mód arra, hogy megszámlálásban ne vizsgáljuk meg egy adatsor összes elemét, és mégis helyes adatot kapjunk? 4. A végrehajtás lépéseinek számát tekintve az eldöntés és a kiválasztás miben tér el a többi eljárástól? 1.

60


5. ADATSORHOZ EGY ADATOT RENDELŐ ELJÁRÁSOK 1. – KERESÉSEK 5.1

CÉLKITŰZÉS

A keresések az informatikai algoritmusok nagyon gyakran alkalmazott csoportját alkotják. Keresőprogramokkal keresünk információt az interneten, szóra vagy szövegrészre keresünk a szövegszerkesztő programban, kulcs alapján keresünk az adatbázisokban stb. Ez a lecke a legalapvetőbb keresési eljárásokat mutatja be. Az eddigiekhez hasonlóan ezeket az eljárásokat is vektorokon mutatjuk be, de a gyakorlatban ezeket általában más adatszerkezeteken alkalmazzák. A keresőeljárások célja hasonló a kiválasztáséhoz, de lényeges különbség, hogy nem lehetünk biztosak abban, hogy a keresett elem valóban megtalálható a vektorban: előfordulhat, hogy a keresés eredménytelen lesz. Adott az N elemű A vektor és az X elem. Kérdés: mi az X indexe az A vektorban, ha egyáltalán megtalálható benne? Az alábbiakban többféle keresőeljárást mutatunk be.

5.2 TARTALOM 5.3 A TANANYAG KIFEJTÉSE – A teljes keresés – A strázsás keresés – A lineáris keresés – A bináris keresés – Sztring keresése sztringben – mintaillesztés 5.3.1

A teljes keresés

Ez az eljárás nagyon hasonlít az eldöntés tételéhez. Egyesével vizsgálunk minden elemet, hogy az-e a keresett X elem. A vizsgálat akkor ér véget, ha az I indexű elem éppen a keresett elem, vagy az utolsó elemet is megvizsgáltuk és a keresés nem hozott eredményt (I = N). Ez a keresés nem hatékony, de rendezetlen vektorok (és egyéb adatszerkezetek) esetén az egyetlen, amely megbízhatóan működik.

61

AZ ALGORITMIZÁLÁS ALAPJAI eljárás teljesKeresés I = 0 ciklus, amíg (I < N) és (A[I] ≠ X) I = I + 1 ciklus vége ha I < N, akkor ki: I különben ki: "A keresett elem nem található." elágazás vége eljárás vége 5.3.2

A strázsás keresés

A teljes keresésben összetett ciklusfeltételt látunk. Egy összetett ciklusfeltétel kiértékelése mindig bonyolultabb (és több időt igényel a processzortól), mint egy egyszerű feltételé. Próbáljuk meg egyszerűsíteni a ciklusfeltételt. A kiválasztás tételében nem kellett azt az esetet vizsgálnunk, hogy a ciklusváltozó értéke nagyobb-e, mint a legnagyobb tömbindex, mert biztosan tudtuk, hogy a keresett elem megtalálható a tömbben, és „meg fogja állítani” a keresést. Hogyan alakíthatnánk a teljes keresést kiválasztássá? Ha biztosak lehetnénk abban, hogy a keresett elem megtalálható a vektorban. Hogyan lehetünk biztosak ebben? Ha beletesszük a vektorba a keresett elemet. A strázsás keresés lényege, hogy a keresett elemet elhelyezzük a tömb utolsó valódi eleme mögött (A[N] = X). Ekkor az így kibővített tömbön már alkalmazható a kiválasztás tétele, mert biztosan tudni fogjuk, hogy a keresett elem szerepel a vektorban. Ha a kiválasztáskor ezt a strázsaelemet (illetve annak indexét) találjuk meg, az azt jelenti, hogy a keresett elem az eredeti tömbben nem szerepelt. Az eljárás sebességét tekintve lehet hatékonyabb, mint a teljes keresés, a helyfoglalás szempontjából viszont biztosan kevésbé hatékony, hiszen nagyobb tárterületre van szükségünk a tömb számára. Ha a tömbelemek például hosszú karakterláncok, emiatt a plusz helyfoglalás miatt elképzelhető, hogy nem is célszerű ezt a keresést alkalmaznunk. eljárás strázsásKeresés A[N] = X I = 0 ciklus, amíg A[I] ≠ X I = I + 1 ciklus vége ha I < N, akkor ki: I különben ki: "A keresett elem nem található." eljárás vége

62


A lineáris keresés

A keresés előfeltétele, hogy az adatsor rendezett legyen, vagyis teljesüljön az alábbi feltétel: a0 ≤ a1 ≤ a2 ≤ … ≤ an. Az eljárás lényege, hogy teljes keresést végzünk az első elemtől kezdve, de csak addig, amíg a keresett elem egyáltalán előfordulhat a tömbben.

34. kép

Lineáris keresés

Mivel az adatsor rendezett, megállhatunk, ha az A[I] < X feltétel már nem teljesül. Vagy azért, mert A[I] = X (számunkra ez a kedvező eset), vagy mert a tömb I-nél nagyobb indexű elemei mind nagyobbak, mint X, tehát biztosan nem fog közöttük szerepelni. eljárás lineárisKeresés I = 0 ciklus, amíg (I < N) és (A[I] < X) I = I + 1 ciklus vége ha (I < N) és (A[I] = X), akkor ki: I különben ki: "A keresett elem nem található." eljárás vége 5.3.4

A bináris (logaritmikus) keresés

Mielőtt áttekintenénk ezt a programozási tételt, képzeljük el a következő játékot, melyet ketten játszhatnak. Az egyik játékos gondol egy egész számot 1 és 100 között, a másiknak az a feladata, hogy minél gyorsabban kitalálja ezt a számot. Ehhez mond egy tippet, amelyre a számot gondoló játékos válaszként megmondja, hogy az általa gondolt szám kisebb vagy nagyobb-e, illetve, ha a tippelő eltalálta a számot, akkor természetesen ezt is jelzi. Mi lehet a legcélszerűbb első tipp? Nyilván az 50, hiszen ezzel máris kizárható az eredeti számok fele, sőt, még annál is több. Ha a tippelő az 50-et mondja, a számot gondoló játékos megmondja neki, hogy az ő száma kisebb, nagyobb, vagy éppen egyenlő ezzel a számmal. Ha például kisebb, akkor a második tippnek nem is 1 és 50 közé kell esnie, hiszen az 50-et is kizárhatjuk: ha az lett volna a gondolt szám, a játék már véget ért volna. A második tippnek így 1 és 49 közé kell esnie, ez célszerűen a 25 lehet. Ha a gondolt szám ennél nagyobb, akkor 26 és 49 közé kell esnie. A harmadik tipp így lehetne ennek a két számnak a számtani közepe: 38. (Felfelé kerekítettünk, bár a matematika szabályai szerint 37 lenne a 63

AZ ALGORITMIZÁLÁS ALAPJAI kerekítés.) Tegyük fel, hogy a gondolt szám ennél kisebb, vagyis 26 és 37 közé kell esnie, 26 és 37 számtani közepe felfelé kerekítve 32, ez lehet a negyedik tipp. Tegyük fel, hogy a gondolt szám ennél kisebb, vagyis 26 és 31 közé esik. Az ötödik tipp így legyen 28. Tegyük fel, hogy a gondolt szám ennél kisebb, ekkor csak a 27 lehet az. Ez azt jelenti, hogy a 6. tippre eltaláltuk a számot. Ha nem ezzel a módszerrel tippeltünk volna, hanem 1-től kezdve egyesével mondtuk volna a tippeket, 27 lépésben találtuk volna el a gondolt számot. A bináris (logaritmikus) keresés alkalmazásának szintén előfeltétele, hogy az adatsor rendezett legyen. Nézzük meg egy példa segítségével, hogyan működik, ha az adatokat egy vektorban tároljuk. A

7

8

10

10

17

21

23

23

31

37

40

49

61

67

73

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

A kereséshez három segédváltozót használunk: E (a tartomány első eleme), U (a tartomány utolsó eleme) és K (a tartomány középső eleme). A keresett elem X, a tartomány a tömbnek az a része, amelyben még megtalálható lehet a keresett elem. A tartományon kívül eső elemek között biztosan nem szerepelhet az X. Tegyük fel, hogy X = 37.

1.

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

7

8

10

10

17

21

23

23

31

37

40

49

61

67

73

↑ E=0

↑ K=7

↑ U=14

2.

↑ E=8

3.

↑ E=8

↑ K=11 ↑ K=9

↑ U=14

↑ U=10

1. lépés: A kezdőállapotban E = 0, U = 14, K = (E + U) / 2 = 7. A K-adik elem (A[K]) 23. A 23 kisebb, mint X (= 37), vagyis ha az X egyáltalán megtalálható a vektorban, akkor csakis a jelenlegi K-adik elem után lehet. Ezért megváltoztatjuk a tartomány kezdőelemének indexét: E = K + 1. 2. lépés: Az első lépés után E = 8, U = 14, K = (E + U) / 2 = 11. A[K] = 49, ez nagyobb, mint a kereset X, vagyis ha az X egyáltalán megtalálható A-ban, akkor csakis a jelenlegi Kadik elem előtt lehet. Ezért megváltoztatjuk a tartomány utolsó elemének indexét: U = K – 1. 3. lépés: E = 8, U = 10, K = (E + U) / 2 = 9. A[K] = 37 = X, ezt az elemet kerestük, vége az eljárásnak.

64

AZ ALGORITMIZÁLÁS ALAPJAI Lássunk most egy olyan esetet, amikor a keresett elem nem található. Legyen X = 9! 0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

7

8

10

10

17

21

23

23

31

37

40

49

61

67

73

1.

↑ E=0

2.

↑ E=0

3.

↑ E=0

↑ K=7 ↑ K=3 ↑ K=1

↑ U=14

↑ U=6

↑ U=2 ↑ E=K=U=2

4. ↑ U=1

5.

↑ E=2

1. lépés: Kezdőállapot, E = 0, U = 14, K = (E + U) / 2 = 7. A[K] = 23, ez nagyobb, mint X, tehát ha X egyáltalán eleme A-nak, akkor csak a K-adik elem előtt lehet. U = K – 1. 2. lépés: E = 0, U = 6, K = (E + U) / 2 = 3. A[K] = 10, ez nagyobb, mint X, tehát ha X egyáltalán eleme A-nak, akkor az indexe csak K-nál kisebb lehet. U = K – 1. 3. lépés: E = 0, U = 2, K = (E + U) / 2 = 1. A[K] = 8, ez kisebb, mint X, tehát ha X egyáltalán eleme A-nak, akkor az indexe csak K-nál nagyobb lehet. E = K + 1. 4. lépés: E = U = K = 2, A[K] = 10, ez nagyobb, mint X, tehát ha X egyáltalán eleme Anak, akkor az indexe csak K-nál kisebb lehet. U = K – 1. 5. lépés: E = 2, U = 1, vége az eljárásnak, mert annak a tartománynak egy eleme sincs, amelynek első eleme a kettes, utolsó eleme az egyes indexű elem. Ha tehát az E > U feltétel teljesül, az azt jelenti, hogy a keresett elem nem található az adatsorban. Kimondhatjuk, hogy a bináris (logaritmikus) keresés legfeljebb M = log2 N + 1 lépésben megtalálja a keresett elemet, vagy megáll, ha a keresett elem nem található az adatsorban. Az x jelölés x felső egészrészét jelenti. Ha N = 10, akkor M = log2 10 + 1 = 5. Ha N = 100, akkor M = log2 100 + 1 = 8. Ha N = 1000, akkor M = log2 1000 + 1 = 11. Ha N = 10 000, akkor M = log2 10 000 + 1 = 15. Ha N = 100 000, akkor M = log2 10 000 + 1 = 18. … Látható, hogy ha N értékét nagyságrendekkel növeljük is, a maximális lépések száma a keresésben csak minimálisan növekszik. Ezért ennek az eljárásnak igazán a nagy elemszámú adatsorokban nagy a hatékonysága. Természetesen nem szabad elfelednünk azt az előfeltételt, hogy az algoritmus rendezett adatsort igényel. Jogos kérdés lehet, hogy ha a keresett elemnek több előfordulása is van az adatsorban (a rendezettség feltétele miatt ezek az előfordulások egymást követik), vajon melyik előfordulást találja meg az eljárás. Legyen X = 35, A pedig az alábbi: …

k–1

k

k+1

…

i–2

i–1

i

i+1

i+2

…

l–1

l

l+1

…

…

8

9

11

…

33

35

35

35

37

…

59

61

67

…

65

AZ ALGORITMIZÁLÁS ALAPJAI A választ N nagysága, illetve az A elemeinek nagysága és eloszlása is befolyásolhatja, így általános képletet nem tudunk mondani arra, hogy ilyen esetben X melyik előfordulásának indexét találja meg az algoritmus. Ha X szerepel az A-ban, akkor az algoritmus biztosan megtalálja. Ha szükséges, egy másik algoritmussal összegyűjthetjük X összes előfordulását, amelyek nyilvánvalóan K-nak az ε sugarú környezetében találhatók, ahol ε ≤ N / 2. eljárás logaritmikusKeresés E = 0 U = N – 1 K = (E + U) / 2 ciklus, amíg (E ≤ U) és (A[K] ≠ X) ha A[K] < X, akkor E = K + 1 különben U = K – 1 elágazás vége K = (E + U) / 2 ciklus vége ha (E ≤ U), akkor ki: K különben ki: "A keresett elem nem taláható." elágazás vége eljárás vége

5.3.5

Sztring keresése sztringben – mintaillesztés

Gyakori feladat, hogy egy karakterláncot kell megkeresnünk egy másik karakterláncban, ezt a műveletet nevezik mintaillesztésnek (pattern matching) is. Az a karakterlánc, amelyben keresünk, lehet akár egy teljes dokumentum is egy szövegszerkesztő programban. A feladat nemcsak sztringek esetén értelmezhető és használható, ugyanezt a problémát kell megoldani akkor is, ha egy szakaszt keresünk egy DNS-láncban. A keresett minta lehet reguláris kifejezés is. Ilyenkor nem egy konkrét sztinget keresünk, hanem egy a lehetséges sztringek alkotta halmazt (egyszerű regulári kifejezés az is, amikor az operációs rendszerben fájlok kereséséhez helyettesítő – joker – karaktereket használunk, pl.: *.doc, szepes?.txt). Egyes – nem imperatív – programozási nyelvekben a mintaillesztés rendszerszinten támogatott szolgáltatás (pl. Perl). A problémával számos szakirodalom foglalkozik. Jegyzetünkben a legegyszerűbb, az ún. „brute force” eljárást ismertetjük. Hatékonysági mutatóit tekintve ez a leggyengébb módszer, viszont egyszerű és könnyen megérthető. A téma iránt érdeklődők figyelmébe

66

AZ ALGORITMIZÁLÁS ALAPJAI ajánljuk az alábbi mintaillesztő eljárások tanulmányozását: KMP (Knuth–Morris–Pratt) algoritmus, Rabin–Karp algoritmus, Boyer–Moore algoritmus13, Dömölki algoritmus. A brute force (nyers erő) vagy egyszerű mintaillesztési eljárás egy lineáris keresésbe ágyazott lineáris keresés. A sztringeket most tekintsük olyan tömböknek, amelyek karaktereket tartalmaznak (sok programozási nyelvben ez egyébként nem áll távol a konkrét megvalósítástól). Legyen A az a tömb, amelyben keresünk, B pedig a keresett sztring karaktereit tartalmazó tömb. Legyen N az A hossza, M pedig B hossza (karaktereinek száma). Így nyilvánvaló, hogy a legutolsó karakterpozíció, ahol az illeszkedés egyáltalán bekövetkezhet az (N – M) pozíció. Az alábbi egyszerű algoritmus kiírja az első olyan kezdőpozíciót, ahol a B illeszkedik A-ra. Ha nincs ilyen, akkor pedig azt, hogy a keresett sztring nem található. eljárás egyszerűMintaillesztés I = 0 J = 0 K = 0 ciklus, amíg I ≤ (N – M) és J < (M – 1) ha A[K] = B[J], akkor K = K + 1 J = J + 1 különben I = I + 1 J = 0 K = I elágazás vége ciklus vége ha J = (M – 1), akkor ki: "Illeszkedik ezen a pozíción:", I különben ki: "Nincs illeszkedés." eljárás vége

35. kép

13

Egyszerű mintaillesztés

E három algoritmus elemzésekkel együtt megtalálható többek között itt: Thomas H. Cormen – Charles E. Leiserson – Ronald L. Rivest: Algoritmusok, 34. fejezet. Műszaki Könyvkiadó, Budapest, 1997.

67


5.4 ÖSSZEFOGLALÁS Ebben a leckében olyan elemi algoritmusokkal ismerkedtünk meg, amelyek adatsorból egy adatot állítanak elő. Javasoljuk, hogy az Olvasó is találjon ki az ismertetett példákban látottakhoz hasonló kérdéseket, és próbálja megadni a megoldások algoritmusát. Feladatokat konkrét adatok ismerete nélkül is kitalálhatunk. Ebben az esetben még nagyobb szerepe van annak, hogy olyan algoritmusokat adjunk meg, amelyek fel vannak készítve a szélsőséges esetekre is.

5.5 ÖNELLENŐRZŐ KÉRDÉSEK Milyen esetekben kell teljes keresést alkalmaznunk? 2. Mit jelent a mintaillesztés kifejezés? 3. Milyen okból kapta a nevét a logaritmikus keresés? 4. Gondolja végig, hogyan keres meg egy számot a telefonkönyvben vagy egy szót a szótárban (ne online adatbázisra, hanem nyomtatott könyvre gondoljon)! Próbáljon meg algoritmust adni erre a módszerre! 1.

68


6. ADATSORHOZ ADATSORT RENDELŐ ELJÁRÁSOK 1. 6.1 CÉLKITŰZÉS Ebben a fejezetben olyan algoritmusokkal ismerkedünk, amelyek adatsorból adatsort, vektorok esetében a forrásadatokból vektort állítanak elő. Ez lehet egy másik vektor, vagy pl. a rendezőeljárások esetében maga a forrásvektor. 6.2

TARTALOM

A leckében az alábbi algoritmusokat mutatjuk be: − A kiválogatás − Az összefuttatás


Kiválogatás

Adott az N elemű A vektor és egy T tulajdonság. Másoljuk a B vektorba A összes T tulajdonságú elemét! Az eljárás leginkább a korábban tárgyalt megszámlálás tételre hasonlít. Megjegyezzük, hogy bár az alábbiakban olyan eljárást mutatunk be, melyben az eredményként létrehozott adatsor egy vektor, ez helyfoglalás szempontjából nem hatékony megoldás. Ha előzetesen nincs információnk arról, hogy az A vektorban hány T tulajdonságú elem található, a B deklarációjakor csak az A elemszámát vehetjük alapul. Ez egyedül abban az esetben nem jár felesleges helyfoglalással, ha A minden eleme T tulajdonságú. Ennél a tételnél az eredményadatsor adattípusának célszerűbb dinamikus adatszerkezetet (pl. lista) választani. eljárás kiválogatás J = 0 ciklus I = 0-tól (N – 1)-ig ha A[I] T tulajdonságú, akkor B[J] = A[I] J = J + 1 elágazás vége ciklus vége eljárás vége Az eljárás végén a J változó a B számosságát (elemszámát) fogja tárolni. Természetesen J indexű eleme a B-nek sem lesz, hasonlóan A-hoz, amelynek N indexű eleme nincs. A legnagyobb indexek (J – 1) és (N – 1).

69


36. kép

Egyedek kiválogatása

A kiválogatásnak egy speciális változata az, amelyben az eredményadatsor tartalmazza a forrásadatsorban található összes elemet, de mindegyiket csak egyszer (például ismerjük 100 autó adatait – típus, márka, rendszám, szín stb. –, és készítünk egy olyan kiválogatást, amelynek eredménye az az adatsor, amelyben szerepel minden típus, de csak egyszer). Ehhez hasonló művelet adatbázis-kezelő rendszereknél az a lekérdezés, amelynek SQLparancsában szerepel a GROUP BY záradék. Egy lehetséges megoldásban az A vektor első elemét átmásoljuk a B vektor első indexű helyére, hiszen ezt megelőzően a B vektor még üres14. Ezután az A vektor második elemétől az utolsó elemig minden elem esetén végrehajtunk egy eldöntést: az I indexű A-beli elem szerepel-e már B-ben. Ha nem szerepel, akkor felvesszük B-ben az utolsó elem utáni helyre. eljárás kiválogatás2 B[0] = A[0] 14

Az üres kifejezés pontatlan. A memóriában lefoglalt terület nem függ a tárolt adatok tartalmától. A deklarációkor meg kell adnunk, hogy az egyes tömbelemek hány bájtot foglalnak. Pl. ha a tömb elemei 20 karakter hosszúságú sztringek, akkor az egyenként 20 vagy 40 bájtot foglalnak attól függően, hogy a programozási nyelv 8 vagy 16 bites jelkódolást alkalmaz. Dinamikus adatszerkezetek esetében az üres kifejezés azt jelenti, hogy egyetlen eleme sincs, és nem foglal memóriaterületet. Vektorok esetében legfeljebb azt jelentheti az üres szó, hogy az elemei valamilyen nullás kezdőértékkel rendelkeznek (numerikus adatok értéke 0 vagy 0.0, a karakterláncok értéke az üres sztring).

70

AZ ALGORITMIZÁLÁS ALAPJAI K = 1 ciklus I = 1-től (N – 1)-ig J = 0 ciklus, amíg (J < K) és (A[I] ≠ B[J]) J = J + 1 ciklus vége ha (J = K), akkor B[K] = A[I] K = K + 1 elágazás vége ciklus vége ciklus vége eljárás vége Ez az eljárás kombinálható megszámlálással is. Ekkor egy harmadik vektorban (C) azt tartjuk nyilván, hogy B elemei hányszor fordulnak elő B-ben. Az első lépésben B első eleme A első eleme lesz, C első eleme pedig 1-es értéket kap. Az A második elemétől az utolsó elemig minden elemre végrehajtunk egy eldöntést: szerepel-e műr az I indexű A-beli elem B-ben. Ha nem, akkor felvesszük B utolsó eleme után új elemként, C-be pedig ezzel az indexszel felveszünk egy 1-es értéket. Ha igen, akkor C-ben megnöveljük a megfelelő indexű elem értékét 1-gyel.

37. kép

Egyedek kiválogatása megszámlálással

71

AZ ALGORITMIZÁLÁS ALAPJAI eljárás kiválogatás3 B[0] = A[0] C[0] = 1 K = 1 ciklus I = 1-től (N – 1)-ig J = 0 ciklus, amíg (J < K) és (A[I] ≠ B[J]) J = J + 1 ciklus vége ha (J = K), akkor B[K] = A[I] K = K + 1 különben C[J] = C[J] + 1 elágazás vége ciklus vége eljárás vége 6.3.2

Az összefuttatás

Az összefuttatás tétele két rendezett sorozatból állít elő egy harmadik rendezett sorozatot, melyben a két input adatsor minden eleme szerepel, de ha egy elem mindkét adatsornak eleme volt, az eredmény adatsorban csak egyszer fog szerepelni. Képzeljük el, hogy egy iskolában matematikából és angolból egy időben rendeznek tanulmányi versenyt. A szervezők szeretnének kimutatást készíteni arról, hogy az iskola összes tanulójának hány százaléka vett részt a versenyen, és név szerint kik azok a tanulók, akik részt vettek valamelyik versenyen. Így ha egy tanuló mindkét versenyen részt is vett, ebben a névsorban csak egyszer fog szerepelni a neve. A kiválogatáshoz hasonlóan az eredményadatsor számára a vektor nem optimális adatszerkezet, mert nem tudjuk, hogy hány elem eleme mindkét input adatsornak. Ha egyetlen olyan X elem sincs, hogy X A és X B, akkor C elemszáma N + M lesz, ahol N A elemszámát, M pedig B elemszámát jelöli: N = |A| , M = |B|, |C| = N + M. Mivel nem minden esetben tudhatjuk, hogy mennyi az ismétlődő elemek száma, C-t (N + M) méretűre kell deklarálnunk. Az A vektor elemeit az I, a B vektor elemeit a J indexváltozó segítségével érjük el. A C elemeinek indexváltozója K lesz. A és B elemeit páronként hasonlítjuk össze (A[I]-t B[J]hez hasonlítva). A két elem közül a kisebbet bemásoljuk C-be. Ha a kisebb elem A-ból való, akkor az I, ha B-ből való, akkor a J értékét növeljük eggyel. Ha A[I] = B[J], akkor A[I]-t másoljuk a C[K] helyre, és I-t és J-t is növeljük eggyel.

72

AZ ALGORITMIZÁLÁS ALAPJAI Általában nem egyszerre „fogynak el” az elemek A-ból és B-ből, ezért ha egy A-beli elemet már egyetlen B-beli elemhez sem tudunk hasonlítani, mert elfogytak B elemei, akkor A összes maradék elemét át kell másolnunk C-be. Hasonló a helyzet akkor is, ha A elemei „fogynak el” hamarabb.

38. kép

Összefuttatás

73

AZ ALGORITMIZÁLÁS ALAPJAI eljárás összefuttatás K = 0 I = 0 J = 0 ciklus, amíg (I ≤ N – 1) és (J ≤ M – 1) ha A[I] < B[J], akkor C[K] = A[I] I = I +1 különben ha A[I] > B[J], akkor C[K] = B[J] J = J + 1 különben C[K] = A[I] I = I + 1 J = J + 1 elágazás vége K = K + 1 ciklus vége ciklus, amíg I ≤ N – 1 C[K] = A[I] I = I + 1 K = K + 1 ciklus vége ciklus, amíg J ≤ M – 1 C[K] = B[J] I = I + 1 K = K + 1 ciklus vége eljárás vége

6.4 ÖSSZEFOGLALÁS Ez a lecke két olyan algoritmust tárgyalt, melyeket gyakran használunk pl. adatbáziskezelő rendszerekben. Az adatbázis-kezelő rendszerekben használt műveletek között az egyik leggyakoribb az ún. lekérdezés, amelynek során az adatbázisban tárolt egyedekre, azok egyes mezőire megfogalmazott feltételeket használjuk a keresett rekordok eléréséhez. A kiválogatás úgy is értelmezhető, mint egy egytáblás lekérdezés, amelyben a feltétel egyetlen mezőre vonatkozik. A lekérdezések ennél természetesen sokkal bonyolultabbak is lehetnek, célunk az elemi algoritmus bemutatása volt. Az összefuttatáshoz hasonló tétel a halmazelméletben ismert egyesítés (unió) műveletét végrehajtó algoritmus. Az összefuttatás azonban annyiban hatékonyabb, hogy nem igényel keresést, mivel a két eredeti vektor elemeit párhuzamosan dolgozza fel, ugyanis ezek rendezettek.

74


6.5 ÖNELLENŐRZŐ KÉRDÉSEK Milyen kapcsolat van a kiválogatás tétele és az adatbázis-kezelő rendszerekben végezhető lekérdezések között? 2. Milyen feltételek mellett hajtható végre két adatsoron az összefuttatás tétele? 3. Milyen összefüggés van az adatsor elemszáma és az eredményhalmaz elemszáma között kiválogatás esetén? 4. Miért nem hatékony adatszerkezet a tömb egy kiválogatás eredményhalmazának tárolásához? 1.

75


7. ADATSORHOZ ADATSORT RENDELŐ ELJÁRÁSOK 2. – RENDEZŐ ELJÁRÁSOK

7.1 CÉLKITŰZÉS A korábbi leckékben ismertetett eljárások között többnél szerepelt az az előfeltétel, hogy az adatsornak rendezettnek kell lennie. Ebben a leckében rendezőeljárásokkal fogunk ismerkedni. Az alábbiakban bemutatott eljárások mindegyike a bemenetként kapott tömbben rendez, tehát nem új adatsort állít elő, hanem az input adatsor elemeinek sorrendjét megváltoztatva állítja elő az output adatsort. Ezek a rendező eljárások tehát ún. belső rendezések. A rendezések során az A adatsornak egy olyan permutációját állítjuk elő, melyben igaz, hogy ai ≤ ai+1 (növekvő sorrend) vagy ai ≥ ai+1 (csökkenő sorrend), ahol ai A, i = 0 .. (n – 1). Számos rendező eljárás ismeretes, ezek közül ebben a jegyzetben csak néhány nagyon közismert módszert mutatunk be, és azokat is csak vektorokon. Az algoritmizálás, algoritmuskészítés alapvetőnek tartott egyik szakirodalmában, Donald Ervin Knuth (1938–) A számítógép-programozás művészete című könyvsorozatának 1978-ban megjelent 3. kötetében a szerző kb. 25 eljárást mutat be, jelezve, hogy ennél (már akkor) lényegesen több eljárást publikáltak.

39. kép

7.2 TARTALOM − − − − − − − − 76

két elem cseréje egy vektorban rendezés közvetlen kiválasztással buborékrendezés rendezés szélsőérték-kiválasztással beszúró rendezés Shell módszere gyorsrendezés rendezőeljárások hatékonysága

Donald Ervin Knuth



Két elem cseréje egy vektorban

A rendezések során az A adatsor (vektor) egy olyan permutációját állítjuk elő, melyben igaz, hogy ai ≤ ai+1 (növekvő sorrend) vagy ai ≥ ai+1 (csökkenő sorrend), ahol ai A, i = 0 .. (n – 1). Ahhoz, hogy az elemek sorrendjét megváltoztathassuk, a rendező eljárásokban az I és J indexű tömbelem cseréjéhez az alábbi értékadásokat fogjuk használni: S = A[I] A[I] = A[J] A[J] = S Megjegyzés: ha a tömbelemek numerikus adatok, akkor a csere történhet segédváltozó nélkül is: A[I] = A[I] + A[J] A[J] = A[I] – A[J] A[I] = A[I] – A[J] 7.3.2

Rendezés közvetlen kiválasztással

Az eljárás nem hoz létre új adatszerkezetet, hanem a bemenő struktúra elemeit rendezi, ez a példánkban a megszokott módon egy vektor. Az algoritmus két egymásba ágyazott ciklust használ. A külső ciklus változója (I) azt mutatja meg, hogy a tömb hányadik elemétől kezdődik a még rendezetlen tömbrész. Az eljárás kezdetén ez az első elem (I = 0). A belső ciklus J = (I + 1)-től a hátralévő elemeket hasonlítja hozzá, és ha kisebbet (nagyobbat) talál, rögtön felcseréli őket. Ha az utolsó elemmel is összehasonlította a még rendezetlen tömbrész első elemét, akkor ez az elem biztosan a helyére került. Ekkor az I = (I + 1) indexű elemhez hasonlítjuk az őt követő elemeket, egészen az I = (I –2) indexű elemig, amelyet az (I – 1) indexű elemhez hasonlítva a vektor rendezett lesz. Egyszerű rendezési eljárásról van szó, mégsem használjuk, mert nagyon nagy lehet a felesleges cserék száma, és ez a futási idő növekedését eredményezi.

77


40. kép

Rendezés közvetlen kiválasztással

eljárás rendezésKözvetlenKiválasztással ciklus I = 0-tól (N – 2)-ig ciklus J = (I + 1)-től (N – 1)-ig ha A[J] < A[I], akkor S = A[I] A[I] = A[J] A[J] = S elágazás vége ciklus vége ciklus vége eljárás vége 7.3.3

A buborékrendezés

Ebben a rendező eljárásban szomszédos elemeket hasonlítunk egymáshoz. Ha a J és (J + 1) indexű elemek sorrendje nem jó (pl. növekvő sorrendet szeretnénk elérni, de A[J] > A[J + 1]), akkor felcseréljük őket. Ha J = 0-tól (N – 2)-ig az összes {J, (J + 1)} elempárt összehasonlítottuk és szükség esetén felcseréltük, akkor a tömb (N – 1) indexű (utolsó) eleme a helyre került. Ekkor újrakezdjük a vizsgálatokat J = 0-tól (N – 3)-ig stb.

78


41. kép

Buborékrendezés

eljárás buborékrendezés ciklus I = (N – 1)-től 1-ig –1 lépésközzel ciklus J = 0-tól (I – 1)-ig ha A[J] > A[J + 1], akkor S = A[J] A[J] = A[J + 1] A[J + 1] = S elágazás vége ciklus vége ciklus vége eljárás vége Abban az esetben, ha a tömb „nagyon rendezetlen” (pl. egy növekvő sorrendben lévő elemeket tartalmazó tömböt szeretnénk csökkenő sorrend szerint rendezni) a cserék száma itt is jelentős, tehát ez az eljárás sem tekinthető hatékonynak. 7.3.4

Rendezés szélsőérték-kiválasztással

A cserék számát tekintve az előző rendező eljárásoknál jóval hatékonyabb rendezés lehet a szélsőérték-kiválasztásos rendezés. A szélsőértéket – mely lehet maximum és minimum – mindig a még rendezetlen tömbrészben keressük meg, majd felcseréljük a (még rendezetlen) tömbrész első vagy utolsó elemével, attól függően, hogy növekvő vagy csökkenő sorba szeretnénk-e rendezni az adatokat, illetve minimumot vagy maximumot keresünk.

79


42. kép

Rendezés szélsőérték-kiválasztással (minimumkiválasztással)

A tétel alkalmazása során egy N elemű tömbben maximum (N – 1) csere történik, mivel az utolsó elempár cseréjekor két elem kerül a végleges helyére. A rendezés itt is két egymásba ágyazott ciklussal történik. A külső ciklus változója (I) azt mutatja meg, hogy a tömb hányadik elemtől kezdve rendezetlen még, a belső ciklus pedig az (I + 1) indexű tömbelemtől az (N – 1) indexűig (az utolsóig) megvizsgálja, hogy a még rendezetlen tömbrészben van-e kisebb (nagyobb) elem, mint a még rendezetlen tömbrész első eleme. Ha van, akkor annak indexét megjegyezve a következő elemet, mint lehetséges szélsőértékhez már ahhoz hasonlítja. Az (N – 1) indexű elem vizsgálata után a még rendezetlen tömbrész szélsőérték-elemét felcseréli a még rendezetlen tömbrész első elemével – ha szükséges. Akkor nem szükséges a csere, ha a még rendezetlen tömbrész első eleme a tömbrész szélsőértéke, vagyis ez az elem eredetileg is a megfelelő helyen volt. Az alábbi algoritmus a minimumkiválasztásos rendezést mutatja be. Ebben a példában az A tömb elemeit növekvő sorba rendezzük. eljárás rendezésMinimumkiválasztással ciklus I = 0-tól (N – 2)-ig MINHELY = I ciklus J = (I + 1)-től (N – 1)-ig ha A[J] < A[MINHELY], akkor 80

AZ ALGORITMIZÁLÁS ALAPJAI MINHELY = J elágazás vége ciklus vége ha MINHELY ≠ I, akkor S = A[I] A[I] = A[MINHELY] A[MINHELY] = S elágazás vége ciklus vége eljárás vége 7.3.5

A beszúró rendezés

Az eljárás megértéséhez képzeljük el, hogy a kezünkben lévő (rendezetlen sorrendű) kártyalapokat szeretnénk sorba rendezni (vagy a kapott csomagot az asztalról laponként felvéve kialakítani a rendezett sorozatot). A soron következő kártyalapot kézbe véve megkeressük a helyét a már rendezett lapok között, és a beszúrás helye utáni lapokat egy helylyel jobbra mozgatjuk, amíg a rendezetlen rész utolsó eleme is a helyére nem kerül a rendezett lapok között.

43. kép

Beszúró rendezés 81

AZ ALGORITMIZÁLÁS ALAPJAI eljárás beszúróRendezés ciklus I = 1-től (N – 1)-ig J = I – 1 X = A[I] ciklus, amíg (J ≥ 0) és (X < A[J]) A[J + 1] = A[J] J = J – 1 ciklus vége A[J + 1] = X eljárás vége 7.3.6

Shell módszere

Donald L. Shell (1924–) 1959-ben publikált módszere nem önálló rendezési algoritmus, de bármilyen más algoritmus hatékonysága javítható vele. A beszúró rendezés vizsgálatakor látható, hogy az eljárás futási ideje N2-tel arányos. Az eljárás (más algoritmusokhoz hasonlóan) egyszerre csak egy hellyel mozgatja el az elemeket. Az átlagos hatékonyságon növelni tudunk, ha megengedjük, hogy az elemek nagyobb ugrásokat is megtegyenek egy lépésben.

44. kép

Donald L. Shell

A Shell-módszer alapgondolata az, hogy definiálunk egy sorozatot, amely azt mutatja meg, hogy a rendezés egyes „futamaiban” az egymástól hány lépésre lévő elemeket rendezzük. Knuth a Számítógép-programozás művészete című könyvében ezt a módszert fogyó növekményes módszernek nevezte el, és bebizonyítja, hogy ennek a sorozatnak az elemei bármilyen (egészekből álló) számsorozatot alkothatnak, de a sorozat elemeinek egyre kisebbeknek kell lenniük és az utolsó elemnek 1-nek kell lennie, vagyis a rendezés utolsó „futamában” a teljes sorozat egymás melletti elemein végezzük a rendezést. Knuth azt is megmutatja, hogy vannak jobb és rosszabb hatékonyságú sorozatok. Ezen bizonyítások bemutatása nem tárgya jegyzetünknek. A cserék számának átlagát azért csökkenti (akár jelentősen) a Shell-féle módszer, mert mire az egymástól nagyobb távolságra lévő elemeken végzett „futamokat” végrehajtottuk, a vektor (vagy más adatsor) elemeinek sorrendje közelebb fog állni a rendezett sorrendhez, mint eredetileg. A Shell-módszer futamai tehát nagyjából rendezik az elemeket, minden futam jobban, mint az előző. Ezzel nagyon sok felesleges csere is elkerülhető. 82


45. kép

A Shell-féle módszer

Az alábbiakban a beszúró rendezés Shell-féle módszerrel javított változatát mutatjuk be. A példában a „futamok” fogyó növekménye a D = (

N 3

1,

N 9

1, ,1 ) sorozat lesz.

eljárás beszúróRendezésShellMódszerével D = N ciklus D = D / 3 + 1 ciklus E = 0-tól (D – 1)-ig J = E + D ciklus, amíg J ≤ N I = J – D X = A[J] ciklus, amíg (I ≥ 0) és (X < A[I] A[I + D] = A[I] I = I – D ciklus vége A[I + D] = X J = J + D ciklus vége ciklus vége amíg D > 1 eljárás vége 7.3.7

A gyorsrendezés

Az eljárás Sir Charles Antony Richard Hoare (1934–) nevéhez fűződik, és valóban gyors, mert a belső ciklusok általában nagyon gyorsan lefutnak. Egy nagy elemszámú adatsor esetében a gyorsrendezés akár nagyságrenddel gyorsabb lefutást eredményez más, kevésbé hatékony rendezőeljárással összehasonlítva.

83


46. kép

Sir Charles Antony Richard Hoare

Az eljárás alapgondolata az, hogy egy adatsor valamely elemét mozgassuk arra a helyre, amely helyet a rendezett adatsorban foglalna el. Közben rendezzük át az adatsor többi elemét is úgy, hogy a nála kisebb indexű elemek értékei ne legyenek nála nagyobbak, a nála nagyobb indexű elemek értékei pedig ne legyenek tőle kisebbek. Ezután osszuk két részre az adatsort ezen elem mentén, és ismételjük meg ezt az eljárást a két részadatsorra is. Az így „szétválogatott” két részt két-két további részre osztja egy-egy újabb „középelem”, így azokra a részadatsorokra is hajtsuk végre ezt az eljárást, és így tovább, egészen addig, amíg a teljes rendezettség be nem következik. Ebből a leírásból látható, hogy ez a módszer a megoldandó problémát kisebb és kisebb részekre bontja, majd a megoldást ezeken az egyre kisebb részeken hajtja végre úgy, mintha a kiinduló feladat ezekre a kisebb problémákra vonatkozott volna. Más szavakkal az eljárás önmagát hívja a megoldás során. Ezt a módszert nevezzük rekurziónak. A rekurzióval gyakran találkozunk a matematika különböző területein. A kombinatorikából ismert az ún. faktoriális függvény, n! 1 2 3  (n 1) n Kiszámításához használható az alábbi rekurzív definíció is:

n!:

1, n

0 esetén

n (n 1)!, egyébként

függvény faktoriális(N) ha N = 0, akkor faktoriális = 1 különben faktoriális = N * faktoriális(N – 1) függvény vége A rekurzióról a 10. fejezetben bővebben olvashatunk.

84

AZ ALGORITMIZÁLÁS ALAPJAI Térjünk vissza most a gyorsrendezéshez, melynek algoritmusát rekurzív módon fogjuk megadni. A fent leírottakból következik, hogy az lenne jó, ha meg tudnánk mondani, hogy a szétválogatandó elemsorozatnak melyik az az eleme, amelyet „középre” kellene mozgatnunk, mert ez az elem két azonos méretű részsorozatra bontaná a rendezendő sorozatot. Mivel ennek az elemnek a megkeresése csak egy másik eljárással lenne megoldható, és ez felesleges időveszteséget okozna, nem keressük az optimális elemet, hanem önkényesen választunk egyet. Lehet, hogy így az egyik részsorozat kevesebb elemet fog tartalmazni, mint a másik, de az algoritmus ettől függetlenül helyesen fog működni, legrosszabb esetben lassabban.

47. kép

Robert Sedgewick

A legjobb megoldás Robert Sedgewick (1946–) módszere. Ez két mutatót használ: I = 1-et és J = (N – 1)-et. Feltételezve, hogy a szétválogatás után A[I] a bal részsorozathoz fog tartozni, növeljük meg I-t addig, amíg egy olyan A[I] elemhez érünk, amely a jobboldali részsorozat eleme lesz majd. A J értékét pedig csökkentsük addig, amíg egy a bal oldali részsorozathoz tartozó A[J]értéket nem találunk. Ha I < J, akkor A[I]-t és A[J]-t felcseréljük, majd folytatjuk a feldolgozást, amíg I ≥ J nem teljesül. Az utolsó csere A[J] és A[0] cseréje.

85


48. kép

Gyorsrendezés

eljárás gyorsrendezés(A, ALSÓ, FELSŐ) I = ALSÓ J = FELSŐ X = A[(ALSÓ + FELSŐ) / 2] ciklus ciklus, amíg A[I] < X I = I + 1 ciklus vége ciklus, amíg A[J] > X J = J – 1 ciklus vége ha I < J, akkor S = A[I] 86

AZ ALGORITMIZÁLÁS ALAPJAI A[I] = A[J] A[J] = S elágazás vége ha I ≤ J, akkor I = I + 1 J = J – 1 elágazás vége amíg I ≤ J ha ALSÓ < J, akkor gyorsrendezés(A, ALSÓ, J) elágazás vége ha I < FELSŐ, akkor gyorsrendezés(A, I, FELSŐ) elágazás vége eljárás vége 7.4

ÖSSZEFOGLALÁS

Ebben a leckében olyan eljárásokkal foglalkoztunk, amelyek rendezetlen adatsorokat rendezettekké tesznek. Szeretnénk hangsúlyozni, hogy a fenti eljárások csak kiragadott példák, a programozás irodalmában ennél lényegesen több algoritmust publikáltak már. A közölt eljárások mind tömböket használnak, de természetesen más adatszerkezetek elemei is rendezhetők. Nem biztos, hogy a fent közölt eljárások a legegyszerűbbek, de biztos, hogy nem a leghatékonyabbak. A hatékonyság kérdése mindig többrétű: egy eljárás hatékonyságát vizsgálhatjuk gyorsaság, bonyolultság és tárfoglalás tekintetében is. Biztos, hogy a fent közölt eljárások az egyszerűbbek közé tartoznak, de nem biztos, hogy a legkézenfekvőbb módszereket mutatják be. Akinek van rá lehetősége, végezze el az alábbi kísérletet: kérjük meg néhány ismerősünket, hogy rakjanak sorba egy csomag számkártyát az asztalon. Hogy a különböző személyek módszerét össze tudjuk hasonlítani, igyekezzünk hasonló körülményeket teremteni: pl. a kártyák sorrendje legyen „álvéletlen”, vagyis legyenek összekeverve, de mindig azonos sorrendben kövessék egymást a lapok. Kísérletezzünk sok (pl. 25-nél több) és kevés (5-6) kártyával is! Figyeljük meg, van-e különbség az alkalmazott módszerek között! Figyeljük meg a módszereket és próbáljuk őket algoritmizálni!

7.5 ÖNELLENŐRZŐ KÉRDÉSEK Hogyan mérhetjük meg egy rendezés hatékonyságát? (Természetesen az a szempont nem jöhet szóba, hogy helyes sorrendet állítanak-e elő, hiszen ez minimális követelmény.) 2. A fent közölt eljárások közül melyik az, amelyik a legközelebb áll hétköznapi módszerekhez? Miért? 3. A rendezés tételei nemcsak numerikus adatokon használhatók, mert pl. hasonló elven történik a betűrendbe sorolás is. Gondoljuk át, hogy hogyan tudnánk magyar szavakat betűrendbe sorolni! Gondolkodjunk el a konkrét gépi megva1.

87

AZ ALGORITMIZÁLÁS ALAPJAI lósítások okozta nehézségeken is (pl. az ASCII, ISO-8859-2 és UNICODE kódrendszerek egyikében sem a magyar betűrendnek megfelelő sorrendben követik egymást a betűk). 4. A fenti példák egy-egy adatsor rendezését mutatták be. Táblázatkezelőkben, adatbázis-kezelő rendszerekben természetes, hogy több tulajdonság alapján is rendezhetünk. Gondolkodjunk el azon, hogyan algoritmizálnánk azt a feladatot, ha adott egy neveket, egy életkorokat és egy lakóhelyeket tartalmazó vektor, és szeretnénk bennük az elemeket úgy átrendezni, hogy az adatok sorrendje lakóhely szerint legyen rendezve, az azonos lakóhelyen lakók között döntsön az életkor. Két azonos lakóhelyű és életkorú személy sorrendjében döntsön a név!

88


8. PÉLDÁK AZ ELJÁRÁSOK ALKALMAZÁSÁRA 8.1

CÉLKITŰZÉS

Ez a lecke az előző négy leckében bemutatott elemi vektorkezelő eljárásokra épülő példákat mutat be. 8.2

TARTALOM Példák a tételek alkalmazására

8.2.1

8.2.1.1 Hegymászó Egy hegymászó 20 kilométeres túrát tett, és kilométerenként megmérte az tengerszint feletti magasságot. Az alábbi értékeket rögzítette az ADATOK vektorban:

49. kép

A hegymászó rögzítette adatok

ADATOK[ ] 650 0

628 1

658 2

683 3

683 4

683 5

644 6

611 7

645 8

619 9

619 10

580 11

580 12

626 13

626 14

626 15

598 16

636 17

612 18

584 19

1. Hányadik mérésnél járt a legmagasabban? eljárás hegymászó1 MAXHELY = 0 ciklus I = 1-től 19-ig ha ADATOK[I] > ADATOK[MAXHELY], akkor MAXHELY = I elágazás vége ciklus vége ki: MAXHELY eljárás vége

89

AZ ALGORITMIZÁLÁS ALAPJAI 2. Hányadik mérésnél járt a legalacsonyabban? eljárás hegymászó2 MINHELY = 0 ciklus I = 1-től 19-ig ha ADATOK[I] < ADATOK[MINHELY], akkor MINHELY = I elágazás vége ciklus vége ki: MINHELY eljárás vége 3. Mennyi volt a mérések átlaga? eljárás hegymászó3 SUM = ADATOK[0] ciklus I = 1-től 19-ig SUM = SUM + ADATOK[I] ciklus vége ki: SUM / 20 eljárás vége 4. Járt-e 1000 méter fölötti magasságban? eljárás hegymászó4 I = 0 ciklus, amíg (I <= 19) és (ADATOK[I] <= 1000) I = I + 1 ciklus vége ha (I <= 19) akkor ki: "Igen, járt 1000 méter fölött" különben ki: "Nem, nem járt 1000 méter fölött" elágazás vége eljárás vége

5.

90

AZ ALGORITMIZÁLÁS ALAPJAI Hány alkalommal mért 600 és 650 méter közötti magasságot? eljárás hegymászó5 DB = 0 ciklus I = 0-tól 19-ig ha (ADATOK[I] >= 600) és (ADATOK[I] <= 650), akkor DB = DB + 1 elágazás vége ciklus vége ki: DB eljárás vége 6. Mennyi volt az áltagos magasság a legalacsonyabb és a legmagasabb pont között? A feladat két elemi algoritmussal megoldható: 1. meg kell keresnünk a legalacsonyabb és a legmagasabb mérés helyét (szélsőérték-kiválasztás), 2. a két mérés között kell kiszámítanunk a mérések átlagát (összegzés). Feltételezzük, hogy van szintkülönbség a legalacsonyabb és a legmagasabb pont között (nem a Hortobágyon sétált a hegymászó): eljárás hegymászó6 MINHELY = 0 MAXHELY = 0 ciklus I = 1-től 19-ig ha ADATOK[I] > ADATOK[MAXHELY], akkor MAXHELY = I elágazás vége ha ADATOK[I] < ADATOK[MINHELY], akkor MINHELY = I elágazás vége ciklus vége ha MINHELY < MAXHELY, akkor ELEJE = MINHELY VÉGE = MAXHELY különben ELEJE = MAXHELY VÉGE = MINHELY elágazás vége SUM = 0 ciklus I = ELEJE-től VÉGE-ig SUM = SUM + ADATOK[I] ciklus vége ki: SUM / (VÉGE – ELEJE + 1) eljárás vége

91

AZ ALGORITMIZÁLÁS ALAPJAI 7. Melyik két mérés között volt a legmeredekebb lejtő? A megoldás tulajdonképpen egy maximumkiválasztás. Sorra meg kell állapítanunk az 1–2., 2–3., 3–4. stb. mérések különbségét, ahol ez az érték a legnagyobb, ott volt a legmeredekebb lejtő. Gondot okozhat a MAX kezdőértékének meghatározása: azért állítjuk –1re, mert a –1-es érték azt jelenti, hogy a két mérés között emelkedő volt, azaz bármilyen csekély lejtő is van a mérések között, annak mértéke biztosan nagyobb, mint –1. eljárás hegymászó7 MAX = -1 MAXHELY = –1 // a –1 egy nem létező helyen mért "lejtő" ciklus I = 0-tól 18-ig ha ADATOK[I] – ADATOK[I + 1] > MAX, akkor MAX = ADATOK[I] – ADATOK[I + 1] MAXHELY = I elágazás vége ciklus vége ki: "A legnagyobb lejtő: a(z) ", I, I + 1, "pont között." eljárás vége 8. És a legmeredekebb emelkedő? A megoldás megegyezik az előző feladatéval, az eltérés annyi, hogy most egy minimumkiválasztást érdemes alkalmaznunk. A MIN kezdőértéke az előző feladatban leírtak szerint célszerűen 1 lehet, hiszen az 1-es érték lejtőnek felel meg, ennél minden emelkedő meredekebb (vagyis a különbség minden emelkedő esetén negatív szám lesz).ű eljárás hegymászó8 MIN = 1 MINHELY = –1 ciklus I = 0-tól 18-ig ha ADATOK[I] – ADATOK[I + 1] < MIN, akkor MIN = ADATOK[I] – ADATOK[I + 1] MINHELY = I elágazás vége ciklus vége ki: "A legnagyobb emelkedő: a(z) ", I, I + 1, "pont között." eljárás vége

92

AZ ALGORITMIZÁLÁS ALAPJAI 9. Járt-e fennsíkon a hegymászó? (A fennsíkot definiáljuk így: 600 m fölött két egymást követő mérés között 5 m-nél kisebb az eltérés.) A megoldás egy egyszerű eldöntés: van-e két olyan, egymást követő pont, melyek mindegyike 600 m fölötti és különbségük kisebb, mint 5 m? eljárás hegymászó9 I = 0 ciklus, amíg (I <= 18) és (abs(ADATOK[I] – ADATOK[I+1]) >= 5 vagy ADATOK[I] < 600 vagy ADATOK[I+1] < 600) I = I + 1 ciklus vége ha I <= 19 akkor ki: "Igen, van fennsík." különben ki: "Nem, nincs fennsík." eljárás vége Az abs(x) kifejezés x abszolútértékét jelöli abs(X) = |X| 10. Mennyi volt a teljes megtett szintkülönbség? Ez egy összegzéssel megadható, mindössze arra kell figyelnünk, hogy minden szintkülönbség előjelét pozitívnak tekintsük! eljárás hegymászó10 SUM = 0 ciklus I = 0-tól 18-ig DIFF = ADATOK[I] – ADATOK[I + 1] ha DIFF < 0, akkor DIFF = DIFF * (–1) // vagy DIFF = ABS(DIFF) elágazás vége SUM = SUM + DIFF ciklus vége ki: SUM eljárás vége

93

AZ ALGORITMIZÁLÁS ALAPJAI 11. Hol van a második legmagasabb pont? Egy megoldási lehetőség, hogy először megkeressük a legmagasabb pontot, majd újrakezdjük a keresést, és úgy keressük a legmagasabb pontot, hogy közben kizárjuk az egyenlőséget az előbb megkeresett, valóban legmagasabb ponttal. eljárás hegymászó11 MAXHELY = 0 ciklus I = 1-től 19-ig ha ADATOK[I] > ADATOK[MAXHELY], akkor MAXHELY = I elágazás vége ciklus vége ha MAXHELY = 0, akkor // ha véletlenül épp az első pont a legmagasabb MAXHELY2 = 1 különben MAXHELY2 = 0 elágazás vége ciklus I = (MAXHELY2 + 1)-től 19-ig ha (ADATOK[I] > ADATOK[MAXHELY2]) és (I ≠ MAXHELY), akkor MAXHELY2 = I elágazás vége c .v ki: MAXHELY2 eljárás vége

94

AZ ALGORITMIZÁLÁS ALAPJAI 12. Mennyi idő alatt tette meg a teljes távot az elsőtől az utolsó mérésig? Tegyük fel, hogy hegymászónk nem fáradékony, így a túra végén ugyanolyan sebességgel haladt, mint az elején: hegymenetben 3 km/h, lejtmenetben 6 km/h, vízszintes terepen pedig 5 km/h sebességgel. eljárás hegymászó12 S1 = 20 // 20 perc alatt egy kilométer hegymenetben S2 = 10 // 10 perc alatt egy kilométer lejtmenetben S3 = 12 // 12 perc alatt egy kilométer sík területen SUM = 0 ciklus I = 0-től 18-ig DIFF = ADATOK[I] – ADATOK[I + 1] ha DIFF > 0, akkor SUM = SUM + S1 különben ha DIFF < 0, akkor SUM = SUM + S2 különben SUM = SUM + S3 elágazás vége ciklus vége Ki: SUM // óra:perc-ben megadva: Ki: SUM div 60, SUM mod 60 // ahol a div az egészosztás, // a mod pedig az osztás maradékát kiszámító operátor // (pl. 15 div 4 = 3, 19 mod 6 = 1). eljárás vége 13. Hány fennsíkon járt a hegymászó? Válasz: négyen. Fennsík van a 2–3, az 5–6, a 10–11 és a 14–16 mérések között. A 12– 13 pontok között nem, mert az 600 m alatt van! 14. Adjuk meg valamelyik mérés sorszámát, majd keressük meg azokat a mérési pontokat, amelyek erről a pontról láthatók! Pl. a 4-es pontról látható pontok az 1–3, illetve az 5. pont, a többi nem, mert az 5–6 pont „hegycsúcsa” eltakarja őket. Az utolsó két feladat megoldását az Olvasóra bízzuk!

95


4.3.8.2 Híres emberek Ismerjük 30 híres ember fenti adatait15. Az adatokat nem egy, hanem 6 tömbben tároljuk, mind a hat tömb egydimenziós. Az összetartozó adatokat a tömbök indexei kötik öszsze: pl. a 15-ös indexű híres ember minden adatának indexe 15. (NÉV[15] = "Talmácsi Gábor", SZÜLETETT[15] = 1981 stb., lásd a kiemelt sort.) A MEGHALT tömb értéke a ma (2010. június) élő személyek esetében 0. A GOOGLE tömbben található értékek az adott személy nevére keresve a Google által adott találatok körülbelüli számát jelenti. NÉV

SZÜLETETT

MEGHALT

FOGLALKOZÁS

NEMZETISÉG

GOOGLE

Alain Delon

1935

0

színész

francia

1 580 000

Marcus Grönholm

1968

0

sportoló

finn

232 000

David Beckham

1975

0

sportoló

angol

20 100 000

Vlagyimir Kramnyik

1975

0

sportoló

orosz

22 800

Luc Besson

1959

0

filmrendező

francia

2 570 000

Juliette Binoche

1964

0

színész

francia

1 860 000

Woody Allen

1935

0

színész

amerikai

6 330 000

Laurence Olivier

1907

1989

színész

angol

1 030 000

Julia Roberts

1967

0

színész

amerikai

5 660 000

Sándor Pál

1939

0

filmrendező

magyar

26 000

Esterházy Péter

1950

0

író

magyar

180 000

Papp László

1926

2003

sportoló

magyar

296 000

Eric Clapton

1945

0

zenész

amerikai

8 770 000

Ernest Hemingway

1899

1961

író

angol

2 600 000

Mika Waltari

1908

1979

író

finn

149 000

Talmácsi Gábor

1981

0

sportoló

magyar

99 900

Louis Armstrong

1901

1971

zenséz

amerikai

4 200 000

Mark Knopfler

1949

0

zenész

amerikai

2 300 000

Jean-Paul Belmondo

1933

0

színész

francia

477 000

Agatha Christie

1890

1976

író

angol

4 470 000

Steven Spielberg

1946

0

filmrendező

amerikai

4 840 000

Paavo Nurmi

1897

1973

sportoló

finn

99 600

Walt Disney

1901

1966

filmrendező

amerikai

28 000 000

Colin Firth

1960

0

színész

angol

2 070 000

Bátorfi Csilla

1969

0

sportoló

magyar

9 560

Dés László

1954

0

zenész

magyar

38 600

Borisz Paszternak

1890

1960

író

orosz

46 000

Gárdonyi Géza

1863

1922

író

magyar

221 000

Kimi Räikkönen

1979

0

sportoló

finn

2 450 000

Robert Merle

1908

2004

író

francia

75 100

15

Az adatok 2010 júniusában voltak érvényesek.

96

AZ ALGORITMIZÁLÁS ALAPJAI 1. Ki a legidősebb ma élő író? Maximumkiválasztás. Azonban – mivel nem mindenki író a fentiek közül – nem hasonlíthatjuk az adatokat az első személy adataihoz. eljárás híres1 MAX = 0 MAXHELY = –1 ciklus I = 0-től 29-ig ha (FOGLALKOZÁS[I] = "író") és (2010 – SZÜLETETT[I] > MAX), akkor MAX = 2010 – SZÜLETETT[I] MAXHELY = I elágazás vége ciklus vége ki: NÉV[MAXHELY] eljárás vége 2010 helyett természetesen az aktuális évszámot kell behelyettesíteni. 2. Átlagosan hány találatot kapunk a Google-ban a fenti amerikaiak nevére keresve? Összegzés. Ügyeljünk az extrém esetekre is: mi van, ha nincs is köztük amerikai...? Eljárás híres2 ÖSSZEG = 0 DB = 0 ciklus I = 0-tól 29-ig ha NEMZETISÉG[I] = "amerikai", akkor ÖSSZEG = ÖSSZEG + GOOGLE[I] DB = DB + 1 elágazás vége ciklus vége ha DB > 0, akkor ki: ÖSSZEG / DB különben ki: "Nincs közöttük amerikai." elágazás vége eljárás vége

97

AZ ALGORITMIZÁLÁS ALAPJAI 3. Ki az az orosz író, aki 1960-ban halt meg? (Tudjuk, hogy pontosan egy ilyen van.) A feladat kiírása sejteti, hogy ez egy kiválasztás. Kiválasztásnál a ciklus feltétele a következő elemre való lépés feltétele: ha az aktuális elem nem az, amelyet kerestünk, léphetünk a következőre. Ebben a feladatban a továbblépés feltétele összetett: P: orosz Q: író R: 1960-ban halt meg P Q R = orosz író, aki 1960-ban halt meg (P Q R) = P Q R: nem orosz, vagy nem író, vagy nem 1960-ban halt meg eljárás híres3 I = 0 ciklus, amíg (NEMZETISÉG[I] ≠ "orosz") vagy (FOGLALKOZÁS[I] ≠ "író") vagy (MEGHALT[I] ≠ 1960) I = I + 1 ciklus vége ki: NÉV[I] eljárás vége 4. Mennyi az amerikaiak átlagéletkora? (Csak a ma élőket kell figyelembe venni.) Feltételes összegzés és megszámlálás. Csak arra kell külön figyelnünk, hogy van-e egyáltalán még ma élő amerikai közöttük, nehogy 0-val osszunk. eljárás híres4 DB = 0 ÖSSZEG = 0 ciklus I = 0-tól 29-ig ha (NEMZETISÉG[I] = "amerikai") és (MEGHALT[I] = 0), akkor ÖSSZEG = ÖSSZEG + (2010 – SZÜLETETT[I]) DB = DB + 1 elágazás vége ciklus vége ha DB > 0, akkor ki: ÖSSZEG / DB különben ki: "Nincs közöttük ma élő amerikai." elágazás vége eljárás vége A 2010 helyett természetesen az aktuális évszámot kell behelyettesíteni.

98

AZ ALGORITMIZÁLÁS ALAPJAI 5. Ki az a francia színész, aki 1963-ban született? (Lehet, hogy nincs is ilyen.) Keresés. Ha a Gipsz Jakab 1963-ban született francia színészt felvesszük 30-as indexszel a tömbök végére, akkor felírható a strázsás keresés, anélkül csak a teljes keresés jöhet szóba, mivel az adatok rendezetlenek. eljárás híres5a NÉV[30] = "Gipsz Jakab" NEMZETISÉG[30] = "francia" SZÜLETETT[30] = 1963 MEGHALT[30] = 0 FOGLALKOZÁS[30] = "színész" GOOGLE[30] = 0 I = 0 ciklus, amíg (NEMZETISÉG[I] ≠ "francia") vagy (SZÜLETETT[I] ≠ 1963) vagy (FOGLALKOZÁS[I] ≠ "színész") I = I + 1 ciklus vége ha I < 30, akkor ki: NÉV[I] különben ki: "Nincs ilyen színész." elágazás vége eljárás vége eljárás híres5b I = 0 ciklus, amíg (I <= 30) és ((NEMZETISÉG[I] ≠ "francia") vagy (SZÜLETETT[I] ≠ 1963) vagy (FOGLALKOZÁS[I] ≠ "színész")) I = I + 1 ciklus vége ha I <= 29, akkor ki: NÉV[I] küllönben ki: "Nincs ilyen személy." elágazás vége eljárás vége

99

AZ ALGORITMIZÁLÁS ALAPJAI 6. Mi a nemzetisége annak az írónak, aki legutolsóként halt meg a fenti írók között? Az halt meg utoljára, akinek a MEGHALT tömbben található értéke a legnagyobb. Mivel azonban nem tudhatjuk, hogy az első személy író-e, az ő adataihoz nem hasonlíthatjuk a többieket. Más adatok esetén azt sem tudhatjuk biztosan, hogy egyáltalán van-e közöttük író. eljárás híres6 MAX = 0 MAXHELY = –1 ciklus I = 0-tól 29-ig ha (FOGLALKOZÁS[I] = "író") és (MEGHALT[I] > MAX), akkor MAX = MEGHALT[I] MAXHELY = I elágazás vége ciklus vége ha MAXHELY > –1, akkor ki: NEMZETISÉG[I] különben ki: "Nincs közöttük olyan író, aki már meghalt volna." elágazás vége eljárás vége 7. Van-e idősebb ma élő író, mint a már nem élő írók közül a legidősebb korában meghalt személy? (Tegyük fel, hogy ma élő és már meghalt írók is vannak a listában!) Ez egy eldöntés. Tudnunk kell hozzá, hány éves volt a legidősebb korában meghalt író. (Érdemes megfigyelni, hogy azt viszont nem szükséges tudnunk, hogy ő hányadik személy a listában.) Érdemes továbbá azt is megfigyelni, hogy a maximumkiválasztás feltételében nem kell külön szerepeltetni azt a feltételt, mely azt vizsgálná, hogy az illető él-e még, hiszen ha él, akkor a MEGHALT[I] – SZÜLETETT[I] kifejezés értéke egy –1900-nál kisebb szám lesz (pl. 0 – 1963 = –1963), ennyi évesen (–1963) pedig egészen biztosan nem lesz senki sem a legtovább élt, de már meghalt személy, tekintve, hogy a kiírás szerint vannak olyanok a listában, akik már valóban meghaltak. Az ő esetükben ez a különbség ugyanis pozitív szám lesz, ami biztosan nagyobb, mint mínusz ezerkilencszáz-valamennyi. eljárás híres7 MAX = 0 ciklus I = 0-tól 29-ig ha (FOGLALKOZÁS[I] = "író") és (MEGHALT[I] – SZÜLETETT[I] > MAX), akkor MAX = MEGHALT[I] – SZÜLETETT[I] MAXHELY = I elágazás vége 100

AZ ALGORITMIZÁLÁS ALAPJAI ciklus vége I = 0 ciklus, amíg (I < 30) és ((FOGLALKOZÁS ≠ "író") vagy (MEGHALT[I] > 0) vagy (2007 – SZÜLETETT[I] <= MAX)) I = I + 1 ciklus vége ha I <= 30, akkor ki: "Igen, van ilyen személy." különben ki: "Nem, nincs ilyen személy." elágazás vége eljárás vége 8. Mennyi a már nem élők átlagos találati száma? Összegzés és megszámlálás, figyelve arra, hátha nincs is olyan személy, aki már meghalt volna. (Ez nem szerepel a feladat kiírásában, de jobb az óvatosság.) eljárás híres8 ÖSSZEG = 0 DB = 0 ciklus I = 0-tól 29-ig ha MEGHALT[I] > 0, akkor ÖSSZEG = ÖSSZEG + GOOGLE[I] DB = DB + 1 elágazás vége ciklus vége ha DB > 1, akkor ki: ÖSSZEG / DB különben ki: "Nincs olyan személy, aki már meghalt volna." elágazás vége eljárás vége

101

AZ ALGORITMIZÁLÁS ALAPJAI 9. Mi a foglalkozása a legtöbb találattal rendelkező angolnak? (Tudjuk, hogy vannak angolok a listában.) Maximumkiválasztás. De nem mindenki angol. eljárás híres9 MAX = 0 MAXHELY = –1 ciklus I = 0-tól 29-ig ha (NEMZETISÉG[I] = "angol") és (GOOGLE[I] > MAX), akkor MAX = GOOGLE[I] MAXHELY = I elágazás vége ciklus vége ki: FOGLALKOZÁS[MAXHELY] eljárás vége 10. Találati gyakoriságuk szerint növekvő sorrendben írja ki egy listában16 a már nem élő személyek nevét! Azok nem élnek, akiknél a MEGHALT tömb értéke nem 0. Ki kell válogatnunk a nevüket és a találati gyakoriságukat egy-egy segédtömbbe, majd utóbbi szerint rendeznünk kell az adatokat. A feladat kiírása nem jelzi, de érdemes gondolnunk arra az esetre is, mi van, ha még mindenki él, vagy csak egyetlen személy van, aki már meghalt. Ez esetben nincs mit rendeznünk. eljárás híres10 DB = 0 ciklus I = 0-tól 29-ig ha MEGHALT[I] > 0, akkor DB = DB + 1 NÉV2[DB] = NÉV[I] GOOGLE2[DB] = GOOGLE[I] elágazás vége ciklus vége ha DB > 1, akkor ciklus I = 0-től (DB – 2)-ig MINHELY = I ciklus J = I + 1-től DB-ig ha GOOGLE[J] < GOOGLE[MINHELY], akkor MINHELY = J elágazás vége ciklus vége ha MINHELY ≠ I, akkor SNÉV = NÉV2[I] 16

A lista szó itt és a következő példákban a tágabb értelemben vett listát, és nem a lista adatszerkezetet jelenti.

102

AZ ALGORITMIZÁLÁS ALAPJAI NÉV2[I] = NÉV2[MINHELY] NÉV2[MINHELY] = SNÉV SG = GOOGLE2[I] GOOGLE2[I] = GOOGLE2[MINHELY] GOOGLE2[MINHELY] = SG elágazás vége ciklus vége elágazás vége ciklus I = 0-től (DB – 1)-ig ki: NÉV2[I], GOOGLE2[I] ciklus vége eljárás vége 11. Készítsen listát, melyben az látható, hogy nemzetiségenként hány személy található a fenti adatok között! (Tegyük fel, hogy nem tudjuk előre, milyen és hányféle nemzetiség található az adatok között, de biztosan nincs több, mint a személyek száma.) Ez egy eldöntés. Készítenünk kell egy olyan tömböt, mely a nemzetiségek listáját tartalmazza (NEMZETISÉGEK[]). Az első személy nemzetiségét automatikusan felvesszük ebbe az első helyre, majd a másodiktól a harmincadik személy nemzetiségéig mindenkiét megvizsgáljuk, szerepel-e már ebben a listában (itt az eldöntés). Ha nem, akkor felvesszük újként az utolsó helyre. Ezzel egy időben nyilvántartjuk azt is egy másik vektorban (EMBEREKSZÁMA[]), hogy eddig hányan voltak már ilyen nemzetiségűek. Ha olyan nemzetiségű személy adata van épp „a kezünkben”, amilyen már volt a listában, akkor ezt a számot eggyel megnöveljük. Az „új” nemzetiségek esetén ennek a számnak 1-es kezdőértéket adunk. eljárás híres11 NEMZETISÉGEK[0] = NEMZETISÉG[0] EMBEREKSZÁMA[0] = 1 DB = 1 ciklus I = 1-től 29-ig J = 1 ciklus, amíg (J <= DB) és (NEMZETISÉG[I] ≠ NEMZETISÉGEK[J]) J = J + 1 ciklus vége ha J <= DB, akkor EMBEREKSZÁMA[J] = EMBEREKSZÁMA[J] + 1 különben NEMZETISÉGEK[DB] = NEMZETISÉG[I] EMBEREKSZÁMA[DB] = I DB = DB + 1 elágazás vége 103

AZ ALGORITMIZÁLÁS ALAPJAI ciklus vége ciklus I = 0-tól (DB – 1)-ig ki: NEMZETISÉGEK[I], EMBEREKSZÁMA[I] ciklus vége eljárás vége 12. Melyik foglalkozás képviselőire adja átlagosan a legtöbb találatot a Google? Ehhez határozza meg, hogy foglalkozásonként mennyi a találatok átlaga! Készítenünk kell egy listát a foglalkozásokról, ehhez ld. az A csoport 4-es feladatának megoldását. A másik segédtömbben a foglalkozásokhoz tartozó Google-beli találatok számát összegezzük, majd ezen végrehajtunk egy maximum-kiválasztást. eljárás híres12 FOGLALKOZÁSOK[0] = FOGLALKOZÁS[0] ÖSSZTALÁLATOK[0] = GOOGLE[0] DB = 1 ciklus I = 1-től 29-ig J = 1 ciklus, amíg (J <= DB) és (FOGLALKOZÁSOK[J] ≠ FOGLALKOZÁS[I]) J = J + 1 ciklus vége ha J <= DB, akkor ÖSSZTALÁLATOK[J] = ÖSSZTALÁLATOK[J] + GOOGLE[I] különben FOGLALKOZÁSOK[DB] = FOGLALKOZÁS[I] ÖSSZTALÁLATOK[DB] = GOOGLE[I] DB = DB + 1 elágazás vége ciklus vége MAXHELY = 0 ciklus I = 1-től (DB – 1)-ig ha ÖSSZTALÁLATOK[I] > ÖSSZTALÁLATOK[MAXHELY], akkor MAXHELY = I elágazás vége ciklus vége ki: FOGLALKOZÁSOK[MAXHELY] eljárás vége

104

AZ ALGORITMIZÁLÁS ALAPJAI 13. Írja ki a magyarok nevét találati gyakoriságuk szerint csökkenő sorrendben! Először válogassuk ki a magyarokat és találati gyakoriságukat, majd rendezzük őket az utóbbi szerint, célszerűen maximumkiválasztásos rendezéssel. (Az egyszerűség kedvéért tegyük fel, hogy 1-nél több magyar van a fenti személyek között.) eljárás híres13 DB = 0 ciklus I = 0-től 29-ig ha NEMZETISÉG[I] = "magyar", akkor MAGYAROK[DB] = NÉV[I] TALÁLATOK[DB] = GOOGLE[I] DB = DB + 1 elágazás vége ciklus vége ciklus I = 0-tól (DB – 2)-ig MAXHELY = I ciklus J = (I + 1)-től (DB – 1)-ig ha TALÁLATOK[J] > TALÁLATOK[MAXHELY], akkor MAXHELY = J elágazás vége ciklus vége ha MAXHELY ≠ I, akkor SNÉV = MAGYAROK[I] MAGYAROK[I] = MAGYAROK[MAXHELY] MAGYAROK[MAXHELY] = SNÉV STALÁLATOK = TALÁLATOK[I] TALÁLATOK[I] = TALÁLATOK[MAXHELY] TALÁLATOK[MAXHELY] = STALÁLATOK elágazás vége ciklus vége ciklus I = 0-tól (DB – 1)-ig ki: MAGYAROK[I], TALÁLATOK[I] ciklus vége eljárás vége

105

AZ ALGORITMIZÁLÁS ALAPJAI 14. Születési évük szerint növekvő sorrendben írja ki a külföldiek nevét! Az külföldi, aki nem magyar. Először válogassuk ki őket, majd rendezzük születési évük szerint őket. Az egyszerűség kedvéért tételezzük fel, hogy 1-nél több külföldi van a fenti személyek között. eljárás híres14 DB = 0 ciklus I = 0-tól 29-ig ha NEMZETISÉG[I] ≠ "magyar", akkor KÜLFÖLDI[DB] = NÉV[I] SZÜL[DB] = SZÜLETETT[I] DB = DB + 1 elágazás vége ciklus vége ciklus I = 0-tól (DB – 2)-ig MINHELY = 1 ciklus J = (I + 1)-től (DB – 1)-ig ha SZÜL[J] < SZÜL[MINHELY], akkor MINHELY = J elágazás vége ciklus vége ha MINHELY ≠ I, akkor SNÉV = KÜLFÖLDI[I] KÜLFÖLDI[I] = KÜLFÖLDI[MINHELY] KÜLFÖLDI[MINHELY] = SNÉV S = SZÜL[I] SZÜL[I] = SZÜL[MINHELY] SZÜL[MINHELY] = S elágazás vége ciklus vége ciklus I = 0-tól (DB – 1)-ig ki: KÜLFÖLDI[I], SZÜL[I] ciklus vége eljárás vége

106


4.3.8.3 Megyék, városok, régiók MEGYE

RÉGIÓ

MJV

VÁROS

NAGYKÖZSÉG

KÖZSÉG

RÉGIÓK

Bács-Kiskun

0

1

19

9

90

Dél-Alföld

Baranya

1

1

11

5

284

Dél-Dunántúl

Békés

0

1

17

12

45

Észak-Alföld

Borsod-Abaúj-Zemplén

3

1

23

12

322

Észak-Magyarország

Csongrád

0

2

7

4

47

Közép-Dunántúl

Fejér

4

2

10

15

81

Közép-Magyarország

Győr-Moson-Sopron

6

2

7

7

166

Nyugat-Dunántúl

Hajdú-Bihar

2

1

20

10

51

Heves

3

1

8

4

108

Jász-Nagykun-Szolnok

2

1

17

7

53

Komárom-Esztergom

4

1

9

4

62

Nógrád

3

1

5

0

125

Pest

5

1

39

27

120

Somogy

1

1

13

4

227

Szabolcs-Szatmár-Bereg

2

1

23

19

186

Tolna

1

1

8

7

93

Vas

6

1

9

3

203

Veszprém

4

1

13

3

200

Zala

6

2

7

3

245

(Forrás: KSH)

A RÉGIÓ tömb annak a régiónak a sorszámát tartalmazza, amelybe az adott megye tartozik (pl. J-N-K Szolnok megye esetében ez a szám a 2, mivel a megye az Észak-Alföld régióban található, amely a 2-es indexű elem a RÉGIÓK tömbben). Az MJV tömb a megyében található megyei jogú városok számát, a VÁROS, a NAGYKÖZSGÉG és a KÖZSÉG tömbök pedig az adott megye megfelelő közigazgatási besorolású helységeinek számát tartalmazzák (pl. Fejér megyében 10 város, Somogy megyében 4 nagyközség stb. van).

107

AZ ALGORITMIZÁLÁS ALAPJAI 1. Hány megyében kisebb a községek száma, mint az átlag? Tudnunk kell először, hogy mennyi a községek száma átlagosan. Ezután megszámláljuk, hány megyében van ennél kevesebb. eljárás megye1 ÖSSZEG = KÖZSÉG[0] ciklus I = 1-től 18-ig ÖSSZEG = ÖSSZEG + KÖZSÉG[I] ciklus vége ÁTLAG = ÖSSZEG / 19 DB = 0 ciklus I = 0-tól 18-ig ha KÖZSÉG[I] < ÁTLAG, akkor DB = DB + 1 elágazás vége ciklus vége ki: DB eljárás vége 2. Van-e olyan megye, ahol több nagyközség található, mint város? Ez egy egyszerű eldöntési feladat. eljárás megye2 I = 0 ciklus, amíg (I < 19) és (NAGYKÖZSÉG[I] <= VÁROS[I]) I = I + 1 ciklus vége ha I < 19, akkor ki: "Igen, van ilyen megye." különben ki: "Nem, nincs ilyen megye." elágazás vége eljárás vége

108

AZ ALGORITMIZÁLÁS ALAPJAI 3. Melyik régióban van az a megye, ahol a legkevesebb város található? Ki kell választanunk azt a megyét, ahol a legkevesebb város van, majd a régiójának sorszáma alapján meg kell határozunk a RÉGIÓK tömb segítségével, melyik régióban van. eljárás megye3 MINHELY = 0 ciklus I = 1-től 18-ig ha VÁROS[I] < VÁROS[MINHELY], akkor MINHELY = I elágazás vége ciklus vége ki: RÉGIÓK[RÉGIÓ[MINHELY]] eljárás vége 4. Átlagosan hány nagyközség van megyénként? Összegezzük a nagyközségek számát, majd osztjuk a megyék számával. Egyszerű öszszegzés.

eljárás megye4 ÖSSZEG = NAGYKÖZSÉG[0] ciklus I = 1-től 18-ig ÖSSZEG = ÖSSZEG + NAGYKÖZSÉG[I] ciklus vége ki: ÖSSZEG / 19 eljárás vége 5. Van-e olyan régió, ahol kevesebb a város, mint a nagyközség? Egyszerű eldöntési feladat. eljárás megye5 I = 0 ciklus, amíg (I < 19) és (VÁROS[I] >= NAGYKÖZSÉG[I]) I = I + 1 ciklus vége ha I < 19, akkor ki: "Igen, van ilyen megye." különben ki: "Nem, nincs ilyen megye." elágazás vége eljárás vége

109

AZ ALGORITMIZÁLÁS ALAPJAI 6. Melyik régióban van az a megye, ahol a legtöbb helység található (a megye összes helységét figyelembe véve)? Ez egy olyan maximumkiválasztás, ahol nem egy vektor értékeinek, hanem négy vektor értékei összegének maximumát keressük. eljárás megye6 MH = 0 ciklus I = 0-től 18-ig ha MJV[I] + VÁROS[I] + NAGYKÖZSÉG[I] + KÖZSÉG[I] > MJV[MH] + VÁROS[MH] + NAGYKÖZSÉG[MH] + KÖZSÉG[MH], akkor MH = I elágazás vége ciklus vége ki: RÉGIÓK[RÉGIÓ[MH]] eljárás vége 7. Hány nagyközség van összesen a Nyugat-Dunántúl régióban? (Tudjuk, hogy van ilyen nevű régió.) Ez egy egyszerű (feltételes) összegzés. Hasonlóan a fentiekhez, az előzetes feladatunk csak az, hogy megtudjuk, mi a Nyugat-Dunántúl régió sorszáma. eljárás megye7 MELYIK = 0 ciklus, amíg RÉGIÓK[MELYIK] ≠ "Nyugat-Dunántúl" MELYIK = MELYIK + 1 ciklus vége ÖSSZEG = 0 ciklus I = 0-tól 18-ig ha RÉGIÓ[I] = MELYIK, akkor ÖSSZEG = ÖSSZEG + NAGYKÖZSÉG[I] elágazás vége ciklus vége ki: ÖSSZEG eljárás vége 8. Van-e olyan megye a Közép-Dunánúl régióban, amelyben 10-nél több város található? Eldöntés, de ugyanúgy, mint fent, most is ismernünk kell előre a régió sorszámát. Gondoljuk át előre, mi lesz az a T tulajdonság, amelynek megfelelő megyét keresünk! eljárás megye8 MELYIK = 0 ciklus, amíg RÉGIÓK[MELYIK] ≠ "Közép-Dunántúl" MELYIK = MELYIK + 1 110

AZ ALGORITMIZÁLÁS ALAPJAI ciklus vége I = 1 ciklus, amíg (I < 19) és ((RÉGIÓ[I] ≠ MELYIK) vagy (VÁROS[I] <= 10)) I = I + 1 ciklus vége ha I < 19, akkor ki: "Igen, van ilyen megye." különben ki: "Nem, nincs ilyen megye." elágazás vége eljárás vége 9. Hány megyei jogú város van összesen az Észak- és a Dél-Alföld régióban? (Tudjuk, hogy vannak ilyen nevű régiók.) Összegzés, mely előfeltételezi, hogy ismerjük a kérdéses régiók sorszámát. Ez persze nem lehet gond, már úgy belejöttünk. eljárás megye9 EGYIK = 0 ciklus, amíg RÉGIÓK[EGYIK] ≠ "Észak-Alföld" EGYIK = EGYIK + 1 ciklus vége MÁSIK = 0 ciklus, amíg RÉGIÓK[MÁSIK] ≠ "Dél-Alföld" MÁSIK = MÁSIK + 1 ciklus vége ÖSSZEG = 0 ciklus I = 0-től 18-ig ha (RÉGIÓ[I] = EGYIK) vagy (RÉGIÓ[I] = MÁSIK), akkor ÖSSZEG = ÖSSZEG + MJV[I] elágazás vége ciklus vége ki: ÖSSZEG eljárás vége

111

AZ ALGORITMIZÁLÁS ALAPJAI 10. Írja ki a régiók neveit a bennük található községek száma szerinti emelkedő sorrendben! Régiónként meg kell számlálnunk a községeket. Ehhez létrehozunk egy DB nevű 7 elemű vektort, melynek minden eleme az egyes régiókban található községek számát jelenti. Ezután eszerint a vektor szerint rendezzük a régiókat. eljárás megye10 ciklus I = 0-től 6-ig DB[I] = 0 ciklus vége ciklus I = 0-től 18-ig DB[RÉGIÓ[I]] = DB[RÉGIÓ[I]] + KÖZSÉG[I] ciklus vége ciklus I = 0-től 5-ig MINHELY = I ciklus J = (I + 1)-től 6-ig ha DB[J] < DB[MINHELY], akkor MINHELY = J elágazás vége ciklus vége ha MINHELY ≠ I, akkor SDB = DB[I] DB[I] = DB[MINHELY] DB[MINHELY] = SDB SRÉGIÓ = RÉGIÓK[I] RÉGIÓK[I] = RÉGIÓK[MINHELY] RÉGIÓK[MINHELY] = SRÉGIÓ elágazás vége ciklus vége ciklus I = 0-tól 6-ig ki: RÉGIÓK[I], DB[I] ciklus vége eljárás vége 11. Másolja a MEGYE2 tömbbe azoknak a megyéknek a nevét, amelyek nem az Észak-Alföld vagy a Nyugat-Dunántúl régiókban vannak! (Tudjuk, hogy vannak ilyen nevű régiók.) Ez pedig egy egyszerű kiválogatási feladat. Tudnunk kell viszont, hogy mi a sorszáma az Észak-Alföld és a Nyugat-Dunántúl régióknak. Mivel tudjuk, hogy vannak ilyen nevű régiók, alkalmazható a kiválasztás tétele. eljárás megye11 EGYIK = 0 ciklus, amíg RÉGIÓK[EGYIK] ≠ "Észak-Alföld" EGYIK = EGYIK + 1 112

AZ ALGORITMIZÁLÁS ALAPJAI ciklus vége MÁSIK = 0 ciklus, amíg RÉGIÓK[MÁSIK] ≠ "Nyugat-Dunántúl" MÁSIK = MÁSIK + 1 ciklus vége J = 0 ciklus I = 0-tól 18-ig ha (RÉGIÓ[I] ≠ EGYIK) és (RÉGIÓ[I] ≠ MÁSIK) akkor J = J + 1 MEGYE2[J] = MEGYE[I] elágazás vége ciklus vége eljárás vége 12. Írja ki a megyék nevét a bennük található városok száma szerint csökkenő sorrendben, amely megyékben 10-nél több nagyközség van! Először ki kell válogatnunk a feltételnek megfelelő megyéket és a bennük található városok számát, majd ez utóbbi szerint rendeznünk kell a kiválogatott megyéket. A csökkenő sorrendhez célszerűnek látszik a maximum-kiválasztásos rendezés alkalmazása. Nem muszáj vizsgálni, de célszerű, hogy csak akkor rendezünk, ha 1-nél több ilyen megye van, 0 vagy 1 megyét felesleges. eljárás megye12 DB = 0 ciklus I = 0-tól 18-ig ha NAGYKÖZSÉG[I] > 10, akkor MEGYE2[DB] = MEGYE[I] VÁROS2[DB] = VÁROS[I] DB = DB + 1 elágazás vége ciklus vége ha DB > 1, akkor ciklus I = 0-tól (DB – 2)-ig MAXHELY = I ciklus J = (I + 1)-től (DB – 1)-ig ha VÁROS2[J] > VÁROS2[MAXHELY], akkor MAXHELY = J elágazás vége ciklus vége ha MAXHELY ≠ I, akkor SMEGYE = MEGYE2[I] MEGYE2[I] = MEGYE2[MAXHELY] MEGYE2[MAXHELY] = SMEGYE SVÁROS = VÁROS2[I] VÁROS2[I] = VÁROS2[MAXHEYL] 113

AZ ALGORITMIZÁLÁS ALAPJAI VÁROS2[MAXHELY] = SVÁROS elágazás vége ciklus vége elágazás vége ciklus I = 0-tól (DB – 1)-ig ki: MEGYE2[I] ciklus vége eljárás vége 13. Melyik megyék vannak az Észak-Alföld régióban? (Tudjuk, hogy van ilyen nevű régió.) Másolja a neveiket az ÉSZAKALFÖLD nevű tömbbe! Kiválogatás. Tudnunk kell viszont, hogy mi a sorszáma az Észak-Alföld régiónak. Mivel tudjuk, hogy van ilyen nevű régió, alkalmazható a kiválasztás tétele. eljárás megye13 MELYIK = 0 ciklus, amíg RÉGIÓK[MELYIK] ≠ "Észak-Alföld" MELYIK = MELYIK + 1 ciklus vége J = 0 ciklus I = 1-től 19-ig ha RÉGIÓ[I] = MELYIK, akkor J = J + 1 ÉSZAKALFÖLD[J] = MEGYE[I] elágazás vége ciklus vége eljárás vége 14. Írja ki a régiók neveit a bennük található városok és nagyközségek számának összege szerinti csökkenő sorrendben! Összegeznünk kell a városok és nagyközségek számát régiónként. Ehhez hozzuk létre az ÖSSZEG nevű hételemű tömböt, melynek elemei az egyes régiókban található, adott típusú helységek számának összegei lesznek. Ha ezzel készen vagyunk, már csak rendeznünk kell. A csökkenő sorrend eléréséhez célszerűnek látszik a maximum-kiválasztásos rendezés. eljárás feladat_4C ciklus I = 0-től 6-ig ÖSSZEG[I] = 0 ciklus vége ciklus I = 0-tól 18-ig ÖSSZEG[RÉGIÓ[I]] = ÖSSZEG[RÉGIÓ[I]] + VÁROS[I] + NAGYKÖZSÉG[I] ciklus vége

114

AZ ALGORITMIZÁLÁS ALAPJAI ciklus I = 0-tól 5-ig MAXHELY = I ciklus J = (I + 1)-től 6-ig ha ÖSSZEG[J] > ÖSSZEG[MAXHELY], akkor MAXHELY = J elágazás vége ciklus vége ha MAXHELY ≠ I, akkor SÖSSZEG = ÖSSZEG[I] ÖSSZEG[I] = ÖSSZEG[MAXHELY] ÖSSZEG[MAXHELY] = SÖSSZEG SRÉGIÓ = RÉGIÓK[I] RÉGIÓK[I] = RÉGIÓK[MAXHELY] RÉGIÓK[MAXHELY] = SRÉGIÓ elágazás vége ciklus vége ciklus I = 0-tól 6-ig ki: RÉGIÓK[I] ciklus vége eljárás vége

4.3.8.4 Autók RENDSZÁM LYN-582 YWX-715 NZI-110 PAW-517 PHC-448 FQE-168 GER-115 KVS-920 NNB-904 QEX-962 LLF-939 ZOZ-218 MBX-182 MWZ-731 SOR-203 WTO-573 BMF-822 AUG-189 UOC-918 UKD-803 ONT-300 UPY-402 TZC-007

MÁRKA Opel Renault Fiat Toyota Renault Toyota BMW Renault Mercedes Fiat BMW Opel Mercedes Fiat Volkswagen Renault Ford Suzuki Volkswagen Mercedes Mercedes Renault Volkswagen

SZÍN kék piros fehér fehér fekete zöld kék zöld fekete piros fekete piros zöld fekete kék kék szürke szürke piros fekete szürke fehér fehér

ÜZEMANYAG diesel benzin diesel diesel benzin benzin diesel benzin diesel diesel benzin diesel benzin benzin benzin benzin diesel diesel diesel diesel benzin diesel benzin

CCM 1700 1600 1200 2200 2000 2200 1500 2200 1800 1200 1800 1200 1300 1900 2000 1800 2000 1600 1400 1300 1500 1900 1700

KILOMÉTER 75481 59749 49369 74736 34970 76498 57711 58838 50545 31163 77858 37658 26113 72356 26128 22998 71370 49334 62527 47369 63144 79076 49002

ÁR 2135000 1642000 2020000 1773000 557000 1004000 1786000 1495000 1306000 1538000 449000 1533000 1512000 1725000 753000 438000 763000 2201000 2036000 2097000 1192000 756000 1069000

115

AZ ALGORITMIZÁLÁS ALAPJAI LSP-155 PYS-619 YPT-336 MKY-268 YBF-696 ARG-116 UWL-228 ZUE-691 JEH-568 HXH-645 TQM-629 JIL-882 XMP-469 NRN-598 KXG-142 LZX-198 LVK-184 WJL-522 CBO-222 AIL-142 WAJ-325 QUB-316 FQX-609 YFH-943 NVS-665 NSX-924 THN-312

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.

116

BMW Volkswagen Fiat Fiat Ford Mercedes BMW Suzuki Volkswagen Toyota Mercedes Citroën Fiat BMW Nissan Suzuki Opel Audi Toyota Mercedes Mercedes Mercedes Nissan Audi Toyota BMW Nissan

fehér fekete piros fekete piros zöld piros fehér fekete kék szürke szürke piros fehér fekete fehér zöld zöld piros fehér kék fehér kék fekete zöld fehér fekete

benzin diesel diesel benzin diesel diesel diesel diesel diesel diesel benzin benzin diesel benzin diesel benzin diesel diesel diesel benzin diesel diesel benzin diesel diesel benzin benzin

1600 1200 1700 2000 2100 1400 2000 1300 1800 1700 2100 1700 2200 2100 2000 1900 2100 1500 1700 1400 1600 1300 1300 1800 1900 2200 2000

57669 38941 34004 69538 79825 63744 49154 18407 16420 76102 23099 47040 80621 28787 18941 62275 57307 22005 59260 43784 69567 30580 21032 43746 84602 16643 31800

2174000 2083000 2282000 2230000 1716000 1846000 1522000 1877000 1399000 551000 477000 1626000 1433000 2135000 1648000 884000 2123000 694000 1612000 1767000 1687000 2291000 463000 1980000 956000 1341000 1189000

Milyen színű autóból van a legtöbb? Mennyi az 50 000 km-nél többet futott diesel autók átlagára? Milyen márkájú autó az XYZ-573 rendszámú? Alkalmazzon strázsás keresést! Van-e olyan benzines autó, amelyik több kilométert futott, mint a diesel autók által futott kilométerek átlagának háromszorosa? Határozza meg, hogy szürke színű vagy Nissan típusú autóból van-e több? Van-e olyan autó, ami többet futott 70 000 km-nél és drágább, mint 2 000 000 Ft? Adja meg a legnagyobb hengerűrtartalmú (CCM), kék színű diesel autó rendszámát! Figyelem, lehet, hogy nincs is ilyen! Adja meg a Suzukik és a Mercedesek átlagára közötti különbséget! Van-e olyan piros színű diesel autó, ami többe kerül, mint a legtöbb kilométert futott zöld színű autó? Mennyibe kerül a legtöbb kilométert futott autó az 1500 cm3-nél kisebb kategóriájú autók közül? Miből van több: 1 500 000 Ft-nál drágább Mercedesből vagy benzines Nissanból? Van-e olyan fehér autó, ami többe kerül a legdrágább benzinesnél?

AZ ALGORITMIZÁLÁS ALAPJAI 13. Hány 1500 cm -nél kisebb hengerűrtartalmú (CCM) autó van? 3

14. Átlagosan hány km-t futottak a BMW-k? 15. Van-e olyan Mercedes, ami olcsóbb, mint a legolcsóbb Fiat? 16. Milyen márkájú az ABC-123 forgalmi rendszámú autó? A feladatot teljes ke17. 18. 19. 20. 21. 22.

8.3

reséssel oldja meg! Melyik autó a második legolcsóbb? (Az árát tekintve a legolcsóbb után következő.) Hány diesel autó hengerűrtartalma (CCM) nagyobb, mint a benzines autók átlag-hengerűrtartalma? Melyik márkában van a legtöbb piros autó? A zöld autók közül melyik futotta a legkevesebb kilométert? Adja meg rendszámát! Van-e 2 000 000 Ft-nál drágább diesel? Milyen színű a második legolcsóbb BMW?

ÖSSZEFOGLALÁS

Ebben a leckében olyan gyakorló feladatokat mutattunk be, amelyek az elemi vektorkezelő eljárások ismeretében oldhatók meg. Javasoljuk, hogy az Olvasó is találjon ki az ismertetett példákban látottakhoz hasonló kérdéseket, és próbálja megadni a megoldások algoritmusát. Feladatokat konkrét adatok ismerete nélkül is kitalálhatunk. Ebben az esetben még nagyobb szerepe van annak, hogy olyan algoritmusokat adjunk meg, amelyek fel vannak készítve a szélsőséges esetekre is. Az ismertetett példák mondatszerű leírónyelven megadott algoritmusai egy konkrét nyelv szintaxisának ismeretében egyszerűen átírhatók programmá, és így a gyakorlatban is kipróbálhatók.

8.4 ÖNELLENŐRZŐ KÉRDÉSEK Milyen esetekben alkalmazunk keresést kiválasztás helyett? 2. Van-e olyan eset, amikor a minimumkiválasztásos rendezés választása célszerűbb, mint a maximumkiválasztásos és fordítva? 3. Milyen esetekben érdemes bináris keresést használnunk más keresőeljárások helyett? 4. Átlagszámításnál milyen szélsőséges esetekre kell felkészülnünk? 1.

117


9. ALGORITMUSOK HATÉKONYSÁGA 9.1 CÉLKITŰZÉS Ebben a leckében betekintést nyújtunk az algoritmusok hatékonyságának vizsgálatába. Az algoritmusok elemzése programozási nyelvektől és számítógépektől független, absztrakt matematikai tudomány. Algoritmusok elemzésekor vizsgálható egy eljárás időigénye, illetve az adatok (adatszerkezetek) helyfoglalása, vagyis tárigénye. Ezzel a két területtel a bonyolultságelmélet foglalkozik, és az idő- és tárigényt a bemenet függvényében adja meg. Általában nem pontos értékeket határozunk meg, hanem nagyságrendeket. Pontos értékek azért is lennének nehezen megadhatók, mert a különböző programozási nyelven írott programok különböző architektúrájú gépeken futtatva nagyon különböző (konkrét) futási időket is produkálhatnak. A bemenet nagyságához mért időigény nagyságrendje így elegendően pontos információ lehet. A kiszámíthatóság-elmélet az algoritmusok futásának befejeződését, eredményes lefutásának lehetőségét és viszonyait vizsgálja. Algoritmusok elemzésére azért van szükség, hogy legyen eszközünk az algoritmusok hatékonyságainak összehasonlítására, vagyis egy adott probléma ismeretében ki tudjuk választani a leghatékonyabb algoritmust. Ebben a leckében bemutatjuk hatékonyságmérés absztrakt eszközeit. 9.2 − −

TARTALOM Algoritmusok műveletigénye Aszimptotikus jelölések


Algoritmusok műveletigénye

A műveletigény meghatározásakor általában csak az algoritmus meghatározó műveleteinek elemzését végezzük. Egy művelet meghatározó az algoritmusban, ha a többi művelethez képest jelentős a végrehajtási ideje, vagy a végrehajtásainak a száma. Jellemzően ilyen művelet egy rendezési eljárásban az összehasonlítások és a cserék száma, szemben például a ciklusváltozók értékének növelésével. A 7.3.3 fejezetben bemutattuk a buborékrendezés algoritmusát. Vizsgáljuk meg ennek az eljárásnak a műveletigényét. Amint azt fent leírtuk, a műveletek között meghatározók az összehasonlításokat és a cseréket végző műveletek. Vizsgáljuk meg őket külön-külön! A műveletigényt a rendezendő elemek száma (n) nagyságának függvényében adjuk meg. Jelöljük Ö(n)-nel az összehasonlítások számát! A külső ciklus (n–1)-szer fut le, az egyes lefutásokon belül a belső ciklus (n–1), (n–2), … 1 iterációs lépést hajt végre. Az összehasonlítást minden lépésben végre kell hajtani, még akkor is, ha cserére nincs szükség, így azt mondjuk, hogy az összehasonlítások száma állandó. Az összehasonlítások száma:

118

AZ ALGORITMIZÁLÁS ALAPJAI Ö(n) = (n–1) + (n–2) + … + 1 =

n(n 1) 2

n2 2

n . 2

Az összehasonlítások számának nagyságrendje így n függvényében n2. Ezt így jelöljük: Ö(n) = Θ(n2) és teta n-négyzetnek ejtjük. A nagyságrend meghatározásánál az n-es tagot nem kell figyelembe vennünk, mert egyre nagyobb n-ek esetében ennek nagysága elenyésző az n2-hez képest. Lássuk most a cserék számát, jelöljük ezt Cs(n)-nel! A cserék száma nem állandó, mert nem minden elempár esetében kell cserélnünk. Ezért a cserék számának pontos meghatározásához ismernünk kell a szomszédos elemek relációs viszonyait is, így viszont nem tudunk általános értéket adni a cserék számának nagyságrendjéhez. Tekintsük ezért a cserék átlagos számát kiindulási alapnak! Ha növekvő sorrendet szeretnénk létrehozni, és a vektor elemei már eleve növekvő sorrendben vannak, akkor a cserék száma 0. Ekkor Csmin(n) = Θ(0). A legrosszabb eset az, amikor a vektor elemei éppen fordított sorrendben, tehát nagyság szerint csökkenő sorban rendezettek. Ekkor a cserék száma: Csmax =

n(n 1) , azaz Csmax(n) = Θ(n2). 2

Ha feltételezzük, hogy a vektor minden eleme különböző, akkor mondhatjuk, hogy az átlagos cserék száma a legrosszabb érték fele: Csátlag(n) =

n(n 1) = Θ(n2), 4

de ennek nagyságrendje még mindig n2. Kimondhatjuk, hogy a buborékrendezés a legrosszabb és az átlagos esetben is nagyságrendben n2-es algoritmus, akár az összehasonlítások, akár a cserék számát tekintjük. Hasonlóan n2-es rendezés a beszúró rendezés az elemek mozgatása, és a szélsőértékkiválasztásos rendezés a szélsőérték megtalálása tekintetében. Ezen állítások bizonyítását az Olvasóra bízzuk. Általában elmondhatjuk azt, hogy egy Θ(n2) futásidejű algoritmus gyorsabban fut a legrosszabb esetben, mint egy Θ(n3), de csak „elegendően nagy” n-ek esetében. 9.3.2

Aszimptotikus jelölések

Az előző fejezetben a legrosszabb futási időt (T) határoztuk meg. A buborékrendezésnél a legrosszabb futási idő: T(n) = Θ(n2). Mint arról korábban már szóltunk, a Θ(n2) nem egy konkrét értéket, hanem egy nagyságrendet jelöl. Adjuk meg ennek a jelölésnek a pontos definícióját! R0 függvényt, amely a természeteses számok halmazán van érTekintsük az f : N telmezve és nemnegatív valós értékeket vehet fel. N = {0, 1, 2, …} Most pedig definiáljuk egy adott g függvény esetén azon függvények halmazát, amelyek nagyságrendben − nem nagyobbak, mint g − nem kisebbek, mint g − megegyeznek g nagyságrendjével.

119

AZ ALGORITMIZÁLÁS ALAPJAI Egy adott g függvény esetén O(g)-vel jelöljük (és nagy ordó g-nek ejtjük) függvényeknek azt a halmazát, amelyre O(g(n)) = {f(n): van olyan c > 0 és n0 ≥ 0 állandó, hogy minden n ≥ n0 esetén 0 ≤ f(n) ≤ c∙g(n)} teljesül. Ha f O(g), akkor azt mondjuk, hogy g aszimptotikus felső korlátja f-nek. Ebben az esetben szokásos módon inkább az f = O(g) jelölést alkalmazzuk. Jelölje Ω(g) (ejtsd: omega g) azon függvények halmazát, amelyekre Ω(g(n)) = {f(n): van olyan c > 0 és n0 ≥ 0 állandó, hogy minden n ≥ n0 esetén 0 ≤ c∙g(n) ≤ f(n)} áll fenn. Ha f Ω(g) – szokásos jelöléssel f = Ω(g) –, akkor azt mondjuk, hogy g aszimptotikus alsó korlátja f-nek. Végül, Θ(g) (ejtsd: teta g) jelöli azt a függvényhalmazt, amelyet a Θ(g(n)) = {f(n): van olyan c1 > 0, c2 > 0 és n0 ≥ 0 állandó, hogy minden n ≥ n0 esetén 0 ≤ c1∙g(n) ≤ f(n)≤ c2∙g(n)} összefüggés ír le. Ha f Θ(g) – szokásos jelöléssel f = Θ(g) –, akkor azt mondjuk, hogy g aszimptotikusan éles korlátja f-nek.

50. kép

Grafikus példák a Θ, O és Ω jelölésekre

Gyakori hiba, hogy algoritmusok műveletigényének jellemzésekor -t használnak, de -t értenek alatta. Az így leírt egyenlőség általában igaz, de mást (kevesebbet) fejez ki, (n 2 ) , de töbmint amit a közlő ért alatta. Pl. a buborék rendezésre igaz, hogy MT (n)

(n 2 ) . bet mond az, hogy MT (n) A T (n) jelölés használata is hibát rejthet. T (n) az összes lehetséges futási időt magában foglalja, amelyek nagyságrendben különbözőek lehetnek. Pl. ahogy korábban láttuk, a (n 2 ) és buborék rendezésre igaz (Cs helyett most T-vel), hogy: MT (n) (n 2 ) . A legkedvezőbb esetben azonban nincs csere, vagyis mT (n) 0 . Ek(n 2 ) (felületes) kijelentés nem igaz, helyette a T (n) (n 2 ) kijelentést kor a T (n) AT (n)

kellene használni, mely az összes esetre helyes lesz. De ez kevesebb információt tartalmaz, mint a fenti két egyenlőség, ezért ajánlatos MT (n) -t és AT (n) -t használni.

120

AZ ALGORITMIZÁLÁS ALAPJAI Befejezésül, konkrét példaként lássuk a gyorsrendezés elemzését – bizonyítások nélkül. Legrosszabb esetben Θ(n2), átlagos esetben Θ(n ∙ lg n). A futási idő attól függ, hogy a felosztás kiegyensúlyozott-e, vagy sem. A felosztás az a művelet, amely során a tömb egy elemét úgy mozgatjuk végleges helyére, hogy vele együtt a többi elemet is átrendezzük: a nála kisebbek tőle balra, a nála nagyobbak tőle jobbra kerülnek. Ha minden felosztás esetén az adott elemtől balra és jobbra azonos számú elem lesz, a felosztás kiegyensúlyozott. Ha a felosztás nem kiegyensúlyozott, akkor a módszer aszimptotikusan olyan lassú lehet, mint a beszúró rendezés. Az ún. összefésüléses rendezés és kupacrendezés legrosszabb esetben O(n∙lg n) időben rendezi az n elemet, a gyorsrendezésnek ez az átlagos futási ideje. Léteznek olyan eljárások, amelyek ennél is gyorsabban, lineáris időben tudnak rendezni. Az érdeklődő olvasók figyelmébe ajánljuk a leszámláló rendezést, a számjegyes rendezést és az ún. edényrendezést. 9.4

ÖSSZEFOGLALÁS

Ennek a rövid leckének az volt a célja, hogy bemutassa az algoritmusok műveletigényének meghatározására szolgáló jelöléseket. Jegyzetünknek nem célja, hogy részletesen tárgyalja és bizonyítsa az egyes eljárások műveletigényét, de fontosnak tartjuk legalább jelölések értelmezésének megadását, mert ezek ismerete nélkül nem érthető meg a különböző szakirodalmakban található eljárások elemzése.

9.5 ÖNELLENŐRZŐ KÉRDÉSEK Gondolja át, hogy a megismert eljárásokban az elemszám függvényében hány összehasonlítást kell végrehajtani. 2. Vizsgálja meg a megismert rendező eljárásokat, hogy cserék számát tekintve melyik hatékonyabb és melyik kevésbé hatékony! 3. Miért hatékonyabb a strázsás keresés, mint a teljes keresés? 1.

121


10. ALPROGRAMOK 10.1 CÉLKITŰZÉS Ez a lecke nem kapcsolódik szorosan az algoritmizálás témaköréhez, sokkal inkább programozással, programozási nyelvekkel kapcsolatos tudnivalókat tartalmaz. Mégis fontos az alapvető tudnivalók áttekintése, mert az alprogramok az összes eljárásorintált (procedurális) nyelvben a strukturált programozás alapeszközei. Az objektumorientált nyelvekben is megtaláljuk a procedurális nyelvekben használatos alprogramokat, de nem az adatoktól különválasztva, hanem azokkal szoros egységekbe, objektumokba zárva. Kissé pontatlan megfogalmazásban: ami a procedurális nyelvekben az alprogram, az az objektumorientált nyelvekben a metódus. 10.2 TARTALOM − − − −

Az alprogramok célja, jellemzői, fajtái Formális és aktuális paraméterek A rekurzió Hatókör, élettartam

10.3 A TANANYAG KIFEJTÉSE 10.3.1 Az alprogramok célja, jellemzői, fajtái Az alprogramok minden eljárásorientált nyelvben megtalálhatók és a nyelvek alapeszközei közé tartoznak. Használatuk fő okai az alábbi két tulajdonságuk: − Újrafelhasználhatóság: ha egy programban két vagy több helyen ugyanazt az utasítássorozatot használjuk, akkor célszerű őket kiemelni, nevet (azonosítót) adni nekik, és a kiemelés helyén ezzel az azonosítóval hivatkozni rájuk − Paraméterezhetőség: ha a kiemelt utasítássorozathoz paramétereket is rendelhetünk, nemcsak egy konkrét művelet, de műveletcsoport is helyettesíthető ezzel a módszerrel. Az alprogram tehát olyan nyelvi szerkezet, amelynek segítségével nevet rendelhetünk egy kódrészlethez, hogy azt később egyszerűen végrehajthassuk. A végrehajtás kezdeményezése (alprogramhívás) az alprogram nevének és esetleges paramétereinek megadásával történik. A fenti tulajdonságaikon túl azért alkalmazzuk őket, mert javítják a programkód olvashatóságát. Egy jól megválasztott alprogramnév kifejezőbb lehet az olvasó számára, mint az alprogramot megvalósító kód. A jegyzetünkben közölt rendezőeljárásokban gyakran volt szükség arra, hogy két tömbelemet megcseréljünk. A 8. leckében bemutatott példákban előfordult, hogy egyidejűleg több tömb elemein is kellett cserét eszközölnünk. Ilyenkor ezt a három értékadást alkalmaztuk:

122

AZ ALGORITMIZÁLÁS ALAPJAI S = A[I] A[I] = A[J] A[J] = S Azokban a példákban, ahol egynél több tömb elemeit kellett rendeznünk, vagyis az elemeket cserélnünk, a kódot rövidebbé tehettük volna, ha készítünk egy a cserét megvalósító eljárást. Azokban a kódokban, ahol csak egy tömböt kell rendeznünk, az olvashatóságon javítottunk volna. eljárás CSERE(A, B) S = A A = B B = S eljárás vége Ahol pedig az elemek tényleges cseréjét hajtottuk végre, elegendő lett volna hivatkozni erre az eljárásra (más szóval meghívni a csereeljárást): ... ha A[I] > A[J], akkor CSERE(A[I], A[J]) elágazás vége ... Kétféle alprogramot ismerünk, az eljárást és a függvényt. Az eljárás a paraméterein, vagy a program környezetén elvégzett transzformációkat ad meg. Adattranszformációt vagy tevékenységet végez. Hívásakor az eljárás nevét mint utasítást használhatjuk. Turbo Pascal, Free Pascal program pelda; var a, b : integer; procedure csere(a, b : integer); var s : integer; begin s := a; a := b; b := s; end; begin ... csere(a, b); ... end. 123

AZ ALGORITMIZÁLÁS ALAPJAI A függvények ezzel szemben mindig visszatérési értéket számítanak ki és adnak meg. Transzformációt nem végeznek, sem a program változóinak értékére, sem a program környezetére nincsenek hatással. Úgy is mondjuk, hogy a függvényeknek nincs mellékhatásuk. A függvényeket kifejezésekben használjuk. Ha az eljárásokra úgy tekintettünk, mint a programozási nyelv utasításkészletének kibővítéseit jelentő eszközöket, akkor a függvényekre tekinthetünk úgy is, mint a kifejezésekben használható operátorok körét kibővítő eszközök. függvény GYÖK1(A, B, C) GYÖK1 = (–B + SQRT(B * B – 4 * A * C)) / (2 * A) // SQRT()-vel jelöltük a négyzetgyökvonást függvény vége függvény GYÖK2(A, B, C) GYÖK2 = (–B – SQRT(B * B – 4 * A * C)) / (2 * A) függvény vége eljárás másodfokúEgyenletMegoldása be: A, B, C DISZKRIMINÁNS = (B * B) – (4 * A * C) ha DISZKRIMINÁNS ≥ 0, akkor ki: GYÖK1(A, B, C), GYÖK2(A, B, C) különben ki: "Nincs valós gyök." elágazás vége eljárás vége C# double gyök1(double a, b, c) { return (–b + Math.Sqrt(b * b – 4 * a * c)) / (2 * a); } Vannak olyan nyelvek, amelyekben külön kulcsszóval definiálható az eljárás és a függvény (például a Turbo Pascalban vagy Free Pascalban procedure az eljárás és function a függvény definiálására). Más nyelvekben nyelvi szinten nincs jelentős különbség az eljárás és a függvény definíciója között. Ilyen nyelvek a C-szerű nyelvek (C, C++, C#, Java). Ezekben az alprogramok definícióját így adjuk meg:

124

AZ ALGORITMIZÁLÁS ALAPJAI típus azonosító(paraméterek) { törzs; [return visszatérési érték;] } A típus a függvény visszatérési értékének típusa. Ha a definiált alprogram nem függvény, hanem eljárás, vagyis nincs visszatérési értéke, akkor a típus helyére a void kulcsszó kerül. Ebben az esetben a függvény törzsében nem kell szerepelnie a return kulcsszónak sem. 10.3.2 Formális és aktuális paraméterek Az alprogram definíciója formálisan így néz ki: fej(paraméterek) törzs vég A definícióban a fej a specifikáció eszköze. A specifikáció arról ad információt, hogy az alprogramot hogyan kell használni, hogyan kell meghívni. Híváskor az alprogram nevét és a végrehajtáshoz szükséges paramétereket kell megadni. Az alprogramok paraméterezhetősége minden procedurális nyelvben használható eszköz, eltekintve a BASIC nyelv néhány régi változatától. Amikor definiáljuk az alprogramot, a specifikációban megadjuk az ún. formális paraméterlistát. Itt azonosítókat és típusokat sorolunk fel, hasonlóan a változók deklarációjához. A formális paraméterlistában felsorolt nevek az alprogram lokális nevei lesznek. A lokális és globális változókról a hatókör, élettartam fejezetben bővebben olvashatunk. Híváskor az alprogram neve mellett aktuális paramétereket adunk meg. Ezek azok a konkrét értékek, amelyek felhasználásával az alprogramot végre kell hajtani. Fontos, hogy az aktuális paraméterlista elemeinek konkrét értékeknek (vagyis literáloknak vagy értékkel rendelkező változóknak) kell lenniük. Híváskor a pereméterek egyeztetésére is sor kerül. A legegyszerűbb eset, amikor a formális paraméterlista első elemének értéke az aktuális paraméterlista első értéke lesz, a formális paraméterlista második elemének értéke az aktuális paraméterlista második értéke lesz és így tovább. C# double kerület(double x, y, z) { return x + y + z; } double terület(double x, y, z) // a Hérón-képlettel { double s = (x + y + z) / 2.0; return Math.Sqrt(s * (s – x) * (s – y) * (s – z)); 125

AZ ALGORITMIZÁLÁS ALAPJAI } void Main() { double a, b, c; System.Console.Write("Adja meg a háromszög oldalait"); System.Console.Write("a="); a = Convert.ToDouble(System.Console.ReadLine()); System.Console.Write("b="); b = Convert.ToDouble(System.Console.ReadLine()); System.Console.Write("c="); c = Convert.ToDouble(System.Console.ReadLine()); System.Console.WriteLine("Kerület: {0}", kerület(a, b, c)); System.Console.WriteLine("Terület: {0}", terület(a, b, c)); } A fenti példában híváskor a formális paraméterlista x, y, z változóinak értéke rendre a, b és c lesz. A paraméterkiértékelés azonban a különböző nyelvekben teljesen különböző szabályok szerint történhet, ezért jegyzetünkben nem tárgyaljuk ezt a kérdéskört. Az érdeklődő olvasóknak javasoljuk, hogy önállóan kutassanak az alábbi kifejezések jelentése után: sorrendi kötés, típusegyeztetés, számbeli egyeztetés, valamint paraméterátadás (cím szerint, érték szerint, eredmény szerint, érték/eredmény szerint, szöveg szerint, név szerint) és alprogramnevek túlterhelése. 10.3.3 A rekurzió A rekurzióról korábban már esett szó. Alprogramok esetében akkor beszélünk rekurzióról, ha egy alprogram törzsében az alprogram saját magát hívja meg. Az alábbi egyszerű példa az n! értékét számolja ki17. ANSI C int faktorialis(int n) { if(n <= 1) return 1; return n * faktorialis(n – 1); }

17

Az int típus az ANSI C-ben kétbájtos előjeles egészet jelent, értéke –32 768 .. 32 767 közötti lehet. A fenti példa emiatt csak n ≤ 7 esetén működik, mert 8! = 40 320.

126

AZ ALGORITMIZÁLÁS ALAPJAI 10.3.4 Hatókör, élettartam A hatókör a program neveihez (változók, alprogramok) kapcsolódó fogalom. A hatókör a programnak az a része, ahol a jelölt programelem (változó, alprogram stb.) az adott néven elérhető. A hatókörkezelés az a folyamat, amikor egy névhez meghatározzuk annak hatókörét. Beszélhetünk statikus és dinamikus hatókörkezelésről. A statikus hatókörkezelés alapja a programegységek egymásba ágyazása. Egy név deklarációja az őt követő befoglaló programegység végéig van érvényben. Azon kívül nem, de azon belül még az őt követő beágyazott programegységekben is érvényes név.

51. kép

Statikus hatókörkezelés

A dinamikus hatókörkezelés alapja nem a forráskód, hanem a hívási lánc. Ha egy A programegységben deklarálunk egy nevet, majd meghívjuk a B programegységet, akkor ez a név B-ben is érvényes lesz, függetlenül attól, hogy B az A-ba van-e ágyazva, vagy sem. Ezt a módszert azonban viszonylag kevés programozási nyelv alkalmazza. Az imperatív nyelvek általában statikus hatókörkezelést alkalmaznak.

127


52. kép

Dinamikus hatókörkezelés

Az élettartam a program végrehajtási idejének az a része, ameddig egy adott tárterületet arra használunk, hogy az adott programelem (változó) értékét tárolja. Más szóval: az élettartam a futási idő azon része, amelyben a változó címkomponenssel rendelkezik. 10.4 ÖSSZEFOGLALÁS Ebben a leckében a programozási nyelvek egyik fontos eszközéről, az alprogramokról beszéltünk. Az alprogramok megvalósítása és jellemzői (pl. paraméterátadás, paraméterkiértékelés, hatókörkezelés) az egyes programozási nyelvekben nagyon különböző is lehet, ezért ebben a jegyzetben ezeket nem fejtettük ki részletesen. Célunk ebben a leckében is csak a betekintés volt.

10.5 ÖNELLENŐRZŐ KÉRDÉSEK Mi a különbség eljárás és függvény között? 2. Lehet-e egy függvény rekurzív, vagy csak eljárásoknál létezik a rekurzió? 3. Mi a különbség statikus és dinamikus hatókörkezelés között? 4. Milyen esetekben célszerű és milyen esetekben nem célszerű egy programrészből alprogramot készíteni? 1.

128


11. DINAMIKUS ADATSZERKEZETEK 11.1 CÉLKITŰZÉS Ebben a leckében betekintést nyújtunk a dinamikus adatszerkezetek kezelésébe. Mint azt korábban hangsúlyoztuk, egy adatszerkezet statikus vagy dinamikus volta nem befolyásolja a tárolási módot, a reprezentációt. A reprezentáció azt mutatja meg, hogy egy adott adatszerkezet elemeit milyen módon érhetjük el. Ahhoz, hogy az elemeket elérjük, azokat tárolni kell a memóriában. A tárolás lehet folytonos, ekkor az elemek a tárban fizikailag egymás után vannak tárolva, de nem biztos, hogy az elérés sorrendjében, vagyis a logikai sorrend eltérhet a fizikai sorrendtől. A tárolás lehet szétszórt is, ekkor az elemek fizikailag a tár különböző, nem egymást követő rekeszeiben vannak eltárolva. Ebben az estben gondoskodnunk kell arról, hogy meghatározható legyen, hogy melyik elemnek melyik a megelőzője és melyik a rákövetkezője.

53. kép

Folytonos tárolás

54. kép

Szétszórt tárolás

Bármely adatszerkezet esetében alkalmazható a folytonos és a szétszórt tárolás is, de vannak, amelyekhez célszerűbb az egyik, míg másokhoz a másik tárolási mód alkalmazása. Például a tömbök tárolása a programozási nyelvekben általában a folytonos a memóriában. (Az egyes elemek tárbeli címének meghatározására szolgál az ún. címaritmetika. Ha ismerjük az első elem címét a tárban, és tudjuk, hogy az egyes elemek hány bájtot foglalnak, bármely elem memóriacíme könnyen meghatározható.) Dinamikus adatszerkezetek 129

AZ ALGORITMIZÁLÁS ALAPJAI esetében gyakori a szétszórt tárolás, hiszen a dinamikus adatszerkezetek elemszáma bármikor növelhető. Előre nem tudhatjuk, hogy hány eleme lesz egy adatszerkezetnek, így előre nem lehet pontos méretű összefüggő adatterületet foglalni az elemek számára.

55. kép

Címaritmetika

Ebben a fejezetben bemutatjuk néhány gyakori dinamikus adatszerkezet kezelését, és szót ejtünk a tárolás kérdéseiről is.

11.2 TARTALOM − − − − − −

A halmaz A lista A verem A sor A fa A háló

11.3 A TANANYAG KIFEJTÉSE 11.3.1 A halmaz

11.3.1.1 Halmazok reprezentációja A halmaz struktúra nélküli adatszerkezet. Ez azt jelenti, hogy az elemek között nincs kapcsolat, nem tudjuk meghatározni a sorrendjüket. Meg tudjuk viszont állapítani, hogy egy elem eleme-e a halmaznak. A halmazban minden elem egyszer fordulhat elő, így egy tetszőleges elem vagy eleme a halmaznak, vagy nem. A multihalmaz olyan speciális adatszerkezet, amelyben megengedett egy elem többszöri előfordulása. Bár a matematikában ismeretes a végtelen halmaz (sőt: megszámlálható és kontinuum végtelen halmaz is) fogalma, a 3.3.3.2 fejezetben leírtak alapján végtelen halmaz adatszerkezetként nem létezik.

130


56. kép

Halmaz, multihalmaz

Tároláskor hagyományos halmazok és multihalmazok esetében is általában folytonos reprezentációt alkalmaznak. Jegyzetünkben csak a halmazon értelmezett műveleteket mutatjuk be, a multihalmaz műveleteinek implementálást az Olvasóra bízzuk. A halmaz leképezhető pl. tömbre (vektorra). Ilyenkor a vektor tárolja a halmaz elemeit. A vektort elegendően nagy elemszámúra kell deklarálnunk, hiszen a tömb statikus adatszerkezet, így a deklarált elemszám nagyságát futás alatt nem lehet tovább növelni. A vektor „nem használt” elemeinek olyan értéket kell felvenniük, amely a halmaznak nem lehet eleme (pl. ha a halmaz csak természetes számokat és nullát tartalmazhat, akkor a nem halmazelemeket reprezentáló tömbelem értéke lehet –1), vagy nyilván kell tartanunk egy külön változóban, hogy hány eleme van a halmaznak. Megjegyzés: létezik ettől alapvetően eltérő ábrázolási/tárolási módszer is, melynek alapja az ún. karakterisztikus függvény. Ennek segítségével a memóriában minden egyes elem számára csak egy bitet (!) foglalunk. A tárolandó elemeket sorba rendezzük. A karakterisztikus függvény segítségével határozzuk meg, hogy az egyes elemeket melyik bit jelöli a lefoglalt területen. Ha az adott elem megtalálható a halmazban, akkor a bitet 1-re állítjuk, ha nem, akkor 0-ra.

57. kép

Halmaz reprezentációja karakterisztikus függvénnyel

A halmaz inicializálása (üres halmaz létrehozása) történhet úgy, hogy a vektor összes elemét kezdőértékkel töltjük fel, és/vagy az elemszámot mutató változó értékét nullára állítjuk. Feltételezzük, hogy a halmaz maximum N elemű lehet.

131

AZ ALGORITMIZÁLÁS ALAPJAI eljárás inicializálás ciklus I = 0-tól (N – 1)-ig A[I] = ciklus vége elemszámA = 0 eljárás vége A halmaz bővítése történhet unióval (a jelenlegi halmaz uniója a felveendő értékkel, mint egyelemű halmazzal). A = {5, 9, 17, 34, 62} új elem: 41 A := A {41} Ha egy elemet törölni akarunk a halmazból, képeznünk kell az eredeti halmaz és a törlendő elem, mint egyelemű halmaz különbségét. törlendő elem: 62 A := A \ {62} Az A és B halmazok egyenlők, ha pontosan ugyanazokat az elemeket tartalmazzák. Jelölése: A = B. Alapvető halmazelméleti operátor az (eleme). Mivel a halmaz reprezentációja egy rendezetlen vektor, és előfordulhat az az eset, hogy egy elem nem eleme a halmaznak, a művelet implementálása csak teljes kereséssel történhet. Definiáljunk egy logikai függvényt, amelynek paraméterei az A halmaz, ennek elemszáma: N és az X elem. Visszatérési értéke IGAZ, ha az X eleme A-nak, HAMIS egyébként. függvény eleme(A, N, X) I = 0 ciklus, amíg (I < N) és (A[I] ≠ X) I = I + 1 ciklus vége eleme = (I < N) függvény vége A függvény teljes keresés. Figyeljük meg, hogyan kap visszatérési értéket! Ha a keresés sikeres volt, vagyis az X eleme A-nak, akkor az I < N feltétel igaz, és ez a logikai érték lesz a függvény visszatérési értéke. Ha a keresés sikertelen volt, akkor az I < N feltétel hamis, így ez lesz a függvény visszatérési értéke.

8.3.1.2 Az egyesítés (unió) Hasonló a korábban tárgyalt összefuttatáshoz, de mégsem ugyanaz, mert a halmazokat reprezentáló vektorok esetében nem követelmény a rendezettség. Az algoritmus A és B 132

AZ ALGORITMIZÁLÁS ALAPJAI halmazokból létrehozza azt a C halmazt, amelynek elemei megtalálhatók A-ban vagy Bben, vagy mindkét halmazban.

58. kép

Halmazok egyesítése

Ebből következően C-nek eleme lesz az A összes eleme, illetve B-ből azok az elemek, amelyek az A-ban nem szerepelnek. (A halmazban minden elem csak egyszer szerepel, így azok az elemek is, amelyek mindkét halmaznak elemei.) Ezért az algoritmus először átmásolja C-be A összes elemét, majd B-ből azokat, amelyek nem elemei A-nak. eljárás egyesítés ciklus I = 0-tól (ELEMSZÁMA – 1)-ig C[I] = A[I] ciklus vége ELEMSZÁMC = ELEMSZÁMA ciklus I = 0-tól (ELEMSZÁMB – 1)-ig ha nem eleme(A, ELEMSZÁMA, B[I]), akkor C[ELEMSZÁMC] = B[I] ELEMSZÁMC = ELEMSZÁMC + 1 elágazás vége ciklus vége eljárás vége

11.3.1.3 A metszet A és B halmaz metszete az a C halmaz, amelynek elemei mind az A, mind a B halmaznak elemei.

59. kép

Halmazok egyesítése

A metszetképzés során a létrejövő C halmaz elemszáma nem lesz nagyobb, mint a két eredeti halmaz közül a kisebb elemszámú. Annak eldöntésére, hogy az A egyik eleme Bnek is eleme-e, a korábban leírt eleme() függvényt használjuk. Mivel ebben egy teljes kere133

AZ ALGORITMIZÁLÁS ALAPJAI sést implementáltunk, célszerű a nagyobb elemszámú halmaz elemeit keresni a kisebb elemszámú halmazban, mert így az összes keresési lépések száma kisebb lesz. eljárás metszet ELEMSZÁMC = 0 ha ELEMSZÁMA < ELEMSZÁMB, akkor ciklus I = 0-tól (ELEMSZÁMB – 1)-ig ha eleme(A, ELEMSZÁMA, B[I]), akkor C[ELEMSZÁMC] = B[I] ELEMSZÁMC = ELEMSZÁMC + 1 elágazás vége ciklus vége különben ciklus I = 0-tól (ELEMSZÁMA – 1)-ig ha eleme(B, ELEMSZÁMB, A[I]), akkor C[ELEMSZÁMC] = A[I] ELEMSZÁMC = ELEMSZÁMC + 1 elágazás vége ciklus vége elágazás vége eljárás vége

11.3.1.4 Halmazok különbsége A és B halmaz különbsége az a C halmaz, amelynek elemei szerepelnek A-ban, de nem szerepelnek B-ben.

60. kép

Halmazok különbsége

Az eljárás megadásához ismét felhasználjuk az eleme() függvényt. C elemszáma legfeljebb akkora lehet, mint A-é.

134

AZ ALGORITMIZÁLÁS ALAPJAI eljárás különbség ELEMSZÁMC = 0 ciklus I = 0-tól (ELEMSZÁMA – 1)-ig ha nem eleme(B, ELEMSZÁMB, A[I]), akkor C[ELEMSZÁMC] = A[I] ELEMSZÁMC = ELEMSZÁMC + 1 elágazás vége ciklus vége eljárás vége

11.3.1.5 A részhalmazvizsgálat Azt mondjuk, hogy B részhalmaza A-nak (jelölése: B A), ha B minden eleme egyben eleme A-nak is. B A teljesül akkor is, ha B = A. Ilyenkor azt mondjuk, hogy B nem valódi részhalmaza A-nak. A vizsgálat egy eldöntés, meg kell vizsgálnunk, hogy B minden eleme szerepel-e A-ban. Ha igen, akkor B részhalmaza A-nak, különben nem. A definícióból következik, hogy ha Bnek nagyobb az elemszáma, mint A-nak, akkor semmiképpen sem teljesülhet, hogy B A.

61. kép

Részhalmazok

Adjunk meg egy logikai visszatérési értékű függvényt, amely eldönti, hogy B részhalmaza-e A-nak! függvény részhalmaz(A, ELEMSZÁMA, B, ELEMSZÁMB) ha ELEMSZÁMB > ELEMSZÁMA, akkor részhalmaz = hamis különben I = 0 ciklus, amíg (I < ELEMSZÁMB) és (nem eleme(A, ELEMSZÁMA, B[I]) I = I + 1 ciklus vége részhalmaz = (I < ELEMSZÁMB) elágazás vége függvény vége

135


11.3.1.6 Feladatok A fent leírtak felhasználásával 1. Készítsünk függvényt, amely eldönti, hogy az A és B halmazok diszjunktak-e. Két halmazt akkor nevezünk diszjunktnak, ha nincs közös elemük. A függvényt adjuk meg többféle módon is! (Pl. A és B diszjunkt, ha A-nak egy eleme sem szerepel B-ben, vagy ha A B = , vagy ha A-nak és B-nek nincs közös részhalmaza.) 2. Készítsünk függvényt, amely eldönti, hogy B valódi részhalmaza-e A-nak! B akkor valódi részhalmaza A-nak, ha teljesül, hogy B A és B A. 11.3.2 A lista A lista adatszerkezet dinamikus, homogén. Az adatszerkezet elemei között értelmezhető sorrend, és minden elemre igaz, hogy pontosan egy megelőzője és pontosan egy rákövetkezője van, kivéve az első és az utolsó elemet. Az első elemnek nincs megelőzője, az utolsó elemnek nincs rákövetkezője. Minden listának van első és utolsó eleme, kivéve az üres listát (empty list), melynek egyetlen eleme sincs. A lista első eleme a listafej (head). A lista vége (end) az utolsó elem. A lista farka (tail) az első n elem elhagyásával kapott lista. A lista esetében is tudnunk kell annak méretét, amely a benne tárolt elemek számát jelenti. Szeretnénk ismét hangsúlyozni, hogy ez a leírás a lista adatszerkezetre vonatkozik, és nem annak tárolási módjára. A tárolási mód (reprezentáció) ennél az adatszerkezetnél is lehet folytonos és szétszórt is.

11.3.2.1 Láncolt listák A szétszórt tárolás egyik gyakran alkalmazott módszere az ún. láncolt lista, amely lehet egyirányban vagy kétirányban láncolt. Beszélünk továbbá cirkuláris (körkörös) listáról is, mely szintén lehet egy- és kétirányban láncolt is. Láncolt listával azonban nemcsak lista adatszerkezetet, hanem bármilyen adatszerkezetet (tömböt, halmazt stb.) reprezentálhatunk. Lásd: 11.1 fejezet.

62. kép

136

Egyirányban láncolt lista


63. kép

Kétirányban láncolt lista

64. kép

Cirkuláris lista

A láncolt lista tárolási módszer esetében minden elem tartalmaz egy adattagot és egy vagy két mutatótagot. Az adattag az elem által tárolt érték, míg a mutató(k) szerepe a következő (és előző) elem kijelölése. Speciális az első elem, melynek nincs megelőzője, és az utolsó elem, melynek nincs következője. Az utolsó elem mutatótagja egy speciális elemre,a NIL-re mutat. (Minden olyan programozási nyelvben létezik implementációja a NIL-nek, amely támogatta a mutatók használatát.) A lista belépési pontja a fejnél van. Ezt a fejre mutató olyan elemmel valósíthatjuk meg, amelynek csak mutatótagja van, adattagja nincs.

65. kép

Listaelemek láncolt listában

Cirkuláris listánál az utolsó elem következőelem-mutatója nem a NIL-re, hanem az első elemre mutat. Kétirányú láncolás esetében az első elem előzőelem-mutatóját az utolsó elemre állítjuk. A cirkuláris listába is a fejmutatón keresztül léphetünk be. A lista bejárása a listaelemek elérését jelenti. Ha csak egy irányban (az elsőtől az utolsó felé) kell bejárnunk a listát, elegendő az egyirányú láncolás. Ha szükséges ismernünk egy elem megelőzőjét is, akkor viszont célszerű a kétirányú láncolás, bár enélkül is bejárható a lista a láncolással ellentétes irányban is: a megelőző elem az az elem, amelynek következőelem-mutatója éppen az aktuális elemre mutat. Ha viszont ezt a módszert használjuk, akkor az előző elem megtalálásához be kell járnunk a lista összes, az aktuális elem előtti elemét.

137

AZ ALGORITMIZÁLÁS ALAPJAI Egy elem beszúrása bárhová megtörténhet a listában. Speciális eset, ha a fej elé (új első elemként) vagy a vég mögé (új utolsó elemként) szúrunk be elemet. A beszúrás azért hatékonyabb, mint például a tömbnél, mert a már listában lévő elemek fizikai mozgatására nincs szükség. A beszúrás során helyet kell foglalnunk a memóriában az új elemnek, majd be kell állítani a megelőző elem (illetve kétirányú láncolásnál a rákövetkező elem) mutatóját erre a most beszúrt elemre. A fejnél és a végnél ettől különböző módon kellhet eljárnunk. (Cirkuláris lista esetében nem.)

66. kép

Elem beszúrása a láncolt listába

Az elem törlése nem igényel fizikai törlést. Bejárással megkeressük a törlendő elem megelőzőjét, majd annak következőelem-mutatóját a törlendő elem rákövetkezőjévé állítjuk. Ha a lista kétirányban láncolt, akkor a törlendő elem rákövetkezőjének előzőelemmutatóját a törlendő elemet megelőző elemre állítjuk. A fejnél és a végnél itt is ettől eltérő teendőnk lehet.

67. kép

Elem törlése a láncolt listából

11.3.3 A verem A verem (stack, LIFO) adatszerkezet egy olyan lista adatszerkezet, amelyben az új elemet mindig a lista elejére helyezhetjük el, illetve elemet is csak a lista tetejéről érhetünk el. A verem adatszerkezetben először mindig a legutoljára eltárolt elemhez férhetünk hozzá, miután ezt kivettük (töröltük), jöhet az utolsó előttinek eltárolt elem és így tovább.

138


68. kép

Verem

A verem reprezentációja történhet folytonos és szétszórt tárolási módszerrel is. 11.3.4 Sor A sor (queue, FIFO) adatszerkezet olyan lista, amely a fejnél bővíthető, de a végnél érhetők el az elemei. Azt az elemet érthetjük el először, amelyet először tároltunk el benne. A sor adatszerkezet segítségével valósítható meg pl. a billentyűzetpuffer, amely a billentyűzeten lenyomott gombok kódját tárolja a felhasználásig.

69. kép

Sor

11.3.5 Fa Az informatikában nagyon gyakran használt adatszerkezet. Találkozhatunk vele például az operációs rendszerek logikai fájlkezelésénél a könyvtárak szerkezetének tanulmányozásakor. A fa egy körmentes irányított gráf, a fa adatszerkezet hierarchikus. Az elemek alá-fölé rendeltségi viszonyban vannak. A gráf kiinduló eleme a gyökér, ennek nincs szülőeleme. A gráf többi elemére igaz, hogy pontosan egy szülő, és tetszőleges számú leszármazott (utód) eleme lehet, kivéve a levélelemeket. A levélelemeknek nincs utódja.

139


70. kép

Fa

Az informatikában fontos szerepe van az ún. bináris fáknak. Ezekben minden elemnek legfeljebb két rákövetkezője lehet (a szigorúan bináris fáknál ez a szám pontosan 0 vagy pontosan 2 lehet). Ezeket a rákövetkezőket szokás bal és jobb oldali rákövetkezőknek jelölni. A fa reprezentálása történhet folyamatos és szétszórt ábrázolási módszerrel is. Minden elemnél tárolni kell az adattagot, és szükség van egy bal és egy jobb oldali rákövetkezőelem-mutatóra. A levélelemek mutatói NIL-ek.

71. kép

Bináris fa

A fák esetében az elemek elérése szintén bejárással történik. A fabejárás többféle módon történhet annak függvényében, hogy milyen céllal hoztuk létre a fát. Preorder bejárás: ha a fa üres, akkor vége az eljárásnak. Ha nem, akkor dolgozzuk fel a gyökérelemet, majd preorder eljárással járjuk be a bal oldali részfát, majd a jobboldali részfát. 140


72. kép

Preorder fabejárás

Inorder bejárás: ha a fa üres, akkor vége az eljárásnak. Ha nem, akkor járjuk be inorder módon a bal oldali részfát, dolgozzuk fel a gyökérelemet, végül járjuk be inorder módon a jobboldali részfát.

73. kép

Inorder fabejárás

Posztorder bejárás: ha a fa üres, akkor vége az eljárásnak. Ha nem, akkor posztorder módon járjuk be a bal oldali, majd a jobb oldali részfát, végül dolgozzuk fel a gyökérelemet.

141


74. kép

Posztorder fabejárás

11.3.6 A háló A fa adatszerkezettel szemben ennél az adatszerkezetnek egy elemnek akárhány megelőzője és rákövetkezője lehet. Egy elem akár saját maga megelőzője és rákövetkezője is lehet. Reprezentációja ún. szomszédossági listával vagy szomszédossági mátrixszal történhet.

75. kép

142

Háló és reprezentációja

AZ ALGORITMIZÁLÁS ALAPJAI A gráf egy útja egy listát alkotó elemsorozat: hogyan juthatok el az A csomópontból Bbe. A háló nem körmentes, vagyis létez(het)nek benne körök. A körút olyan út, amelynek utolsó eleme egyben az első is. 11.4 ÖSSZEFOGLALÁS Ebben a leckében betekintést adtunk az informatikában gyakran használt dinamikus adatszerkezetek világába. Szót ejtettünk a különböző adatszerkezetek reprezentációiról is. Mivel azonban ezek az adatszerkezetek, illetve ezek közül nem mindegyik áll rendelkezésünkre a különböző programozási nyelvek szolgáltatásaként (van olyan nyelv, amelyik készen adja a programozónak például a listát vagy a vermet, míg más nyelveknél a programozó dolga a megvalósítás), ezek implementálásától és kezelésének algoritmusszintű bemutatásától eltekintettünk. Az érdeklődők számos irodalomban megtalálják ezeket az algoritmusokat, de ezek megértéséhez, főként szétszórt tárolási módszerek alkalmazása mellett általában szükséges az adott nyelv mélyebb ismerete.

11.5 ÖNELLENŐRZŐ KÉRDÉSEK Milyen esetekben indokolt dinamikus adatszerkezetek használata? Gondolja át, milyen adatszerkezetek alkalmazása lehet szükséges egy olyan szoftverben, amely nyilvántartja egy könyvtár állományát és a kölcsönzések adatait, az ezekhez kapcsolódó egyéb adatokkal együtt. 3. Mi a különbség fa és bináris fa között? 4. Mi a különbség sor és verem között? 1. 2.

143


12. ÖSSZEFOGLALÁS 12.1 A KURZUSBAN KITŰZÖTT CÉLOK ÖSSZEFOGLALÁSA Az algoritmizálás alapjainak megismerése minden informatikával foglalkozó szakember számára szükséges lehet munkája során. A szoftvertechnológia fejlődésével átalakulóban van ez a szükséglet, hiszen az újabb szoftverek újabb eszközei sok olyan feladat megoldását automatizálják, amelyeket korábban csak programozási eszközökkel lehetett megvalósítani. Nem szabad azonban megfeledkeznünk arról, hogy az algoritmusok tervezése és megvalósítása nem azonos tevékenység a programozással, még akkor sem, ha a programozás során nagyon gyakran van szükségünk algoritmusokra. Az algoritmizálás nem kötődik csupán egyetlen programozási nyelvhez, és algoritmusokat nemcsak programozási feladatok megoldásakor használunk. Jegyzetünk célja, hogy bevezetést adjunk az algoritmusok megismeréséhez. A jegyzetet elsősorban az informatikával, és főként a programozással nem szakmaszerűen foglalkozó szakemberek képzésében tartjuk felhasználhatónak, bár a jegyzetben szereplő ismereteket azok is fel tudják használni, akik a programozással (és így az algoritmusokkal) szorosabb kapcsolatban állnak tanulmányaik során. Mivel az algoritmusok tágabb értelemben adatokon végzett manipulációk sorozata, szükséges, hogy az informatikában gyakran alkalmazott adatszerkezetekbe is betekintést nyerjünk. Jegyzetünk azokat az adatszerkezeteket tárgyalta, amelyek az alapvető algoritmusok megadásához és elemzéséhez szükségesek. Az adattípusokat, adatszerkezeteket vizsgáló és az ehhez kapcsolódó tudományok (pl. típuselmélet) a formális matematika eszközeit alkalmazzák. Jegyzetünkben ezeket az eszközöket nem használtuk, az absztrakt és formális megközelítés helyett a gyakorlati alkalmazások bemutatása volt a célunk.

12.2 TARTALMI ÖSSZEFOGLALÁS 12.3 A TANANYAGBAN TANULTAK RÉSZLETES ÖSSZEFOGLALÁSA 12.3.1 Bevezetés A bevezetésben áttekintettük a kurzus céljait. Szót ejtettünk arról, hogy az informatika mely területein lehet szükség algoritmusok ismeretére, illetve milyen kapcsolat van az algoritmusok és az ún. imperatív programozási nyelvek között. 12.3.2 Az algoritmusok jellemzői és leírásuk Ebben a leckében az algoritmusok jellemzőiről, illetve a megadásukkal kapcsolatos legfőbb jellemzőkről beszéltünk. Az algoritmusokkal szemben támasztott követelmények közül az egyik legfontosabb az egyértelműség. Ez vonatkozik a probléma felvetése és a megoldás kérdéseire. Ha nem definiáljuk egyértelműen, hogy mi a feladat, akkor algoritmust sem tudunk rá adni. Ha megadjuk egy probléma megoldásának egy algoritmusát, akkor tudnunk kell azt pontosan leírni is. Ehhez különféle algoritmusleíró eszközöket használhatunk. A 2. lecke ezen eszközöket és jellemzőiket is bemutatta. 144

AZ ALGORITMIZÁLÁS ALAPJAI 12.3.3 Adatok, adatszerkezetek Ebben a leckében az algoritmusokban és a programokban megjelenő adatokról és azok jellemzőiről beszéltünk. Az algoritmusok absztrakt eszközök, de a belőlük készült programok konkrét utasítássorozatok. Az adatok kapcsán is megfigyelhető ilyen kettősség: míg az algoritmusok megadásakor nem tulajdonítottunk jelentőséget az feldolgozandó adatok típusának (kivéve az egyértelmű helyzeteket: pl. összegzés nem hajtható végre sztringeken), a konkrét nyelvi implementációkban központi kérdés is lehet, hogy milyen adattípusokat, adatszerkezeteket használjunk, és ezeket hogyan deklaráljuk. A lecke bemutatta az algoritmizálásban és a programozásban alkalmazott gyakori adattípusokat és adatszerkezeteket. Szót ejtettünk a literálokról és változókról, a változók azonosítóiról, jellemzőikről – adattípus: értékkészlet és értelmezett műveletek köre, hatókör, élettartam –, memóriabeli reprezentálásukról és az általuk felvehető értékekről. 12.3.4 Adatsorhoz egy adatot rendelő eljárások 1. Az elemi algoritmusok között ebben a leckében az összegzés, eldöntés, megszámlálás, kiválasztás és szélsőérték-kiválasztás tételeivel ismerkedtünk meg. 12.3.5 Adatsorhoz egy adatot rendelő eljárások 2. Keresések Ez a lecke a keresőeljárásokat, illetve azok közül az egyszerűbbeket mutatta be. A keresés az informatikában a leggyakoribb műveletek közé tartozik. Azért használunk adatbázisokat, azért fontos az adatbázisok minél hatékonyabb gépi megvalósítása, hogy minél gyorsabban találjunk meg bennük keresett adatokat. 12.3.6 Adatsorhoz adatsort rendelő eljárások 1. Ebben a leckében két gyakran használt eljárás algoritmusát tekintettük át: a kiválogatásét és az összefuttatásét. 12.3.7 Adatsorhoz adatsort rendelő eljárások 2. Rendező eljárások A kereséseket bemutató leckében szót ejtettünk az adatok rendezettségének fontosságáról. Rendezett adatsorokon gyorsabbá tehető a keresés, mint rendezetleneken, ezért fontos a különböző rendező eljárások ismerete. 12.3.8 Példák az eljárások alkalmazására Ebben a leckében számos példával találkozhat az olvasó. A példák esetében nem fontosak a konkrét tárolt értékek, ezek pontos ismerete nélkül is készíthetünk algoritmusokat. A konkrét adatok csak azért szerepeltek ebben a leckében, hogy az algoritmusokkal generált eredmények összevethetők legyenek az Olvasó által helyesnek vélt eredményekkel, így az algoritmusok ellenőrizhetőbbek. 12.3.9 Az algoritmusok hatékonysága Ez a rövid lecke csak betekintést nyújt az ún. bonyolultságelméletbe. Az algoritmusok hatékonyságának mérése nagyon fontos, mert ezzel egy algoritmusnak nemcsak a gyorsasága mérhető, hanem más „költsége” is. 145

AZ ALGORITMIZÁLÁS ALAPJAI 12.3.10 Alprogramok A strukturált programozás egyik fontos eszköze volt az alprogramok megjelenése a magas szintű programozási nyelvekben. A strukturált programozás óta már megjelent egy újabb paradigma, az ún. objektumorientált programozás, de az alprogramok szerepe nem csökkent. A programokban kétféle alprogram használható, az eljárás és a függvény. Az eljárás tulajdonképpen egy névvel ellátott kódrészlet, így tekinthető a programozási nyelv utasításkészletét kibővítő eszköznek is. A függvényeknek nincs mellékhatásuk, van viszont visszatérési értékük, így a függvényeket a programozási nyelvben használható operátorok körét kibővítő eszközként is felfoghatjuk. Az alprogramok paraméterezhetők. Ebben a leckében szót ejtettünk a formális és aktuális paraméterlistáról, illetve érintőlegesen a paraméterkiértékelés kérdéseiről is. Szintén ebben a fejezetben tárgyaltuk a hatókör és az élettartam kérdéseit is. 12.3.11 Dinamikus adatszerkezetek A utolsó fejezetben az informatikában gyakran használt dinamikus adatszerkezetek legfontosabb jellemzőit tekintettük át.

12.4 ZÁRÁS A jegyzet, mint azt a bevezetőben is leírtuk, főként azon hallgatók számára készült, akiknek tanulmányaik során találkozniuk kell algoritmusokkal, de az algoritmizálás és a programozás nem tartozik a fő tárgyaik közé. A jegyzet számos pontján találkozhatunk nyitva hagyott kérdésekkel, melyek kutatását az olvasóra bíztuk. Ennek az az oka, hogy ezek a kérdések általában messze túlmutatnak jelen kötet határain és céljain, viszont fontosnak tartottuk megemlítésüket, mert a témához szorosan kapcsolódó kérdésekről van szó. Reményeink szerint a tananyagot feldolgozó hallgatók más informatikai kurzusok tanulmányozása során is hasznát veszik az itt leírtaknak.

12.5 EGYÉB

146


13. KIEGÉSZÍTÉSEK 13.1 IRODALOMJEGYZÉK Könyv KNUTH: A számítógép-programozás művészete. 1–3. kötet. Műszaki Könyvkiadó, Budapest, 1987, 1988 FEKETE ISTVÁN: Algotimusok és adatszerkezetek I. Egyetemi jegyzet. Eötvös Loránd Tudományegyetem, 2009 IVÁNYI ANTAL et al.: Informatikai algoritmusok 1. ELTE Eötvös Kiadó, Budapest, 2004 JÁRDÁN TAMÁS – POMAHÁZI SÁNDOR: Adatszerkezetek és algoritmusok. EKTF Líceum Kiadó, Eger, 1996 JUHÁSZ ISTVÁN: Informatika II. Adatszerkezetek és algoritmusok. Egyetemi jegyzet, Kossuth Lajos Tudományegyetem, 2000 JUHÁSZ ISTVÁN – KÓSA MÁRK – PÁNOVICS JÁNOS: C példatár. Panem Könyvkiadó, Budapest, 2005 NYÉKYNÉ GAIZLER JUDIT szerk.: Programozási nyelvek. Kiskapu Kiadó, Budapest, 2003 THOMAS H. CORMEN – CHARLES E. LEISERSON – RONALD L. RIVEST: Algoritmusok. Műszaki Könyvkiadó, Budapest, 1997 DONALD E.

Elektronikus dokumentumok / források László: NIIFP hálózati multimédia pilot projekt. Budapest, SZTAKI, 2008. [elektronikus dokumentum] [2010.február 1.]

KOVÁCS

147

ALGORITMIZÁLÁS ALAPJAI. Tömösközi Péter

Recommend Documents