Programozás | Delphi » Fábián Zoltán - BMF-NIK Problémaosztályok és Algoritmusok

02 - Tevékenységek Delphiben (értékadás, ciklus, elágazás) Értékadás A bal oldalon csak változó állhat, míg a jobb oldalon konstans, változó, kifejezés, függvényhívás. A jobb oldali rész egyetlen értéket képvisel, amelyet a bal oldalon álló változó vesz fel. Fontos, hogy az érték, amit a változónak át szeretnénk adni, kompatibilisnek kell lennie a változó típusával. PL. x:=5*6+1; {Így x=31 lesz} Elágazás Az if utasítás Az if utasítás kétirányú, feltételes elágazást hajt végre, ha a logikai kifejezés értéke igaz. Általános formája: If logikai kifejezés then utasítás1 else utasítás2; Ha több utasítás áll a then vagy az else után, begin-end közé kell őket kapcsolni. Az else előtt soha nem lehet ‘;’. A case.of utasítás Ez az utasítás sok if.then helyett alkalmazható, a következő módon: case szelektor of A szelektor csak sorszámozott típus lehet, tehát real vagy string nem. Működése: a szelektor

bizonyos értéke esetén valamilyen utasítást végrehajt, vagy ha egyik sem egyezik a szelektor értékkel, az else ág hajtódik végre. Ez elhagyható. Fontos, hogy az else után álló utasítás után nem állhat pontosvessző, ha csak egy utasítás van A case.of utasítás az end; kulcsszóval zárul, mely jelzi a gép számára, hogy ne keressen további szelektorértéket. Formája: Case szelektor of Érték1: utasítás1; Értékn: utasításn; Else utasítás End; Ha az else után több utasítás van, azt begin.end közé kell zárni Az utolsó utasítás és az end utáni pontoavesszők elhagyhatók. Az értékek, amire az utasítás végrehajtódik, lehet egy karakter is Ebben az esetben a megadás a következő: case szelektor of ’A’: write(.) Ciklus A for utasítás A for utasítás arra való, hogy a ciklusmagot egy meghatározott számszor végrehajtsuk. Kétféle for ciklus van: az egyik a növekvő, a másik a csökkenő. For ciklusváltozó:=kezdőérték

to végérték do Begin Utasítások; End; Egy utasításból álló ciklusmag esetén a begin-end elhagyható. Ha csökkenő ciklust szeretnénk, a downto kulcsszó kerül a to helyére. A while.do utasítás Ez tartalmaz egy logikai kifejezést, amely vezérli az ismételt utasítások végrehajtását. Elöltesztelő Formája: While logikai kifejezés do begin utasítások; end; While esetén a logikai kifejezés kerül először kiértékelésre, és a ciklusmag csak akkor hajtódik végre, ha a feltétel igaz. Ha hamissá válik, a ciklus befejezi működését Egy utasítás esetén a begin-end elhagyható A repeat.until utasítás A repeat után található logikai kifejezés vezérli a ciklus végrehajtását. Egyszer mindenképpen végrehajtódik a ciklusmag, a logikai kifejezés csak ezután kerül kiértékelésre. A ciklus addig fut, amíg a feltétel hamis Ha igazzá válik, a futás befejeződik. Hátultesztelő Formája: Repeat utasítások; until logikai kifejezés;

(*Soha nem kell a begin-end) 3. Egyszerű és Összetett típusok és műveleteik Egyszerű adattípusok A sorszámozott típusok Ezek közé tartoznak: integer, shortint, longint, byte, word, boolean, char. Ide tartozik még a felsorolt típus, és a bármelyik sorszámozott típus elemiből felépített résztartománytípus. Egész típusok Az Integer és a Cardinal általános egész típusok mérete függ a fejlesztői rendszertől. Az Int64 típussal 2GB-nál nagyobb merevlemezek mérete is lekérdezhető. Típus méret értékhatár jelentése (byte) char 1 byte 0-255 Egy karakter az ASCII kódtáblából 0-255 byte 1 byte előjel nélküli egész -128.127 shortint 1 byte előjeles rövid egész -32768.32767 integer 2 byte előjeles egész 0.65535 word 2 byte előjel nélküli egész 31 31 -2 .2 -1 longint 4 byte előjeles hosszú egész 2,939*10 38 39 real 8 byte valós szám .1,701*10 string 1 byte egy max. 255 elemből álló karakterlánc 0.255 boolean 1 byte logikai

változó, igaz vagy hamis true / false A valós típusok A valós számok tárolására öt különböző típus (real, single, double, extended, comp) áll rendelkezésre. A real típus minden megkötés nélkül használható. A másik négy típushoz a 8087 mód bekapcsolása szükséges: {$N+} Ha a processzor nem tartalmazza a lebegőpontos modult, akkor annak működését emulálni kell. Erre a fordítót a {$N+,E+} globális direktívával utasíthatjuk. A {$N+} direktíva hatására olyan program keletkezik fordításkor, amely csak FPU-t tartalmazó processzoron futtatható. A lebegőpontos (floating point) elnevezés a valós számok tárolására utal. A valós számok b a x 2 formában tárolódnak, ahol az a egy fixpontos kettedes tört, míg a b a 2 hatványkitevője. típus értékkészlet Pontosság Helyfoglalás -39 38 real 2.9x10 17x10 .11-12 6 byte -45 38 single 1.5x10 34x10 .7-8 4 byte -324 308 double 5.0x10 17x10 .15-16 8 byte -4932 4932 extended 3.4x10 .11x10

.19-20 10 byte -63 63 comp .-2 :2 -1 .19-20 8 byte Logikai információk tárolása A DELPHI-ban újabb típusok is megjelentek (ByteBool, WordBool, LongBool), amelyek csak a tárolási hosszban különböznek egymástól. Alaphelyzetben az egybájtos boolean típus használata javasolt A char típus Csak egyetlen karakter tárolására alkalmas. Ennek módja: karakter:=’A’; vagy karakter:=#65; A string típus Karaktersorozatok tárolására használjuk. Lásd később A chr függvény Integer paramétere egész számot fogad és az annak megfelelő sorszámú karaktert ad vissza. Például a 65 az ASCII kódtáblában az ’A’ betűt jelöli, így: x:=chr(65) esetén x értéke ’A’ lesz. Persze x -nek k arakter típusúnak k ell lennie, különben hibaüzenetet kapunk. Az ord függvény Ha bemenő paramétere byte típusú érték, akkor az ennek megfelelő karaktert adja vissza. Tehát a megadott paraméterértékhez rendelt sorszámot szolgáltatja. Formája: X:=Ord(a); (*

x=97 lesz, mert az ’a’ ASCII kódja 97 ) A succ függvény A típus értékkészletéből megkapjuk a bemenő paraméter után következő (eggyel nagyobb sorszámú) értéket. PL Succ(’A’)=’B’ A pred függvény Megadja a paraméter értéke előtt álló (tőle eggyel kisebb sorszámú) értéket. PL Pred(30)=29 A Delphi két olyan függvényt is tartalmaz, melyek segítségével megtudhatjuk egy sorszámozott típus értékkészletének határait. A low függvény az alsó, míg a high függvény a felső határt szolgáltatja PL high(integer)=32767 A felsorolt típus Lehetőség van arra, hogy magunk is létrehozzunk sorszámozott típust. Ilyen felsorolt típus úgy készíthetünk, hogy kerek zárójelben, vesszővel elválasztva felsoroljuk az egyedi azonosítókat. A felsorolás egyben nagyság szerinti sorrendet is jelent, ahol az első elem sorszáma 0. Pl. var nyelvek: (angol, német, spanyol); A fenti deklaráció esetén az ord, succ, pred, low, high

függvények természetesen használhatóak. A résztartománytípus Ilyet bármely sorszámozott típus tetszőleges értéksorozatával definiálhatunk. PL. var index: 1100; Ha futás közben ellenőrizni kívánjuk, hogy nem lépjük-e át a résztartomány határát, akkor a programot {$R+} fordítási direktívával kell lefordítani. Ezt csak akkor ajánlatos használni, ha a program helyes működését ellenőrizzük, mivel a vizsgálat lassítja a program működését. Mutatótípusok A memória jobb kihasználása érdekében a lehetőség van dinamikus memóriakezelésre. Ennek során nem a fordítóprogram, hanem a programozó gondoskodik helyről a változók számára a memóriában. A mutató, melynek helyfoglalása 4 byte, memóriacímet tartalmaz. A cím első két byte-ja az offset-et, míg a következő képt byte a szegmenscímet tartalmazza. A mutatót egyrészt a pointer típusnévvel, másrészt pedig ^típus alakú típusleírás segítségével

deklarálhatjuk: var hely: pointer; ip: ^integer; A Delphi támogatja a C nyelvben használt sztringkezelést. Az ilyen 0-végű sztringekre mindig mutatóval hivatkozunk, melynek típusa pchar (^char). A mutatótípusok értékkészlete lehetővé teszi a DOS által elérhető teljes 1MB memória címzését. Annak jelölésére, hogy egy mutató sehova sem mutat, a nil értéket használjuk: pmem:=nil; Az Idő tárolása Delphiben az időpontok tárolását a TDateTime típusú változókban végezhetjük. Ezt a típust a System modul definiálja Összetett adattípusok Strukturált típusok tömörített tárolása A strukturált típusok adatelemei alaphelyzetben szó vagy duplaszó határon kezdődnek, a gyorsabb elérés érdekében. Ez azt jelenti, hogy a memória nem optimálisan kihasznált. Ha a deklarációban a típusmegadás előtt a packed kulcsszót használjuk, akkor elérhetjük a memória hézagmentes felhasználását, de az adatok elérése lassúbbá válik. PL.

type TNumbers = Packed array [1100] of real; Az adatelemek méretének meghatározásához használhatjuk a SizeOf függvényt, amely a típus vagy változó által lefoglalt bájtok számával tér vissza. Tömbtípusok A tömb adott számú, azonos típusú elemet tartalmazó adattípus. Az elemtípus határozza meg, hogy milyen adatokat tartalmaz a tömb. Az elemek típusa lehet egyszerű, összetett vagy a felhasználó által definiált típus A tömb lehet egy – két vagy több dimenziós. Az egydimenziós tömb a vektor, a kétdimenziós a mátrix Minden tömb a memória egy-egy folytonos területén helyezkedik el. Az egydimenziós tömb esetén az elemek egyszerűen az indexek növekvő sorrendjében követik egymást. Többdimenziós tömb elemeinek tárolása esetén mindig először a legutolsó index fut körbe, majd az utolsó előtti, stb. Az indexhatár átlépése kideríthető a {$R+} fordítási direktíva használatával. Rekord típusok Tetszőleges számú,

különböző tulajdonságú rész szerepelhet benne. Típusdeklarációja a record és az end foglalt szavak között helyezkedik el. Hivatkozás a mezőkre: pl rectankor:=’I/14’; Egy variálható rekordnak megadott feltételtől függően más és más mezői lehetnek. A lehetséges szerkezeteket a case szó mögött adjuk meg, a hagyományos mezők után. A rekordok azonosítójára vonatkozó egyetlen értékadó lépésben másolhatjuk át a mezők tartalmát, ha a rekordok ugyanolyan típusúak. Halmaz A halmaz bizonyos tulajdonságú elemek összessége. Var változó: set of alaptípus Egy halmaz maximum 256 elemet tartalmazhat, és az alaptípus csak sorszámozott típus lehet. Pl abc: set of ’a’’z’; Az in utasítás segítségével megállapítható, hogy egy elem benne van-e a halmazban. / if (halmazelem in halmaz) then/ Állománytípusok A fájl azonos típusú komponensekből álló adatszerkezet, amely nagy mennyiségű adat tárolását teszi lehetővé

a háttértárolón. Deklaráció: var fájlváltozó: file of típus; Használhatunk típus nélküli állományokat is. Ilyenkor típuskonverzió nélkül érhetjük el a lemezen lévő információt Var allomany: file; A sztringek A sztring karakter típusú elemekből épül fel. Maximális hossza 255 karakter A sztring 0 byte-ja a s ztring hosszát tartalmazza, ezért például egy 12 karakterből álló sztring 13 byte-ot f oglal a m emóriában. H a a sztring d eklarációjánál hosszabb láncot határozunk meg, mint amennyit a sztringbe írunk majd, a felesleges helyek véletlenszerű karakterekkel lesznek kitöltve. A string típust kétféleképpen használhatjuk. Az első esetben a sztringváltozó számára maximális t erületet foglal le a fordítóprogram: var nev: string; Amennyiben nincs szükség 255 karakteres sztringekre, a deklarációban szögletes zárójelek között megadhatjuk a sztring maximális hosszát: kod: string[4]; A string típusú változóban

tárolt szöveget egy darabban és k arakterenként i s f eldolgozhatjuk. A k arakteres el érés es etén a s ztringindexben ( a s ztring a zonosítója melletti szögletes zárójelben) kell megadni a vizsgálandó karakter sorszámát: nev:=’UFO’; elso:=nev[1]; //elso=U Szabványos eljárások és függvények a sztringek kezelésére Az upcase függvény Ez egyetlen kisbetű karaktert fogad, és visszatér a nagybetűs megfelelőjével. (’a’’z’) Ha paramétere nem kisbetű, változatlanul adja vissza a karaktert. Formája: upcase(a) (=’A’) A concat függvény A sztringek összefűzésére alkalmazható ez a függvény, a ’+’ operátor mellett. Így bármely sztringeket összefűzhetünk, de az í gy k apott s ztring h ossza s em hal adhatja m eg a 255 k araktert. F ormája: c oncat(sztring1,sztring2,sztring3); vagy ujsztring:=’tartalom’+’másik tartalom’; Ha az összefűzött sztring hossza túlnő a 255 karakteren, akkor onnantól az eredménysztring

tartalma elveszik. A copy függvény Ezzel egy részsztringet másolhatunk ki egy nagyobb sztringből. Három paramétere van Az első a sztring neve, amiből másolni ak arunk, a második a karakter sorszáma, ahonn an k ezdjük a másolást, a har madik pedi g m egmondja, hog y hány karakter kerüljön másolásra. Formája: S1:=’Vadember’; S2:=copy(s1, 4, 8); (* Így s2 értéke: ’ember’ ) A delete eljárás Ez az eljárás sztringből karaktereket töröl. Első paramétere a sztring, amelyből törölni kell, a második az első törlendő karakter helye, a harmadik pedig a törlendő karakterek száma. Használata: S1:=’assholefucker’; S2:=delete(s1, 4, 4); (* Így s2 értéke: assfucker ) Az insert eljárás Ezzel egy sztringbe egy részsztringet szúrhatunk be. Első paramétere a beszúrandó részsztring, második a módosítandó sztring, harmadik pedig, hogy a módosítás hányadik karaktertől kezdődjön. Formája: S1:=’fog’; S2:=insert(’kefe’, s1,

4); (* Így s2 értéke: fogkefe ) A length függvény A paraméterben megadott sztring hosszát adja vissza. Jól használható, ha egy sztring végét szeretnénk meghatározni, majd onnantól bővíteni azt. Vagy ha egy sztring elemein akarunk műveleteket végrehajtani, egy for ciklust írunk length(sztring)-ig. Formája: S:=’Nincs pénzem’; Length(s); (* s= 12 lesz, hiszen a szóköz is egy karaktert foglal ) A pos függvény Ezen f üggvény s egítségével s ztringben m egadott részsztringet lehet keresni. A pos első paramétere a részsztring, a második pedig, amiben keresünk. A függvény visszatérési értéke lehet 0, ha a részsztringet nem találta, pozitív visszatérési érték esetén megtalálta, az említett számnak megfelelő helyen. Formája: S:=’Esik az eső’; Pos(’sik’,s); (* A pos visszatérési értéke 2 ) Az str eljárás Első paramétere integer vagy real típusú szám, amelyet a második paraméterben megadott sztringbe

karaktersorozattá alakít át. Az egész szám paraméternél használhatjuk a mezőszélességet, valamint valós szám esetén a tizedek számára vonatkozó megadási módot is. Ha valós számnál 0 mezőszélességet adunk meg, akkor a szám egy egész és egy tizedes normál alakjában jelenik meg. Formája: -2 Str(0.05 : 0, s); (* s=5.0E-02 lesz //5*10 ) A val eljárás Három par amétere v an: e gy s ztring, amelyet s zámmá k ell al akítani, num erikus v áltozó ( int/real), amely a s zámértéket fogadja, és eg y e gész t ípusú v áltozó a h iba j elzésére. H a a hi baváltozó ér téke 0, a kkor a k onverzió hi bátlan v olt, egyébként az elsőnek előforduló hiba helyére mutat a sztringben. Formája: S:=’1500’; X:=0; Val(s,x,hiba); (* x=1500 lesz, a konverzió sikeres, tehát hiba=0 ) 4. Rekord, halmaz adattípus és műveletei Felsorolás, intervallum típus és műveletei Rekord típusok Tetszőleges számú, különböző tulajdonságú rész

szerepelhet benne. Típusdeklarációja a record és az end foglalt szavak között helyezkedik el. Hivatkozás a mezőkre: pl rectankor:=’I/14’; Egy variálható rekordnak megadott feltételtől függően más és más mezői lehetnek. A lehetséges szerkezeteket a case szó mögött adjuk meg, a hagyományos mezők után. Pl. Varialhato rekord = record Mezo1: type1; Mezon: typen; Case [mezo dont:] sorszamozott tipus of Konstans1: (mezo1: type11; mezo11: type1n;); konstansn: (mezo1: type11; mezo11: typenm;); end; A case kulcsszó után a mezo dont mező definíció elhagyható. Ha használjuk, akkor az a rekord önálló mezőjeként kezelhető. A fordító mindenképpen a leghosszabb meződefiníciós esetre készül fel, a variálható definíció csak a programozó kényelmét szolgálja. A rekordok azonosítójára vonatkozó egyetlen értékadó lépésben másolhatjuk át a mezők tartalmát, ha a rekordok ugyanolyan típusúak. Ugyanakkor elemenként (mezőnként) is

végezhetnénk az értékadást Halmaz A halmaz bizonyos tulajdonságú elemek összessége. Var változó: set of alaptípus Egy halmaz maximum 256 elemet tartalmazhat, és az alaptípus csak sorszámozott típus lehet. Pl. var abc: set of ’a’.’z’; szamok: set of 0.100 ascii: set of char; Az in utasítás segítségével megállapítható, hogy egy elem benne van-e a halmazban. /if (halmazelem in halmaz) then/ A felsorolt típus Lehetőség van arra, hogy magunk is létrehozzunk sorszámozott típust. Ilyen felsorolt típus úgy készíthetünk, hogy kerek zárójelben, vesszővel elválasztva felsoroljuk az egyedi azonosítókat. A felsorolás egyben nagyság szerinti sorrendet is jelent, ahol az első elem sorszáma 0. Az egyedi azonosítókat nem szabad aposztrófok közé tenni, mivel ezek nem sztringet jelölnek. Ugyanaz a név nem szerepelhet két különböző típus elemeként Pl. var nyelvek: (angol, német, spanyol); A fenti deklaráció esetén az ord (sorszám),

succ (következő elem), pred (előző elem), low (alsó határ), high (felső határ) függvények természetesen használhatóak. A résztartománytípus Ilyet bármely sorszámozott típus tetszőleges értéksorozatával definiálhatunk. A definícióban a részsorozatok, mint intervallumot, az alsó és felső határral adjuk meg. A határokat két ponttal választjuk el egymástól PL. var index: 1100; (egész számok részintervalluma) var kisbetu: ’a’’z’; (karakterek részintervalluma) Ha futás közben ellenőrizni kívánjuk, hogy nem lépjük-e át a résztartomány határát, akkor a programot {$R+} fordítási direktívával kell lefordítani. Ezt csak akkor ajánlatos használni, ha a program helyes működését ellenőrizzük, mivel a vizsgálat lassítja a program működését. 5. Verem és Sor A sor A sor olyan sorozat, amelynek az egyik végére lehet tenni új elemeket, a másik végéről pedig el lehet venni őket. Amit először tettem be, azt veszem

ki először. Angolul First In First Out (FIFO) Így működik pl a billentyűzet puffere A sor jellegű adatszervezés során általában ugyanolyan típusú adatokat használunk. A HOVA azt mutatja meg, hogy melyik helyre rakhatunk elemet, a HONNAN pedig, hogy hol van a következő kivehető elem. u 5 4 3 2 1 S(N): n elemet tartalmazó sor Műveletek: Eljárás (Üresre állítás) HOVA:=1 ; HONNAN:=1 Eljárás vége. /Ha HOVA=HONNAN akkor a sor üres./ Eljárás (SORBA(x)) Ha HOVA>N akkor HIBA(„betelt a sor”) különben S(HOVA):=x ; HOVA:=HOVA+1 Ha vége Eljárás vége. /x az új elem/ Problémák: csak egyszer megyünk végig a soron, ezért nem veszi észre ha berak-kivesz, hogy vannak szabad helyek. Nem hatékony. Ez kiküszöbölhető ha léptetjük a tömböt (lassú) vagy, ha új változót vezetünk be, ami a sor elemszámát tartalmazza (db). Javítva: Eljárás (SORBA(x)) Ha db>=MAX akkor HIBA Különben S(HOVA):=S(HONNAN); db:=db+1; Ha (HOVA=MAX) akkor

HOVA:=1 (visszaáll az elejére) Eljárás(SORBÓL(x)) Ha HONNAN=HOVA akkor HIBA(„üres a sor”) különben x:=S(HONNAN) ; HONNAN:=HONNAN-1 Ha vége Eljárás vége. Javítva: Eljárás(SORBÓL(x)) Ha db=0 akkor üres Különben MIBE:=S(HONNAN) MIBE:=MIBE-1; Ha (HONNAN=MAX) akkor HONNAN:=1 (visszaáll az elejére) A Verem A verem olyan sorozat, amelynek csak az egyik végét tudjuk kezelni, oda tehetünk be új elemet és onnan vehetünk ki elemet. Amit legutoljára tettünk be, azt kell kivenni először Ez angolul Last In First Out (LIFO) A vele végezhető műveletek: a verem tetejére való ráhelyezés és a verem tetejéről való levétel. Megszakítások kezelésekor, és eljáráshívások visszatérési címének tárolásakor használjuk. d c b a PUSH(x): tegyünk be adott elemet POP(x): kiveszünk egy elemet úgy hogy fizikailag is kikerüljön TOP(x): A verem tetején lévő elem vizsgálata V: array[1.max] of integer; (a verem tömbös megvalósítása) VM: A

veremmutató (ha a következő szabad helyet mutatja, akkor a leghatékonyabb) Ha VM=1, a verem üres. Minden beírás előtt meg kell nézni, hogy nem fogunk-e túlcsordulni Műveletek: Eljárás (TOP(x)) (Üresre állítás) VM:=1 Eljárás vége. Eljárás (PUSH(x)) Ha VM>max akkor HIBA („betelt a verem”) különben V(VM):=x ; VM:=VM+1 (berakjuk az új elemet(x) és növeljük a veremmutató értékét) Ha vége Eljárás vége. Eljárás (POP(x)) Ha VM:=1 akkor HIBA („üres a verem”) különben VM:=VM-1 ; x:=V(VM) (csökkentjük a mutatót, majd kivesszük az elemet) Ha vége Eljárás vége. 6. Láthatóság, élettartam, lokalitás, globalitás, mellékhatás Lokalitás, Globalitás Az alprogramok lokális deklarációs részében az eljárásban felhasználni kívánt címkéket, konstansokat, típusokat, változókat és alprogramokat deklarálhatjuk. A lokális deklarációs rész az eljárás fejléce és a törzse között helyezkedik el. A lokálisan

deklarált azonosítók az eljáráson kívülről nem érhetők el. A lokális változók csak az eljárás hívásakor jönnek létre, és meghalnak, ha az eljárás visszatér a hívó programhoz. A legtöbb programnyelv az ilyen jellegű objektumait egy speciálisan kezelt adatterületen, a veremben (stack) tárolja. Ezzel szemben a főprogram szintjén létrehozott változók a program adatterületén helyezkednek el, és statikus élettartamúak. Ezek a változók a program indításakor jönnek létre, és csak a programból való kilépéskor semmisülnek meg. (globálisak) Mellékhatás Egy globális változó mindenütt látszik, így értékét meg is tudjuk változtatni. A változók deklarálása csak az adott blokkon belül, valamint minden, az adott blokkon belül lévô blokkban érvényes. Ha a változót újra deklaráljuk, a külsô blokkbeli deklarációtól eltérôen, akkor a változó a belsô blokkban az új deklarációnak megfelelô tipust veszi fel, új,

lokális változóként viselkedik. A belsô blokk befejezésével, a külsô blokkba visszatérve, a változó ismét a külsô blokkban meghatározott deklarációnak megfelelô lesz. A változók élettartama A változók élettartama szoros kapcsolatban van a blokkszerkezettel. Egy változó akkor jön létre, amikor a programunk belép a változót definiáló blokkba. A blokkból való kilépéskor a változó megsemmisül. Legtovább a főprogram szintjén definiált változók élnek Az Object Pascalban lokálisan elérhető, de globális élettartamú változókat is létrehozhatunk. Az ilyen objektumokat az alprogramban típusos konstansként kell deklarálni. Láthatóság Az azonosítók érvényességi tartománya (láthatósága) a program azon részeit jelöli, ahonnan elérhetjük az azonosítóval jelölt objektumot. Szabályok: - minden azonosítót a felhasználás helye előtt deklarálni kell - Egy azonosító érvényességi tartománya arra a blokkra terjed

ki, amelyben az azonosítót deklaráltuk - Egy blokkon belül minden objektumot egyedi azonosítóval kell ellátni - Ugyanazzal a névvel különböző blokkokban különböző objektumokat deklarálhatunk - Ha a saját készítésű alprogram neve megegyezik valamelyik szabványos alprogram nevével, akkor a szabványos eljárás elérhetetlenné válik abból a blokkból, amelyik a saját alprogram definícióját tartalmazza. A szabványos függvények mindig elérhetők, ha nevük előtt a System előtagot használjuk: y:=System.sin(pi/3) Megjegyzendő: attól, hogy a változó él, még nem biztos, hogy látszik is. 7. Programozási tételek Összegzés tétele Általános feladat: Adott egy N elemű számsorozat. Számoljuk ki az elemek összegét! A sorozatot most és a továbbiakban is az N elemű A(N) vektorban tároljuk. Algoritmus: Eljárás S:=0 Ciklus I=1-től N-ig S:=S+A(I) Ciklus vége Eljárás vége. Eldöntés tétele Általános feladat: Adott egy N elemű

sorozat és egy, a sorozat elemein értelmezett T tulajdonság. Az algoritmus eredménye: annak eldöntése, hogy van-e a sorozatban legalább egy T tulajdonsággal rendelkező elem. Algoritmus: Eljárás I:=1 Ciklus amíg I<=N és A(I) nem T tulajdonságú I:=I+1 Ciklus vége VAN:=I<=N //a VAN egy logikai változó, amely csak akkor igaz értékű, ha I<=N Eljárás vége Kiválasztás tétele Általános feladat: Adott egy N elemű sorozat, egy, a sorozat elemein értelmezett T tulajdonság, valamint azt is tudjuk, hogy a sorozatban van legalább egy T tulajdonságú elem. A feladat ezen elem sorszámának meghatározása Algoritmus: Eljárás I:=1 Ciklus amíg A(I) nem T tulajdonságú I:=I+1 Ciklus vége SORSZ:=I Eljárás vége. A megszámlálás tétele Általános feladat: adott egy N elemű sorozat és egy, a sorozat elemein értelmezett T tulajdonság. A T tulajdonsággal rendelkező elemek megszámlálása a feladat Algoritmus: Eljárás S:=0 Ciklus I=1-től N-ig Ha

A(I) T tulajdonságú, akkor S:=S+1 Ciklus vége Eljárás vége A maximum kiválasztás tétele Általános feladat: Egy sorozat legnagyobb elemét kell megtalálni. A feladatot visszavezetjük az elemenkénti feldolgozásra: egy elem maximumát mindig tudjuk. Ha ismerjük K elem közül a legnagyobbat, és veszünk hozzá egy új elemet, akkor a maximum vagy az eddigi, vagy pedig az új elem lesz. (Minimum kiválasztásnál csak a feltételes utasítás feltétele fordul meg: ’<’ helyett ’>’ lesz) Algoritmus: Eljárás INDEX:=1 Ciklus I=2-től N-ig Ha A(INDEX) < A(I) akkor INDEX:=I Ciklus vége MAXINDEX:=INDEX Eljárás vége Ha a kérdést úgy tesszük fel, hogy mennyi a legnagyobb érték, akkor egy másik megoldást is kaphatunk: Eljárás ÉRTÉK:=A(1) Ciklus I=2-től N-ig Ha ÉRTÉK < A(I) akkor ÉRTÉK:=A(I) Ciklus vége MAXÉRTÉK:=ÉRTÉK Eljárás vége 8. Keresési módszerek (normál, logaritmikus) A lineáris keresés tétele Általános

feladat: Rendelkezésre áll egy N elemű sorozat, egy, a sorozat elemein értelmezett T tulajdonság. Olyan algoritmust kell írni, amely eldönti, hogy van -e T tulajdonságú elem a sorozatban, és ha van, akkor megadja a sorszámát. Algoritmus: Eljárás I:=1 Ciklus amíg I<=N és A(I) nem T tulajdonságú I:=I+1 Ciklus vége HA I<=N akkor VAN (A VAN egy logikai változó, ha van akkor true) Ha VAN akkor SORSZ:=I Ha I>N akkor NINCS Eljárás vége. Logaritmikus keresés Általános feladat: Adott egy N elemű rendezett sorozat és egy keresett elem (X). Olyan algoritmust kell írni, amely eldönti, hogy szerepel -e a keresett elem a sorozatban, s ha igen, akkor megadja a sorszámát. Kihasználjuk, hogy a vizsgált sorozat rendezett Ez alapján bármely elemről el tudjuk dönteni, hogy a keresett elem előtte vagy utána vane, vagy esetleg éppen megtaláltuk. A és F mindig annak a részintervallumnak az alsó és felső végpontjai, amelyben a keresett elem benne

lehet. Algoritmus: Eljárás A:=1 ; F:=N Ciklus K:=INT((A+F)/2) (A és F által határolt intervallum középső elemére mutat rá) Ha A(K)<X akkor A:=K+1 Ha A(K)>X akkor F:=K-1 amíg A<=F és A(K)<>X Ciklus vége Ha A<=F akkor VAN Ha VAN akkor SORSZ:=K Eljárás vége. 9. Kiválogatás és szétválogatás Kiválasztás tétele Általános feladat: Adott egy N elemű sorozat, egy, a sorozat elemein értelmezett T tulajdonság, valamint azt is tudjuk, hogy a s orozatban van legalább egy T tu lajdonságú elem. A feladat ezen ele m sorszámának meghatározása. Algoritmus: Eljárás I:=1 Ciklus amíg A(I) nem T tulajdonságú I:=I+1 Ciklus vége SORSZ:=I Eljárás vége. Szétválogatás tétele (helyben) Általános feladat: Rendelkezésre áll egy sorozat, valamint egy kijelöl t eleme. Cseréljük fel úgy a sorozat elem eit, hogy az B -nél kisebbek B előtt legyenek, a nála nagyobbak pedig utána. Algoritmus: Eljárás BDB:=0; CDB:=0 Ciklus i:=1-től n-ig

Ha A(I) T tulajdonság akkor BDB:=BDB+1; B(BDB):=A(I) Különben CDB:=CDB+1; B(N-CDB+1):=A(I) Ha vége Ciklus vége Eljárás vége Szétválogatás tétele (külön) Általános feladat: Szétválogatjuk a T tulajdonságú tömbbe, a nem T tulajdonságúakat egy másikba. elemeket az egyik Algoritmus: Eljárás BDB:=0; CDB:=0 Ciklus i:=1-től N-ig Ha A(I) T tulajdonság akkor BDB:=BDB+1; B(BDB):=A(I) Különben CDB:=CDB+1; C(CDB):=A(I) Ha vége Ciklus vége Eljárás vége 10. Rendezési módszerek, Quicksort Rendezés közvetlen kiválasztással A módszer lényege: A rendezendő számok legyenek az A vektor elemei. Az első menetben kiválasztjuk a vektor legkisebb elemét úgy, hogy az A(1) -et összehasonlítjuk A(2). A(N) mindegyikével. Ha A(1)-nél kisebb elemet találunk, felcseréljük őket, vagyis ezt a kisebbet tesszük A(1)-be. Így a menet végére A(1) biztosan a vektor legkisebb elemét tartalmazza majd. Az eljárást A(2) -vel folytatjuk, ezt hason lítjuk

össze az A(3) , , A(N) elemekkel. És így tovább N-1 lépésben a vektor rendezett lesz Algoritmus: Eljárás Ciklus I=1-től N-1-ig Ciklus J=I+1-től N-ig Ha A(J)<A(I) akkor A:=A(J) ; A(J):=A(I) ; A(I):=A Ciklus vége Ciklus vége Eljárás vége. Rendezés minimum kiválasztással A módszer lényege: A felesleges cserék kiküszöbölése érdekében két segédváltozót vezetün k be. Az ÉRTÉK tarta lmazza az adott me netben legkisebb sz ámot, az INDEX ped ig annak lelőhelyét a vektorban. Algoritmus: Eljárás Ciklus I=1-től N-1-ig INDEX:=I ; ÉRTÉK:=A(I) Ciklus J=I+1-től N-ig Ha ÉRTÉK>A(J) akkor ÉRTÉK:=A(J) ; INDEX:=J Ciklus vége A(INDEX):=A(I) ; A(I):=ÉRTÉK Ciklus vége Eljárás vége. Buborékos rendezés A buborékos rendezé s alapgondolata a szomszédos elemek cseréje. Az első menetben a rendező A vektor végéről indulva minden elemet összehasonlítunk az előtte lévővel. Amennyiben rossz sorrendben vannak, felcseréljük őket. Az első

menet végére a legkisebb elem biztosan a helyére kerül. Minden további menetben ismét a vektor végéről indulunk, de egyre kevesebb hasonlításra van szükségünk, mert a vektor eleje fokozatosan rendezetté válik. Javított Algoritmus: Eljárás Algoritmus: i:=n; Eljárás While i>1 do Ciklus I=2-től N-ig begin Ciklus J=N-től I-ig (-1-esével) cs:=0; Ha A(J-1)>A(J) akkor A:=A(J-1) for j:=1 to i-1 do A(J-1):=A(J) begin A(J):=A if a[j]>a[j+1] then Elágazás vége begin Ciklus vége cs:=j; Ciklus vége csere(a[j],a[j+1]) Eljárás vége. Eljárás vége Egyszerű beillesztéses rendezés A rendezést úgy vé gezzük, mintha kárt yáznánk, és kezünkb e egyesével vennénk fel az asztalról a kiosztott lapokat. Az éppen felvett lapnak megkeressük a kezünkben lévő, már rendezett soroz atban a helyét úgy , hogy közben a ná la nagyobbakat egy hellyel elcsúsztatjuk, végül beillesztjük a felvett lapot a neki megfelelő helyre. N elem esetén a végső

sorrend kialakításához N-1 menetre van szükség. Eredeti: 1. menet után: 2. menet után: 3. menet után: 64 56 8 8 56 8 42 64 8 42 56 64 42 42 56 64 5 5 5 5 12 12 12 12 16 16 16 16 40 40 40 40 3 3 3 3 31 31 31 31 47 47 47 47 22 22 22 22 24 24 24 24 33 33 33 33 7 7 7 7 46 46 46 46 4. menet után: 5. menet után: . 15. menet után: 5 5 8 42 56 64 12 16 40 8 12 42 56 64 16 40 3 5 7 3 31 47 22 24 33 3 31 47 22 24 33 7 46 7 46 8 12 16 22 24 31 33 40 42 46 47 56 64 Javított Algoritmus: Eljárás for i:=2 to n do begin j:=i-1; x:=a[i]; while (j>0) and (a[j]>x) do begin a[j+1]:=a[j]; j:=j-1; end; if j<>i-1 then a[j+1]:=x; Eljárás vége Algoritmus: Eljárás Ciklus J=2-től N-ig I:=J-1 ; A:=A(J) Ciklus amíg I>0 és A<A(I) A(I+1):=A(I) ; I:=I-1 Ciklus vége A(I+1):=A Ciklus vége Eljárás vége. Quicksort Igen gyors és hatékony rendezésről van szó, amelynek alapja az, hogy egymástól távol lévő elemeket hasonlítunk össze

egymással, és szükség esetén felcseréljük azokat. Válasszuk ki az A vektor első elemét, és vegyük ki a vektorból. A helye üres marad A vektor végéről indulva keresünk egy ennél kisebb elemet. Ha találunk, azt b etesszük a felszabadult helyre. Most a lyuk ott ke letkezik, ahonnan e zt az elemet kiv ettük Ide a vektor elejéről keresünk egy, a kiválasztott elemnél nagyobb elemet. Ha találunk, beillesztjük, ha nem, akkor oda éppen a kiválasztott elem illik. 64 64 64 46 46 56 56 56 56 8 8 8 8 42 42 42 42 5 5 5 5 12 12 12 12 16 16 16 16 40 40 40 40 3 3 3 3 31 31 31 31 47 47 47 47 22 22 22 22 24 24 24 24 33 33 33 33 7 7 7 7 46 46 64 A konkrét példában nem sikerült a vektort nem sikerült két részre vágni, mert a 64 éppe n a legnagyobb elem. A következő lépésben a 46-ot emeljük ki a vektor elejéről, és hátulról haladva keressünk nála kisebb elemet, és így tovább. 46 46 46 46 46 46 7 7 7 7 7 7 56 56 33 33 33 33

8 8 8 8 8 8 8 42 42 42 42 42 42 42 5 5 5 5 5 5 5 12 12 12 12 12 12 12 16 16 16 16 16 16 16 40 40 40 40 40 40 40 3 3 3 3 3 3 3 31 31 31 31 31 31 31 47 47 47 47 24 24 22 22 22 22 22 22 22 24 24 24 24 24 46 33 33 33 47 47 47 7 56 56 56 56 56 64 64 64 64 64 64 64 A 46 most a végleg es he lyére került. Tőle balra a nála kisebb, jobbra a nála nagyobb elemek helyezkednek el. Az eljárást az így kettévágott vekt or egyik részének el emeivel a fent leírt módon folytatjuk tovább. Algoritmus: Eljárás Quick(AH, FH) Szétválogat(AH, FH, E) Ha AH<E-1 akkor Quick(AH, E-1) Ha E+1<FH akkor Quck(E+1, FH) Eljárás vége A szétválogató eljár ás a vektor elemeit úgy rendezi át, ho gy az E -edik elem e lé kerülnek a nála kisebbek, mögé pedig a nagyobbak. Teljes Algoritmus Eljárás gyorsrendezés (n, A) Eljárás rendez(also, felso) I:=also; J:=felso; X:=A[(also+felso) div 2]; {n – elemszám, A - tömb} {az intervallumok szélei} {a

középső elem, div – egész osztás} Ciklus Ciklus amíg A[I]<x I:=I+1 ciklus vége {elölről} Ciklus amíg A[J]>x J:=J-1 ciklus vége {hátulról} Ha I<=J akkor csere(A[I];A[J]); I:=I+1; J:=J-1; Amíg I>J Ha also<J akkor rendez(also,J); {addig áll fenn, amíg a különbségük} Ha I<felso akkor rendez(I, felso); {legalább 1. 1-hosszúra már nem hívjuk meg} Eljárás vége Begin End; Rendez(1,N); Megjegyzések: {a főprogram} A középső elem mindig más, amíg a két határ össze nem ér. Az algoritmus sebessége függ az elemek rendezettségétől Akkor a leglassabb, ha a középső elem a legkisebb vagy a legnagyobb Akkor igazán gyors, ha nagy méretű tömbbel dolgozik Nem ismeri fel, ha a tömb rendezett, d e ekkor is gyors. A rekurzív újrahívás megtörténik. • A kis méretű tömbökre azért nem jó, mert a rekurzió lassít Hibrid megoldás: Ha a tömbméret lecsökken mon djuk 100 ele mre, akkor egy hagyományos rendező algoritmust

használunk. Tipp: a quicksort algoritmus lefutása előtt egyszerűen ellenőrizhetjük, hogy a tömb neme rendezett már. • • • • • 11. Szövegállományok kezelése A szövegfájlok karaktereket tartalmazó különböző hosszúságú sorokból épülnek fel. Minden sort az EOLN (End Of LiNe) jel zár, az egész állományt pedig az EOF (End Of File) jel zárja, ami hiányozhat is a fájl végéről (fájlvége jel lehet az állomány belsejében is). A SeekEoLN( fájlváltozó) akkor is jel zi a sor végét, ha az aktuális fájlpoz íció és a sor vége között csak szóköz vagy tabulátor karakterek állnak. EOLN EOF #13#10 (CR,LF) #26 <ENTER> <CTRL+Z> A szövegfájl a szekvenciális állományokhoz tartozik: tartalmát az elejétől olvashatjuk, vagy felülírhatjuk. Lehetőség van a fájl végétől kezdődő hozzáírásra is A fájlkezelés lépései Az állományok tartalmána k eléréséhez az oprendszertől és a programnyelvtől

függetlenül mindig ugyanazokat a főbb lépéseket kell végrehajtani: előkészületek, megnyitás, feldolgozás fájlműveletekkel, az állomány lezárása. Előkészületek A lemezen tárolt állományokat a fájlváltozóval azonosítjuk. Deklarálása: var változónév : TextFile; A megfelelő típusú fájlváltozó létrehozása után, az AssignFile eljárás segítségével össze kell rendelni a fájlváltozót egy létező vagy új állomány nevével. AssignFile(fájlváltozó, fájlnév elérési útja ) Ha az elérési utat nem adjuk meg, akkor a hivatkozás relatív lesz, tehát ott keresi maj d a fájlt, ahol a program elhelyezkedik. („hordozható lesz” a program) A fájlnyitás A reset eljárás segítségével csak létező állomány nyitható meg. A nyitás ut án az EOF függvény true értéke jelzi, ha a fájl üres. A Reset az aktuális fájlpozíciót a fájl elejére állítja (a művelet már megnyitott állományon is elvégezhető). A rewrite

eljárás új állományt hoz létre, vagy a már meglévő fájlt újraírja, így annak teljes tartalma elvész. Az állomány elejére állítja az aktuális fájlpozíciót Az append eljárás létező szöveges állományt nyit meg hozzáírásra. Az aktuális fájlpozíciót a fájl végére állítja. Szöveges állomán yok esetén mindháro m fájlnyitó eljárás egy 128 bájtos ad atátviteli puffert rendel az állományhoz. A fájlműveletek tovább gyorsíthatók, ha az alapértelmezési szövegpuffer helyett egy nagyobb méretűt jelölünk ki. Ezt a SetTextBuf eljárás hívásával, az állomány megnyitása előtt hajthatjuk végre. Ajánlott a pufferméretet 2 hatványána k választani. Írás és olvasás Ha írásra nyitottuk meg a fájlt, akkor a Write és a Write ln eljárásokkal vég ezhetjük a beírást. A különbség, hogy a writeln eljárás sorvége jeleket is ír a fájlba A szöveges állományba történő írás esetében a karakterek először az

adatátviteli pufferbe kerülnek, és csak a puffer k iürítésekor kerülnek ki a fájlba. Enne k ürítése: Flush(fájlváltozó). A Write, Writeln, Closefile automatikusan ürítik a puffert Ha olvasásra nyitott uk meg, akkor a Rea d és a Readln haszn álható. A Read kara kterenként olvas be, az aktuális fájlpozíció a következő karakter előtt lesz. A Read ln soroka t olvas, az aktuális fájlpozíció a következő sor eleje lesz. Módja: read(fájlváltozó, változólista) {A második paraméter, amibe beolvasunk} A fájl lezárása A CloseFile eljárás frissíti az állományt, így az utoljára végrehajtott műveletek eredménye is megjelenik az állományban. Az állomány lezár ása után is megmara d a kapcsolat a fáj lnév és a fájlválto zó között, így ha a programban újra meg kell nyit ni egy már lezárt á llományt, akkor nin cs szük ség újabb AssignFile hívására. A Delphi program ból kilépve minden nyitott állományt automatikusan, a

fájltartalom frissítése nélkül zár le a rendszer. Ez az írásra megnyitott fájlok esetén adatvesztéssel járhat. Előnyei: Platform-független, nyelv -független, ember szá mára olvasható, rögzítetlen struktúrájú. Hátrányai: nem hatékony tárolás (a számokat karakteres formában tárolja, míg a típusos fájl bináris formában) Szövegfájl tartalmának kiolvasása Var i: textfile; St: string; Assignfile(t, ’adat.txt’); Reset(t); While not eof(t) do Readln(t,st); {teljes sort olvas} Szövegfájl sorainak megszámlálása Db:=0; While not eof(t) do db:=db+1; Tömb tartalmának kiírása szövegfájlba Var t: textfile; A: array[1.10] of rec; I: integer; Rewrite(f); For i:=1 to 10 do writeln(t, A[i].nev, A[i]cím); Törlés szövegfájlból Amit nem szeretnénk törölni, átmásolju k egy típusos fájl ba, majd onnan vis szaírjuk a kiürített szövegfájlba. While not eof(t) do begin Readln(t,str,i,j); Rec.x:=i; Rec.y:=j; Rec.szoveg:=str;

Write(f,rec); End; Karakterenként olvasás Karakterenként olvassuk a fájlt, amíg egy adott elválasztójelhez nem érünk. While ch<> ’,’ do begin End; Read(t,ch); Str:=str+ch; Elemekre darabolás sztringműveletekkel db:=0; while not eof(t) do begin db:=db+1; readln(t,sor); tomb[db].eloado:=copy(sor,1,pos(#,sor)-1); delete(sor,1,pos(#,sor)); tomb[db].albumcim:=copy(sor,1,pos(#,sor)-1); delete(sor,1,pos(#,sor)); tomb[db].ar:=strtoint(sor); delete(sor,1,length(sor)); delete(sor,1,pos(#,sor)+1); end; 12. Típusos állományok kezelése A típusos fájlok olyan adathalmazok, amelyek azonos típusú adatelemekből épülnek fel. Az adatelemek típusa tetszőleges lehet. Az adatelemek azonos mérete lehetővé teszi, hogy az adatokat szekvenciálisan és közvetett módon egyaránt elérjük. A fájlban tárolt a datelemek a felírás sorrendjében 0 -tól kezdve egyesével számozódnak. A fájl feldolgozásánál a sorszám felhasználásával az állomány

tetszőleges elemére pozícionálhatunk. A fájl méretét a benne található adatelemek száma adja. A típus nélküli fájlok A számítógépen tárolt állományok többsége nem tagolható szövegsorokra, és a bennük tárolt adatelemek mérete sem azonos. Az ilyen állományokat típus nélküli fájlként kezelhetjük . Ez nagy segítséget jelent ismeretlen vagy nem sza bályos szerkezetű fájlok feldolgozásakor. Mivel az adatforgalom a fájl és a program között ellenőrzés nélkül megy végbe, gyors fájlkezelés valósítható meg. (var valtozonev: file) A fájlkezelés lépései Az állományok tartalmának eléréséhez az oprendszertől és a programnyelvtől függetlenül mindig ugyanazokat a főbb lépéseket kell végrehajtani: előkészületek, megnyitás, feldolgozás fájlműveletekkel, az állomány lezárása. Előkészületek A lemezen tárolt állományokat a fájlváltozóval azonosítjuk. Deklarálása: var változónév : file of tipus; A megfelelő

típusú fájlváltozó létrehozása után, az AssignFile eljárás segítségével össze kell rendelni a fájlváltozót egy létező vagy új állomány nevével. AssignFile(fájlváltozó, fájlnév elérési útja ) Ha az elérési utat nem adjuk meg, akkor a hivatkozás relatív lesz, tehát ott keresi maj d a fájlt, ahol a program elhelyezkedik. („hordozható lesz” a program) A fájlnyitás A reset eljárás segítségével csak létező állomány nyitható meg. A nyitás után az EOF függvény true értéke jelzi, ha a fájl üres. A Reset az aktuális fájlpozíciót a fájl elejére állítja (a művelet már megnyitott állományon is elvégezhető). A rewrite eljárás új állományt hoz létre, vagy a már meglévő fájlt újraírja, így annak teljes tartalma elvész. Az állomány elejére állítja az aktuális fájlpozíciót A fájlnyitó eljá rások nem határozzá k meg az adatok ára mlásának irányát. A fájlnyitás előtt a System modul FileMode

változójának történő értékadással beállíthatjuk, hogy a Reset eljárással megnyitott típuso s –és típus nélküli fájlokhoz milyen műveletekkel lehet hozzáférni: 0 (csak olvasható), 1 (csak írható), 2 (írható és olvasható). Típusos fájlok I/O műveletei A megnyitott típusos fájlban az aktuális fájlpozíció a fájl elején helyezkedik el, és az első, 0. sorszámú adatelemre mutat Minden írási vagy olvasási művelet után a fájlpozíció a következő adatelemre mutat. A fájlba írásra a Write a fájlból olvasásra a Read(fájlváltozó, változólista) szolgál. A fájl utolsó elemét követően az Eof(fájlváltozó) true értéke jelzi az állomány végének elérését. A Seek(fájlváltozó, index) eljárás az aktuális fájlpozíciót a longin t típusú index paraméterben megadott sorszámú elemre mozgatja. Ha a fájl vége után pozícionálunk (az index nagyobb, mint a fájl adatelemeinek száma), akkor az Eof függvény true

értéket ad vissza. Ilyen pozíció esetén az olvasás művelete „Read beyond end of file” hibát eredményez. A FileSize(fájlváltozó) függvény i nteger típusú viss zatérési értékben adja meg a fájlban tárolt adatelemek számát. Ha a fájl üres, az érték 0 A FilePos(fájlváltozó) függvény a longint típusú aktuális fájlpozíció értékével tér vissza. Az aktuális fájlpozíció kijelöli azt az adatelemet, amelyet a következő művelettel elérünk. Az állomány végének elérésekor a FileSize és a FilePos ugyanazt az értéket adja. A Truncate(fájlváltozó) eljárás az aktuális fájlpozíciótól kezdve csonkolja a z állományt. A fájl lezárása A CloseFile eljárás frissíti az állományt, így az utoljára végrehajtott műveletek eredménye is megjelenik az állományban. Az állomány lezár ása után is megmara d a kapcsolat a fáj lnév és a fájlválto zó között, így ha a programban újra meg kell nyit ni egy már

lezárt á llományt, akkor nin cs szükség újabb AssignFile hívására. A Delphi program ból kilépve minden nyitott állományt automatikusan, a fájltartalom frissítése nélkül zár le a rendszer. Ez az írásra megnyitott fájlok esetén adatvesztéssel járhat. Előnyei: könnyű és gyors adatkezelés, kis fájlméret a bináris tárolásnak köszönhetően. Hátrányai: Ismerni kell a típusát, hogy kezelni tudjuk; ember számára olvashatatlan; Az utolsó adatelem utánra való pozícionálás hozzáíráshoz Seek(fájlváltozó, filesize(fájlváltozó)); Az állomány teljes tartalmának törlése Seek(fájlváltozó, 0); Truncate(fájlváltozó); Egy adott adatelem törlése Módszer: az utolsó elemmel felülírjuk a törlendő elemet. Hátránya, hogy a fájl rendezetlen lesz. Módszer: a törlendőt felülírjuk az utána következővel, azt pedig az azután következővel. A végét csonkoljuk. Így a rendezettség megmarad Seek(f, filesize(f)-1); Read(f, rec);

Seek(f, i); Write(f, rec); Seek(f, filesize(f)-1); Truncate(f); Létező fájl listázása Reset(f); For i:=1 to filesize(f) do begin end; read(f, rec); memo1.linesadd(rec); 13. Rekurzió (Faktoriális, Fibonacci, Ackermann) Rekurzió A programozási nyel vekben a rekurzióró l akkor beszélünk, amikor egy program saját magát hívja (önrekurzió), vagy ha több alprogram hívja egymást (kölcsönös rekurzió). A rekurzív problémák rekurzív alprogrammal viszonylag egyszerűen megoldhatók, azonban ez a megoldás idő és memóriaigényes. Minden rekurzív problémának létezik iteratív megoldása is (és fordítva), amely általában nehezebben programozható, de több szempontbó l hatékonyabb a rekurzív megoldásnál. A program futása során az alprogram minden újabb hívásakor újabb memóriaterülete t foglal le a verembe n a paraméterek és a változók tárolásár a, ami a memória el fogyásához vezethet. Az ismétlődő hívások miatt pedig a

számítási idő nő meg Ha egy feladat rekurzív megoldásának létezik egy viszon ylag jól programozha tó iteratív (cikluso s) párja, akkor mindig az utóbbi használata javasolt. A rekurzió végre hajtása során egy ú gynevezett báziskritériumot (megállási feltételt) adunk meg, amikor a függvény vagy eljárás már nem hívja meg önmagát. Faktoriális A rekurzív működés jól tanulmányozható a faktoriális számítás algoritmusán (nem tipikusan rekurzív feladat). A faktoriális rekurzív definíciója n! = 1, ha n=0 n*(n-1)!, ha n>0 Pl. 4! Kiszámítása 4! = 4*3! 3! = 3*2! 2! = 2*1! 1! = 1*0! 4! = 4*321 = 24 Az általános függvény Function fakt rek(n: integer): integer; Begin If (n=0) then result:=1; Else result:=n*fakt rek(n-1); End; A fenti példában az n= 0 feltétel a rek urzió befejezésének feltétele. Ekkor a z utoljára hívott függvénypéldány 1 értéket ad vissza. Ezt követően a hívási lánc tagjai sorban visszatérnek a

megfelelő részeredménnyel. Utoljára a lánc első eleme, az általunk hívott függvény fejezi be működését, megadva a kívánt faktoriális értéket. A faktoriális iteratív definíciója 0! = 1 n! = n(n-1)(n-2).(n-k+1) Az általános függvény Function fakt it(n:integer): longint; Begin S:=1; For i:=1 to n do S:=S*i; Result:=s; End; Fibonacci A Fibonacci-féle számsorozat 0,1,1,2,3,5,8,13,21,34,. (a sorozat egy új eleme az előző kettő összegéből képezhető) Megoldás rekurzióval Lefelé haladva egyszerűsítjük az értékeket, amíg Fib(0)=0 vagy Fib(1)=1 nem lesz az eredmény. Ezen meg oldás hátránya, ho gy nem veszi észr e, ha már egy ré szeredményt kiszámolt. Function Fib(n: integer): integer; Begin If (n=0) then result:=0 Else If (n=1) then result:=1 Else Result:=Fib(n-1)+Fib(n-2); End; Ha a sorozat 1-ről indul, és nem 0-ról, akkor: if (n=0) or (n=1) then result:=1; Vagy: if (n<2) then result:=1; Megoldás iterációval Funtion Fib it(n:

integer): integer; Begin UE:=1; U:=1; {Utolsó Előtti, Utolsó elem} {A sorozat 1-ről indul} For i:=3 to n do begin F:=U+UE; UE:=U; U:=F; End; Ackermann A kétváltozós Ackermann -függvény: A(x,y). Már A(10,10) esetén is nagy számokat generál és egyre több számítást igényel. Ha (m=0) akkor A(0, n)=n+1 Ha (m>0) és (n=0) akkor A(m, 0):=A(m-1, 1) Ha (m>0) és (n>0) akkor A(m, n):=A(m-1, A(m, n-1)) , 14. Rekurzív ábrák Koch algoritmus A megállási feltétel a pontok koordinátái. Koch (szint: integer, x0, y0, x1, y1: integer) Var xx, yy: integer; Begin If (szint=1) then line(x0, y0, x1, y1) Else Begin Koch(szint-1, x0, y0, round(2*x0+x1/3), round(2y0+y1/3)) xx:=round((x0+x1)/2+(y0-y1)/2*sqrt(3)) yy:=round((y0+y1)/2+(x0-x1)/2*sqrt(3)) {harmadoló pont meghatározása} Koch(szint-1,xx,yy) . . . End; End; Hegyrajzolás Vegyünk egy háromszöget, oldalainak felezőpontjaira állítsunk egy merőleges szakaszt. Véletlenszerűen jelöljünk ki egy-egy pontot

a szakaszon, majd ezeket kössü k össze a csúcspontokkal. Négy darab háromszög keletkezik Ezekkel ugyanígy folytatjuk Algoritmus Hegy(szint, A, B, C): integer If (szint=1) then line(A,B,C) {A háromszög megrajzolása} Else Hegy(szint-1, A, Z, X) . . 15. Visszaléptetéses keresés (egy megoldás, összes megoldás) Általános feladat: adott N sorozat, ame lyek rendre M(1), M (2), . elemszámúak Ki kell választani mindegyikből egy-egy elemet úgy, hogy az egyes sorozatokból való választások más választásokat b efolyásoljanak. Tulajdonképpen ez egy b onyolult keresési f eladat: egy adott tulajdonsággal rendelkező szám N-est kell keresni. A megoldást úgy ké szítjük el, hogy ne kelljen az összes lehetőséget végignézni! Először megpróbálunk az első sorozatból választani e gy elemet, ezután a következőből, s ezt mindaddig csináljuk, amíg a választás lehetséges. Amikor áttérünk a következő sorozatra, akkor jeleznünk kell, hogy

ebből még nem próbáltunk elemet választani. X(I) jelöli az első sorozat kiválasztott elemének sorszámát, ha még nem választottunk, akkor értéke 0 lesz. Ha nincs jó választás, akkor visszalépünk az előző sorozathoz, s megpróbálunk abból egy másik elemet választani. Ez az egész eljárá s vagy úgy ér véget, hogy minden sorozatból sikerült választani (ekkor megkaptuk a megoldást), vagy pedig úgy, hogy a visszalépések után már az első sorozatból sem lehet újabb elemet választani (ekkor a feladatnak nincs megoldása). A megoldás egyszerűbbé válik, ha tudjuk, hogy van megfelelő tulajdonságú elemsorozat. Általános algoritmus Eljárás I:=1 Ciklus amíg I>=1 és I<=N Ha VAN JÓ ESET(I) akkor I:=I+1 ; X(I):=0 különben I:=I-1 Elágazás vége Ciklus vége Ha I>N akkor VAN Eljárás vége. Az első sorozatból úgy választunk elemet, hogy próbálunk mindaddig új elemet venni, amíg van további elem, és az éppen vizsgáltat nem

lehet választani. Ha a keresgélés közben a sorozat elemei nem fogytak el, akkor az előző szintnek mondhatjuk azt, hogy sikeres volt a választás. Ha pedig az utolsó sem felelt meg, akkor azt, hogy vissza kell lépni az előző sorozathoz. VAN JÓ ESET(I): Ciklus X(I):=X(I)+1 amíg X(I)<=M(I) és ROSSZ ESET(I,X,(I)) Ciklus vége Ha X(I)<=M(I) akkor VAN JÓ ESET Eljárás vége. ROSSZ ESET(I,X(I)): J:=1 Ciklus amíg J<I és (J,X(J)) nem zárja ki (I,X(I))-t J:=J+1 Ciklus vége Ha J<I akkor ROSSZ ESET Eljárás vége. A backtrack algoritmusra alapozva a keresési feladatokhoz hasonlóan el lehet készíten eldöntési, kiválasztási, megszámolási, kiválogatás i feladatok megoldását, sőt még valamilyen szempontból legjobb megoldás megkeresését is. i a 16. 8 királynő Adott nxn-es sakktáblán helyezzünk el n vezért úgy, hogy semelyik kettő sem üsse egymást. Nem lehet: 2,3. Lehet: 1,4,5 A megoldás módjai: valamely szisztéma szerint lépésről

lépésre az összes lehetőséget kipróbáljuk (szisztematikus); vagy próbálgatással (heurisztikus). Algoritmus (egy megoldás) Procedure Probal(i: integer, var Q: boolean) Var J: integer; Begin Repeat J:=J+1; If Y[J] and A[I+J] and B[I-J] then begin X[I]:=J; Y[J]:=false; A[I+J]:=false; B[I-J]:=false; End; Until Q or (J=8); If (I < 8) then begin Probal(I+1, Q); If not Q then begin Y[J]:=true; A[I+J]:=true; B[I-J]:=true; End; End; Else Q:=true; End; Magyarázat Q: ha találtunk megoldást, igazzá válik I: a szintet tárolja, és megőrzi az értéket J: lokális változó, az utolsó próbálkozás helyének sorát tárolja Y,A,B,X: globális változók J:=J+1: végigmegy az összes lehetséges soron, egészen J=8-ig Y[J]: logikai változókat tartalmazó tömb A[I+J]: mellékátlók (az indexek összege) B[I-J]: főátlók (az indexek különbsége) X[I]:=J: Letesszük a z elemet. Így X töm b I-edik eleme J le sz Az (I,J) pozíció ba tettünk elemet Y[J]:=false:

megjegyzi, hogy a J-edik sor foglalt A[I+J]:=false: megjegyzi, hogy a mellékátlókba már nem tehetünk elemet B[I-J]:=false: megjegyzi, hogy a főátlókba már nem tehetünk elemet If (i<8): Mivel még nem jutottunk el a 8. Oszlopba (csak ott találhatunk mego ldást), nem vagyunk készen. Egy szinttel feljebb lépünk {probal(i+1,Q)} a globális keretekkel If not Q: ellenőrzi, hogyan léptünk vissza. Ha nincs találtunk, akkor is visszalépünk, de Q értéke igaz lesz. megoldás, Q értéke hamis. Ha Y[J]:= true; A[I+J]:= true; B[I -J]:= true: Ha nem találtunk megoldást (Q értéke hamis), levesszük a tábláról a most felhelye zett elemeket, mivel ez az elrendezé s nem a d megoldást. A sorok és átlók felszabadulnak Else Q:=true: Ha Q értéke igaz, elértünk a 8. oszlopba, megoldást találtunk Until Q or (J=8): Mivel Q igaz, befejeződik a repeat ciklus, és az eljárás is. Visszalé p egészen az 1-es szintig, az eredmény pedig az X tömbben jelenik meg.

Ha Q hamis volt, a következő sorral próbálkozik, egészen 8-ig, s a ciklus emiatt áll le. Megvalósítás Y: array[1.8] of boolean; A: array[2.16] of boolean; B: array[-7.7] of boolean; Mindegyiket for ciklusok segítségével kell igazra állítani. A Q kezdőértéke hamis Grafika: If Q then ’X tömb kirajzolása’ Algoritmus (összes megoldás) Aránylag gyorsan megoldható az összes megoldása keresése. Procedure probal(i: integer) Var j: integer; Begin Ciklus k=1-től n-ig {k az adott szint, minden lehetőséget végigpróbál} k-adik jelölt kiválasztása ha megfelel, akkor jegyezzük fel ha i<n akkor probal(i+1); {ha nem vagyunk kész, következő szint} különben a megoldás kinyomtatása {ha elértük n-t} feljegyzés törlése {mindenképp töröljük, ha találtunk megoldást, akkor is} ciklus vége end; 17. A huszár útja a sakktáblán Algoritmus (egy megoldás) Procedure probal(i: integer; x,y: integer; var Q:boolean); Var k,u,v: integer; Begin

k:=0; Repeat k:=k+1; u:=x+A[k]; v:=y+B[k]; if (u>=1) and (u<=8) and (v>=1) and (v<=8) and H[u,v]=0 then begin H[u,v]:=i; If (i<n*n) then begin Probal(i+1,u,v,Q) If not Q then H[u,v]:=0; End; Else Q:=true; End; Until Q or k=8 End; Magyarázat Az i változó tárolja, hogy hányadik szinten vagyunk. Megoldás esetén i=n*n lesz, leraktuk az összes elemet. Az x és y jelöliazt a pozíciót, ahova letettünk elemet A H tömb tárolja a megoldást, a Q ért éke true, ha találtunk megoldást, u és v pedig az utolsó próbált hely koordinátái. A k változó tárolja, hogy az adott szinten hányadik próbálkozásnál tartunk. (a szisztematikus próbálkozás változója) Egy pontból maximum 8 lépés lehet (ha pont középen van ), így ha ezt végigprób áltuk, új szintre lépünk. (k:=k+1) Az x+A[k] a k által kijelölt pozícióba lép, ide fog mutatni u és v (v:=y+B[k]). If (i<n*n): Ha rajta vagyunk a sakktáblán, és szabad H[ u,v]:=i, feljegyezzük a

megoldást, hogy hányadik lépéssel kerültük oda. If not Q: ha még nem vagyunk készen, újrahívjuk az eljárást. Töröljük az előző lépést Ha Q igaz, megnéztü k a 64. helyet is, az until visszalép a legfelső szintre Ha k<8, próbálja a következőt. Az A és B tömb a relatív elmozdulásokat tárolja: hova tud a huszár elmozdulni. Ez maximum 8 lehetséges irányt jelent. Algoritmus (összes megoldás) Procedure probal(i: integer) Var k: integer; Begin For k:=1 to 8 do begin If (A[k]) and (B[i+k]) and (C[i-k]) then begin X[i]:=k; A[k]:=false; B[i+k]:=false; C[i-k]:=false; If i<8 then probal(i+1); End Else kiírás(x) A[k]:=true; B[i+k]:=true; C[i-k]:=true; End; End; Kezdeti értékek Q:=false, H tömb nullázása, H[1,1]:=-1 (az első huszárt le kell tenni 1,1 pozícióra) Probal(2,1,1,Q): először az i értéket (2) írja be az első elmozdított pozícióba 18. Optimális keresés Az optimális választás feladata Egy hátizsákba meghatározott

térfogatú és fontossági értékű tárgyakat kel el beraknunk úgy, hogy az összes pontérték minél nagyobb legyen. Az összes tárgy térfogata együtt nagyobb, mint a hátizsák térfogata, tehát az összes tárgy nem rakható be. Meg kel l határozni, hogy a tárgyak mely kombinációja esetén lesz a pontérték maximális. Heurisztikus próbálkozás: - Csökkenő pontérték Relatív fontosság sorrendben töltjük A megoldást nem fogadjuk el, ha a feladat mérete mérete, akkor jó megoldásnak tekintjük (nk). szerint tesszük be a tárgyakat ( pontérték/térfogat) szerint csökkenő fel a hátizsákot a kitevőben van. Ha az alap a feladat Általános feladat Adott tárgyak halmazából valamilyen optimalitási szempont alapján a legjobb részhalmaz kiválasztása. Módszer: - előállítjuk az összes lehetséges részhalmazát a halmaznak - Kiszámoljuk a pontértéket - Kiszámoljuk a térfogat-értéket, hogy még beleférjen - Kiválasztjuk a maximális

pontértékűt Ez egy Branch -Bound algoritmus, amely szeleteket vesz a keresési térben; az elev e reménytelen ágakkal nem próbálkozik. A hátizsákos feladatra: Ha kivesszük az utoljára berakottat, a hátralévő összes lehetséges elem ber akásával kaphatunk -e jobb megoldást, mint az eddigi leg jobb? Ez a vágás. Ha ezt nem teljesíti, nem próbálkozunk ezzel az ággal Algoritmus Procedure probal(i: integer, TW, AV: integer) Var AV1: integer; Begin If TW+A[i].W<=limW then begin S:=S+[i]; If i<n then probal(i+1, TW+A[i].W, AV) Else If AV>MAXV then begin MAXV:=AV; OPTS:= S; End; S:=S-[i]; End; AV1:= AV-A[i].V; If AV1>MAXV then begin If i<n then probal(i+1, TW, AV1) Else begin MAXV:=AV1; {maximum kiválasztás} OPTS:=S; End; End; End; Magyarázat I: a szinteket tárolja (hányadik tárggyal próbálkozunk) TW: a hátizsákban lévő tárgyak összes súlyértéke AV: híváskor az összes tárgy pontértékéttartalmazza LimW: a hátizsákba rakható

tárgyak maximális összsúlya If TW+A[i].W: ha még a súlykorláton belül vagyunk, a következő tárgyat is betehetjük S:=S+[i]: betesszük a következő tárgyat If i<n: ha van m ég további tárgy, akkor nincs kész. Újrahí vjuk a megnövelt sú lyértékkel (az aktuális tárgyat beraktuk – TW+A[i].W) Else if AV>MAXV: megtelt a hátizsák. Nagyobb-e a berakott új tárggyal a térfogat,befér-e? AV1:= AV -A[i].V: az utoljára berakott tárgy nélkül kaphatunk -e jobb megoldást, mint az eddigi legjobb? If i<n: ha van még tárgy, be tudjuk rakni? (probal) MAXV: feljegyezzük, mennyi a hátizsákban lévő pontérték OPTS: optimális halmaz, a felhasznált tárgyak indexei Ha az utolsó probal eljárás hívódik meg, a következő else ág nem hajtódik végre. Hívása: probal(1,0,totv): probal(első elem, üres táska, tárgyak fontossági sorrendjeinek összege) Az A tömbbe a tárgyakat súly szerinti növekvő sorrendben kell berakni