Algoritmus készítés Szoftver fejlesztése. 2. Összetett adatszerkezetek 2.1. Egydimenziós tömbök 2.2. Stringek. 2.3

TARTALOMJEGYZÉK

1. Alapfeladatok és algoritmusok

1.1.1.

Algoritmus készítés

1.1.1. Az algoritmus fogalma 1.1.2. Algoritmus tervezés, moduláris programozás 1.1.3. Strukturált program, mondatszerű leírás

1.2. Szoftver fejlesztése 2.

Összetett adatszerkezetek

2.1. Egydimenziós tömbök 2.2. Stringek 2.3. Többdimenziós tömbök

2.3. A rekord fogalma 3.

Programozási tételek

3.1. Egy sorozathoz egy értéket rendelő algoritmusok 3.1.1. Sorozatszámítás 3.1.2. Eldöntés 3.1.3. Kiválasztás 3.1.4. Lineáris keresés 3.1.5. Megszámlálás 3.1.6. Maximum kiválasztás 3.2. Egy sorozathoz egy sorozatot rendelő algoritmusok 3.2.1. Kiválogatás 3.2.2. Másolás 3.2.3. Rendezés 3.3. Több sorozathoz egy sorozatot rendelő algoritmusok 3.3.1. Egyesítés 3.3.2. Metszetképzés 3.3.3. Különbségképzés 3.3.4. Rendezett sorozatok egyesítése

3.4. Egy sorozatból egy sorozatot előállító algoritmusok 3.4.1. Szétválogatás

4.

A rekurzió fogalma, rekurzív algoritmusok

5.

Rendezési és keresési algoritmusok

5.1.

Tömbök rendezése.

5.1.1.

Rendezés beszúrással

5.1.2.

Rendezés közvetlen kiválasztással

5.1.3.

Cserélő rendezések

5.1.4.

Cserélő rendezések - Buborék rendezés

5.1.5.

Gyorsrendezés (Quicksort)

5.2.

Keresési eljárások

6.

Adatszerkezetek

6.1. Lineáris listák 6.1.1. Szekvenciális helyfoglalás 6.1.2.

Láncolt helyfoglalás, láncolt sor

6.1.3. Ciklikusan láncolt listák 6.1.3.

Kétszeresen láncolt listák

6.2.

Hasító táblázatok

6.3. Fák, bináris fák

7.

Függvények általános jellemzői

8.

Adatállományok kezelése

9.

Gráfalgoritmusok 9.1. Alapfogalmak, jelölések 9.2. A legrövidebb utak problémája (egy forrásból) 9.3. Az összes csúcspár közötti távolság meghatározása 9.4. Mélységi bejárás 9.5 A szélességi bejárás 9.6 Maximális párosítás páros gráfokban

10. Turing-gépek. Az NP nyelvosztály 2 Problémaosztályok, algoritmusok Segédlet

PMMK Számítástechnika Tanszék

1. Alapfeladatok és algoritmusok 1.1. Algoritmus készítés Áttekintés:    

Az algoritmus fogalma, tulajdonságai Az algoritmus tervezés lépései, moduláris programozás A strukturált program fogalma, elemei Algoritmus leíró eszközök, a pszeudokód

1.1.1. Az algoritmus fogalma Feladat: homokvár körüli vizesárok feltöltése tengervízzel. Megoldás: Vedd a kezedbe a kisvödröt. Ismételd az alábbiakat mindaddig, amíg tele nem lesz a vizesárok: Merítsd tele a vödröt tengervízzel. Töltsd a vizesárokba. Tedd le a kisvödröt. Bár a fenti tevékenységek ismétlést tartalmaznak, véges számú lépésben a feladat megoldásához (megtelik a vizesárok) vezetnek. Algoritmusnak nevezzük az egyértelműen előírt módon és sorrendben végrehajtandó tevékenységek véges sorozatát, melyek alapján egy feladattípus véges számú lépésben megoldható. Az algoritmus leírásának egyértelműnek, pontosnak, lépésenként végrehajthatónak kell lennie. FONTOS, az algoritmus NYELVFÜGGETLEN, vagyis nem tartalmaz olyan jelöléseket, elemeket, ami csak egy, vagy néhány programozási nyelvben fordul elő! Az algoritmus struktúráját szekvenciák, szelekciók és iterációk alkotják, melyeket tetszőleges mélységben egymásba lehet ágyazni. A legtöbb számítógépben csak egy processzor van, amely képtelen a párhuzamos feldolgozásra - mi sem foglalkozunk ilyen algoritmusokkal. Az algoritmus alapján elkészítendő programjainkban a számítógép egyszerre csak egy tevékenységet képes végrehajtani, majd ezután kezd hozzá a következő tevékenységhez, vagy megvizsgál egy feltételt és annak függvényében az egyik, vagy egy másik tevékenység végrehajtását kezdi el. Mi a C++ nyelvet használjuk majd a feladataink végső megoldásához. Egy számítógép által érthető nyelven megírt algoritmust programnak nevezünk.

Az algoritmus, illetve program leglényegesebb tulajdonságai, és a vele szemben támasztott követelmények: 

Az algoritmus lépésekből (elemi tevékenységekből, instrukciókból, utasításokból) áll. Az algoritmus végrehajtása lépésenként történik. A végrehajtás során megtett lépések sorozatát folyamatnak (processznek ) nevezzük.



Minden lépésnek egyértelműen végrehajthatónak kell lennie. Az algoritmus leírásában a végrehajtót minden lehetséges esetre fel kell készíteni. A végrehajtónak minden egyes lépés után tudnia kell, hogy mi lesz a következő lépés.



Egy algoritmusban hivatkozhatunk összetett lépésekre is, melynek részletezését később adjuk meg. A részletezés során olyan szintig kell eljutnunk, ahol már végrehajtható (elemi) tevékenységek szerepelnek.



A végrehajtásnak mindig van valamilyen tárgya. Ezeket a tárgyakat a programozásban adatoknak nevezzük. Az adatoknak tulajdonságai vannak. Az algoritmus készítésénél csak azokat az adatokat és tulajdonságokat vesszük figyelembe, amelyek a feladat végrehajtásához szükségesek. Ezt a válogatási, egyszerűsítési eljárást absztrakciónak nevezzük.



A végrehajtandó utasításoknak valamilyen célja van, a végrehajtás során megváltoznak az adatok bizonyos tulajdonságai.



Az algoritmusnak véges számú lépésben el kell vezetnie a feladat megoldásához. A végesség a meghatározásban kétszer is szerepel. A feladat megoldására szolgáló lépések száma is vége kell legyen, de minden egyes lépésnek is be kell fejeződnie.



Az algoritmusnak általában vannak bemenő (input) adatai, melyeket felhasznál. Ezeket az adatokat nevezzük inputnak. Az input adatok bizonyos jól meghatározott halmazból kerülnek ki.



Az algoritmusnak legalább egy kimenő (output) adatot produkálnia kell. Bármilyen fantasztikus dolgokat is művel egy folyamat, ha nem kommunikál a külvilággal, definíció szerint nem algoritmus. (Az output természetesen nem feltétlenül numerikus érték, lehet szöveg, grafika, vagy más egyéb információ, amely az algoritmus eredményeként jön létre.)

3 Problémaosztályok, algoritmusok Segédlet




Az algoritmus legyen hatékony. Az instrukciók legyenek könnyen követhetőek, pontosak, egyszerűen végrehajthatóak.



Legyen a program felhasználóbarát, a felhasználó szempontjait maximálisan vegye figyelembe.

1.1.2. Algoritmus tervezés, moduláris programozás Az algoritmus tervezésének első lépése a feladat körültekintő és alapos elemzése, a probléma megfogalmazása. A feladat leírását feladat specifikációnak is szokás nevezni, ezt írásban is rögzíteni kell. Az algoritmusok leírására számtalan eszköz létezik, ilyen a mondatszerű leírás, a folyamatábra, a stuktogram vagy a Jackson jelölés. Feladat specifikáció Egy számítógépen megoldandó feladat felmerülésekor törekedni kell arra, hogy a feladat megfogalmazása egyértelmű legyen, valamennyi lehetséges esetet lefedjen. A megrendelő gyakran hiányos, és/vagy pontatlan igényekkel lép fel, a megoldási módszer keresése viszont csak akkor kezdődhet el, ha a feladatot pontosan ismerjük és írásban is rögzítettük, vagyis megadtuk a feladat specifikációt. Adatok tervezése Mivel az algoritmus adatokon dolgozik, meg kell tervezni a feladatban szereplő külső és belső adatokat, adat szerkezeteket. Csak ezután kezdhetünk hozzá az adatokat mozgató, manipuláló lépések megtervezéséhez. Moduláris programozás Az algoritmus (program) tervezésének alapja a dekompozíció. A bonyolultabb feladatokat általában nem lehet egyszerre megoldani, ezért részekre, modulokra kell azokat bontani. A részekre ki kell dolgozni a megoldás menetét, majd a részeket újra össze kell állítani, hogy azok együttműködve, egymásra épülve a teljes feladat megoldását szolgáltassák. A moduláris programozás olyan programozási mód, melyben a teljes program modulokból áll. Az egyes modulok jól meghatározott részfeladat megoldását végzik, kezelhető méretűek, egyértelmű céljuk van és jól definiáltan csatlakoznak a program többi moduljához. A moduláris programozás irányelvei a következők: 

"Oszd meg és uralkodj" elv: A feladatokat egyértelműen le kell osztani modulokra. A modulok belső működésébe más modul nem szól bele. A modul a saját feladatának tökéletes elvégzéséért felelős. Fontos, hogy a modulok lehetőleg egymástól függetlenül működjenek, mert így a hibák kiszűrése egyszerűbb, a feladat átláthatóbb, könnyebben módosítható.



Adatok (információ) elrejtésének elve: Az egyes modulok csak saját adataikon dolgozzanak, csak akkor használjanak közös adatokat, ha ez elkerülhetetlen.



Döntések elhalasztásának elve: Csak akkor hozzunk meg egy döntést, ha az elengedhetetlenül szükséges. Mindazon döntéseket, amelyekhez még nincs elég ismeretünk, halasszuk későbbre - különben előfordulhat, hogy egy korán meghozott döntést a későbbiekben meg kell változtatnunk.



Döntések kimondásának elve: A feladat megoldása során, ha már meghoztunk egy döntést, azt le kell rögzíteni, mert különben erről később esetleg megfeledkezve, ellentmondásos döntéseket hozhatunk.

A modulokra bontás iránya alapvetően kétféle lehet:  

Felülről lefelé (top-down) tervezés esetén a megoldást felülről lefelé, fokozatosan, lépésenként finomítjuk. A feladatot részfeladatokra, a részfeladatokat ismét kisebb feladatokra bontjuk mindaddig, amíg az úgynevezett elemi tevékenységekhez jutunk. Az elemi tevékenységek tovább nem bonthatók, egy lépésben végrehajthatók. Az alulról felfelé (bottom-up) tervezés lényege, hogy már meglévő, kész modulokból építkezünk. Erre akkor kerül sor, ha bizonyos részfeladatokat egy előző feladat kapcsán már megoldottunk (gondolva a későbbi felhasználásokra is), vagy amikor egy rutingyűjteményt (szoftvert) vásároltunk.

A bonyolult feladatok megoldásánál többnyire mind a felülről lefelé, mind az alulról felfelé tervezést használjuk, megfelelően ötvözve a két módszert.

1.1.3. Strukturált program, mondatszerű leírás Tetszőleges algoritmus felépíthető a következő elemekből:    

Szekvencia: Egymás után végrehajtandó tevékenységek sorozata. Szelekció: Választás megadott tevékenységek közül Iteráció: Megadott tevékenységek ismételt végrehajtása. Feltétel nélküli ugrás: Vezérlés átadása a program egy megadott pontjára.

Tulajdonképpen a feltétel nélküli ugrás nem igazán szükséges elem, gyakori használata áttekinthetetlenné teszi a programot.



Böhm és Jacopini tétele A szekvencia, szelekció és az iteráció segítségével minden olyan algoritmus felépíthető, amelynek egy belépési és egy kilépési pontja van.

Strukturált program A csak szekvenciákból, szelekciókból és iterációkból építkező programot strukturált programnak nevezzük. A strukturált programozásban nem megengedett a feltétel nélküli ugrás, így többek között a ciklusból sem ugorhatunk ki. Ebből az is következik, hogy a program minden vezérlő szerkezetének (szekvencia, szelekció, iteráció) - és magának a teljes programnak is - egyetlen belépési és egyetlen kilépési pontja van, így a program lényegesen áttekinthetőbb. A strukturált programozás általános módszereit E. W. Dijkstra dolgozta ki. Mondatszerű leírás A mondatszerű leírás, vagy pszeudokód lényege, hogy az algoritmust mondatszerű elemekből építjük fel. Ez nagyon hasonlít a beszélt nyelvre, illetve annak írásos formájára, de be kell tartanunk bizonyos szabályokat, a struktúrák képzésére megállapodás szerinti formákat és szavakat használunk.

Az alapelemek az alábbiak: bevitel, kivitel, szekvencia, szelekciók, ciklusok

Bevitel, kivitel: Be: ... változók felsorolása ...[......................................] az adatokkal szemben támasztott követelmények Ki: ... kifejezések felsorolása... [......................................] a kiírás formájára vonatkozó követelmények

Szekvencia: Az egymás után végrehajtandó tevékenységek sorozata. Tevékenység1 Tevékenység2 Tevékenység3 Az egy sorba írt tevékenységeket kettőspont választja el: Tevékenység1 : Tevékenység2 : Tevékenység3 PÉLDA: Elindulás autóval... Értékadó utasítás: a szekvencia egy speciális fajtája, formája: változó = kifejezés

Szelekciók (elágazások, feltételes utasítások): Programrészek közötti választás Egyágú szelekció Ha Feltétel akkor Utasítás(ok) Elágazás vége Jelentése: Ha Feltétel teljesül, akkor az Utasítás(ok) végrehajtásra kerülnek, egyébként nem. A program az Elágazás vége után folytatódik.

Kétágú szelekció Ha Feltétel akkor Utasítás(ok)1 Egyébként Utasítás(ok)2 Elágazás vége



Jelentése: Ha Feltétel teljesül, akkor az Utasítás(ok)1 kerül(nek) végrehajtásra, egyébként Utasítás(ok)2. A program mindkét esetben az Elágazás vége után folytatódik. PÉLDA: Ha süt a nap, akkor kimegyek napozni egyébként kitakarítom a szobámat. Elágazás vége Szelekció IGAZ és HAMIS ágán is állhat újabb szelekció. Ezeket egymásba ágyazott szelekcióknak nevezzük. Az ilyen egymásba ágyazott szelekciók speciális esete a többágú szelekció. Az egy/kétágú szelekció valamilyen (logikai)feltételtől függő tevékenység végrehajtás, míg a többágú szelekció egy kifejezés (egész) értékétől függő tevékenység végrehajtás. Minden többágú szelekció megoldható egymásba ágyazott kétágú szelekcióval. Többágú szelekció Elágazás kifejezés szerint értékcsoport1 esetén Utasítás(ok)1 értékcsoport2 esetén Utasítás(ok)2 .......... értékcsoportn esetén Utasítás(ok)n egyéb esetben Utasítás(ok)n+1 Elágazás vége

Az egyes értékcsoportok véges, diszkrét halmazokat alkotnak! Egy értékcsoportot, az összes elemének felsorolásával lehet megadni. Jelentése: Ha a kifejezés értéke valamelyik értékcsoport tartományába esik , akkor a neki megfelelő utasítás(oka)t kell végrehajtani, majd a feladat megoldása az Elágazás vége után folytatódik.

PÉLDA: Elágazás Piros lámpa esetén Megállok : Kézifék beh. Sárga lámpa esetén Megállok : Kézifék beh Zöld lámpa esetén Továbbhaladok Elágazás vége Ha egymásba ágyazott szelekciók esetén pl. mindkét szelekció igaz ágán ugyanazt a tevékenységsorozatot kell végrehajtani, akkor a feltétel megfogalmazható összetett logikai kifejezésként és csak egy szelekcióra van szükség, a már megbeszélt logikai operátorok segítségével.

Iteráció (Ciklus): Valamely tevékenység sorozat ismételt végrehajtását jelenti. Az ismétlés feltételhez kötött.

Példa: számolj el 50-ig… 1. 2. 3. 4. 5.

Gondolj az 1-es számra, takard el a szemedet Mondd ki hangosan a gondolt számot Növeld meg eggyel a gondolt számot A gondolt szám nagyobb, mint 50 ? Ha nem, akkor folytasd a 2-es sorszámú feladattól. Miután kimondtad hangosan az 50-et is, indulj megkeresni a társaidat.

A programozási nyelvekben bizonyos utasítások ismétlését biztosító programszerkezeteket iterációnak vagy ciklusnak nevezzük. Az ismétlés mindaddig tart, amíg az ismétlési, vagy lefutási feltétel igaz. Vannak olyan programszerkezetek is, ahol a ciklus akkor fejeződik be, amikor egy meghatározott kilépési feltétel válik igazzá, vagyis az ismétlés addig tart, amíg a kilépési feltétel hamis. A C nyelvben valamennyi ciklus-utasításban lefutási feltételt kell megfogalmazni. A fenti kis feladat megoldása pszeudokóddal is leírható: Program Változók: gondolt_szam: pozitív egész szám gondolt_szam = 1 Ciklus 6 Problémaosztályok, algoritmusok Segédlet


Ki: gondolt_szam // Ciklusmag utasításai gondolt_szam = gondolt_szam + 1 amíg gondolt_szam <= 50 Ciklus vége Ki: "Aki bújt, aki nem, megyek !" Program vége

A ciklusok két típusát különböztetjük meg: - Elöltesztelő ciklus - Hátultesztelő ciklus

Elől tesztelő ciklus Ciklus amíg Lefutási feltétel Ciklusmag utasításai Ciklus vége Működése A ciklusmag utasításait mindaddig kell végrehajtani. amíg a Lefutási feltétel igaz. Ha a lefutási feltétel hamissá válik, a végrehajtás a ciklus vége után folytatódik. Ha a lefutási feltétel már a ciklusba való belépéskor hamis a ciklusmag utasításai egyszer sem hajtódnak végre. Tehát a ciklusfeltétel kiértékelése a ciklusmag előtt történik meg, és lehet olyan eset, mikor a ciklusmag egyszer sem fut le, PÉLDA: Ciklus amíg van nálam "Mosópor reklám anyag" elmegyek a köv. lakásig bedobom a csomagot Ciklus vége

Az előreolvasás fogalma: Az elöltesztelő ciklus megvalósítása mindig előreolvasással történik. Ez azt jelenti, hogy a feltételben vizsgált adatot előbb meg kell határozni (értékadás vagy beolvasás a billentyűzetről), és azután megvizsgáljuk, hogy a megadott érték megfelel-e a lefutási feltételnek, beléphetünk-e a ciklusmagba. A ciklusmagban pedig biztosítanunk kell a feltétel hamissá válását, különben ha nem változik meg a feltétel, mindig igaz lesz, sohasem lépünk ki a ciklusból, végtelen ciklust kapunk. A biztosíték a feltétel hamissá válásához vagy a megadott érték növelése / csökkentése, vagy újbóli beolvasása, ami a ciklusmag utolsó utasítása kell legyen, így a feltétel kiértékelése szempontjából ismét van egy előre meghatározott érték!

Hátul tesztelő ciklus: Ciklus Ciklusmag utasításai mígnem Kilépési feltétel Ciklus vége Működése: A ciklusmag utasításait mindaddig kell végrehajtani. amíg végre a Kilépési feltétel igazzá válik. Ha a Kilépési feltétel igazzá válik, a végrehajtás a ciklus vége után folytatódik. A ciklusmag utasításait egyszer mindenképpen végrehajtja a rendszer, mivel a Kilépési feltétel kiértékelése a ciklusmag utasításainak végrehajtása után történik.

PÉLDA Ciklus leszedek egy almát a fáról mígnem tele a kosár Ciklus vége

A legtöbb magasszintű programnyelvtől eltérően a C nyelvben a hátul tesztelő ciklus megvalósítása Lefutási feltétel megfogalmazásával, az alábbi pszeudokód szerint történik: Hátul tesztelő ciklus a C-ben



Ciklus Ciklusmag utasításai amíg Lefutási feltétel Ciklus vége Működése: A ciklusmag utasításait mindaddig kell végrehajtani. amíg a Lefutási feltétel igaz. Ha a lefutási feltétel hamissá válik, a végrehajtás a ciklus vége után folytatódik. A ciklusmag utasításait egyszer mindenképpen végrehajtja a rendszer, mivel a lefutási feltétel kiértékelése a ciklusmag utasításainak végrehajtása után történik.

A lefutási feltétel és a kiugrási feltétel kapcsolata. Gyakran előfordul, hogy a feladat szövegében a feltétel úgy van megfogalmazva, hogy mikor kell az ismétlődő eseményeket befejezni (kiugrási feltétel). Pl. a testmagasság 110 – 210 cm jelentése: jó eset, ha a testmagasság 110 és 210 cm között van, rossz eset, ha 110 cm alatti vagy 210 cm-nél nagyobb. Mivel a ciklusunk feltétele lefutási feltétel kell legyen, vagyis mindig ciklusban bennemaradási feltételt kell megfogalmaznunk, ezért valamilyen módon a megadott kiugrási feltételt lefutási feltétellé kell konvertálni! A megoldás a DeMorgan azonosságok alkalmazása, az összetett logikai kifejezés negációjával: I, II,

nem(A vagy B) = nem A és nem B nem(A és B) = nem A vagy nem B

Példák: (logikai feltételek értéke IGAZ és HAMIS illetve C-ben NEM0 és 0) Állítás (jó eset) Tagadás (rossz eset) megvalósítás C-ben a<>0 a=0 a==0 a=0 a<>0 a!=0 a>0 a<=0 a<=0 a=0 és b=0 a<>0 vagy b<>0 a!=0 || b!=0 a>0 vagy b<=0 a<=0 és b>0 a<=0 && b>0 a>5 és a<10 a<=5 vagy a>=10 a<=5 || a>=10 a<5 vagy a>10 a>=5 és a<=10 a>=5 && a<=10

Az elöltesztelő ciklus speciális esete, a Növekményes (számláló) ciklus. Ennél a szerkezetnél nem a feltétel teljesüléséig tart a ciklus, hanem pontosan ismerjük a lefutások számát. Minden Növekményes ciklus megoldható elöltesztelős ciklussal de fordítva ez már nem igaz! Növekményes (számláló) ciklus Ciklus ciklusváltozó = ....kezdőértéktől .... végértékig .... lépésközzel Ciklusmag utasításai Ciklus vége Működése: A ciklusmag utasításai addig és annyiszor hajtódnak végre, míg a ciklusváltozó a kezdőértéktől a végértékéig a lépésköznyi növekedéssel vagy csökkenéssel el nem jut.

FELADATOK 1.1. feladat: Készítsen programot, amely bekéri egy felnőtt testmagasság (110-210 cm) és testsúly (30-150 kg) adatait, majd kiírja azokat. Csak a megadott határok közötti értékeket fogadhat el. Megoldás: Pontosítsuk a feladatot: Ha nem a megadott határok közötti értéket kaptam, akkor álljon le a program ? Válasz: Nem! 8 Problémaosztályok, algoritmusok Segédlet


Elemezzük a feladatot: Külön ciklussal fogjuk bekérni a magasságot, külön a testsúlyt. Így egyszerűbb a lefutási feltételek megfogalmazása és csak a hibásan megadott adat újra bevitelét kérjük. A "bekérési" ciklus addig kell fusson, amíg hibás a kapott érték ! Pszeudokód: Program Változók: magassag, suly (pozitív valós értékek) Ciklus Be: magasság [110-210 cm] amíg (magassag < 110 vagy magassag > 210) Ciklus vége Ciklus Be: suly [30-150 kg] amíg (suly < 30 vagy suly > 150) Ciklus vége Ki: magassag, suly Program vége

A hátultesztelő ciklusnál a ciklusmag utasításait egyszer mindenképpen végrehajtja a rendszer. Ez nem mindig a legalkalmasabb szerkezet a feladataink megoldására. 1.2. feladat Állítsunk elő 0 és 50 közötti véletlen-számokat addig, amíg a 25-ös szám generálása is megtörtént. Írassuk ki a kapott számokat. Megoldás: Elemezzük a feladatot: Állítsunk elő egy véletlen-számot, majd ismételjük az alábbi tevékenységeket: Ha a szám nem egyenlő 25-tel, akkor: írjuk ki állítsunk elő egy újabb véletlen-számot.

Pszeudokód: Program Változók: szam (pozitív egész) véletlenszám-generátor inicializálása szam = random (51) Ciklus amíg (szam <> 25) Ki: szam szam = random (51) Ciklus vége Ki : "Megvan a 25-ös !" Program vége

//előreolvasás //feldolgozás //előreolvasás

Példák: Lépetéses ciklus: 9 Problémaosztályok, algoritmusok Segédlet


n-ig az összes prímszám kiírása (1-n-ig pontosan ismert a lefutások száma) 50 véletlen szám meghatározása ( 50-szer kell a ciklusmagot végrehajtani)

Elöltesztelős ciklus az első n db prímszám kiírása (lefutási feltétel: db25) csillag végjelig karakterek beolvasása (lefutási feltétel: karakter<>’*’) 1.3. feladat Készítsen programot, amely n darab * karaktert ír ki a képernyőre. Megoldás: Pontosítsuk a feladatot: Az n értékét honnét veszem ? Pszeudokód: Program Változók: n - darabszám, pozitív egész i - ciklusváltozó, pozitív egész Ciklus Be: n amíg (n<= 0) ciklus vége Ciklus i= 1 kezdőértéktől n végértékig 1 lépésközzel Ki: "*" ciklus vége Program vége 1.4. feladat Készítsen szorzótáblát ! Megoldás: Elemezzük a feladatot: A képernyőre először kiírjuk a SZORZÓTÁBLA feliratot középre, majd egy külön sorban a számokat 1től 9-ig. (szorzó1). Ezután sorra vesszük a másik szorzótényezőt (1-től 9-ig), nevezzük ezt szorzó2-nek, és soronként kiírjuk: a következő szorzót, és a szorzatokat egymás mellé. Két ciklust kell szerveznünk. A képernyőre úgy tudunk a legegyszerűbben egy táblázatot kiírni, hogy vesszük a táblázat sorait egymás után (ez lesz a külső ciklus, szorzo2-vel), és a soron belül vesszük az oszlopokat egymás után (ez lesz a belső ciklus szorzo1-gyel).

1 2 3 4 5 6 7 8 9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

2

4

6

…

Pszeudokód: 10 Problémaosztályok, algoritmusok Segédlet


Program Változók : szorzo1, szorzo2: pozitív egész Ki: "SZORZÓTÁBLA" //Következik a fejléc-sor kiírása Ciklus szorzo1 = 1 kezdőértéktől szorzó1 = 9 végértékig 1-es lépésközzel Ki: szorzo1 Ciklus vége //szorzo1 // a szorzótábla elemei

Ki:soremelés Ciklus szorzo2 = 1 kezdőértéktől szorzó2 = 9 végértékig 1-es lépésközzel Ki: szorzo2 //első oszlop elemei… Ciklus szorzo1 = 1 kezdőértéktől szorzó1 = 9 végértékig 1-es lépésközzel Ki: szorzo1 * szorzo2 Ciklus vége //szorzo1 Ciklus vége //szorzo2 Program vége

1.5. feladat Keresse meg programmal a 2001 szám legnagyobb természetes osztóját ! (1 és önmagán kívül) Megoldás: Elemezzük a feladatot: Egy egész szám osztója legalább kétszer megvan a számban, tehát a legnagyobb osztó keresését elegendő a szám felénél kezdeni, majd egyesével haladni lefelé, amíg az első olyan számot megtaláljuk, amellyel osztva 2001-et, a maradék = 0Pszeudokód: Program Változók : oszto pozitív egész Ciklus oszto = 2001/2 kezdőértéktől 2 végértékig -1-es lépésközzel Ha (2001 mod oszto = 0) Ki: "A legnagyobb természetes osztó:", oszto kiugrás ciklus vége Ki: "A vizsgálat befejeződött." Program vége Struktúrált megoldás: Program Változók : oszto pozitív egész oszto = 2001/2 Ciklus amíg 2001 mod oszto <>0 és oszto>1 oszto=oszto-1 ciklus vége Ha oszto>1 Ki: "A legnagyobb természetes osztó:", oszto Program vége if (2001%oszto == 0)

Összefoglaló 11 Problémaosztályok, algoritmusok Segédlet


Ebben a fejezetben megismertük az algoritmus fogalmát, A moduláris programozás, a strukturált program elemeit. Az algoritmusok leírására itt és a továbbiakban is a pszeudokódot, vagy mondatszerű leírást alkalmazzuk. Az algoritmus alapvető struktúráit (szekvencia, szelekció, iteráció) a további fejezetekben példákon keresztül is begyakoroljuk. Vegyük észre, hogy a pszeudokódnak áttekinthetőnek kell lennie, a bekezdésekkel, a kulcsszavak kiemelésével is hangsúlyozzuk az összetartozó részeket. Az algoritmus, illetve a program készítésénél a logikusan átgondolt, tiszta és követhető megoldásokra kell törekedni.

Ellenőrző kérdések:    

      

Melyik az a három vezérlőszerkezet, amelyekből a programok felépíthetők ? Mi a lényege a "felülről-lefelé", illetve az "alulról felfelé" építkezésnek ? Milyen eszközök állnak rendelkezésre az algoritmusok megtervezéséhez ? Mit jelentenek az alábbi fogalmak ? Algoritmus Szekvencia, szelekció, iteráció Dekompozíció Lépésenkénti finomítás Moduláris program Strukturált program Pszeudokód A moduláris programozás irányelvei Az egyágú szelekció leírása pszeudokóddal, működése. A kétágú szelekció leírása pszeudokóddal, működése. A többágú szelekció leírása pszeudokóddal, működése. Az elől tesztelő ciklus leírása pszeudokóddal, működése. A hátul tesztelő ciklus leírása pszeudokóddal, működése. A növekményes (számláló) ciklus leírása pszeudokóddal, működése.

1.2. Szoftver fejlesztése Áttekintés  

A szoftver fejlesztésének fázisai: Analízis, Tervezés, Kódolás, Tesztelés, Dokumentálás A szoftver élete.

Egy összetett feladat számítógép segítségével történő megoldása hosszú és bonyolult munkafolyamat eredménye. Bár a számítástechnikában alkalmazott eszközök rohamos fejlődésével e munkafolyamat nagy része automatizálható, a feladat minden részletre kiterjedő megfogalmazása, elemzése, gépre vitele, majd a működő program ellenőrzése és átadása a felhasználó számára mind-mind olyan szervezői, programozói és alkalmazói feladatokat feltételez, amelyek emberi beavatkozást, tehát hibalehetőséget is feltételeznek. Egy program, illetve programcsomag fejlesztése alapvetően négy fázisból áll, melyet kiegészít az elkészült termék dokumentálása: Analízis, Tervezés, Kódolás, Tesztelés, Dokumentálás. Az analízis és a tervezés a probléma megoldására irányul, a kódolás a már átgondolt és írásban is rögzített megoldást implementálja (megvalósítja), azaz lefordítja a számítógép nyelvére. A tesztelés és a dokumentálás a hibátlan és a feladat kiírást maradéktalanul kielégítő termék kibocsátását és a használhatóság biztosítását szolgálja.

1.2.1. Analízis Az analízis (elemzés) során felmérjük, hogy a feladat kiírás kellően pontos-e, egyáltalán megoldható-e a probléma számítógéppel. Tisztázni kell az input adatok körét, a feldolgozás célját és az input adatokat. Meg kell becsülni a feladat megoldásához szükséges időt és a költségeket. A megoldásnak már ebben a szakaszában tisztázni kell minden lehetséges részletkérdést.

A feladat megfogalmazása legyen -

egyértelmű, teljes, minden részletre kiterjedő,



-

érthető, áttekinthető, pontos, szabatos, tömör, lényegretörő, szemléletes, jól felépített és tagolt, előretekintő.

A beviteli (input) adatokkal szemben a következő kérdéseket kell tisztázni: -

Melyek az input adatok (felsorolás, egyértelmű azonosítás), Az input adatok értéktartománya, beviteli formátumuk, Milyen módon kell befejezni a bevitelt, A hibásan bevitt adatok utólagosan javíthatók-e, ha igen, milyen módon, Vannak-e speciális megszorítások, előírások, Milyen kapcsolatok vannak a beviteli adatok között, ezeket kell-e ellenőrizni a bevitel során.

A kiviteli (output) adatoknál a következőket kell tisztázni: Mely adatokat kell megjeleníteni, A megjelenítés milyen formában történjen, Mely adatokat kell megőrizni későbbi felhasználásra, illetve többszöri megjelenítésre, Milyen formában kell az adatokat megőrizni. Az analízis eredményeként születik meg a feladat specifikáció, melyet dokumentálni kell. Ennek tartalmaznia kell a feladat pontos megfogalmazásán túl az esetleges képernyő- és listaterveket is. Nagyobb rendszerek esetén rendszertervet készítenek, ez többnyire egy szakértői csapat munkájának ez eredménye.

1.2.2. Tervezés A tervezés feladata, hogy az analízis során összegyűjtött információt alapul véve véglegesen kialakítsa az adat struktúrákat és az adatokat feldolgozó, átalakító algoritmusokat. Egy program megtervezése bonyolult feladat, bár vannak feladat-típusok, többnyire minden feladatot másképpen kell algoritmizálni és nehéz erre általános szabályokat megfogalmazni. Vannak programtervezési módszerek, ajánlások, szabványok, jelölési rendszerek, melyeket ajánlott, illetve egy adott csapatban dolgozva kötelező betartani. Hogy milyen tervezési módszert válasszunk, az a következő dolgoktól függhet: -

A számítástechnika által adott lehetőségek és eszközök Milyen számítógép(ek)re, milyen rendszerre készül a program A megoldandó feladat nagyságrendje, a kezelendő adatok mennyisége Milyen módszerek állnak a rendelkezésre Milyen a tervező csapat felkészültsége, informáltsága Milyen szoftverek állnak a rendelkezésre a tervezéshez Vannak-e tradíciók Van-e megfelelő anyagi fedezet A fejlesztő cég elvárásai, szabványai, főnöki utasítás.

A programtervezési módszereket illetően hosszú ideig a strukturált programozás, programtervezés volt a jellemző. Lényege, hogy a programot felülről lefelé, funkcionálisan egyre kisebb lépésekre (modulokra, eljárásokra) bontjuk. A Jackson-féle programtervezési módszer szintén strukturált módszer, de itt a programszerkezet a bemenő és a kimenő adatszerkezetek összefésüléséből adódik. Az objektumorientált programozás napjaink divatos irányzata, segítségével kisebb energia befektetéssel sokkal hatékonyabban, biztonságosabban tudjuk elkészíteni a programokat. Ennél a módszernél az információ elrejtésének elve minden eddiginél jobban érvényesül: az egyes objektumok adataikkal és eljárásaikkal együtt teljes mértékben felelősek a rájuk bízott feladatok hibátlan megoldásáért. A tervezési szakasz dokumentációja a programterv. A programtervet is tesztelni, ellenőrizni kell, ilyenkor elképzeljük a bemenő adatokat és "fejben" lefuttatjuk a programot. Közben minduntalan fel kell tenni a "Mi történik, ha ..." kezdetű kérdéseket. A program megtervezésével lényegében meg van oldva a probléma. Fontos, hogy a programterv hibátlan legyen, mert a későbbi szakaszokban egyre nehezebb a hibajavítás.

1.2.3. Kódolás Ha a terv elkészült, akkor jöhet annak implementálása, azaz kivitelezése. Ennek első fázisa a programtervnek megfelelő forrásprogram elkészítése egy kiválasztott programnyelven. Ez egy eléggé mechanikus folyamat, de feltételezi a programterv alapos ismeretét és természetesen a használt programozási nyelv készségszintű alkalmazását. Mi már elkezdtük a C++ alapvető elemeinek a megismerését, s a továbbiakban is ezt az eszközt használjuk algoritmusaink kódolására. A kódolási szakasz dokumentációja forrásprogram, illetve forrásnyelvi lista. A forrástervi lista akkor jó, ha pontosan követi a programterv utasításait áttekinthető,



-

tömör és egyértelmű megjegyzésekkel van megtűzdelve.

A forrásprogram begépelésével természetesen még nincs kész a kódolás, formailag és tartalmilag ellenőrizni kell az elkészült forrásprogramot. A program szintaktikai (formai) és szemantikai (tartalmi) hibákat tartalmazhat. Szintaktikai hibának nevezzük azt a hibát, amely abból eredt, hogy a nyelv formai szabályainak egyikét nem tartottuk be, ezért a fordító számára nem egyértelmű, hogy mit kell tennie. A szemantikai hiba akkor lép fel, ha a program tartalmilag nem azt valósítja meg, amit a programterv előírt. A szintaktikai hibák kiszűréséhez a fordató ad segítséget, a szemantikai hibák felderítése a programozó, illetve az őt segítő tesztelő munkatárs feladata.

1.2.4. Tesztelés Amikor egy program szintaktikailag hibátlan, még nem feltétlenül működik helyesen. Az igényes programozó maga is teszteli, ellenőrzi a programját különböző próba-adatokkal, hogy meggyőződjön a program hibátlan, a programtervnek megfelelő működéséről. A programok tesztelésének külön tudománya van, bonyolultabb feladatoknál alaposan elő kell készíteni a tesztelés fázisait, a teszt-adatokat, hogy lehetőleg minden lehetséges variációt kipróbáljunk. A program tesztelésekor a következőkre kell figyelni: -

Pontosan úgy működik-e a program, ahogyan az a feladat leírásában, illetve a programtervben szerepel ? Van-e olyan bemenő adat-kombináció, amelynél hibásan működik, vagy leáll a programfutás ? Eléggé hatékony-e a programfutás ? Biztonságos és egyértelmű-e a program használata ? A program felhasználóbarát ? (Pl szépen néz ki a képernyő, nem idegesítő, teljes mértékben szolgálja a felhasználót, ...)

Statikus tesztelési módszerek: Kódellenőrzés A kódellenőrzés a program szövegének vizsgálatát jelenti. Az algoritmus logikáját kell a programban végigkövetni, és megfigyelni, hogy a kettő egyező-e? Sokszor a programozó maga veszi észre a hibákat, miközben valakinek részletesen magyarázza. Formai ellenőrzés Szintaktika / szemantika A program minden utasítását végre kell hajtani legalább egyszer. Igen sok információt ad a programról ha a változóink felhasználásáról készítünk egy táblázatot. Tartalmi ellenőrzés, ellentmondás keresés Ilyen hiba lehet az, ha egy változónak értéket adunk, de ezután nem használjuk semmire, vagy közvetlenül utána még egyszer értéket kap. Előfordulhat, hogy egy utasításhoz soha nem jut el a program. Illetve, ha kezdőérték nélkül használunk egy változót kifejezésben.

Dinamikus tesztelési módszerek: Alapelv, hogy a programot működés közben vizsgáljuk Fekete doboz módszer a kód ismerete nélkül tesztel  Ekvivalencia osztályok keresése Mivel a a kimerítő bemeneti tesztelés gyakorlatilag megvalósíthatatlan, meg kell elégednünk a bemenő adatok szűk részhalmazával való teszteléssel. Azért, hogy a részhalmaz minél hatásosabb legyen a benne szereplő tesztesetekre teljesüljenek a következők: Minden tesztesetnek annyi bemeneti feltételt kell kielégítenie, amennyit csak lehetséges, hogy ezzel a szükséges tesztesetek számát csökkentsük. A bemeneti tartományt valamilyen módon részekre kell bontani, és ezekre a részekre jellemző teszteseteket kell választani Ezekre a részekre legyen igaz az, ha egy ilyen osztályból választunk egy tesztesetet, és ezzel hibát találunk a programban, akkor az osztály más elemét választva is nagy valószínűséggel hibát találnánk, illetve, ha a kiválasztott tesztesetre a program jól működik, az osztály más elemét választva is nagy valószínűséggel helyes eredményt adna.

MEGJEGYZÉS: Ekvivalencia osztályokat nem csak az érvényes, hanem az érvénytelen adatokhoz is létre kell hozni, és azokkal kipróbálni. 

Határeset elemzés Az ekvivalencia osztály kiválasztott elemének a határon lévő elemeket választja Nem csak bemeneti, hanem kimeneti ekvivalencia osztályt is figyelembe veszi Pl. ha a rendeznünk kell 1..128 számot, akkor célszerű kipróbálni 0,1,128,129 adatokkal vagy ha a bemeneti tartomány (0,1) nyílt intervallum, akkor a 0,1,0.01,0.99 értékekkel érdemes kipróbálni a programot Fehér doboz módszer a kód ismeretének felhasználásával  Utasítások egyszeri lefedésének elve A módszer lényege olyan tesztesetek kiválasztása, amelyek alapján minden utasítást legalább egyszer végrehajtunk a programban. Bár ez sokszor jó módszer, de nem tökéletes : Ha X>0 akkor ki: X



Ebben a példában egyetlen próbával elérhetjük az összes utasítás végrehajtását (pl. X=1), de ezzel a próbával nem derülne ki az, ha az X>0 feltétel helyett az X>=0 szerepelne, azaz a program esetleg hibás lenne.  Döntéslefedés elve A programban minden egyes elágazást igaz illetve hamis ágát legalább egyszer be kell járni a tesztelés során. A döntéslefedés elvét figyelembe véve eleget teszünk az utasításlefedés követelményének is. Itt is maradnak azonban problémák: Ha X>0 vagy Y>0 akkor ki: X*Y Ebben az esetben az (X=1, Y=1) és az (X=-1,Y=-1) tesztesetek lefedik a döntéseket, de nem vennénk észre velük, ha a második feltételt (Y>0) rosszul írtuk (vagy lehagytuk) volna.  Feltétellefedés elve Ebben az esetben a döntésekben szereplő minden feltételt legalább egyszer hamis illetve igaz eredménnyel értékelünk ki. Ha X>0 és Y>0 akkor ki: X*Y Itt az (X=1, Y=1) és az (X=-1,Y=-1) tesztadatok elégségesek ezen elv megvalósításához, de az elágazás igaz ágát egyiknél sem hajtjuk végre, s így ez az előző elv követelményét nyilvánvalóan nem teljesíti. 

Döntés- vagy feltétellefedés elve

Az előző pontban lévő példából látható, hogy a feltétellefedés követelményét kielégítő tesztesetek nem feltétlenül elégítik ki a döntéslefedés követelményét. Ezért az előző két elvet egyesítő módszert kell készíteni úgy, hogy mindkét elv érvényesüljön.  Stressz teszt Olyan esetben alkalmazzuk, mikor a program nagy adatmennyiséggel dolgozik, vagy fontos, hogy az adott feladatot meghatározott időn belül elvégezze. Próbáljuk ki a programot nagy adatmennyiséggel, ha mód van rá, akkor a felhasználó minél gyakoribb beavatkozásával.

1.2.5. Dokumentálás Minden fázisnak megvan a maga "terméke", dokumentációja A program elkészülte után is meg kell őrizni valamennyi fázis dokumentációját, ez megkönnyíti a későbbi esetleges bővítések, módosítások kivitelezését. A program fejlesztését végigkísérő dokumentáció összességét fejlesztői dokumentációnak nevezzük, ezt a felhasználó nem, csak a fejlesztő cég őrzi meg. A fejlesztői dokumentáció részei: -

Feladat specifikáció Programterv Forrásprogram Kész program (telepíthető és futtatható program) Tesztadatok listája, a tesztelés jegyzőkönyvei Fejlesztési lehetőségek

A kész rendszerhez elkészül a felhasználói dokumentáció, amelyet a felhasználó kap meg. A felhasználói dokumentáció részei: -

-

A program által megoldható feladat leírása, az alkalmazás korlátjai A szükséges hardver környezet leírása. Számítógép típusa, a minimálisan szükséges konfiguráció, amely a program futtatásához szükséges. Szoftver környezet. Operációs rendszer, a futtatáshoz szükséges esetleges kiegészítő szoftverek. Fejlesztői környezet, programozási nyelv. A program telepítése, betöltése, futtatása. A program használatának részletes leírása: speciális billentyűk használata, az esetlegesen használt ikonok, szimbólumok jelentése, funkciója, a menürendszer ismertetése, segítségkérés lehetőségei. A működés leírása minden részletre kiterjedően, az egyes funkciók elérésének módja. Milyen kérdésre milyen válasz adható Képernyőtervek, listatervek. Hibaüzenetek felsorolása, értelmezése, teendők a hiba elhárítására. Biztonsági előírások (pl. adatok időszakos mentése). Felhasználói jogosultságok, esetleges jelszó megadási módok. Ki és milyen feltételekkel jogosult a szoftver használatára (Licence szerződés).



1.2.6. A szoftver élete Amikor a felhasználó használni kezdi a letesztelt és hibátlannak vélt programot, szinte biztosra vehetjük, hogy lesz még dolga a fejlesztőnek. Egyrészt a leggondosabb tesztelés mellett is előfordulhatnak rejtett hibák, olyan esetek, melyekre a programfejlesztő nem gondolt, de a használat során kiderül, nem megfelelően működik a program. Másrészt a feladat elemzése során nem mindig sikerül a felhasználó minden igényét feltárni, később merülnek fel megoldandó rész-feladatok. A felhasználó többnyire akkor érez rá a számítógép által élvezhető előnyökre, amikor már egy ideje használja a megrendelt és elkészült programját. Így utólagos bővítésekre, javításokra szinte mindaddig szükség van, amíg a programot használják és rendelkezésre áll a fejlesztői gárda, a fejlesztői dokumentáció. Egy szoftver javított, illetve továbbfejlesztett változatait verziószámmal szokás ellátni. Nagyobb változtatások esetén a verziószám egészrésze, kisebb javításoknál, módosításoknál a verziószám törtrésze változik.

Ellenőrző kérdések:     

Hogyan kell elkezdeni egy feladat megoldását ? Hogyan kell megtervezni egy programot ? A fejlesztői dokumentáció milyen elemekből áll ? Mire kell kitérnie a felhasználói dokumentációnak ? Mit jelentenek a következő fogalmak: Analízis Feladat specifikáció Fejlesztői dokumentáció Felhasználói dokumentáció Kódolás Tesztelés Felhasználóbarát.

2. Összetett adatszerkezetek Eddigi példáinkban olyan változókat használtunk, amelyek egyetlen érték (skalár) tárolására alkalmasak. A változók deklarálásánál megismerkedtünk a skalár típusokkal. Már eddig is találkoztunk olyan feladatokkal, ahol egyszerre több értékkel kellett dolgoznunk, például a csoport zh - átlagának kiszámításakor. Ha az egyes zh - eredményeknek az átlagtól való eltérésére is kíváncsiak vagyunk, akkor a pontszámokat tárolni kell, nem elég pusztán az adatok bevitelekor számolni azokkal. Ebben a fejezetben megtanuljuk, hogyan használjunk különböző adattípusokat több értéknek ugyanabban a változóban való tárolására. C-ben: Elemi adat-típusok: karakter egész lebegőpontos dupla lebegőpontos double érték nélküli

char int float void

Typedef: szinoním típusnevek bevezetéséhez Enum: felsorolt típusok csoportos, egymással kapcsolatban álló konstansok létrehozására pl. enum szin {piros, feher, zold, kek, sarga}; enum valasz {igen, nem}; Összeállított (aggregate) típusok. Tömb,struktúra, bitmező, union

Tömb definíció: Összetett adatszerkezet, véges számú azonos típusú elemek összessége.

2.1. Egydimenziós tömbök Áttekintés: 16 Problémaosztályok, algoritmusok Segédlet


   

 

A tömb olyan összetett adatszerkezet, amely lehetővé teszi, hogy egyetlen változó több értéket tároljon. A tömb (array) típus olyan objektumok halmaza, amelyek azonos típusúak és a memóriában folytonosan helyezkednek el. Amikor deklarálunk egy tömböt, meg kell adnunk a tárolandó érték típusát és a tételek (tömb elemek) maximális számát. Egy tömbben minden elemnek ugyanolyan típusúnak kell lennie, Egy értéknek a tömbben való tárolásához meg kell adjuk a tömb nevét és az elem tömbön belüli sorszámát, melynél az értéket tárolni akarjuk. A tömb első eleme az 1. sorszámú, de a C nyelvben az indexek nullától indulnak ! Az elemek elérése a tömb nevét követő indexelés operátorban megadott elemsorszám (index) segítségével történik. Egy tömb deklarálásakor megadhatjuk az egyes elemek kezdeti értékét, éppúgy, mint a skalár típusoknál.

A leggyakrabban használt tömbtípus egyetlen kiterjedéssel (dimenzióval) rendelkezik. Az egydimenziós tömböket szokás vektoroknak is nevezni. Többdimenziós tömbök (mátrix) használatára is van lehetőség, ezek elemeinek tárolása a memóriában C++ esetén sorfolytonosan történik. A tömböket deklarálnunk kell. Az egydimenziós tömb deklarálásának általános alakja: típus tömbnév [méret]; ahol típus az elemek típusát definiálja, a tömbnévre ugyanazok a szabályok vonatkoznak, amelyeket a változónevekkel kapcsolatban már megismertünk, a méret pedig a tömb elemszámát adja. A méretnek a fordító által kiszámítható konstans kifejezésnek kell lennie. Az elemek indexelése C-ben 0-tól méret-1-ig történik. A tömb elemeinek egymás után történő elérésére általában a for ciklust használjuk, melynek ciklusváltozója a tömb indexe.

2.1.1. feladat Készítsen programot, amely bekéri a csoport zh - eredményének pontszámait, kiszámítja az átlagot, majd kiírja - sorszámozva - az egyes pontszámokat és az átlagtól való eltérésüket. Megoldás: Elemezzük a feladatot Tudnunk kell, hogy hány főből áll a csoport. Az aktuális csoport-létszámot a program futásakor is megadhatjuk, de - mivel a pontszámokat tárolnunk kell egy egydimenziós tömbben - a csoport lehetséges (maximális) létszámát már a forráskód megírásakor ismerni kell, legyen ez a példánkban 20 fő. Pszeudokód: Program Változók: letszam az aktuális létszám, pozitív egész cv ciklusváltozó a létszámhoz, pozitív egész pontszam [20] a pontszámok tárolására, elemei egész típusúak atlag valós típusú, a pontszámok átlaga atlag = 0 ciklus Be: letszam //1..20 amíg letszam<1 vagy letszam>20 ciklus vége ciklus cv = 0 kezdőértéktől cv = letszam-1 végértékig 1 lépésközzel Be: pontszam [cv] ciklus vége // beolvasás ciklus cv = 0 kezdőértéktől cv = letszam-1 végértékig 1 lépésközzel 17 Problémaosztályok, algoritmusok Segédlet


atlag = atlag + pontszam [cv] ciklus vége atlag = atlag / letszam Ki: atlag

//átlagszámítás

ciklus cv = 0 kezdőértéktől cv = letszam-1 végértékig 1 lépésközzel Ki: cv+1, pontszam [cv], pontszam [cv] - atlag atlag = atlag + pontszam [cv] ciklus vége program vége Amikor tömböket használunk a C++-ban, figyelni kell arra, hogy a tömb első elemének sorszáma (indexe) mindig 0. A mindennapi gyakorlatban viszont megszoktuk, hogy többnyire 1-

2.1.2. feladat A menzán 10-féle étel közül választhatunk, mindegyiknek meg van adva a kalóriaértéke. Készítsen programot, amely "ismeri" a sorszámmal ellátott ételek kalóriaértékét, s a választott adagok alapján megmondja, hogy összesen mennyi kalóriát képvisel az ebédünk. Megoldás: Elemezzük a feladatot A program "ismeri" a kalóriaértékeket, ez azt jelenti, hogy konstansként fogjuk azokat a programba beépíteni. Input adatként adjuk meg, hogy az egyes ételekből mennyit vettünk meg, ez lehet 0, 0.5, 1, vagy egynél nagyobb egész szám. Két egydimenziós tömböt (vektort) fogunk deklarálni, az összes kalória értékét megkapjuk, ha az azonos sorszámú tömb-elemeket összeszorozzuk és a kapott szorzatok összegét képezzük. (Ez nem más, mint a két vektor skaláris szorzata !) Az alábbi kalóriatáblázat alapján fogunk dolgozni: sorszám étel megnev. kcal 0 zöldségleves 26 1 zöldborsóleves 110 2 halászlé 156 3 vagdalt 168 4 párolt csirke 164 5 natúrszelet 206 6 kelkáp.főzelék 138 7 tökfőzelék 141 8 párolt zöldség 202 9 burgonyapüré 214 Pszeudokód: Program Változók: energia [10] = [26,110,156,168,164,206,138,141,202,214] adag [10] valós típusú tömb ossz_energia pozitív egész, i ciklusváltozó, egész Ciklus i=0 kezdőértéktől i = 9 végértékig 1 lépésközzel Be: adag [i] Ciklus vége ossz_energia = 0 Ciklus i=0 kezdőértéktől i = 9 végértékig 1 lépésközzel ossz_energia = ossz_energia + adag [i] * energia [i] Ciklus vége 18 Problémaosztályok, algoritmusok Segédlet


Ki : ossz_energia Program vége

2.2. Stringek A stringek, vagy karakterláncok olyan információt tárolnak, mint például személynevek, elnevezések, könyv címek. A C nyelv nem rendelkezik önálló string típussal, a karakterláncokat olyan char típusú egydimenziós tömbben tárolja, melynek utolsó, még a karakterlánchoz tartozó eleme után egy ’\0’(ASCII 0) karakter áll.

2.3. Többdimenziós tömbök A többdimenziós tömbök deklarációjának általános alakja: típus tömbnév [méret1][méret2] ... [méretn]; ahol minden dimenzióra külön zárójelezve kell megadni a méreteket. A dimenziók számára semmilyen korlátozást nem tartalmaz a C nyelv definíciója. Ebben a fejezetben csak a kétdimenziós tömbökkel foglalkozunk.

2.3.1. feladat Egy háromfős társaság minden tagja 2-2 lottószelvényt vásárol minden héten. 5-ös lottón, állandó számokkal játszanak. Készítsen programot, amely tárolja a szelvényeken megjátszott tippeket, bekéri a nyerőszámokat és megmondja, hogy volt-e ötös a szelvények között. Megoldás: Elemezzük a feladatot Összesen 6 szelvényünk (tipp-sorunk) van, egy-egy tipphez öt darab egész szám tartozik. Mivel a társaság állandó számokkal játszik, a tippeket előre megadhatjuk a programban. Bekérni csak a nyerőszámokat kell. A 6 szelvényen szereplő tippsor tárolása egy kétdimenziós tömbben történik, melynek egy-egy sora tartalmaz egy tippsort, példaként vegyük az alábbi tippeket: 1. tipp: 11, 34, 45, 66, 2. tipp: 3, 13, 43, 52, 78 3. tipp: 25, 31, 72, 86, 90 4. tipp: 8, 15, 26, 48, 5. tipp: 19, 29, 39, 49, 6. tipp: 21, 32, 43, 54,

89

81 69 65

A C++-ban az alábbi tömböt fogjuk deklarálni a fenti "számhalmaz" tárolására: int tippek [6][5]; vagyis deklarálunk egy int típusú elemeket tartalmazó kétdimenziós tömböt, amelynek 6 sora (első index) és öt oszlopa (második index) van. Az egydimenziós tömbök tárgyalásánál azt mondtuk általánosan, hogy a tömb típus olyan objektumok halmaza, amelyek azonos típusúak és a memóriában folytonosan helyezkednek el. Itt a tippek tömb elemei mind integer típusúak és a memóriában úgy helyezkednek el egymás után, hogy az első sor elemei után 19 Problémaosztályok, algoritmusok Segédlet


következnek a második sor elemei, és így tovább, vagyis a kétdimenziós tömb elemeit a C nyelv sorfolytonosan tárolja. Ezt azért is fontos tudni, mert ha a deklarálás során kezdeti értéket is adunk az elemeknek, akkor az elemek értékeinek sorrendje ezt kell, hogy kövesse. Pszeudokód: Program Változók: tippek [6][5]

a tippeket tartalmazó tömb, elemei pozitív egész számok, melyeket a deklaráláskor kell megadni nyeroszamok [5] a nyerőszámokat tartalmazó 5 elemű tömb i,j ciklusváltozók, pozitív egész számok egyezik segédváltozó, egész típusú vanotos 0 ha nincs ötös, 1, ha van ötös találat a tippek között Ciklus i=0 kezdőértéktől i= 4 végértékig Be: nyeroszamok [i] Ciklus vége vanotos = 0 Ciklus i=0 kezdőértéktől i = 5 végértékig egyezik = 0 Ciklus j = 0 kezdőértéktől j = 4 végértékig egyezik = egyezik + (tippek [i][j] == nyeroszamok [j]) Ciklus vége // j Ha egyezik == 5 kiugrás a ciklusból Ciklus vége //i Ha egyezik == 5 Ki: "Van ötös !" egyébként Ki: "Nincs ötös !" program vége

A kétdimenziós tömbök leggyakoribb felhasználási területe a matematikában használt mátrixok tárolása, műveletek mátrixokkal.

2.3.2. feladat Készítsen programot, amely egy maximum 20 fős tanulócsoport zh eredményeit tárolja egy tárgyból. A csoport öt zh-t ír. Az adatbevitel úgy történik, hogy megadjuk a zh sorszámát, majd az egyes tanulók pontszámait sorban egymás után. A program minden zh-ra kiszámítja az átlagot és le is tárolja azt. A programnak tárolnia kell a hallgatók neveit is. Megoldás: Elemezzük a feladatot A tömbökről már a bevezetőben azt mondtuk, hogy azonos típusú elemeket tárolnak. A hallgatók neveit és a zh-pontszámokat tehát más más tömbben fogjuk tárolni. A neveket tároló tömb egy sora egy hallgató nevének karaktereit tárolja. Pszeudokód: Program Változók: i, j, letszam nevek [20][31] pontok [20][5 ]

egész számok char típusú tömb, soronként egy nevet tartalmaz int típusú tömb, egy sora egy hallgató zh-pontszámait tartalmazza atlag [5] = [0,0,0,0,0] valós típusúak, a zh átlagokat tartalmazzák 20

Problémaosztályok, algoritmusok Segédlet


Be: letszam Ciklus i=0 kezdőértéktől i=letszam-1 végértékig 1 lépésközzel //Névsor beolvasása Be: nevek [i] Ciklus vége Ciklus i=0 kezdőértéktől i=letszam-1 végértékig 1 lépésközzel //Pontszámok beolvasása Ki: nevek [i] Ciklus j=0 kezdőértéktől j=5-1 végértékig 1 lépésközzel Be: pontszam [i][j] Ciklus vége Ciklus vége Ciklus i=0 kezdőértéktől i=letszam-1 végértékig 1 lépésközzel //Átlag számítás Ciklus j=0 kezdőértéktől j=5-1 végértékig 1 lépésközzel atlag [j] = atlag [j] + pontszam [i][j] Ciklus vége Ciklus vége Ciklus j=0 kezdőértéktől j=5-1 végértékig 1 lépésközzel // pontszám átlagok kiírása Ki: atlag [j] / letszam Ciklus vége Program vége

2.4.

A rekord fogalma

Tömb: azonos típusú objektumok összessége Feladat: árukészlet nyilvántartása adat neve

típus

megnevezés char [30] EAN kód long int mennyiségi egység char [10] mennyiség double beszerzési ár nettó float eladási ár nettó float ÁFA kulcs int Tárolás: tömbökben ? memóriában ? Rekord (C-ben struktúra) típus: több, tetszőleges típusú (kivéve a void és a függvény típust) objektum együttese. Ezek az objektumok önálló, a rekordon (struktúrán) belül érvényes nevekkel rendelkeznek. Az objektumok szokásos elnevezése a C-ben: struktúraelem, vagy adattag más nyelvekben: mező

Ellenőrző kérdések   

A többdimenziós tömbök deklarációjának általános alakja a C nyelvben. Egydimenziós tömb deklarálásának általános alakja. Kétdimenziós tömböknél mit jelent a sorfolytonos tárolás ?



3. Programozási tételek Az algoritmusok osztályokba sorolása a bemenő és a kimenő adatok száma, illetve szerkezete, illetve a megoldandó feladat szerint:  Egy sorozathoz egy értéket rendelő algoritmusok  Egy sorozathoz egy sorozatot rendelő algoritmusok  Több sorozathoz egy sorozatot rendelő algoritmusok  Egy sorozathoz több sorozatot rendelő algoritmusok Az egyes osztályokhoz feladat csoportok tartoznak. A feladatcsoportok megoldására mutatunk be algoritmusokat, melyeket programozási tételeknek is neveznek a szakirodalomban.

3.1. Egy sorozathoz egy értéket rendelő algoritmusok 3.1.1. Sorozatszámítás Adott az a[1], a[2], … a[n] sorozat. Az adatok beolvasását itt és a továbbiakban nem részletezzük. a./ Az összegzés algoritmusa A sorozat elemei numerikus értékek. Határozzuk meg az elemek összegét, s-et. Megoldás: s=0 Ciklus cv = 1 kezdőértéktől cv = n végértékig 1 lépésközzel s = s + a [cv] Ciklus vége Ki: s Feladat: A fűtési szezonban naponta egyszer megmértük és feljegyeztük a nappali szoba hőmérsékletét. Mennyi volt a hőmérsékletek átlaga ? a./ A szorzás algoritmusa A sorozat elemei numerikus értékek. Határozzuk meg az elemek szorzatát, p-t. Megoldás: p=1 Ciklus cv = 1 kezdőértéktől cv = n végértékig 1 lépésközzel p = p * a [cv] Ciklus vége Ki: p Feladat: Adott egy n elemű számsorozat. Határozza meg az elemek szorzatát.

3.1.2. Eldöntés Adott az a[1], a[2], … a[n] sorozat és egy, a sorozat elemein értelmezett T tulajdonság. Eldöntendő, hogy van-e a sorozatban legalább egy T tulajdonságú elem. Megoldás: A van nevű változó kezdeti értéke legyen nulla. Sorban megvizsgáljuk a sorozat tagjait. Ha találunk 22 Problémaosztályok, algoritmusok Segédlet


olyan elemet, amely T tulajdonságú, akkor van értékét 1-re változtatjuk. (A van változó lehet logikai típusú is.) van = 0 ciklus cv = 1 kezdőértéktől cv=n végértékig 1 lépésközzel ha a[cv] T tulajdonságú van = 1 elágazás vége ciklus vége ha van Ki: "Van a sorozatban T tulajdonságú elem" elágazás vége Javított algoritmus, ahol az első találat esetén befejeződik a ciklus:

cv=1 ciklus amíg a[cv] nem T tulajdonságú és cv
elágazás vége Feladat: A fűtési szezonban naponta egyszer megmértük és feljegyeztük a nappali szoba hőmérsékletét. Volt-e olyan nap, amikor a hőmérséklet 18 fok alá csökkent ? A megoldás pszeudo-kódja: Program Változók: hofok [200] egész típusú tömb a mért értékek tárolására napok napok száma a fűtési szezonban cv ciklusváltozó, egész típ. van 0 a kezdeti érték, 1, ha volt 18-nál kisebb mért érték Ciklus Be: napok amíg napok < 1 vagy napok > 200

//mérési értékek száma

Ciklus cv = 0 kezdőértéktől cv = napok-1 végértékig 1 lépésközzel Be: hofok [cv] // mért értékek bevitele ciklus vége van = 0 //az eldöntés algoritmusa Ciklus cv = 0 kezdőértéktől cv = napok-1 végértékig 1 lépésközzel Ha hofok [cv] < 18 van = 1 ciklus vége Ha van Ki : "Volt 18 foknál alacsonyabb mért érték" Program vége

3.1.3. Kiválasztás Adott az a[1], a[2], … a[n] sorozat és egy, a sorozat elemein értelmezett T tulajdonság. Tudjuk, hogy van a sorozat elemei között legalább egy T tulajdonságú elem. A feladat az első ilyen T tulajdonságú elemnek, illetve a 23 Problémaosztályok, algoritmusok Segédlet


sorszámának a meghatározása. A feladat hasonló az eldöntéshez, de a kiválasztásnál más az output. Megoldás: ( az első találat esetén befejeződik a ciklus) cv=1 ciklus amíg a[cv] nem T tulajdonságú és cv -1 Ki: "Az elem és a sorszáma:", a [cv], cv elágazás vége hatékonyabban: cv=n ciklus amíg a[cv] NEM T tulajdonságú és cv>1 cv=cv-1 ciklus vége Ha a[cv] T tulajdonságú Ki: "Az elem és a sorszáma:", a [cv], cv különben Ki: ”Nincs ilyen elem” Elágazás vége Feladat: A fűtési szezonban naponta egyszer megmértük és feljegyeztük a nappali szoba hőmérsékletét. Melyik volt az első nap, amikor a hőmérséklet 18 fok alá csökkent ? A megoldás pszeudo-kódja: Program Változók: hofok [200] egész típusú tömb a mért értékek tárolására napok napok száma a fűtési szezonban cv ciklusváltozó, egész típ. indext -1 a kezdeti érték, >=0 ha volt 18-nál kisebb mért érték Ciklus //mérési értékek száma Be: napok amíg napok < 1 vagy napok > 200 Ciklus cv = 0 kezdőértéktől cv = napok-1 végértékig 1 lépésközzel Be: hofok [cv] // mért értékek bevitele ciklus vége indext = -1 //a kiválasztás algoritmusa Ciklus cv = 0 kezdőértéktől cv = napok-1 végértékig 1 lépésközzel Ha hofok [cv] < 18 24 Problémaosztályok, algoritmusok Segédlet


indext = cv kiugrás a ciklusból ciklus vége Ha indext > -1 Ki : " 18 foknál alacsonyabb mért érték volt :", indext, a[indext] Program vége

3.1.4. Lineáris keresés Adott az a[1], a[2], … a[n] sorozat és egy, a sorozat elemein értelmezett T tulajdonság. El kell dönteni, hogy van-e a sorozatban T tulajdonságú elem, és ha van, akkor meg kell adni az összes ilyen elemet és az indexét. Megoldás: ciklus cv = 1 kezdőértéktől cv=n végértékig 1 lépésközzel ha a[cv] T tulajdonságú Ki: a[cv],cv elágazás vége ciklus vége

3.1.5. Megszámlálás Adott az a[1], a[2], … a[n] sorozat és egy, a sorozat elemein értelmezett T tulajdonság. Meg kell számolni, hogy a sorozat hány eleme rendelkezik a T tulajdonsággal. Megoldás: A számlálásra az S változót használjuk, melynek kezdeti értéke 0. Az elemeket meg kell vizsgálni sorban és ha találunk T tulajdonságú elemet, az S értékét eggyel növeljük. s=0 Ciklus cv = 1 kezdőértéktől cv = n végértékig 1 lépésközzel Ha a [cv] T tulajdonságú s=s+1 elágazás vége ciklus vége Ki : s

3.1.6. Maximum kiválasztás Adott egy n elemű sorozat. Keressük meg a legnagyobb elemét. Írassuk ki a legnagyobb elem értékét és a sorszámát. Megoldás: Tegyük fel, hogy a sorozat első eleme a legnagyobb, az elem értékét tegyük a maxelem nevű változóba, az indexét pedig a maxindex nevű változóba. Ezután vizsgáljuk meg a sorozat további elemeit és ha találunk maxelem-nél nagyobbat, akkor az legyen maxelem új értéke, az indexe pedig maxindex új értéke. maxelem = a[1] maxindex = 1 ciklus cv = 2 kezdőértéktől cv = n végértékig 1 lépésközzel Ha a [cv] > maxelem maxelem = a [cv] maxindex = cv elágazás vége ciklus vége 25 Problémaosztályok, algoritmusok Segédlet


Ki: maxelem, maxindex Javítás az algoritmuson: felhasznált tulajdonság: a vektor elemének értékét az indexe segítségével érhetjük el maxindex = 1 ciklus cv = 2 kezdőértéktől cv = n végértékig 1 lépésközzel Ha a [cv] > a [maxindex] maxindex = cv elágazás vége ciklus vége Ki: maxindex, a[maxindex] Feladat: Írja fel a minimum kiválasztás algoritmusát általánosan.

3.2. Egy sorozathoz egy sorozatot rendelő algoritmusok 3.2.1. Kiválogatás Adott egy N elemű sorozat, (a [1], a[2], … a[n]) és egy, a sorozat elemein értelmezett T tulajdonság. Ki kell gyűjteni a sorozat összes T tulajdonságú elemét. A kiválogatott elemeket egy B tömbben tároljuk. (Az algoritmus abban különbözik a kiválasztás algoritmusától, hogy ott egyetlen T tulajdonságú elemet kell kiválasztani, itt pedig az összes T tulajdonságú elemet.) Megoldás: (a sorozat elemeinek bevitelét itt sem részletezzük) cv2 = 0 ciklus cv1 = 1 kezdőértéktől cv1 = n végértékig 1 lépésközzel Ha a [cv1] T tulajdonságú cv2 = cv2 +1 b [cv2] = a [cv1] elágazás vége ciklus vége Ki: b tömb elemei (A kapott sorozat kiíratását nem részletezzük)

3.2.2. Másolás Adott az n elemű sorozat, (a [1], a[2], … a[n]) amelynek alapján egy másik, ugyancsak n elemű sorozatot kell képezni úgy, hogy a sorozat elemein valamilyen átalakítást végzünk. (A sorozat tagjaihoz valamilyen szabály szerint rendelünk új értéket, jelöljük a transzformációt ¤-el.) Az új sorozatot egy másik, b tömbben tároljuk. ciklus cv = 1 kezdőértéktől cv = n végértékig 1 lépésközzel b [cv] = ¤ a [cv] ciklus vége

3.2.3. Rendezés Adott az n elemű sorozat, amelynek elemeit növekvő, vagy csökkenő sorrendbe kell rendezni. A rendező algoritmusokkal később kiemelten foglalkozunk.



3.3. Több sorozathoz egy sorozatot rendelő algoritmusok 3.3.1. Egyesítés Adott két sorozat, a[1], a[2], … a[n] és b[1], b[2], … b[m], melyek nem tartalmaznak ismétlődő elemeket, vagyis a sorozatokat tekinthetjük halmazoknak. Képezzük a két halmaz unióját, melynek elemeit a c tömbben tároljuk. Megoldás: Először az a tömb elemeit átmásoljuk a c tömbbe. Ezután a b tömb elemeiből csak azokat kell tárolni c-ben, amelyek nem elemei a-nak.

3.3.2. Metszetképzés Adott két sorozat, a[1], a[2], … a[n] és b[1], b[2], … b[m], melyek nem tartalmaznak ismétlődő elemeket, vagyis a sorozatokat tekinthetjük halmazoknak. Képezzük a két halmaz metszetét, melynek elemeit a c tömbben tároljuk. Megoldás: Sorra vesszük az a tömb elemeit. Ha az adott elem a b tömbben is megtalálható, akkor bekerül a c tömbbe.

3.3.3. Különbségképzés Adott két sorozat, a[1], a[2], … a[n] és b[1], b[2], … b[m], melyek nem tartalmaznak ismétlődő elemeket, vagyis a sorozatokat tekinthetjük halmazoknak. Képezzük a két halmaz különbségét, melynek elemeit a c tömbben tároljuk. Megoldás: Sorra vesszük az a tömb elemeit. Ha az adott elem a b tömbben NEM található, akkor bekerül a c tömbbe.

3.3.4. Rendezett sorozatok egyesítése Adott két rendezett sorozat. Állítsunk elő belőlük szintén rendezett sorozatot úgy, hogy az eredeti sorozatok minden eleme szerepeljen benne. Ha az eredeti sorozatok halmazok elemei (minden elemük különböző), és az egyesítéssel is halmazt kívánunk előállítani, akkor a két sorozat azonos elemeit csak egyszer vesszük figyelembe. A rendezett halmazok egyesítését összefuttatási feladatnak nevezik a számítástechnikában. A probléma megoldását a rendezéseknél tárgyaljuk, itt csak a rendszerezés miatt említettük meg.

3.4. Egy sorozatból egy sorozatot előállító algoritmusok 3.4.1. Szétválogatás Adott az a[1], a[2], … a[n] részsorozatra bontjuk.

sorozat és egy T

tulajdonság, amelynek alapján a sorozatot két



Azokat az elemeket, amelyek rendelkeznek a T tulajdonsággal, a b tömb első felébe másoljuk, növekvő index szerint, amelyek pedig nem rendelkeznek a T tulajdonsággal, a b tömb második felébe tároljuk, csökkenő index szerint. Így a kapott sorozatok tárolására nem kell két tömböt lefoglalni, melyeknek nem tudjuk előre a hosszát.

4. A rekurzió fogalma, rekurzív algoritmusok

Rekurzió definíciója Egy rekurzió definíciója két részbôl áll: 1. Az alapesetek meghatározása. 2. Redukciós szabályok megadása. A redukciós szabály segítségével a problémát visszavezetjük egy kisebb méretű probléma megoldására. A redukciós szabály megadásakor felhasználjuk a definiálandó fogalmat is. Példa: n! rekurzív definíciója: 1. Alapeset:

n! = 1

2. Redukciós szabály:

n! = n * (n-1) !

ha n = 1 ha n > 1

A C-ben és a C++-ban megengedett, hogy a függvények saját magukat hívják, az ilyen függvényeket rekurzív függvényeknek nevezzük.

4.1. feladat Készítse el a faktoriális számítás rekurzív programját !

A megoldás pszeudokódja: Program Változók: n (egész), fakt (valós) Függvények: rfakt (egész), valós tip. visszatérési.érték Be: n Ki: rfakt (n) Program vége Valós tip. függvény: rfakt (n) Ha n=1, akkor

Visszad: 1 Egyébként Visszaad = n * rfakt (n-1) Függvény vége

4.2. feladat Hány nyúl-párunk lesz 3,4,5, …, n hónap múlva, ha egy nyúl-pár kéthónapos kortól kezdve havonta egy-egy új párt hoz a világra, feltéve, hogy az új párok is ezen törvény alapján szaporodnak, és mind életben maradnak ? Megoldás: a Fibonacci számok sorozata (ha a nulla kezdőelemet figyelmen kívül hagyjuk): 0, 1, 1, 2, 3, 5, 8, 13, 21, …

A. generáció B. generáció C. generáció

1

2

3

4

5

6

7

A

A

A B(A)

A B(A) C(A)

A B(A) C(A)

A B(A) C(A)

A B(A) C(A)



D. generáció

D(A) D(B)

D(A) D(B) E(A) E(B) E(C)

5

8

E. generáció …. Összes pár

1

1

2

3

D(A) D(B) E(A) E(B) E(C) … 13

A sor n-dik elemének meghatározására szolgáló rekurziós szabály: F=n

ha n < 2

F = F (n-1) + F (n-2) ha n > 1

A rekurzív megoldás általában rövidebb és áttekinthetőbb, mint az iteratív megoldás, azonban a memóriaigény és a számítási idő jelentősen több lehet ! Sok egymást követő rekurzív lépés a verem túlcsordulásához is vezethet, mivel a függvény lokális változói, paraméterei és a visszatérési cím is a veremben tárolódnak. Ekkor kapjuk a stack overflow üzenetet. Rekurzív függvények írásakor mindig ügyeljünk arra is, hogy a függvény tartalmazzon valahol egy olyan feltételt, amelynek teljesülésekor a függvény újabb önhívás nélkül tér vissza. A következő feladat megoldása a rekurzió alkalmazása nélkül igen bonyolult. Hanoi tornyai: adott három rúd: A, B és C. A rúdon induláskor N darab különböző átmérőjű lyukas korong helyezkedik el az átmérők csökkenő sorrendjének megfelelően. Feladat: a korongok áthelyezése az alábbi szabályok figyelembe vételével: a B rúd közbenső tárolásra használható minden lépésben csak egy korong mozgatható minden korong csak a nálánál nagyobb átmérőjű korongra helyezhető (Legenda: Hanoi közelében egy kolostorban 64 korongból álló tornyot raknak át a szerzetesek a fenti szabályok betartásával, minden nap egyetlen korongot mozgatva. A legenda szerint akkor lesz vége a világnak, ha az átrakást befejezik). A megoldást ld. a szakirodalomban.

9.

Rendezési és keresési algoritmusok

A rendezés kiemelkedően fontos tevékenység az adatfeldolgozás során. Rendezésnek nevezzük azt a folyamatot, amikor egy halmaz elemeit valamilyen szabály szerint sorba állítjuk. A rendezés meggyorsítja az elemek későbbi keresését. (telefonkönyv, tartalomjegyzékek, tárgymutató, könyvtárak, áruházak, stb. ) Rendezési eljárások: az algoritmusok sokfélesége ... Az algoritmus megválasztása függ a feldolgozandó adatok struktúrájától, a rendező módszereket ezen az alapon két kategóriába soroljuk: tömbök rendezése és (soros) file-ok rendezése. (Belső, illetve külső rendezés). Példa: kártyák tömbszerű strukturálása: ha a kártyákat kiterítjük az asztalon: mindegyik lap látható és közvetlenül elérhető. a kártyák file-szerű strukturálása: kártyacsomag, csak a csomagok tetején lévő lapk láthatók.

5.1.

Tömbök rendezése.

A rendezőmódszerektől megkívánt fontosabb követelmények: - gazdaságos tárkihasználás -> az elemek átrendezését “saját helyükön” kell végrehajtani. - hatékonyság, azaz időtakarékosság: mérése: összehasonlítások száma, tételmozgások száma

Rendezési módszerek: A gyorsabb algoritmusok előtt a közvetlen módszereket mutatjuk be, mivel ezek könnyen érthetőek, rövidek, ugyanakkor kiválóan alkalmasak a legfontosabb rendezőelvek jellemzőinek megvilágítására. A kifinomultabb módszerek kevesebb művelettel járnak, ezek a műveletek részleteikben jóval bonyolultabbak. A közvetlen módszerek gyorsabbak elég kis elemszámra, míg nagyobb elemszám esetén már nem érdemes használni őket.



A rendezőmódszerek, amelyek eredeti helyükön rendezik át a tömböket: -

5.1.1.

Rendezés beszúrással, Rendezés kiválasztással, Rendezés cserével

Rendezés beszúrással

Legyen az adatok száma n. A feladat az adatok növekvő sorrendbe rendezése. Ezt a módszert a kártyajátékosok is alkalmazzák. A tételeket (kártyákat) elvben két részre osztjuk: az

a1, ... ai-1

fogadó sorozatra és az

ai, ...

an

leadó sorozatra. Minden lépésben, i=2-től egyesével n-ig, kiemeljük a leadó sorozat első elemét és áttesszük a fogadó sorozatba, beszúrva őt a megfelelő helyre. Példa: Kiindulási adatok: (kulcsok) i=2

33,

45,

22

66,

33,

45,

22

i=3

33,

66,

45,

22

i=4

33,

45,

66,

22

45,

22,

66

33,

22,

45,

66

22,

33,

45,

66

33,

45,

66

A beszúrás lépései: ( i = 4-nél )

A rendezett adatok:

66,

33,

22,

33 beszúrása a {66} fogadó sorozatba 45 beszúrása a {33, 66} fogadó sorozatba 22 beszúrása a {33, 45, 66} fogadó sorozatba

A megfelelő hely megállapításához célravezető az egymás utáni összehasonlítások és mozgatások alkalmazása, a beszúrandó elem “lerostálása”. A közvetlen beszúró-algoritmus egyszerűen javítható, ha észrevesszük, hogy az a1, ... ai-1 fogadó sorozat, ahová az új tételt beszúrjuk, már rendezett. Így a beszúrás helyének megállapításához használhatunk gyorsabb módszert is. Kézenfekvő a bináris keresés alkalmazása, amelyben a fogadó sorozat felezését addig ismételjük, amíg a beszúrás helyéhez nem érkezünk. A módosított rendezőalgoritmust bináris rendezésnek nevezzük. A digitális számítógépekre a beszúró rendezés nem túl jó módszer (még a bináris beszúrással sem), ugyanis egy tétel beszúrása, amely akár egy egész sor tételnek egyetlen hellyel való odébb tolását váltja ki, gazdaságtalan megoldás.

5.1.2.

Rendezés közvetlen kiválasztással

Legyen az adatok száma n. A feladat az adatok növekvő sorrendbe rendezése. A módszer elve a következő: 1. Válasszuk ki a legkisebb elemet. 2. Cseréljük ki az első elemmel 3. Ismételjük meg ezeket a műveleteket a megmaradó n-1 majd n-2 tételre, és így tovább addig, amíg egyetlen tétel - a legnagyobbik marad. Összehasonlítások száma : 1/2 * n * (n - 1) Példa: Kiindulási adatok: (kulcsok) i=1

66,

45,

33,

22

66,

45,

33,

22

legkisebb elem: 22, csere !

i=2

22,

45,

33,

66

legkisebb elem: 33, csere !

i=3

22,

33,

45,

66

legkisebb elem: 45,

Ez a módszer bizonyos értelemben a közvetlen beszúrás fordítottja. A közvetlen beszúrás ugyanis minden lépésben a leadó sorozat egy következő tételét veszi, és a fogadó sorozat összes tételét tekintve találja meg a beszúrás helyét,



míg a közvetlen kiválasztás a leadó sorozat összes tételét tekintve találja meg a legkisebbet, amit a fogadó sorozat egy soronkövetkező helyére tesz. A közvetlen kiválasztás elemzése (a képletek mellőzésével) azt mutatja, hogy az előnyösebb a közvetlen beszúrásnál, jóllehet, ha a kulcsok kiinduláskor már rendezettek vagy majdnem rendezettek, a közvetlen beszúrás valamivel gyorsabb.

5.1.3.

Cserélő rendezések

Az előbbi két módszert is tekinthetnénk cserélő rendezéseknek. Most olyan rendezésekkel foglalkozunk, amelyekben két tétel felcserélése a legjellemzőbb művelet az eljárás során, vagyis alkalmas tétel-párok összehasonlítása és felcserélése során jutunk el az összes elem elrendezéséhez. Legyen az adatok száma n. A feladat az adatok növekvő sorrendbe rendezése. A rögzített i-dik elemet összehasonlítjuk a nála nagyobb indexű elemekkel, s ha a vizsgált elem nagyobb az i-dik elemnél, az elemeket felcseréljük. Példa: Kiindulási adatok: i=1

i=2

i=3

66,

33,

45,

22

j=2

66,

33,

45,

22

j=3

33,

66,

45,

22

j=4

33,

66,

45,

22

csere !

j=3

22,

66,

45,

33

csere !

j=4

22,

45,

66,

33

csere !

j=4

22,

33,

66,

45

csere !

csere !

Algoritmus: Függvény rendez_csere paraméterek: n: egész, a rendezendő adatok száma adat egydimenziós tömb, a rendezendő adatokat tartalmazza lokális változók: i, j egész tip. cilkus i=1 kezdőértéktől i <= n - 1 végértékig, 1 lépésközzel ciklus j=i+1 kezdőértéktől j <= n végértékig 1 lépésközzel ha adat [j] < adat [i] csere (adat [j], adat [i]) //eljárás, amely felcseréli a két paraméter értékét ciklus vége //j ciklus vége //i rendez_csere fv. vége

5.1.4.

Cserélő rendezések - Buborék rendezés

Ha a tömböt függőlegesen nézzük, a tömböt víztartálynak, a tételeket pedig “kulcsuknak” megfelelő buborékoknak gondolhatjuk. A rendezés során a buborékok felemelkednek ... A működés szemléltetése: Példa: Kiindulási adatok:

66,

33,

45,

22

1. menet

66,

33,

45,

22

66, 33 csere !

33,

66,

45,

22

66, 45 csere !

33,

45,

66,

22

66, 22 csere !



2. menet

33,

3. menet

33,

45,

22,

66

33,

45,

22,

66

33,

22,

45,

66

22,

45,

66

33, 22 csere !

22,

33,

45,

66

22,

33,

45,

66

45, 22 csere !

Algoritmus: Függvény rendez_buborek paraméterek: n: egész, a rendezendő adatok száma adat egydimenziós tömb, a rendezendő adatokat tartalmazza lokális változók: i, j egész tip.

i a menetek száma j a lépések száma

cilkus i=1 kezdőértéktől i <= n - 1 végértékig, 1 lépésközzel //menet ciklus j=1 kezdőértéktől j <= n - 1 végértékig 1 lépésközzel //lépés ha adat [j] > adat [j+1] csere (adat [j], adat [j+1]) //eljárás: felcseréli a két paraméter értékét ciklus vége //j ciklus vége //i rendez_buborek fv. vége Javított buborék rendezés: -

Minden menetben figyeljük, hogy történt-e csere. Az első olyan menetnél, ahol nem történt csere, az algoritmus befejezhető. Az i-dik menet után a hátsó i darab elem már a helyén van, fölösleges vizsgálni. A belső ciklus (n-1) helyett (n-i)-ig megy.

Függvény rendez_buborek_javitott paraméterek: n: egész, a rendezendő adatok száma adat egydimenziós tömb, a rendezendő adatokat tartalmazza lokális változók: i, j egész tip.

i a menetek száma j a lépések száma csere: egész tip, 0, ha nem volt csere, nem nulla, ha volt csere

cilkus i=1 kezdőértéktől i <= n - 1 végértékig, 1 lépésközzel //menet csere = 0 ciklus j=1 kezdőértéktől j <= n - i végértékig 1 lépésközzel //lépés ha adat [j] > adat [j+1] csere = csere + 1 csere (adat [j], adat [j+1]) //eljárás: felcseréli a két paraméter értékét ciklus vége //j ha csere == 0 kiugrás az i ciklusból ciklus vége //i rendez_buborek_javitott fv. vége

Javított buborék rendezés, példa: Kiindulási adatok:

66,

33,

45,

22

n=4



1. menet j = 1

66,

33,

45,

22

66, 33 csere !

j=2

33,

66,

45,

22

66, 45 csere !

j=3

33,

45,

66,

22

66, 22 csere !

33,

45,

22,

66

33,

45,

22,

66

45, 22 csere !

33,

22,

45,

66

33, 22 csere !

33,

45,

66

2. menet j = 1 j=2 3. menet j = 1 Rendezett tömb:

5.1.5.

22,

Gyorsrendezés (Quicksort)

Felosztva cserélő eljárásnak is nevezik. Alapelv: nagyobb hatékonyságot lehet elérni az egymástól minél távolabbi elemek cseréjével. Az eljárás lényege: az első elemet (vagy egy tetszőlegesen kiválasztott elemet) a rendezés kulcsának tekintjük abban az értelemben, hogy a tömböt két részre bontjuk úgy, hogy az első felében ne legyenek a kulcsnál nagyobb, a második felében a kulcsnál kisebb elemek. A két csoportot külön rendezhetjük. A kapott két rendezendő részre ismét alkalmazzuk a leírtakat, tehát egy rekurzív algoritmussal van dolgunk. A rekurzió akkor fejeződik be, amikor a rendezendő rész egy elemből áll. A gyorsrendezés algoritmusa: Kiválasztjuk a tömb egy tetszőleges elemét, legyen ez pl. a tömb középső eleme, értéke x Balról keressük az első, x-nél nagyobb elemet, jobbról az első, x-nél kisebb elemet és ezeket felcseréljük. A keresés - csere műveletsort addig folytatjuk, amíg a kétirányú keresés nem találkozik EREDMÉNY: a tömk két részre osztott, bal oldalon az x-nél kisebb, jobb oldalon az x-nél nagyobb elemek állnak. Az eddigi lépéseket most külön-külön, mind a két részre alkalmazzuk, a kapott részeket osztjuk tovább mindaddig, amíg mindegyik rész már csak egyetlen elemből áll. Az eljárás minden olyan programozási nyelven nagyon röviden felírható, amely a rekurziót támogatja. Más felosztó eljárások is ismeretesek, ezek között a különbség nem lényeges. Az egyik például a kulcsnak kiválasztott elemet a rendezés szerinti végleges helyére teszi, tehát a kiválasztott elem a két rész (kulcsnál kisebbek, illetve kulcsnál nagyobbak) határára teszi.

9.1.

Keresési eljárások

Keresés fileban: ld, később... Keresés tömbökben: adott az N elemű tömb és egy megadott K érték. A keresés feladata megtalálni azt az elemet, amely a megadott értékkel azonos. A keresés befejezésekor két lehetőség fordul elő: -

a keresés sikeres volt, azaz megtaláltuk az elemet, amely a megadott értékkel azonos a keresés sikertelen volt, nem találtunk a tömbben olyan elemet, amely a megadott értékű lett volna.

Szekvenciális keresés Ha a tömb elemei nem rendezettek, akkor nincs más lehetőség, mint az elsőtől az utolsóig valamennyi elemet összehasonlítjuk a keresőkulccsal. Az algoritmus így N lépésből áll, csak akkor fejeződik be kevesebb lépésben, ha a keresett elemet megtaláljuk és tudjuk, hogy nincs két egyforma elem a tömbben. Ha a tömb elemei rendezettek, pl. növekvő sorrendben, csak akkor van értelme a feladatnak, ha a keresett érték az első és az utolsó elem értéke közötti. Sikertelen keresés esetén a műveletigény N-nel arányos. Rendezett táblázatokban hatékonyabb keresési algoritmusokat is alkalmazhatunk.

Bináris (logaritmikus) keresés Adott az N elemű a1, megadott K értékkel.

a2, . . . an

tömb, melynek elemei rendezettek, pl. növekvő sorrendben. Keressük azt az elemet, amely azonos egy



A keresés lényege, hogy a K kulcsot összehasonlítjuk a középső elemmel, Ekkor vagy megtaláljuk az elemet, vagy megállapítjuk, hogy a tömb melyik felében érdemes folytatni a keresést, s ezzel a vizsgálandó elemek számát máris felére csökkentettük. A megoldást egy C++ programon keresztül mutatjuk be.

*****************

6. Adatszerkezetek Az adatokat két nagy csoportba oszthatjuk, egyszerű és összetett adatokra. Az egyszerű adatot egy érték jellemzi, részekre nem bontható. Ilyenek a numerikus értékek (egész, valós), a logikai értékek , illetve a karakterek. Az összetett adatok egyszerű adatokból épülnek fel, melyek között valamilyen strukturális kapcsolat van. Ilyenek a string, a rekord, a tömb, a halmaz. A következőkben ún. absztrakt adatszerkezetekkel, illetve ezek számítógépes megvalósításával foglalkozunk: a lineáris listákkal részletesen, a hasító táblázatok és a fák, bináris fák témakörét csak röviden vázoljuk.

6.1. Lineáris listák Definíció: Egy lineáris lista n >= 0 számú R(1), R(2), ... R(n) (azonos típusú) rekordok halmaza, amelyek szerkezeti tulajdonsága a rekordok egymáshoz viszonyított lineáris elrendezése. Formálisan, ha n > 0, akkor az R(1) az első, R(n) az utolsó és az i-dik R(i) rekordot megelőzi az R(i-1), ha 1 < i <= n és az R(i)-t követi az R(i+1), ha 1 <= i < n. A lineáris lista rekurzív definíciója: Egy lineáris lista lehet: 1. üres, ha n=0, vagy 2. egy R(n) rekord hozzáfűzése egy n-1 elemű lineáris listához, ha n > 0. A lineáris listákkal végezhető műveletek: 1. A lista k-dik rekordjának elérése, hogy mezőinek tartalmát megvizsgáljuk, esetleg megváltoztassuk. 2. A k-dik rekord elé új rekord beszúrása 3. A k-dik rekord törlése 4. Két, vagy több lista egyesítése egy listává 5. Egy lineáris lista felbontása több listává 6. Másolat készítése a listáról 7. Egy listán lévő rekordok számának meghatározása 8. Egy listán lévő rekordok átrendezése valamilyen szenpon(ok) szerint 9. Egy listán lévő rekordok közül kiválasztani azokat, amelyek valamilyen tulajdonsággal rendelkeznek stb. A verem olyan lineáris lista, ahol minden beszúrás (írás) és törlés (kiolvasás) a listának ugyanazon a végén történik. (LIFO: last in, first out). A sor olyan lineáris lista, ahol minden beszúrás a lista egyik végén, minden törlés a lista másik végén történik. (FIFO: first in, first out) A kétvégű sor olyan lineáris lista, ahol minden beszúrás és minden törlés a lista mindkét végén lehetséges. A lineáris listákat a számítógépen tárolhatjuk szekvenciálisan és láncoltan.

6.1.1. Szekvenciális helyfoglalás

Egy lineáris listát a legtermészetesebben úgy tárolhatunk számítógépen, ha a lista elemeit sorban egymás után helyezzük el. A szekvenciális tárolást akkor alkalmazzuk, ha azt akarjuk, hogy a lista logikailag egymás után következő rekordjai a memóriában egymás után következzenek.



A szekvenciális tárolást megvalósíthatjuk egydimenziós tömbökkel. A tömb elemei rekordok. Szekvenciális verem

A szekvenciális tárolás kényelmes megoldást ad a verem kezelésénél. A gyakorlatban a verem mérete maximált, legyen ez VM. Szükség van egy változóra, amely a verem tetejét jelzi, az utolsónak tárolt elem helyét. Jelöljük ezt VT-vel. Ha VT = 0, a verem üres. Ha VT = VM, a verem megtelt. Jelöljük V-vel a vermet és Y-nal azt az információt, amit tárolni szeretnénk. Letárolás a verembe: VT = VT + 1 V [VT] = Y Ez a művelet nem hajtható végre, ha a verem megtelt. Vagyis ha VT = VM, a VT = VT + 1 túlcsordulást eredményez. Kiolvasás, majd törlés a veremből: Y = V[VT] VT = VT -1 Ha a kiolvasás előtt már VT = 0, vagyis a verem üres, akkor ez a művelet nem hajtható végre, nincs mit kiolvasni. Ez a ”lecsordul” eset. A VT = 0 nem feltétlenül jelent hibát, ezt programszervezésre is fel lehet használni. Mindaddig olvashatunk a veremből, amíg VT > 0. A túlcsordulás viszont programhibát jelent ! 6.1. feladat: Készítsen játékprogramot a veremkezelés szemléltetésére. A játékszabályok: Legyen egy 100 elemet befogadni képes verem. Induláskor töltsünk be 20 elemet. Egy-egy elem egy 1 és 10 közötti véletlen szám és a hozzá tartozó súly, amely szintén egy véletlen szám 1 és 5 között. A játék: tippelni kell a verem tetején lévő számra. Ha eltaláltuk, akkor annyi véletlen számmal tölti tovább a program a vermet, amennyi a kitalált szám és a hozzá tartozó súly szorzata. (A játékos nem ismeri a súlyozó tényezőket, sem a számokat) Ha nem találtuk ki a számot, akkor a verem tetején lévő szám törlődik, s az alatta lévő (következő) számra lehet tippelni. A játékos nyert, ha a verem megtelt. A nyeremény a veremben letárolt véletlen számok súlyokkal szorzott összege. A játékos vesztett, ha a verem kiűrült. Megoldás: A verem tárolására egy 100 elemű egydimenziós tömböt fogunk használni. A tömb elemei strukturák. ************** Szekvenciális sor

A sor elemeinek letárolására egydimenziós tömböt definiálunk. Két mutatót definiálunk, a sor elejére E, a sor végére V mutat. E mindig az első értékes, még ki nem olvasott elem előtti helyre mutat, míg V az utoljára beírt elem helyét adja meg. Ha a sor üres, akkor E = V = 0. Beszúrás a sor végére: V = V +1 X(V) = Y

a vége mutató a beírandó elem helyére mutat tároljuk az információt

Olvasás a sor elejéről: E = E + 1 az eleje mutató a kiolvasandó elemre mutat Y = X (E) kiolvassuk az információt. Ha az olvasás után E = V, akkor a sor kiürült, ekkor legyen E = V = 0 ! Ha tudjuk, hogy egyszerre nem kell M elemnél többet tárolni, akkor elegendő egy M elemű tömböt deklarálni a sor elemeinek tárolásához, s az M-dik után ismét az első helyet használni a tárolásra.



6.1.2. Láncolt helyfoglalás, láncolt sor

A láncolt helyfoglalás sokkal rugalmasabb és takarékosabb megoldást ad a lineáris listák tárolására. Ekkor minden rekord tartalmaz egy mutatót is, amely a lista következő rekordjának a helyét adja meg. A tárolási egység: Vektorelem:

adat

Listaelem:

adat / mutató

A láncolt lista ábrázolása: START →

1. elem ∙──→ 2. elem ∙──→ 3. elem ∙──→ 4. elem ∙──→ NULL ╙────┴─╜ ╙────┴─╜ ╙────┴─╜ ╙────┴─╜

A lista azonosítására a START mutató szolgál, ennek értékét mindig meg kell őriznünk. Az utolsó elem mutatója nem mutat sehová. (NULL) Összehasonlítás: 1. A láncolt lista további tárterületet vesz igénybe a mutatók számára. 2. A láncolt lista elemei számára mindig éppen annyi memória foglalható, amennyi az aktuális elemek tárolásához szükséges (dinamikus helyfoglalás). 3. A lista egy kiválasztott elemére sokkal könnyebb hivatkozni szekvenciális tárolás esetén. Láncolt tárolásnál végig kell menni az elemeken, az alkalmazások többségénél azonban nem véletlenszerűen kell elérni az egyes elemeket, hanem amúgy is végig kell haladni a teljes listán. 4. Elemek beszúrása és törlése egyszerűbb a láncolt tárolásnál. Az elemeket nem kell mozgatni, csak a mutatókat kell átírni. 5. Láncolt listáknál könnyebb két listát egymáshoz csatolni, vagy egy listát két részre bontani. Az elemeket sem kell mozgatni, csak a mutatókat kell átirányítani. 6. A láncolt séma bonyolultabb struktúrák létrehozására is alkalmas.

A listakezelés alapvető műveletei: -

a lista felépítése (helyfoglalás (ellenőrzéssel) a listaelem számára - a listaelemben tárolt adatok feltöltése - a listaelem hozzáfűzése a listához (a végéhez) listaelem törlése (a törlendő elem lokalizálása - a törlés elvégzése - a törölt elem területének felszabadítása) új elem beillesztése a listába, beszúrás (a beszúrás helyének lokalizálása - helyfoglalás az új listaelem számára - az elem beillesztése)

További műveletek: -

a lista törlése (valamennyi elem törlése) végighaladás a lista elemein

6.2. feladat Készítsünk listát a házipatikában található gyógyszerekről. Az egyes készítményekről az alábbi adatokat kell nyilvántartani: gyógyszer neve betegség (amelyre alkalmazható) mennyiségi egység mennyiség lejárat dátuma A lista felépítésekor a gyógyszerek neve szerinti sorrend legyen az elsődleges. Készítsen egy-egy függvényt az alábbi funkciókra: Új elem bevitele



-

Törlés Listázás (a tárolási sorrendben) Átrendezés lejárat dátuma szerint Átrendezés gyógyszer neve szerint

Megoldás: Az alábbi programban az új elem felvitele és a listázás parancsok működnek, az olvasóra bízzuk, hogy elkészítse a törlés és az átrendezés parancsokhoz a függvényeket ! A forrásszöveget egészítse ki az előadáson hallott magyarázatokkal, rajzokkal, teszt adatokkal ! ********************************* 6.1.3. Ciklikusan láncolt listák A ciklikusan láncolt lista, vagy ciklikus lista olyan láncolt lista, amelyben az utolsó elem mutatója nem NULL, hanem az első elemre mutató cím. Ilyen módon a lista bármelyik része bármelyik adott pontból kiindulva elérhető. A listában ki kell jelölni egy lista-fejet, ennek címét mindig ismerni kell. ábra:

6.1.4. Kétszeresen láncolt listák

Egyszeresen láncolt lista esetén mindig az első elemtől kiindulva és csak egy irányban lehet bejárni a lista elemeit. Ha egy adott elemen “állunk”, csak a következő elemre léphetünk, visszafelé nem. (Az elem nem tartalmazza a megelőző elem címét.) Kétszeresen láncolt lista: minden rekordban két mutatót helyezünk el, az egyik a rekordot megelőző, a másik a rekordot követő rekord címét tartalmazza. ábra: Az ilyen listát is ciklikussá lehet tenni.

6.2.

Hasító táblázatok

A hasító táblázat a szokásos egydimenziós tömb fogalmának általánosítása. A tömbelemek közvetlen címzésének előnye, hogy egy adott elemet közvetlenül, adott idő alatt lehet elérni. A közvetlen címzést akkor alkalmazhatjuk, ha rendelkezünk olyan nagyságú tárterülettel, hogy minden elemnek megfeleltethetünk egy tömb elemet. A témával részleteiben nem foglalkozunk, az alábbi könyvekben talál további információt: N. Wirth: Algoritmusok + adatstruktúrák = programok (MK. 1982.) Mágoriné Huhn Ágnes: Algoritmusok és adatszerkezetek (JGYF kiadó, Szeged, 2000.)

6.3.

Fák, bináris fák

A fa a számítógépes algoritmusokban előforduló legfontosabb nem lineáris struktúra. Az azonos típusú rekordokból (C-ben struktúra) a következőképpen alkothatunk fastruktúrát, vagy röviden fát: Egy fastruktúra 1. vagy üres, 2. vagy egy kitüntetett csúcshoz (T-hez) kapcsolódó véges sok, közös csúcs nélküli T1, T2, ... Tm, fából áll. A kitüntetett T csúcsot a fa gyökerének, míg a T1, T2, ... Tm fákat a gyökér részfáinak nevezzük.



A lineáris lista tehát olyan fastruktúra, amelyben minden csúcshoz legfeljebb egy részfa tartozik. A line áris listákat ezért elfajult fáknak is tekinthetjük. A témával részleteiben nem foglalkozunk, az alábbi könyvekben talál további információt: N. Wirth: Algoritmusok + adatstruktúrák = programok (MK. 1982.) Mágoriné Huhn Ágnes: Algoritmusok és adatszerkezetek (JGYF kiadó, Szeged, 2000.)

7. Függvények általános jellemzői Bonyolultabb algoritmusok: részfeladat(ok ) kijelölése: Részfeladat típusa Részfeladat neve Tevékenység-sorozat Részfeladat vége A kiemelt rész-feladat: szubrutin. (eljárás, alprogram) Olyan tevékenységsorozatot célszerű szubrutinban megoldani, amely: önállóan kezelhető, ismétlődő (a programban többször szükséges a meghívása). Példa: üzenet kiírása (ismétlődő előfordulás) másodfokú egyenlet megoldása (más-más paraméterekkel …) Eljárás, szubrutin: meghatározott tevékenységsorozat végrehajtását jelenti. Függvény: Olyan szubrutin, amely olyan tevékenységsorozat végrehajtását jelenti, melynek eredményeként a függvény egy értéket állít elő és ad vissza a hívási pontra. A C-ben és a C++-ban a programok építőkövei a függvények. A függvények általános alakja a C-ben:

visszatérési_típus { függvénytörzs }

függvénynév (paraméterlista)

Visszatérési típus: visszatérési érték típusa. (Alapértelmezett: egész típus) Függvénynév: az egyszerű változó nevével kapcsolatos szabályokat kell betartani. Paraméterlista: azon – típussal és névvel megadott – változók felsorolása (vesszővel elválasztva), amelyekkel az átadott paraméterekre hivatkozhatunk a függvényen belül. Ha nincs paraméter: void (C-ben kötelező) Függvénytörzs: deklarációk, utasítások A függvényen belül a végrehajtás végét az utolsó zárójel jelenti, ekkor a hívó eljárás visszakapja a vezérlést. Ennél korábbi visszatérést a return utasítással kényszeríthetünk ki. Egy nem void-ként deklarált függvény visszatérési értékként a return utasítás mögött álló kifejezés értékét kapja meg. Egy függvényen belül tetszőleges számú return utasítás elhelyezhető. A return utasítás feladatai:

  

Befejezi a függvény működését és a vezérlés visszakerül a hívó függvényhez. return; alakban használva olyan függvényből léphetünk ki, amely a nevével nem ad vissza semmilyen értéket. Ha a függvény valamilyen értékkel tér vissza a hívás helyére, ezt az értéket a return utasításban definiálhatjuk: return kifejezés;

7.1. feladat Készítsen egy olyan függvényt, amely valamilyen üdvözlő szöveget ír ki a képernyőre, véletlenszerűen választva 5 letárolt üzenetből. Hívja meg a függvényt háromszor egymás után. Megoldás: A függvénynek nincs paramétere, sem visszatérési értéke. A függvény aktivizálásakor (meghívásakor) egy üzenet fog megjelenni a képernyőn.



#include <stdio.h> #include #include <stdlib.h> void koszon (void);

// A koszon függvény prototípusa

void main (void) { int i; clrscr (); //meghívjuk a koszon függvényt háromszor randomize (); for (i=1; i<4; i++) koszon (); getch(); } void koszon (void) { /*

//A koszon függvény definíciója

A függvény véletlenszerűen választ öt üdvözlő szöveg közül és kiírja azt a képernyőre. A függvény első hívása előtt ki kell adni a randomize() függvényt !

*/ int v; v= random (5); switch (v) { case 0: printf case 1: printf case 2: printf case 3: printf case 4: printf }

//helyi változó deklarációja

("\nÜdvözlöm !"); ("\nJó munkát !"); ("\nSzia !"); ("\nHelló !"); ("\nJó napot! ");

return; return; return; return;

} 7.2. feladat Készítsen egy olyan függvényt, amely adott sorszámú üzenetet ír ki a képernyőre. Hívja meg a függvényt ötször, öt különböző sorszámú üzenet kiírásához. Megoldás: A függvénynek egy paramétere van, a kiírandó üzenet sorszáma, visszatérési értéke 0, ha nincs az átadott paraméternek megfelelő üzenet és 1, ha az üzenet kiírása sikeres volt. #include <stdio.h> #include int uzen (int);

// A koszon függvény prototípusa

void main (void) { int i, ok; clrscr (); //meghívjuk a koszon függvényt hatszor for (i=1; i<7; i++) { ok = uzen (i); //Az uzen függvény hívása printf (" ** %2d **", ok); } getch(); } int uzen (int sorszam)

//Az uzen függvény definíciója



{ switch (sorszam) { case 1: printf ("\nElső üzenet"); case 2: printf ("\nMásodik üzenet"); case 3: printf ("\nHarmadik üzenet"); case 4: printf ("\nNegyedik üzenet"); case 5: printf ("\nÖtödik üzenet"); default: return 0; }

return return return return return

1; 1; 1; 1; 1;

}

Függvények definíciója és deklarációja C-ben Függvények definíciója: Általános alak: Visszatérési érték típusa

függvénynév

(formális paraméterek listája)

/* Függvényfej, melyet nem zár le pontosvessző ! */ { /* A függvény törzse */ lokális definíciók és deklarációk utasítások } A saját függvényeinket mindig definiálni kell. A definíciót csak egyszer lehet megadni. A C programon belül bárhol elhelyezkedhet. Ha a definíció megelőzi a hívás (felhasználás) helyét, akkor ez egyben a függvény deklarációja is. Függvények deklarációja: Általános alak: Visszatérési érték típusa

függvénynév

();

Megadja a függvény nevét és a visszatérési érték típusát, de nincs információ a paraméterektől. A függvény deklarációját mindig pontosvesszővel kell zárni ! Függvények prototípusa: Általános alak:

Visszatérési_érték_típusa

függvénynév (formális_paraméterek_típusai);

A függvény prototípusát mindig pontosvesszővel kell zárni ! C++-ban csak a prototípus használható. (Könyvtári függvények: prototípus az include állományokban …) Prototípus példák:

float sum ( int , float ); /* függvénynév: sum paraméter: 2 db, int és float típusú vissz.ért.típus: float */ uj ( int, long ); /* függvénynév: uj paraméter: 2 db, int és long vissz.ért.típus: int ( default ) fgv ( void ); /* függvénynév: fgv paraméter: nincs vissz.ért.típus: int

(default)

*/

*/



void billentyu(void); /* függvénynév: billentyu paraméter: nincs vissz.érték: nincs */

A függvények paraméterei Definíció, paraméterlista: minden paraméter előtt ott áll a paraméter típusa. FORMÁLIS PARAMÉTEREK Példa: int uzen (int sorszam); A deklarált paraméterek a függvényen belül mint a függvény lokális változói használhatók, a függvényen kívülről azonban nem érhetők el. Prototípus: csak a típusok felsorolása, de a sorrend azonos kell legyen !

A függvényhívás A függvényhívás során a vezérlés átadódik a hívó függvénytől az aktivizált függvényhez. A paraméterek (ha vannak) szintén átadódnak a meghívott függvénynek. A már bemutatott return utasítás végrehajtásakor, vagy a függvénytörzs utolsó utasításának végrehajtása után a vezérlés visszakerül a hívás helyére. Ha a függvény típusa nem void, akkor kötelező a return utasítás használata, s ekkor a return utasításban szereplő kifejezés értéke, mint függvényérték (visszatérési érték) jelenik meg. A függvény hívásnál megadott paramétereket AKTUÁLIS PARAMÉTEReknek nevezzük. Paraméter átadási módok: Érték szerinti

Cím szerinti Érték szerinti paraméterátadás: 1. 2. 3. 4. 5.

A formális paraméter számára lefoglalódik egy megfelelő méretű memóriaterület Ide átmásolódik az aktuális paraméter értéke. Lehet kifejezés is az aktuális paraméter, ekkor a kifejezés értéke kerül másolásra. A rutinban ezen a külön memóriaterületen dolgozunk a formális paraméter értékének módosításakor. A rutin végén a formális paraméterek számára lefoglalt memóriaterület felszabadul.

Példa: A: 5 Az A aktuális paraméter értéke 5 1. lépés: az F formális paraméter számára helyfoglalás a memóriában. 2. lépés: F értéke 5 lesz (az aktuális paraméter értéke ide másolódik) 3. lépés: F módisítása a rutinban, pl. F új értéke 10 lesz 4. lépés: a rutin végén az F számára lefoglalt memóriaterület felszabadul, az ott tárolt érték elvész. Az aktuális paraméter értéke nem változott, A értéke : 5. A paraméter értéke a rutin szempontjából csak bemenő, input érték. A rutin során nem történhet olyan értékadás, amely az algoritmust az eljáráson kívül befolyásolja. Hátránya: a másolat egy új helyen kerül tárolásra.

Cím szerinti paraméterátadás: 1.

Az aktuális paraméter címe rendelődik a formális paraméterhez.

Nincs külön memóriafoglalás, ugyanaz a memóriaterülete az aktuális és a formális paraméternek.

2. A rutinban módosítva a formális paraméter értékét, az aktuális paraméter értéke is megváltozik. 3. A rutin végén a formális paraméter hozzárendelése a memóriaterülethez megszűnik. A paraméter értéke a rutin szempontjából kimenő, output érték is lehet! A paraméternek a rutinban történő módosítása hatással van az algoritmusra a rutinon kívül. A pszeudókódban a cím szerint átadott paramétereket a formális paraméter aláhúzásával jelöljük a rutin fejrészében. Hasonlóan a hívási ponton is.



Az aktuális és a formális paraméterek megfeleltetése balról jobbra, a felsorolás sorrendjében történik. Az aktuális és a formális paramétereknek (típusban), sorrendben és darabszámban egyezniük kell. C-ben csak érték szerinti paraméterátadás van. A paraméterek cím szerint történő átadásáról nekünk kell gondoskodni.

8. Adatállományok kezelése Az adatállományok tárolása rendszerint a számítógépek háttértárain történik (hajlékonylemez, merevlemez), névvel ellátott, fizikailag létező file formájában. A C nyelvben az adatállományokat tartalmuk alapján szöveges és bináris fájlokra osztjuk. Szöveges állományok: A szöveges file tetszőleges hosszúságú sorokból épül fel, a sor végét (MS-DOS állományok esetén) CR/LF zárja, az állomány végét az EOF vezérlő karakter jelzi. Általában olvasható szöveget tartalmaznak, például ilyenek a C++ forrásfileok, a gyakorlatok anyagát tartalmazó, txt kiterjesztésű fileok, stb. Bináris állományok: A bináris állományok byteokból épülnek fel. (A szöveges állomány is feldolgozható, mint bináris file.) Alapvető különbség van a két file-típus között pl. a számok tárolásában. A 2002 egy szöveges állományban a ’2’, ’0’, ’0’, ’2’ karakterek sorozatával kerül letárolásra, míg bináris állományban a szám a short int típusnak megfelelően, 2 byton kerül letárolásra úgy, ahogyan a memóriában megjelenik. A file-kezelés lépései C-ben: -

a file-t azonosító mutató definiálása az állomány megnyitása az állomány tartalmának feldolgozása file-műveletek (olvasás, írás, pozicionálás, stb. ) felhasználásával. az állomány lezárása

A file mutató definiálása

A programban mindegyik felhasználni kívánt állományhoz egy külön file mutatót kell létrehozni. FILE * típusú file-mutató azonosítja az állományt.

A file megnyitása

A háttértárolón lévő file tartalmához csak a file megnyitása után férhetünk hozzá. A megnyitáskor meg kell adni a file típusát (szöveges vagy bináris) és a hozzáférés módját. A megnyitás általános formája C-ben: FILE *fopen (const char *filename, const char *mode); ahol filename az állomány neve, ahogyan az operációs rendszerben használjuk (tartalmazhatja a teljes elérési útvonalat is, ekkor figyelni kell arra, hogy a \ karakter string konstansban való megadása: \\) mode : ez is egy string, amely a file elérését és típusát határozza meg .

A file lezárása

A használat végén fclose függvény hívással le kell zárnunk az írásra és/vagy olvasásra megnyitott fileokat. A file lezárásakor a memóriában a filehoz tartozó pufferek és más területek automatikus felszabadítása is megtörténik. Ha az állományon írási műveletet hajtottunk végre, akkor zárás előtt a memóriában található átmeneti pufferek tartalmát célszerű a fileba írni.



FILE *f1; .... fflush (f1); fclose (f1); A file végének vizsgálata

A file olvasásakor az feof függvény 1 értéke jelzi a file vége esemény bekövetkezését. int feof (FILE *f); A file vége figyelést általában while ciklusban végezzük. while (! feof (f1) { fscanf (f1, ......); } close (f1);

// olvasás a fileból

Pozicionálás a fileban

A file elejére a rewind függvénnyel pozícionálhatunk: rewind (f1); Tetszőleges pozíció kiválasztása az fseek függvénnyel történhet: Hibakezelés

A hibák kezelésére az alábbi függvényeket használhatjuk: feof (fp) 0 a visszatérési érték, ha elértük a file végét (ez nem mindig jelent hibát !) ferror (fp)

0 a visszatérési érték, ha az utolsó file művelet során hiba volt. (A stream hiba-jelző adatát teszteli.)

clearerror (fp)

alaphelyzetbe állítja a stream hiba- és file-vége jelzőjét.

8.1. Szöveges állományok kezelése A megnyitott szöveges adatállományok írására és olvasására C-ben az alábbi függvényeket használhatjuk: Karakter írása és olvasása:

int fputc (int c, FILE *stream); int fgetc (FILE *stream);

String írása és olvasása

int (fputs (const char *s, FILE *stream); char * fgets (char *s, int n, FILE *stream);

Formázott adatok írása és olvasása: int fprintf (FILE *stream, const char *format, ...); int fscanf (FILE *stream, const char *format, ...);

8.2. Bináris állományok kezelése A bináris állományok kezelése byteonként, vagy blokkonként végezhető el. A byteos kezeléshez az fgetc és az fputc függvények adnak lehetőséget. A memóriablokkok fileba írása az fwrite, fileból visszaolvasása az fread függvénnyel végezhető.



size_t fread (void *ptr, size_t size, size_t n, FILE *stream); size_t fwrite (const void *ptr, size_t size, size_t n, FILE *stream); Mindkét függvény adott size méretű adat-elemekkel dolgozik, ezekből n darabot ír ki vagy olvas be a függvényhívás során. A függvények visszatérési értéke a ténylegesen kiírt vagy a visszaolvasott elemek (nem byteok!) számát adja meg. Mivel a C-ben nem létezik a rekordos file fogalma, ezért a rekordok írására és olvasására is a fenti függvényeket használjuk.

9. Gráfalgoritmusok Bevezetés Algoritmikus problémák megoldása során gyakran van szükség dolgok közötti bináris kapcsolatok kezelésére, erre modellként szolgálhatnak a gráfok. Megfeleltetés: a gráf csúcsai az objektumok, a gráf élei az objektumok közötti kapcsolatoknak felelnek meg. (Pl.: Baranya megye települései, a településeket összekötő utak) A gráf mint modellezési eszköz népszerű a számítástudományban egyszerűsége, kezelhetősége, kifejező képességének tágassága miatt. Hálós megközelítés: az egyik legjelentősebb adatmodellező irányzat; irányított gráfokat alkalmaz. Gráf az egész világ. Gráfoknak tekinthetők a belső memóriás adatkezelés listaszerkezetei is, ahol az adatelemek közötti mutatók jelentik az éleket. Ebben a témakörben gyakran előforduló algoritmusok az elérhetőséggel, összefüggőséggel, bejárhatósággal kapcsolatosak. Mi csak az alapfogalmakkal és néhány, az alkalmazásokban gyakran felmerülő feladattal foglalkozunk 9.1. Alapfogalmak, jelölések Egy G gráf két halmazból áll: a csúcsok (vagy pontok) V halmazából, mely egy véges, nem üres halmaz; és az élek E halmazából, amelynek elemei bizonyos V-beli párok. A halmazok elemszáma: n = |V| és e = |E| A gráf jelölése: G = (V, E) Irányított gráf: ha a V-beli pontpárokról kikötjük, hogy rendezettek legyenek. Irányítatlan gráf, vagy egyszerűen gráf: ha a fenti rendezettség nem áll fenn. Az irányított gráfokat szimmetrikus, míg az irányítatlan gráfokat nem szimmetrikus kapcsolatok leírására használhatjuk. Az élekhez súlyokat (költségeket) tarthatunk nyilván. (pl. idő, pénz, távolság…), az objektumok közötti kapcsolat ugyanis gyakran jelenti út létezését, vagy pl. kommunikáció lehetőségét. Út fogalma: csúcsok olyan v1, …, vk sorozata, melyre minden i-re (1 <= i <= k) a (vi, v i+1) éle a gráfnak. Egy utat körnek nevezünk, ha a kezdő és a végpontja megegyezik. Egy út, ill. kör egyszerű, ha minden csúcs, amin áthalad, különböző, kivéve a kör kezdő- és végpontját. Gráfok ábrázolásai Adatszerkezetekkel: adjacencia mátrix, vagy éllista. Adjacencia-mátrix, vagy szomszédsági mátrix: A

G = (V, E) gráf adjacencia mátrixa: 0 ha (i, j) nem eleme E-nek A [i, j] = 1 ha (i, j) eleme E-nek

Irányítatlan gráfok esetén a szomszédossági mátrix szimmetrikus, azaz A [i, j] = A [j, i] teljesül minden i, j csúcspárra.

Példa: 0 0

0 1 0 1 0 0 0 0 0 1



0 0 0

0 0 0

0 0 0 0 0 0

0 1 0 1 0 1

A mátrix kezelése a számítástechnikában: kétdimenziós tömbként, ez egyszerű, tiszta megoldás. Hátránya: a tömb mérete teljesen független az élek számától, így ha a gráf kevés élet, de sok csúcsot tartalmaz, akkor hasznosabb az éllistás megadás.

Gráfok éllistás ábrázolása: A G = (V, E) gráf minden csúcsához egy lista tartozik, ebben a listában tároljuk ezen csúcsból kimenő éleket és ha kell, akkor a súlyokat is. Az élnek a lista egy eleme felel meg. A lista elemeit mutatókkal láncoljuk egymás után (esetlen kétszeresen láncolt megoldást alkalmazva). Egy irányított gráf éllistás megadásában az n listán összesen e cella szerepel, tehát az egész szerkezet elfér n + e cellányi helyen. Az éllistás ábrázolás előnye továbbá, hogy gyorsan áttekinthetjük az egy csúcsból kiinduló összes élet. Az adjacencia mátrix esetén viszont gyorsan el tudjuk dönteni, hogy egy adott (i, j) pár éle-e a gráfnak. 9.2. A legrövidebb utak problémája (egy forrásból) Legyen adott a G = (V, E) irányított gráf a c(f) f Є E élsúlyokkal. A csúcsok például jelenthetik a Mecsek hegység egyes kitüntetett pontjait, az élek pedig az egyes pontokat összekötő turista utakat( ha van adott kér pont között közvetlen összeköttetés), a súlyok pedig azt, hogy mennyi idő alatt lehet elgyalogolni az egyik pontból a másikba. Kérdés lehet, hogy mekkora (időben mérve) a legrövidebb út egy megadott pontból egy másik megadott pontba, vagy egy adott pontból az összes többibe vagy bármely két pont között. Meglepő módon az első két probléma „ugyanolyan nehéz”, vagyis ha az egyiket megoldottuk, az algoritmus a másikat is megoldja. Tehát rögtön a második kérdéssel foglalkozunk.

A feladat pontos megfogalmazása: A G gráf egy u-t v-vel összekötő u ~> v irányított útjának hossza az úton szereplő élek súlyainak összege. Legrövidebb u ~> v út: olyan u ~> v út, amelynek hossza minimális a gráfbeli u ~> v utak közül. Az u és v csúcsok d(u,v) távolsága: 0 ha u = v végtelen, ha nincs u ~> v út a legrövidebb u ~> v út hossza egyébként Vigyázat, u és v nem felcserélhető ! Jelöljünk ki a G gráfban egy s Є V csúcsot forrásnak. Először határozzuk meg az u Є V pontoknak az s-től való távolságát. Tegyük fel, hogy a c(f) élsúlyok nemnegatívak. Adott egy G = (V, E) irányított gráf, a c (f) nemnegatív értékű súlyfüggvény, és egy s Є V csúcs (a forrás). Határozzuk meg minden v Є V -re a d(s,v) távolságot. MEGOLDÁSOK: Dijkstra módszere (az irodalom szerint hatékony és bűbájosan egyszerű) adjacencia mátrixszal, ill. éllistával: az algoritmusokat ld a szakirodalomban. Mindkét algoritmus a futási idő nagyságrendjének megtartása mellett kiegészíthető, legrövidebb utak hosszára, hanem magukra a legrövidebb utakra is kiváncsiak vagyunk.

ha nemcsak a

Bellmann - Ford módszer: olyan módszert ad az egy pontból kiinduló legrövidebb utak hosszának meghatározására, amely akkor is működik, ha bizonyos élsúlyok negatívak. A nagyobb általánosságért idővel fizetünk ! 9.3. Az összes csúcspár közötti távolság meghatározása Hogyan lehet egy irányított gráfban az összes pontpár távolságát meghatározni, majd ennek speciális eseteként csak arra vagyunk kíváncsiak, hogy mely pontok között vezet egyáltalán út.



Összes pontpár távolsága: nemnegatív élsúlyok esetén, ha a Dijkstra algoritmust az összes csúcsra, mint forrásra lefuttatjuk, akkor az összes rendezett pontpár távolságát megkapjuk. Van egy ennél közvetlenebb módszer, amely akkor is működik, ha van a gráfban negatív élsúly: ezt a módszert R. W. Floyd dolgozta ki. Az eljárás kibővíthető: a legrövidebb utak nyomonkövetése. 9.4. Mélységi bejárás Gráfokkal kapcsolatos algoritmikus feladatokban gyakran van szükség arra, hogy az élek mentén haladva végigjárjuk a gráf összes csúcsát. Az erre a célra szolgáló bejáró algoritmusok központi jelentőségűek a gráf_algoritmusok között. A bejáró módszerek segítségével szabályozható a sorrend, amely szerint a csúcsokhoz kötődő munkákat elvégezzük. A bejáró módszerek különösen alkalmasak gráfok szerkezetének feltérképezésére, segítségükkel pontról pontra lépkedve összegyűjthetők a szükséges információk. Két általános, tetszőleges gráfra működő módszer: mélységi bejárás vagy keresés (depth-first-search, DFS) szélességi bejárás vagy keresés (breadth-first-search, BFS) Mindkettő számtalan gráf_algoritmus alapjául szolgál. Példa: egy régi kisváros girbe-gurba utcácskáin bolyongó, kopott emlékezetű lámpagyújtogató… (vagy: Pécs belvárosában reklámújságokat kézbesítő diákcsapat) A lámpagyújtó minden este elindul (onnét, ahol éppen van), hogy végigjárja a kisváros lámpáit (gráf pontjai). Sosem tudja hol jár, csak azt tudja, hogy merről jött és egy-egy lámpánál az onnan induló utcácskákba (gráf élei) bepillantva látja, hogy arrafelé a következő lámpa ég-e. Elindul az egyik (még sötét) utcán. Felgyújtja a következő lámpát is, majd továbbmegy arra, amerről nem lát fényt. Ezt addig folytatja, amíg egy olyan lámpához ér, amelyből kiinduló összes utcában fény van. Ekkor visszamegy arra, amerről ide érkezett, és onnan próbál másfelé, a még sötét lámpák felé indulni. Ha már erre sincs sötét utca, akkor még visszább megy. Egy idő után visszaérkezik a kiinduló pontra, és megpróbál másfelé elindulni. Ha már minden irányt végigjárt, újra visszajut a kezdőpontra és mindenfelől fényt lát. Ekkor hazamehet. A módszer lényege: addig ment egyre „mélyebben” a városkába, ameddig volt olyan hely, ahol még nem járt.

A másik módszer - a szélességi bejárás - szemléltetése: A lámpagyújtogató a születésnapján elhívja az összes barátját, hogy segítsenek neki. A szenilis barátok, - miután az első lámpát közösen meggyújtották - annyifelé oszlanak, ahány utca onnét indul. Meggyújtják az összes szomszédos lámpát, majd tovább osztódnak és a még sötét utcák felé indulnak. Tehát széltében terjeszkedve özönlik el a várost. A két stratégia közötti lényeges különbség jól szemlélhető, ha felülről nézzük a várost: Az első módszer szerint a kiindulóponttól távoli helyeken is már lesz fény, amikor a kiindulópont környékén még van sötét lámpa. A második módszerrel viszont a kiindulópont kis környezetében lesz teljes világosság először. A szélességi bejárás hatékonyan párhuzamosítható, bár itt is van olyan implementáció, ahol a szomszédos pontokat nem egyszerre, hanem egymás után gyújtják meg. 9.4.1. Irányított gráfok mélységi bejárása A mélységi bejárás egyfajta mohó menetelés. Egy kijelölt kezdőponttól kiindulva addig megyünk tovább az irányított élek mentén, amíg már nem tudunk még be nem járt csúcsba jutni. Ekkor visszamegyünk az út utolsó előtti pontjáig, és onnét próbálunk másfelé tovább lépni és előremenni. Ha ezek a lehetőségek is kimerültek, akkor még eggyel visszamegyünk és így tovább… Ha egy v pontból már nem tudunk előre lépni, azt mondjuk, hogy a v pont mélységi bejárása befejeződött. Ha már a kezdőpont bejárását is befejeztük, de még mindig van a gráfnak olyan csúcsa, ahol nem jártunk, akkor új kezdőpontot kell választanunk, mert az eredeti kezdőpontból nem érhető el minden pont irányított úton. Az algoritmust ld. a szakirodalomban. 9.5 A szélességi bejárás



A lámpagyújtogató és az Ő barátai ! Tetszőleges irányított gráfra olyan bejárási sorrendet szeretnénk, ami szerint csak akkor foglalkozunk a kezdőponttól távolabbi csúcsokkal, ha már a közelieket mind lekezeltük. Meglátogatjuk tehát az első csúcsot, majd ennek a csúcsnak az összes szomszédját. Ezután ezen szomszédok összes olyan szomszédját keressük fel, ahol még nem jártunk, és így tovább. Hogyan lehet ezt jól megszervezni ? A legjobb ismert megoldás egy sort (FIFO listát) alkalmaz. Ebbe rakjuk be az éppen meglátogatott csúcsot, hogy aztán a megfelelő időben a szomszédaira is sort kerítsünk. 9.6 Maximális párosítás páros gráfokban A lovagok és udvarhölgyek problémája … A párosítási feladatnak több fontos változata van. Ezek közös magja, hogy egy gráfban minél nagyobb olyan élrendszert (vagyis párosítást) keresünk, amelyben semelyik két élnek nincs közös végpontja. Párosítási feladatként fogalmazható meg egy sor erőforrás-kiosztási probléma, például adottak gépek és elvégzendő munkák véges halmazai: G és M. Egy gép egy adott időben csak egy munkával képes foglalkozni. Tudjuk továbbá, hogy egy-egy gép mely munkák elvégzésére alkalmas. Elérendő cél: egy időszakban minél jobban kihasználni a gépeket. A problémának megfelelő gráf ponthalmaza G U M. A g Є G gépet akkor köti él az m Є M munkához, ha g képes az m elvégzésére. A megoldások a gráf maximális élszámú párosításai.



Algoritmus készítés Szoftver fejlesztése. 2. Összetett adatszerkezetek 2.1. Egydimenziós tömbök 2.2. Stringek. 2.3

Recommend Documents