KURZUS: Programozás alapjai
MODUL: I. modul
1. lecke: Bevezetés
Az első lecke során még nem a programnyelvi sajátosságokra helyezzük a hangsúlyt, hanem a számítógép képességeinek megismerésére, a megvalósítandó algoritmusok, adatszerkezetek leírására. Ebből kifolyólag ebben a leckében a legfontosabb alapfogalmakat, elméleti ismereteket tekintjük át, amelyek a későbbi programozási tevékenységekhez elengedhetetlenül fontosak lesznek. A lecke elkészítésekor támaszkodtunk az [1-4] irodalmakra, melyekben további részletek is találhatók az itt tárgyalt témákkal kapcsolatban. | ||||||||||||||||||||||||||
A lecke végére a hallgatónak tisztában kell lennie | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
A lecke kulcsfogalmai: adat, program, konstans, (egyszerű és összetett) változó, változó neve, típusa, memóriaterülete, bit, bájt, fixpontos számábrázolás, kettes komplemens alak, lebegőpontos alak, mantissza, karakterisztika, ASCII kód, tömb, tömb dimenziója, vektor, mátrix, függvény, kifejezés, annak kiértékelése, típusa és értéke, precedencia és asszociativitás, alap- és vezérlőtevékenységek, szekvencia, szelekció, iteráció, elöltesztelő, növekményes és hátultesztelő ciklusok, algoritmus, folyamatábra, függvény, aktuális és formális paraméterek, visszatérési érték. | ||||||||||||||||||||||||||
A számítógép legfontosabb komponensei és képességei | ||||||||||||||||||||||||||
Elsőként fontos tisztázni azt, hogy mire képes egy számítógép: a számítógép egy információ feldolgozó eszköz. Különféle információra tesz szert a bemeneti (input) egységein keresztül (pl. billentyűzet, szkenner), ezeket adott utasításokat követve feldolgozza, majd az eredményeket kimeneti (output) egységein keresztül (pl. képernyő, nyomtató) a felhasználó tudomására hozza. Mindenféle probléma megoldása során érdemes figyelembe venni, hogy | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
Az információn belül érdemes megkülönböztetnünk adatot és programot. "Egy feladat adatai mindazok az információk, amelyekből kiindulva, ezekkel műveleteket végezve, átalakítva a megoldásig eljuthatunk; és adat minden olyan információ, a megoldást megadó is, amely a kiinduló adatokból a műveletvégzés, az átalakítás során keletkezik." [1] Ezzel szemben "program az az információ, amely leírja a számítógépnek, hogy hogyan működjön ahhoz, hogy a kiindulási adatokból a keresett megoldás előálljon." [1] A program egyrészt utasításokból áll, melyek információt közölnek a számítógéppel, másrészt rögzített sorrendben kérik a gép által végrehajtható különféle alaptevékenységek elvégzését. | ||||||||||||||||||||||||||
Az általunk a tanulmányok során használandó személyi számítógépek alapvetően Neumann elvűek. Gépeink legfontosabb tulajdonságai közé tartozik pl., hogy az elemi utasításokat a megadás sorrendjében hajtják végre (ez megkerülhető a különféle vezérlésátadó, ugró utasításokkal), kettes számrendszerrel dolgoznak, ugyanabban az operatív tárban ("memóriában") tárolják az adatokat és a programokat is, elektronikus működésűek, központi vezérlőegységükre támaszkodva automatikusan hajtják végre az utasításokat és kellően általános felhasználásúak. Már ebből a leírásból is kiderül, hogy melyek a számítógépek számunkra legfontosabb részegységei: | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
Számítógépünk egyik érdekes tulajdonsága, hogy hogyan ábrázolja és kezeli az adatokat. Ez egyrészt történhet konstansok segítségével, az adatot a megfelelő helyre írva, vagy ún. változók segítségével. Utóbbiak arról kapták nevüket, hogy a bennük tárolt adat megváltoztatható. Attól függően, hogy egy változó egyszerre egyetlen adatot tárol-e vagy adatok egy csoportját, meg szokás különböztetni egyszerű és összetett változókat. Az egyszerű változók három legfontosabb tulajdonsága a következő: | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
Bár a változók tartalmát a memória tárolja, annak tartalmát a processzor nem tudja közvetlenül feldolgozni. Először be kell olvasnia a változó értékét valamelyik regiszterébe, azzal már elvégezhet egy vagy több műveletet, végül a regiszter értékét vissza kell írnia a memóriába. Mivel regiszterből rendszerint sok van, az összes regisztert szokás regisztertömbként is említeni. | ||||||||||||||||||||||||||
Numerikus adatok ábrázolása | ||||||||||||||||||||||||||
Természetes számok ábrázolása | ||||||||||||||||||||||||||
Maradjunk egy kicsit a típusoknál, és nézzük meg, hogyan tárolja számítógépünk a nem negatív egész számokat. A módszert fixpontos (fixed point) számábrázolásnak nevezik, mert a tizedesvessző (angol nyelvterületen tizedespont) mindig ugyanott marad, a számjegyek mögött. Kicsit távolabbról indulva vizsgáljuk meg, hogyan írhatunk fel egy ilyen számot 10-es számrendszerben, 10 hatványainak felhasználásával: | ||||||||||||||||||||||||||
A számítógép azonban az adatokat kettes számrendszerben tárolja, így nem tíz, hanem mindössze két féle számjegy helyezkedhet el egy adott helyi értéken: a 0 és az 1. Ezt a két féle értéket lényegesen könnyebb megkülönböztetni egymástól, és különféle fizikai jellemzőkkel társítani, mint pl. folyik-e áram egy adott áramkörben vagy sem, a feszültség alacsony-e vagy magas, be van-e kapcsolva valamilyen eszköz vagy sem stb. A 2017-es érték kettes számrendszerben felírva a következőképpen fest: | ||||||||||||||||||||||||||
A szám felírásának módja tehát alapvetően ugyanaz: a választott számrendszer alapjának különféle hatványait kell szorozni a nekik megfelelő helyi értéken álló számjeggyel, majd a szorzatösszeget képezni. (Utóbbi egyenletből annak terjengőssége miatt a nulla szorzótényezős tagokat elhagytuk.) Kettes számrendszer esetén tehát a szám értékének meghatározása formálisan a következőképpen fest [3]: | ||||||||||||||||||||||||||
ahol a felhasznált helyi értékek száma, a helyi érték indexe és az i helyi értéken álló számjegy. | ||||||||||||||||||||||||||
Az átalakítást 10-es számrendszerről valamely másikra természetesen könnyedén elvégezhetjük, ha a számot a számrendszer alapjával osztjuk mindaddig, amíg az osztás egészrésze nem lesz 0, és minden osztás után leírjuk a művelet maradékát. A maradékokat fordított sorrendben visszaolvasva megkapjuk a számot az új számrendszerben. Ennek megfelelően pl. 2017 16-os számrendszerben (ahol számjegynek tekintjük a szokásos 10 számjegyen kívül az A, B, ..., F betűket is, melyek rendre 10, 11, ..., 15 értékeknek felelnek meg) | ||||||||||||||||||||||||||
mert | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
Papíron természetesen akárhány számjegyet felhasználhatunk a számjegyek tárolására, de a számítógépes rendszerek ennél rugalmatlanabbak. A memória legkisebb egysége 1 bit kapacitású, amely 1 db. kettes számrendszerbeli számjegy tárolására alkalmas. Jellemzően azonban nem lehet egyetlen bitet közvetlenül címezni, hanem csak bitek csoportjait. A címezhető (azaz a memóriában közvetlenül hozzáférhető) legkisebb egység a bájt (byte), ami 8 bitből áll, de rendszerint lehetőség van 16, 32 vagy akár 64 bittel (azaz 2, 4, 8 bájttal) is közvetlenül dolgozni, a hardver adottságaitól függően. Ebből már könnyű megállapítani, hogy a különféle helyfoglalású változók a intervallumba eső értékeket lesznek képesek tárolni, ahol a felhasznált bitek száma. | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
A 16-os számrendszert is gyakran alkalmazzák az informatikában, mert egy számjeggyel pontosan 4 bit tartalmát lehet leírni, ezért nagyon tömör írásmódot tesz lehetővé. | ||||||||||||||||||||||||||
Egész számok ábrázolása | ||||||||||||||||||||||||||
A fixpontos számábrázolás egy speciálisan módosított változatával, az ún. kettes komplemens képzés segítségével elérhetjük, hogy akár negatív számokat is reprezentálhassunk egy bitsorozattal, de ettől még az adott számú bittel megkülönböztethető értékek száma nem változik, csak a bitmintákhoz rendelt értékek. A használható intervallum ennek megfelelően , ahol a felhasznált bitek száma. Egy negatív érték felírásának lépései a következők: | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
Másképp megközelítve a problémát, úgy lehet egy pozitív szám -1-szeresét képezni, ha kivonjuk -ből, ahol ismét a felhasznált bitek száma. Kedvező tulajdonságai miatt az egész számok ábrázolásának ez az egyik legnépszerűbb, de nem az egyetlen módja. Az egyik ilyen tulajdonság pl., hogy a legmagasabb helyi értékű bit egyértelműen jelzi a szám előjelét, de pusztán ennek módosításával nem képezhető egy szám ellentettje. A kettes komplemens formában felírt szám értéke könnyen meghatározható az alábbi összefüggéssel: [3] | ||||||||||||||||||||||||||
Nézzünk egy példát, írjuk fel a -76-ot kettes komplemens alakban, 8 bitet használva! | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
Vagy a másik módszerrel: | ||||||||||||||||||||||||||
Természetesen ugyanez a módszer működne 10-es számrendszerben is: | ||||||||||||||||||||||||||
Az alsó sorban lévő értéket úgy kell értelmezni, hogy kettes komplemens kódolás esetén ugyanazt a bitsorozatot fogjuk kapni a -76-ra, mint amit egyébként az előjel nélküli tárolás esetén a 180-hoz használtunk (vegyük észre, hogy a 180 bele sem fér a 8 biten, kettes komplemens formában ábrázolható számok intervallumába). | ||||||||||||||||||||||||||
Végül nézzük meg, hogy a különféle bitsorozatok milyen értékeket reprezentálnak: | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
Valós számok ábrázolása | ||||||||||||||||||||||||||
A valós számok ábrázolásához ún. lebegőpontos (floating point) számábrázolást fogunk alkalmazni. Ennek neve onnan ered, hogy a tizedesvesszőt lehet a számjegyek között "lebegtetni". A módszert nem ismertetjük részletesen, csak az alapötletet vázoljuk itt fel. Ez abból áll, hogy a számokat normálalakjukban ábrázoljuk, jellemzően kettes számrendszerben, pl.: alakban, ahol az ún. mantissza, pedig a karakterisztika. értékét praktikusan úgy választják meg, hogy teljesüljön az alábbi egyenlőtlenség: | ||||||||||||||||||||||||||
azaz pl. | ||||||||||||||||||||||||||
Az értékére vonatkozó előírás célja, hogy az első két számjegy mindig ugyanaz legyen (0 és 1), ezért ne legyen szükség a tárolásukra, az így felszabadított biteket pedig az ábrázolható intervallum szélesítésére vagy az ábrázolási pontosság növelésére lehet fordítani. Ennek megfelelően pl. a 2017-es értéket négy bájton lehetne a következőképpen is tárolni: | ||||||||||||||||||||||||||
Fenti bitsorozat értelmezése a következő. A legmagasabb helyi értéken lévő 0 érték a mantissza előjelét jelzi: a 0 érték tartozik a nem negatív, 1 pedig a negatív számokhoz. A további 23 bit tárolja a mantissza értékét előjel, és az első két számjegye nélkül. Az utolsó 8 bit tárolja a karakterisztika értékét ún. 128 többletes formában. Ez azt jelenti, hogy a bitsorozat értékéből le kell vonni 128-at, hogy a karakterisztika értékét (kettő kitevőjét) megkaphassuk. | ||||||||||||||||||||||||||
Megjegyezzük, hogy ez csak egy lehetséges, egyszerű megvalósítása a lebegőpontos számábrázolásnak. A gyakorlatban leggyakrabban előforduló változatokat az IEEE szervezet szabványosította. A szabványok részleteinek ismerete, a megvalósítás módjának okai messze túlmutatnak e tananyag keretein. Azt azonban tudni kell, hogy ezzel a módszerrel is csak adott intervallumba eső számokat ábrázolhatunk, sőt, még ezen az intervallumon belül sem írható le pontosan minden érték. Ilyenkor a gép a kívánthoz legközelebb eső értékkel fog dolgozni. Az ilyen jellegű pontatlanságok, a lassabb műveletvégzés és a jellemzően magasabb tárigény miatt csak akkor szokás lebegőpontos számábrázolást alkalmazni, ha az valóban indokolt. | ||||||||||||||||||||||||||
Szöveges adatok ábrázolása | ||||||||||||||||||||||||||
Egyetlen karakter ábrázolása | ||||||||||||||||||||||||||
Mivel számítógépünk alapvetően számok kezelésére alkalmas, a szöveges adatokat is számokkal írjuk le. A személyi számítógépeken a legelterjedtebb az ún. ASCII (American Standard Code for Information Interchange) kódolás, ami egy 7 bites kódot rendel az angol ábécé betűihez, a számjegyekhez és különféle egyéb írásjelekhez. Mivel gépünk 8 bites egységekben éri el a memória tartalmát, egy-egy bájtban egy karakter kódját tudjuk elhelyezni, és még marad is egy szabad bit. Ezt jellemzően további, nemzetenként változó, főleg ékezetes betűk kódolására szokás használni. A kódolás pontos mikéntjét ún. kódlapok szabályozzák. Mivel minden nemzet valamennyi speciális írásjelét nem lehet kódolni mindössze 128 további értékkel, különféle kódlapok jöttek létre, és az egyikkel írt szöveget nem lehet értelmezni a másik kódlap használatával, nem lehet keverni a különféle nemzetek jeleit stb. A kuszaságban olyan új karakterkódolási módszerek tettek rendet, mint pl. a UNICODE, ami magába integrálta az ASCII kódtáblát is kompatibilitási okokból. Ennek ismertetése ismét túlmutat a tananyag keretein. Bár minden technikai lehetőség adott lenne, az egyszerűség kedvéért, és hogy figyelmünk ne terelődjön el a fontosabb feladatoktól, a továbbiakban lemondunk az ékezetes betűk használatának lehetőségeiről. | ||||||||||||||||||||||||||
Az ASCII kódtábla egyik jellegzetessége, hogy az első 32 kódérték (0-31) különféle vezérlőkaraktereket kódol: ilyen pl. a soremelés kérése a karakteres képernyőn vagy más hardveren, új sor elejére ugrás stb. A betűk ábécé sorrendben vannak felsorolva a kódtáblában, azaz pl. a kis 'a' betű kódja 97, a kis 'b' betűé 98, és így tovább. A nagybetűk és számjegyek kódjai ugyanilyen szemléletben kerültek megválasztásra, csak a konkrét kódok intervalluma eltérő. | ||||||||||||||||||||||||||
Karakterláncok tárolása | ||||||||||||||||||||||||||
Azt már tehát tudjuk, hogyan lehet kódolni egy-egy betűt, de hogyan tárolhatunk karakterláncokat (string)? A probléma többféleképpen megoldható, de itt most csak a C programnyelv által is használt megoldást tárgyaljuk: ez abból áll, hogy a karakterláncot alkotó karakterek kódjait a memória egymást követő bájtjaiban helyezzük el, majd a karakterlánc végét egy speciális, 0 kódú lánczáró karakterrel ('\0') jelezzük. | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
Összetett adatszerkezetek | ||||||||||||||||||||||||||
Az összetett adatszerkezetek egyszerű típusú adatok csoportjából állnak. A tantárgy keretein belül két féle összetett adatszerkezetet fogunk megvizsgálni, melyek a tömbök és a struktúrák. | ||||||||||||||||||||||||||
A tömbök tetszőleges, de azonos típusú egyszerű változókból állnak, ezekre egységesen lehet hivatkozni a változó nevével. Az egységbe foglalt elemekre indexelés segítségével lehet hivatkozni: az első elem indexe mindig 0, az utolsóé pedig az elemek száma mínusz egy. Az indexelés mindig sorfolytonos, és az elemek összefüggő memóriaterületen helyezkednek el. Az indexeléssel kiválasztott elemet azután bárhol lehet használni, ahol az egyszerű változót is lehetne. Pl. egy T nevű, 10 elemű tömb elemeire rendre a T[0], T[1], ..., T[9] módon lehet hivatkozni. | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
A tömb rendelkezik az egyszerű változók három tulajdonságával, valamint egy negyedikkel is, ami a tömb dimenzióját határozza meg. A fenti tömb egy dimenziós, vagy más néven vektor, de az elemek elrendezése szerint beszélhetünk két dimenziós tömbökről (mátrixokról) is. A dimenziók számát csak praktikus okok, mint pl. a programok áttekinthetősége korlátozzák. | ||||||||||||||||||||||||||
A karakterláncokat tömbként valósítják meg a C programnyelvben. Vegyük észre, hogy az alábbi s tömbben a hasznos karakterek száma négy, de a tömbnek legalább öt eleműnek kell lennie, hogy a lánczáró nulla is beleférjen. Mivel az indexelés 0-ról indul, ennek indexe 4 lesz. A tömb elemei egyszerre tekinthetők karaktereknek és egész számértékeknek, hiszen a karaktereket egy kódtábla segítségével kódoltuk. | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
Műveletek | ||||||||||||||||||||||||||
A számítógépünk által közvetlenül végrehajtható, legfontosabb műveleteket az alábbi táblázatban foglaltuk össze. | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
A szám konstansokat akkor tekintik lebegőpontos típusúnak a C nyelvben, ha tizedespontot tartalmaznak. Néhány példa az osztáshoz kapcsolódóan: | ||||||||||||||||||||||||||
6/4==1 | ||||||||||||||||||||||||||
A C programnyelvben nem állnak rendelkezésre operátorok a karakterláncok kezeléséhez. Az olyan tipikus feladatokat, mint pl. két szövegrész összefűzése, függvények segítségével valósítják meg. Más programnyelvekben gyakran a + operátor szolgál a példaként említett célra. | ||||||||||||||||||||||||||
Három logikai műveletet támogat a C programnyelv, melyeket az alábbi táblázat foglal össze. Fontos kiemelni itt azt, hogy ezek logikai műveletek, mert léteznek hasonló műveletek, melyek adatok tartalmával bit szinten végeznek különféle tevékenységeket, nem tekintik a bitek sorozatát egyetlen egységnek. | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
Az alábbi táblázat a logikai műveletek igazságtáblázatát mutatja, azaz azt, hogy milyen értékű operandusokon milyen eredményt adnak. Itt megjegyezzük, hogy a műveletek mindegyike logikai értékekkel dolgozik és ilyet is ad eredményül, ám a C nyelv nem rendelkezik logikai típussal. E helyett minden egész típusú adatot, melynek értéke 0, logikai hamisnak tekint, az összes ettől eltérő értéket pedig igaznak. | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
Szám jellegű adatok összehasonlítására használhatók a különféle relációs operátorok, melyek logikai értéket eredményeznek. Ezek némelyike két karakterből áll, mert a matematikában használatos jelöléseket nehézkes lenne a billentyűzeten megadni. Megjegyezzük, hogy már az osztásnál megadott példák esetében is azért alkalmaztuk az == jelölést, hogy az egyezőséget hangsúlyozzuk, programnyelvi elemekkel. | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
Korábbi matematikai ismereteink és szokásaink alapján egy x érték adott intervallumba esését nagyon kényelmes lenne úgy vizsgálni, hogy | ||||||||||||||||||||||||||
A < x <= B | ||||||||||||||||||||||||||
de sajnos ez programnyelvi környezetben nem megengedett. Kombinálhatjuk azonban egymással a logikai operátorokat és a relációkat: | ||||||||||||||||||||||||||
A<x && x<=B | ||||||||||||||||||||||||||
A Bool-algebra tulajdonságai persze más, ekvivalens felírást is lehetővé tesznek. | ||||||||||||||||||||||||||
!(A>=x || x>B) | ||||||||||||||||||||||||||
Mivel a karaktereket kódjaik segítségével kezeli a számítógép, és a kódok egész számok, a karakterek összehasonlíthatók relációs műveletekkel. Mivel pl. a betűk kódjai az ábécé vége felé haladva nőnek, a kódok sorrendje egyúttal az (angol) ábécébeli sorrendet is szolgáltatja. Szerencsére még magukat a kódokat sem kell fejben tartanunk, mert bármely karakter konstans megadható aposztróf jelek közé írva. Karakterláncok azonban nem hasonlíthatóak össze! | ||||||||||||||||||||||||||
'0' < '1' < '2' < ... < '9' | ||||||||||||||||||||||||||
Függvények | ||||||||||||||||||||||||||
Az operátorokkal elvégezhető alaptevékenységeknél összetettebb feladatokra, különösen, ha annak végrehajtására többször, különféle kiinduló adatokkal is szükség van, és a feladat jól körülírható, kellően általános, függvényeket használunk. A programnyelvhez tartozó függvénykönyvtárak sok beépített függvényt tartalmaznak a leggyakoribb feladatok elvégzéséhez, de mi is elkészíthetjük saját függvényeinket. Ennek megfelelően a C programnyelv is rendelkezik számos matematikai függvénnyel, melyek közül a leggyakrabban használtakat az alábbi táblázatban foglaltuk össze. | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
Ha egy függvényt használatba kívánunk venni, azaz meg szeretnénk hívni, akkor hivatkozni kell a nevére (pl. abs), majd kerek zárójelpárban meg kell adni az aktuális paraméter(eke)t. Ezek azok az értékek, melyekkel a függvény, mint kiinduló adatokkal a megfelelő számításokat elvégzi. Pl. egy C nyelvű programban találkozhatunk az alábbi sorral: | ||||||||||||||||||||||||||
y = abs(x); | ||||||||||||||||||||||||||
Itt y jelöli az eredmény változót, amibe az x változóban tárolt érték abszolút értéke kerül majd. Az = jel a hozzárendelés operátor, mely a jobb oldalán szereplő, jelen esetben az abs függvény által szolgáltatott értéket az y változóhoz rendeli, abban eltárolja. Vegyük észre, hogy az értékadás operátora nem azonos az egyezőségi relációval! A kettő felcserélése nehezen felfedezhető programhibák oka lehet. A sor végét ; zárja, ami a műveletsor végét jelzi. | ||||||||||||||||||||||||||
Többször előfordul, hogy különböző nevű függvények is léteznek ugyanarra a feladatra. Ilyenkor jellemzően a paraméter típusában van eltérés. Pl. az abs függvény egész típusú adatot fogad és ilyenben szolgáltatja az eredményét is, a fabs viszont lebegőpontos típusokkal dolgozik. A trigonometrikus függvények radiánban várják a paraméter értékeket. A hatványozásnál több paraméter, az alap és a kitevő átadására is szükség van, melyek mindegyike tetszőleges valós érték lehet. Az általános használhatóságért a függvény lassabb működésével fizetünk meg, ezért egyszerűbb hatványozási feladatokat, mint pl. egy egész szám négyzetre emelése, a gyakorlatban jellemzően szorzással helyettesítjük. | ||||||||||||||||||||||||||
Kifejezések | ||||||||||||||||||||||||||
A kifejezés (statement) nem más, mint az adatokon elvégzendő műveletek megadása. A kifejezés kiértékelése alatt azt értjük, hogy a számítógép elvégzi a kifejezésben adott konstansokon és változókon a meghatározott műveleteket. A kiértékelés eredményeképpen kapott értéket a kifejezés értékének, az érték típusát a kifejezés típusának nevezzük. Utóbbi elsősorban az operandusoktól függ, ugyanis minden művelet eredményének típusa egyértelműen meghatározott, a kifejezés műveleteit egyenként kell végrehajtani és a végrehajtás sorrendje is kötött. A sorrendet meghatározza a zárójelezés, a precedencia szabályok (műveletek prioritása), és a műveletek asszociativitása, ami az azonos prioritású műveletek közötti kiértékelési sorrendről dönt (többnyire balról jobbra történik). | ||||||||||||||||||||||||||
A zárójelezéssel kapcsolatban említést érdemel, hogy matematikai témájú irodalmakban gyakran különféle típusú zárójelek jelzik, hogy az egymásba ágyazott, zárójelezett részeket milyen sorrendben elvégezni. Pl. | ||||||||||||||||||||||||||
A programnyelvi környezetben viszont egyrészt a kerek zárójellel kialakított részek egymásba ágyazásának sorrendje egyértelműen leírja a műveletvégzés sorrendjét, ezért nincs szükség több féle szimbólum alkalmazására, másrészt a szögletes és kapcsos zárójelek egyéb jelentéssel bírnak. (A szögletes zárójelpár, mint korábban láttuk, tömbindexelésre szolgál. A függvényhívásnál is szerepelnek ugyan kerek zárójelek, de ezek aktuális jelentését a környezetük alapján egyértelműen meg lehet határozni.) Ennek megfelelően a fenti példa a következőképpen írható le helyesen: | ||||||||||||||||||||||||||
(((3+4)*2+5)*9+7) | ||||||||||||||||||||||||||
A műveletek precedenciáját és asszociativitását táblázatokkal adják meg. Az eddig megismert, legfontosabb műveletekre vonatkozó táblázat, mely a műveleteket precedencia szerint csökkenő sorrendben tartalmazza és később még jelentősen kibővítünk, a következő: | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
Tevékenységek | ||||||||||||||||||||||||||
A számítógép három alaptevékenységet tud elvégezni: | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
A számítógép háromféle vezérlő tevékenység végrehajtására képes: | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
Programok tervezése, működésének dokumentálása | ||||||||||||||||||||||||||
Amikor egy problémát számítógépes eszközökkel kívánunk megoldani, mindig két dolgot kell elvégeznünk: az adatszerkezet, adatstruktúra és az algoritmus megadását. E kettő együttesen határozza meg a számítógép által végrehajtandó programot. | ||||||||||||||||||||||||||
Az adatszerkezet megadásából kiderül, hogy | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
Az algoritmussal kapcsolatban azt kell meghatározni, hogy | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
Egy adott feladatnak természetesen több megoldása is lehetséges. Az eltérő adatstruktúra jellemzően más algoritmust igényel, és fordítva. Gyakran a tárolt adatok mennyiségének növekedése árán csökkentjük a programok futásidejét, vagy éppen ellenkezőleg. | ||||||||||||||||||||||||||
Az adatstruktúra megadása legegyszerűbben egy táblázat segítségével történhet. Ebben feltüntetjük minden egyes adat | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
Egy változó a program futása során betölthet többféle funkciót, ölthet többféle jelleget, de egy C programban a típusa nem változhat meg. | ||||||||||||||||||||||||||
Téglalap kerületének és területének kiszámítása | ||||||||||||||||||||||||||
Első példaként nézzük meg, hogy egy téglalap kerületét és területét hogyan határozhatnánk meg! Az adatszerkezeti táblázat a következő lehet: | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
Egyszerű esetekben az algoritmus megadható szövegesen, pl. így: | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
Könnyen belátható azonban, hogy egy összetettebb program esetében túlságosan körülményessé, áttekinthetetlenné válik az ilyen módon történő algoritmus megadás, elsősorban a különféle feltételek és iterációk miatt. A probléma megoldható valamilyen alkalmas diagramtípus alkalmazásával, pl. folyamatábrával. A folyamatábrák legfontosabb komponensei a következők. | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
Az algoritmus kezdetét és végét egy ellipszishez hasonló alakzatba írt "Start" és "Stop" szimbólum jelzi. A háromszög szimbólumok részalgoritmusok megadásakor használatosak. Egy programnak egyetlen kezdő és egyetlen záró eleme lehet. A végrehajtási sorrendet a nyilak adják meg, melyek csak szelekcióknál ágazhatnak el. Ennek megfelelően a startból mindig egyetlen nyíl vezet ki, a stopba pedig be. | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
Az értékadó tevékenységeket téglalap szimbólumokban kell megadni. Egy téglalapba mindig pontosan egy nyíl vezet be, és egy ki. A fenti ábra azt fejezi ki, hogy meghatározandó a kifejezés értéke, amit a v változónak fel kell vennie. A tömörség kedvéért egy téglalapban több értékadó tevékenység is szerepeltethető. | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
A beolvasási (input) tevékenységet a paralelogrammába írt "Be:" szöveggel jelöljük, majd felsoroljuk azoknak a változóknak a neveit, amelyekbe az adatokat be kell olvasni. Minden ilyen szimbólumba egy nyíl vezet be, és egy ki. | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
A kiírás (output tevékenység) szimbóluma szintén a paralelogramma, de ebben most a "Ki:" felirat áll, majd ezt követik azoknak a konstansoknak, változóknak a nevei vagy azok a kifejezések, amelyek az értékét meg kívánjuk jeleníteni. Szintén egy nyíl vezet ki, és egy be. | ||||||||||||||||||||||||||
Miután a folyamatábrák néhány szimbólumát megismertük, megadhatjuk vele első programunk algoritmusát. Mivel nincs akadálya annak, hogy kifejezések értékét jelenítsük meg a kimeneten, az értékadó és output tevékenységek különálló szimbólumai helyett az ábra rövidíthető úgy, hogy ezeket a teendőket egyetlen output tevékenység segítségével végezzük el. Ezzel a módosítással egyúttal két változót is elhagyhatunk. | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
Másodfokú egyenlet megoldása | ||||||||||||||||||||||||||
Bonyolultabb algoritmusok megadásához nem lesz elég a nyilakkal jelzett szekvenciák használata, szelekciós vezérlő tevékenységek meghatározására is szükség lesz. | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
A szelekció logikai kifejezését egy csúcsára állított rombuszba írjuk, melybe egy nyíl vezet be, és kettő ki: az egyik a feltétel teljesülése esetén végrehajtandó további tevékenységekhez vezet, a másik pedig azokhoz a tevékenységekhez, amiket akkor kell végrehajtani, ha a feltétel nem teljesül. Ezeket a nyilakat fel is kell címkézni az egyértelműség kedvéért (i = igen/igaz, n = nem/hamis). Az is megengedett, hogy a két ág valamelyikén semmiféle tevékenység se legyen. | ||||||||||||||||||||||||||
Ennek tudatában már olyan összetettebb algoritmusok is leírhatóvá válnak, mint pl. a másodfokú egyenlet () megoldása. | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
Legnagyobb érték kiválasztása | ||||||||||||||||||||||||||
Végezetül nézzük meg, hogyan ábrázolható folyamatábrával egy iteráció! Az iterációknak (ciklusoknak) két csoportja létezik: az elöltesztelő és a hátultesztelő ciklusok. Ezek nevüknek megfelelően rendre az ismétlendő tevékenységeket tartalmazó ún. ciklusmag végrehajtása előtt, illetve után ellenőrzik, hogy teljesül-e az ismétlés feltétele. A két megoldás között egy lényeges különbség, hogy az elöltesztelő esetben előfordulhat, hogy egyetlen egyszer sem kerül végrehajtásra a ciklusmag, a hátultesztelő esetben azonban ez legalább egy alkalommal biztosan meg fog történni. A ciklusmagnak természetesen valamilyen módon hatással kell lennie az ismétlés feltételére, hiszen ha egy ilyen feltétel örökké teljesülne, akkor a program sosem fejeződne be, és az ún. végtelen ciklus hibáját követnénk el. A ciklusmag több tevékenységből is állhat, magába foglalhat feltételeket, további ciklusokat stb. | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
A gyakorlatban gyakran alkalmazzák az elöltesztelő ciklusnak egy speciális változatát, a növekményes (léptető, vagy for) ciklust. Elméleti jelentősége kicsi, mert minden algoritmus megadható a közönséges elöltesztelő ciklussal is, de a gyakorlatban sokkal nagyobb a kifejező ereje, ha pl. egy ciklusmag előre ismert számú végrehajtása a feladat. Ebből kifolyólag külön szimbóluma is van a folyamatábrákon. | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
A fenti ábrán látható, hogy a kétféle, egymással ekvivalens ciklus közül a második mennyivel tömörebben írja le ugyanazt a feladatot. A mintában CV-vel jelölt ciklusváltozó feladata nyilvántartani, hogy hányadik alkalommal került végrehajtásra a ciklusmag. Értéke kezdetben a KE-vel adott kezdőértékkel egyezik meg, ami a ciklusmag minden végrehajtása után egy lépésnyivel (LE) nő. A ciklusmagot addig kell végrehajtani, amíg CV nem haladja meg a végértéket (VE). A növekményes ciklusban LE értéke legtöbbször 1, ezért ha a hatszög szimbólumban nem adják meg értékét, akkor azt 1-nek feltételezzük. Annak sincs akadálya, hogy CV értéke minden ismétlés során csökkenjen, de akkor a feltétel természetesen CV >= VE-re módosul. | ||||||||||||||||||||||||||
Következő példánk során kérjünk be n darab valós számot a felhasználótól, és állapítsuk meg, hogy ezek közül melyik a legnagyobb! A legnagyobb számról természetesen csak akkor van értelme beszélni, ha a beolvasott értékek száma legalább egy, és ebben az esetben ez maga a keresett érték. Amennyiben egynél több számot adnak meg, akkor a másodiktól kezdve mindegyikről el kell dönteni, hogy az nagyobb-e az eddig megtalált legnagyobb értéknél. Ha igen, ezt az értéket kell feljegyezni, mint jelenleg legnagyobb értéket. Az összes érték vizsgálatát követően már megadható az eredmény. | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
Összetettebb programokban gyakorlatilag elkerülhetetlen, hogy saját függvényeket készítsünk. A függvények egy jól körülhatárolható résztevékenységet foglalnak magukba, és később, ha ennek elvégzését kívánjuk elérni, elegendő csak meghívni a függvényt. Ennek hatására megtörténik a függvényben foglalt tevékenységek végrehajtása, majd a program végrehajtása a függvény hívása utáni ponton folytatódik. A függvények átláthatóbbá teszik a programokat, segítenek elkerülni a kódrészletek ismétlődését, ráadásul a függvényeknek átadható paraméterek segítségével ugyanazt az algoritmust különféle adatokkal is végrehajthatjuk. Egy jól megírt függvény segíti a programkód újrahasznosítását is, mert később akár más programokban is felhasználható lesz. | ||||||||||||||||||||||||||
Az adatstruktúrát leíró táblázatban az azonosító helyére a függvény neve kerül, típusához pedig a függvény által szolgáltatott eredmény, az ún. visszatérési érték típusa, már amennyiben szolgáltat bármiféle eredményt a függvény. A "jelleg" oszlopban a "fv. v. t. érték" szöveget szokás feltüntetni. Külön sorokban meg szokták adni a függvény formális paramétereit, azok nevével, típusával együtt, a jelleg mezőbe írt bejegyzés pedig "paraméter" lesz. Természetesen nem kizárt, hogy egy függvénynek egyetlen paramétere se legyen. A függvény paraméterénél a "formális" jelző arra vonatkozik, hogy a függvényen belül ezeknek a változóknak a nevével lehet hivatkozni a függvénynek átadott értékekre. A formális paraméter neve nem kell, hogy egyezzen a függvény hívásakor használt aktuális paraméter változó nevével, sőt, az aktuális paraméter név nélküli konstans is lehet. A folyamatábrában a függvény hívását az értékadó tevékenységek között lehet feltüntetni, pl. | ||||||||||||||||||||||||||
fvnév(aktuális paraméterlista) | ||||||||||||||||||||||||||
vagy | ||||||||||||||||||||||||||
változó = fvnév(aktuális paraméterlista) | ||||||||||||||||||||||||||
formában. Magának a függvény definiálásának, működése megadásának nincs konkrét szimbóluma, de segíthetnek pl. a részalgoritmus kezdetének és végének jelzésére szolgáló különféleképpen forgatott háromszög szimbólumok, vagy megadhatjuk őket különálló algoritmusokként, saját folyamatábrával. | ||||||||||||||||||||||||||
| ||||||||||||||||||||||||||
A függvény visszatérési értékét a ki- és bemeneti tevékenységekhez hasonlóan lehet jelölni. | ||||||||||||||||||||||||||
|
Feladatok | |||||||||||||||||||||||||
1. Jelölje meg a változók három legfontosabb tulajdonságát!
![]() | |||||||||||||||||||||||||
2. Jelölje meg azokat a számábrázolási módszereket, amelyek alkalmasak a 0 érték tárolására!
![]() | |||||||||||||||||||||||||
3. Jelölje meg azokat a számábrázolási módszereket, amelyek alkalmasak a -1 érték tárolására!
![]() | |||||||||||||||||||||||||
4. Jelölje meg azokat a számábrázolási módszereket, amelyek alkalmasak a 0,5 érték tárolására!
![]() | |||||||||||||||||||||||||
5. Adja meg a fixpontos számábrázolással adott, 8 bites számok értékeit tízes számrendszerben!
![]() | |||||||||||||||||||||||||
6. Írja fel a tízes számrendszerben adott számokat 8 biten, fixpontos számábrázolással!
![]() | |||||||||||||||||||||||||
7. Adja meg a kettes komplemens alakban adott, 8 bites számok értékeit tízes számrendszerben!
![]() | |||||||||||||||||||||||||
8. Írja fel a tízes számrendszerben adott számokat 8 biten, kettes komplemens alakban!
![]() | |||||||||||||||||||||||||
9. Lehetséges-e kerekítési pontatlanságoktól mentesen megadni az 1/3 értéket lebegőpontos számábrázolással?
![]() | |||||||||||||||||||||||||
10. Hány bit alkot egy bájtot?
![]() | |||||||||||||||||||||||||
11. Legalább hány bájt memóriaterület szükséges egy 4 karakteres karakterlánc tárolásához?
![]() | |||||||||||||||||||||||||
12. Amennyiben T egy 16 elemű tömb, jelölje meg, hogy melyek a helyes indexelések!
![]() | |||||||||||||||||||||||||
13. Mi lesz a műveletek eredménye?
![]() | |||||||||||||||||||||||||
14. Mi lesz a kifejezések értéke, ha A=0, B=1 és C=2?
![]() | |||||||||||||||||||||||||
15. Készítsen adatszerkezeti táblázatot és rajzolja meg a folyamatábráját a kör kerületét és területét meghatározó programnak! Olvassa be a sugár (r) értékét, majd értékelje ki a megfelelő kifejezéseket, jelenítse meg az eredményeket! | |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
16. Olyan programot próbáltunk készíteni, amely a gömb felszínét és térfogatát határozza meg. A programnak csak pozitív sugarat szabadna elfogadnia. Jelölje meg azt a folyamatábra változatot, ami az elvárásunknak megfelelően működő programhoz tartozik!
![]() | |||||||||||||||||||||||||
17. Az alábbi folyamatábra azt próbálja felvázolni, hogyan kellene egy pozitív egész n szám faktoriálisát (n!) meghatározni, de hiányos. Mit kellene a kérdőjel helyére írni, hogy a program helyesen működjön? | |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
Mit kellene a kérdőjel helyére írni, hogy a program helyesen működjön?
![]() | |||||||||||||||||||||||||
18. Az a szándékunk, hogy beolvassuk egy háromszög oldalhosszait növekvő sorrendben. | |||||||||||||||||||||||||
| |||||||||||||||||||||||||
Jelölje meg azokat a folyamatábrákat, amelyek alkalmasak ennek a célnak az elérésére!
![]() | |||||||||||||||||||||||||
19. Feltételezhetjük, hogy a három elemű, valós számokból álló o tömb tartalmazza egy háromszög oldalhosszait, növekvő sorrendben. Melyik folyamatábrával leírt program alkalmas a háromszög megszerkeszthetőségének ellenőrzésére?
![]() | |||||||||||||||||||||||||
20. Feltételezheti, hogy egy háromelemű, valós számokból álló tömb már tartalmazza egy háromszög oldalhosszait növekvő sorrendben. Rajzolja meg azt a folyamatábrát, amivel el lehet dönteni, hogy a háromszög derékszögű-e! | |||||||||||||||||||||||||
| |||||||||||||||||||||||||
21. Válassza ki azokat a folyamatábrákat, amelyek alkalmasak egy háromszög kerületének és területének meghatározására, amennyiben az oldalhosszak már ismertek! | |||||||||||||||||||||||||
| |||||||||||||||||||||||||
![]() |