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 kell 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 szerint tesszük be a tárgyakat
-Relatív fontosság (pontérték/térfogat) szerint csökkenő sorrendben töltjük fel a hátizsákot
A megoldást nem fogadjuk el, ha a feladat mérete a kitevőben van. Ha az alap a feladat mérete, akkor jó megoldásnak tekintjük (nk).
Á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 eleve 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 berakásával kaphatunk-e jobb megoldást, mint az eddigi legjobb? 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.
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
Feladat: Adott nxn-es sakktáblán helyezzünk el 8 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;
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;
Until Q or (J=8);
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 az elemet. Így X tömb I-edik eleme J lesz. 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 megoldá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 megoldás, Q értéke hamis. Ha találtunk, akkor is visszalépünk, de Q értéke igaz lesz.
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 felhelyezett elemeket, mivel ez az elrendezés nem ad 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}
Általános feladat: adott N sorozat, amelyek 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 befolyásoljanak. Tulajdonképpen ez egy bonyolult keresési feladat: 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 egy 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íteni eldöntési, kiválasztási, megszámolási, kiválogatási feladatok megoldását, sőt még a valamilyen szempontból legjobb megoldás megkeresését is.
A programozási nyelvekben 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ületet foglal le a veremben a paraméterek és a változók tárolására, ami a memória elfogyá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 viszonylag jól programozható iteratív (ciklusos) párja, akkor mindig az utóbbi használata javasolt.
A rekurzió végrehajtá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*3*2*1 = 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 rekurzió befejezésének feltétele. Ekkor az 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 megoldás hátránya, hogy nem veszi észre, 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))
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 hasonlí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ünk be. Az ÉRTÉK tartalmazza az adott menetben legkisebb számot, az INDEX pedig 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.
Algoritmus:
Eljárás
Ciklus I=2-től N-ig
Ciklus J=N-től I-ig (-1-esével)
Ha A(J-1)>A(J) akkor A:=A(J-1)
A(J-1):=A(J)
A(J):=A
Elágazás vége
Ciklus vége
Ciklus vége
Eljárás vége.
Egyszerű beillesztéses rendezés
A rendezést úgy végezzük, mintha kártyáznánk, és kezünkbe 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 sorozatban 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.
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 betesszük a felszabadult helyre. Most a lyuk ott keletkezik, ahonnan ezt az elemet kivettü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 56 8 42 5 12 16 40 3 31 47 22 24 33 7 46
64__ 56 8 42 5 12 16 40 3 31 47 22 24 33 7 46
6446 56 8 42 5 12 16 40 3 31 47 22 24 33 7 __
46 56 8 42 5 12 16 40 3 31 47 22 24 33 7 64
A konkrét példában nem sikerült a vektort nem sikerült két részre vágni, mert a 64 éppen 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__ 56 8 42 5 12 16 40 3 31 47 22 24 33 7 64
467 56 8 42 5 12 16 40 3 31 47 22 24 33 __ 64
467 __ 8 42 5 12 16 40 3 31 47 22 24 33 56 64
467 33 8 42 5 12 16 40 3 31 47 22 24 __ 56 64
467 33 8 42 5 12 16 40 3 31 __ 22 24 47 56 64
467 33 8 42 5 12 16 40 3 31 24 22 __ 47 56 64
7 33 8 42 5 12 16 40 3 31 24 22 46 47 56 64
A 46 most a végleges helyé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 vektor egyik részének elemeivel 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, hogy az E-edik elem elé kerülnek a nála kisebbek, mögé pedig a nagyobbak.
Teljes algoritmus:
Eljárás gyorsrendezés (n, A) {n – elemszám, A - tömb}
Eljárás rendez(also, felso)
I:=also; J:=felso; {az intervallumok szélei}
X:=A[(also+felso) div 2]; {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
Rendez(1,N); {a főprogram}
End;
Megjegyzések:
·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, de 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 mondjuk 100 elemre, 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 nem rendezett-e már.
Á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.
Szétválogatás tétele (helyben)
Általános feladat: Rendelkezésre áll egy sorozat, valamint egy kijelölt eleme. Cseréljük fel úgy a sorozat elemeit, 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ú elemeket az egyik tömbbe, a nem T tulajdonságúakat egy másikba.
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)
Á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 van-e, 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á)
Á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:
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 adatelemek 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 szabá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.
a) 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 majd a fájlt, ahol a program elhelyezkedik. („hordozható lesz” a program)
b) 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 áramlá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ípusos –é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ó).
c) 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 longint 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 integer típusú visszaté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 az állományt.
d) 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 megmarad a kapcsolat a fájlnév és a fájlváltozó között, így ha a programban újra meg kell nyitni egy már lezárt állományt, akkor nincs szükség újabb AssignFile hívására.
A Delphi programbó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;
e) Az utolsó adatelem utánra való pozícionálás hozzáíráshoz
Seek(fájlváltozó, filesize(fájlváltozó));
f) Az állomány teljes tartalmának törlése
Seek(fájlváltozó, 0);
Truncate(fájlváltozó);
g) 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.
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 jelzi 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 #13#10 (CR,LF) <ENTER>
EOF #26 <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á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.
a) 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 majd a fájlt, ahol a program elhelyezkedik. („hordozható lesz” a program)
b) 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ányok esetén mindhárom fájlnyitó eljárás egy 128 bájtos adatá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ának választani.
c) Írás és olvasás
Ha írásra nyitottuk meg a fájlt, akkor a Write és a Writeln eljárásokkal végezhetjü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 kiürítésekor kerülnek ki a fájlba. Ennek ürítése: Flush(fájlváltozó). A Write, Writeln, Closefile automatikusan ürítik a puffert.
Ha olvasásra nyitottuk meg, akkor a Read és a Readln használható. A Read karakterenként olvas be, az aktuális fájlpozíció a következő karakter előtt lesz. A Readln sorokat 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}
d) 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 megmarad a kapcsolat a fájlnév és a fájlváltozó között, így ha a programban újra meg kell nyitni egy már lezárt állományt, akkor nincs szükség újabb AssignFile hívására.
A Delphi programbó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)
e) 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}
f) Szövegfájl sorainak megszámlálása
Db:=0;
While not eof(t) do db:=db+1;
g) 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);
h) Törlés szövegfájlból
Amit nem szeretnénk törölni, átmásoljuk egy típusos fájlba, majd onnan visszaí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;
i) Karakterenként olvasás
Karakterenként olvassuk a fájlt, amíg egy adott elválasztójelhez nem érünk.
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ő típust 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. A Delphiben 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.
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.
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 /x az új elem/
Ha vége
Eljárás vége.
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.
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.
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)
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 rec.tankor:=’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ány tí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: 1..100; (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.
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.
b) 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
0-255
-128..127
-32768..32767
0..65535
-231..231-1
2,939*10-39..1,701*1038
0..255
true / false
Egy karakter az ASCII kódtáblából
byte
1 byte
előjel nélküli egész
shortint
1 byte
előjeles rövid egész
integer
2 byte
előjeles egész
word
2 byte
előjel nélküli egész
longint
4 byte
előjeles hosszú egész
real
8 byte
valós szám
string
1 byte
egy max. 255 elemből álló karakterlánc
boolean
1 byte
logikai változó, igaz vagy hamis
c) 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
a x 2b 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
real
2.9x10-39..1.7x1038
.11-12
6 byte
single
1.5x10-45..3.4x1038
.7-8
4 byte
double
5.0x10-324..1.7x10308
.15-16
8 byte
extended
3.4x10-4932..1.1x104932
.19-20
10 byte
comp
.-2-63:263 -1
.19-20
8 byte
d) 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.
e) A char típus
Csak egyetlen karakter tárolására alkalmas. Ennek módja: karakter:=’A’; vagy karakter:=#65;
f) A string típus
Karaktersorozatok tárolására használjuk. Lásd később.
g) 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 karakter típusúnak kell lennie, különben hibaüzenetet kapunk.
h) 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 *)
i) 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’
j) 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
k) 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.
l) A résztartománytípus
Ilyet bármely sorszámozott típus tetszőleges értéksorozatával definiálhatunk.
PL. var index: 1..100;
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.
m) 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;
n) 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
a) 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 [1..100] 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.
b) 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.
c) 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 rec.tankor:=’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.
d) 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…/
e) Á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;
f) A sztringek
A sztring karakter típusú elemekből épül fel. Maximális hossza 255 karakter. A sztring 0. byte-ja a sztring hosszát tartalmazza, ezért például egy 12 karakterből álló sztring 13 byte-ot foglal a memóriában. Ha a sztring deklará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 terü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 karakterenként is feldolgozhatjuk. A karakteres elérés esetén a sztringindexben (a sztring azonosí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
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 kapott sztring hossza sem haladhatja meg a 255 karaktert.
Formája: concat(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.
b) 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 akarunk, a második a karakter sorszáma, ahonnan kezdjük a másolást, a harmadik pedig megmondja, hogy hány karakter kerüljön másolásra.
Formája:
S1:=’Vadember’;
S2:=copy(s1, 4, 8); (* Így s2 értéke: ’ember’ *)
c) 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 *)
d) 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 *)
e) 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 *)
f) A pos függvény
Ezen függvény segítségével sztringben megadott 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 *)
g) 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.
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
a) 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 ‘;’.
b) 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 pontosvessző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) 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.
b) 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ó.
c) 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*)
A Delphiben a programírás általában egy form és a komponensek tulajdonságainak leírásával kezdődik. A formot egy unit (egység) írja le. Egy Delphi program tehát a főprogramon kívül legalább egy unitot is tartalmaz.
Egy Delphi program tehát a következő fő részekből áll:
programfej,
egységek felsorolása,
főprogram.
Egy Delphi unit a következő fő részekből áll:
unitfej,
az illesztő rész (interface),
a deklarációs rész (type, var stb.),
a kifejtő rész (implementation),
az egységzárás (end.).
Az illesztő részben, azinterfacekulcsszó után definiálhatjuk azt, amit más programrészek is láthatnak. Az itt nem definiált részek csak az adott unit számára elérhetők. Itt kell megadni azt is, hogy melyik más unitok tartalmát akarjuk használni. Ezt kell felsorolni auseskulcsszó után. A deklarációs részben a unit számára látható típus-, változó-, konstans- és címkedeklarációkat kell megadnunk. Azimplementationután kell a unitot alkotó eljárásokat, függvényeket leírnunk. Ezek közül kifelé csak azok láthatók, ha azinterfaceután felsoroljuk őket (az eljárás- és függvényfejeket). Az egységetend.zárja le.
A Delphi építőelemei
ADelphinyelvű program alapvető építőelemei, azaz legkisebb értelmezhető egységei a következők:
szimbólumok,
fenntartott szavak,
azonosítók,
címkék,
konstansok,
elválasztójelek.
a) Szimbólumok:A programban bizonyos szimbólumokat használunk. (műveleti jelek, relációs jelek, zárójelek stb.). Pl.
+
-
*
/
=
;
:
,
b) Foglalt szavak:A foglalt szavakat, vagy kulcsszavakat a programozónak nem szabad használni a programban változók, konstansok, eljárások, vagy bármi más elnevezésére. A foglalt szavakat a Delphi vastagon írja a forrásszövegben. PL.
and
array
begin
record
repeat
c) Azonosítók:Az azonosítók a program bizonyos elemeinek elnevezésére szolgálnak. Pl. a programnak nevet kell adni, az egyes változókat, konstansokat, eljárásokat is el kell keresztelni. Az azonosító ASCII karakterekből állhat. Megszorítások:
kis- és nagybetűket (ékezet nélkül!) használhatunk;
számmal nem kezdődhet, de lehet benne;
kötőjel nem, de aláhúzásjel ( _ ) lehet benne;
szóköz, *, !, ? nem lehet;
azonos változó- vagy konstansnév nem szerepelhet kétszer (eltérő típus esetén sem);
fenntartott szó nem lehet;
hossza nem meghatározott, de csak az első 63 karakter számít.
Saját változóink nevét a típusmegadás és a változók felsorolása helyén adhatjuk meg (a type és a var kulcsszavak után). Az azonos típusú változókat vesszővel elválasztva lehet felsorolni, az utolsó után pedig pontosvesszőt kell tenni.
d) Címkék:A címkék használatát általában kerülni kell. A program bármely pontjáról elküldhetjük a vezérlést a program egy másik pontjára. Agoto 10;utasítás segítségével például a program vezérlése az utasítás helyéről átugrik a10:címkével megjelölt helyre (a címke után kettőspontot kell tenni!). A címke elhelyezkedhet a goto előtti vagy utáni programrészen. Ahhoz, hogy a fordító felismerje agotoutáni címkét, a deklarációs részben alabelkulcsszó után kell elhelyezni.
e) Konstansok:A konstans lehet szám- vagy szövegkonstans. Állandókat akkor adunk meg, ha egy bizonyos számértéket vagy szövegrészt a programban gyakran használunk. Ha a fejlesztés során módosítani szükséges, akkor sokkal egyszerűbb állandóként meghatározni, s csak ezt az egy értéket javítani. A konstansokat aconstkulcsszó után egyenlőségjelet használva ismertetjük, pl. így:
sum = 'Összesen:';
vagy
szam = -273.16; .
f) Elválasztó elemek:A Delphi nyelvű programok elválasztó szimbólumai a szóköz és a sorvég-jel. A szóköznek a programozás elemeinek felsorolásakor van jelentősége, a sorvég jel pedig általában pontosvessző (a program végén lévő end után pont). Ha egy programsor után nem teszünk pontosvesszőt, akkor a fordító a következő sort is az előző folytatásának fogja tekinteni.A programban megjegyzéseket helyezhetünk el, ez megkönnyíti a forrásszöveg olvashatóságát. A megjegyzéseket kapcsos zárójelek közé tesszük, de használhatjuk a (* és *) párokat is. Például:
{Az adatbeolvasás kezdete}
vagy
(* Az n szerinti ciklus vége *)
A Delphi rutinjai
A programban deklarált rutinok, azaz az eljárások és függvények arra teremtenek lehetőséget, hogy a programunkat logikailag és funkcionálisan meghatározott különálló egységekre bontsuk. Az eljárásokat és a függvényeket a főprogram (vagy egy másik eljárás) vezérli.
Eljárások
Az eljárás deklarálása aprocedurekulcsszóval indul, amelyet azazonosító(név) követ. A név után zárójelbenparaméter(ek)is megadható(k). Az eljárás feje után a belső (lokális)változók,típusok,konstansokéscímkékfelsorolása következik (de nem biztos, hogy vannak). Az utasításokatbeginésend;között kell felsorolni, a záróendután is pontosvesszőt kell tenni.
a)Példa paraméter nélküli eljárásra:
procedure Uzenet;
begin
ShowMessage('Kevés a memória!');
end;
b)Példa paraméteres eljárásra:
procedure Szorzas5(var Szam: Double);
begin
Szam:=Szam * 5;
end;
Függvények
A függvény abban különbözik az eljárástól, hogy értéket (de csak egy értéket) ad vissza. Deklarálása afunctionkulcsszóval indul, amelyet azazonosító(név), a paraméterek és az eredmény típusának deklarálása követ. Az utasításblokkban adjuk meg a végrehajtandó utasításokat. A függvényt az azonosítóval kell hívni, a paraméterek típusának és sorrendjének egyeznie kell.
A következő példa tetszőleges kitevőjű hatványozásra alkalmas függvényt mutat be:
function Hatvany(alap,kitevo: Double):Double;
begin
Hatvany:=Exp(kitevo*ln(alap));
end;
Hívása:Eredmeny:=2.85*hatvany(szam,4);
Paraméterek
Paramétereket az eljárások és függvények deklarálásakor adhatunk meg az azonosító (név) mögött, kerek zárójelek között. A paraméterek tulajdonképpen a rutinon belüli lokális változók. A paraméterekre az azonosítókkal hivatkozhatunk. A Delphi három paramétertípust különböztet meg:
értékparaméter,
változó paraméter,
típus nélküli paraméter.
Ha egy paramétert csak az azonosítójával adunk meg, akkorértékparaméterről beszélünk. Ha a paraméter előtt avarkulcsszó áll, és a paramétert típusdeklaráció is követi, akkorváltozó paraméterről van szó. Ha avarután nem áll típusdeklaráció, akkortípus nélkülia paraméter.
A sor
