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 leckében szereplő fogalmak jelentésével,
  • ismernie kell a legfontosabb adatábrázolási módokat és
  • a leggyakrabban alkalmazott műveleteket, azokkal képesnek kell lennie egyszerűbb kifejezések alkotására, valamint
  • képesnek kell lennie egyszerű feladatokat megoldó algoritmusok létrehozására, azok dokumentálására adatszerkezeti táblákkal és folyamatábrákkal.

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 adott lehetőségek mellett mit célszerű számítógéppel megoldani és mit nem,
  • milyen fejlesztőeszközök állnak a rendelkezésünkre és ezek közül melyik illeszkedik legjobban céljainkhoz,
  • hogyan tudnánk a lehető legáltalánosabb megoldást adni a feladatra stb.

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:

  • a központi egység ("processzor", Central Processing Unit, CPU), melynek része az aritmetikai/logikai egység (Arithmetic/Logic Unit, ALU) és a fent említett vezérlőegység (Control Unit, CU)
  • az operatív tár (ami működését tekintve írható és olvasható memória, Random Access Memory, RAM) és a
  • be/kimeneti egységek, perifériák (pl. különféle lemezmeghajtók az adatok tartós tárolására).
Sínrendszerű számítógép funkcionális modellje. Forrás: [2]
1.1. ábra.

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ő:

  • neve (azonosítója) van, ezzel hivatkozhatunk rá a programjainkban. Minden programnyelv részletesen meghatározza a névadás szabályait (pl. felhasználható karakterek köre), illetve a programozónak is törekednie kell arra, hogy a név kifejezze a változó rendeltetését, célját a programban ("beszédes" változónevek).
  • Típusa van, ami egyrészt meghatározza, hogy hogyan tárolják a memóriában, másrészt, hogy milyen műveletek végezhetők el vele. A típus az adat jellegét (numerikus, szöveges stb.) is meghatározza.
  • Minden változóhoz tartozik egy memóriaterület, ahol az adatot elhelyezik. Ennek mérete a típustól függ.

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:

2017 10 =2 10 3 +0 10 2 +1 10 1 +7 10 0

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:

2017 10 = 11111100001 2 =1 2 10 +1 2 9 +1 2 8 +1 2 7 +1 2 6 +1 2 5 +1 2 0

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]:

V unsigned = i=0 N1 b i 2 i

ahol N a felhasznált helyi értékek száma, i a helyi érték indexe és b i 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)

2017 10 = 7E1 16

mert

EgészrészekMaradékok
20171
12614 = E16
77
0

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 [ 0;  2 N 1 ] intervallumba eső értékeket lesznek képesek tárolni, ahol N a felhasznált bitek száma.

Bitek számaTárolható értékek száma
8256
1665536
324294967296
6418446744073709551616

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 [ 2 N1 ;  2 N1 1 ] , ahol N a felhasznált bitek száma. Egy negatív érték felírásának lépései a következők:

1.Írjuk fel az érték abszolút értékének kettes számrendszerbeli alakját!
2.Vegyük ennek egyes komplemensét, azaz mivel kettes számrendszerrel dolgozunk, minden 1-es számjegyet cseréljünk 0-ra, és minden 0-t 1-re!
3.Az így kapott eredményből képezzük a kettes komplemenst oly módon, hogy hozzáadunk 1-et.

Másképp megközelítve a problémát, úgy lehet egy pozitív szám -1-szeresét képezni, ha kivonjuk 2 N -ből, ahol N 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]

V two " scomplement = b N1 2 N1 + i=0 N2 b i 2 i

Nézzünk egy példát, írjuk fel a -76-ot kettes komplemens alakban, 8 bitet használva!

76 kettes számrendszerben:01001100
Egyes komplemens alak:10110011
Kettes komplemens alak:10110100

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:

BitmintaÉrték
01111111127
01111110126
......
000000011
000000000
11111111-1
11111110-2
......
10000000-128
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.: m 2 k alakban, ahol m az ún. mantissza, k pedig a karakterisztika. m értékét praktikusan úgy választják meg, hogy teljesüljön az alábbi egyenlőtlenség:

1 2 m<1

azaz pl.

2017 10 =0,11111100001 2 11

Az m é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:

01111100 00100000 00000000| 10001011 2 = 2017 10

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.

Kódolt karakter'J''a''n''i''\0'
Kód 10-es szr.-ben74971101050
Kód 2-es szr.-ben0100 10100110 00010110 11100110 10010000 0000
Kód 16-os szr.-ben4A616E6900
Ö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 tömb 10 darab, azonos típusú egyszerű változót foglal egy csoportba, melyek indexeléssel külön-külön is használhatóak
1.2. ábra

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.

Az s karakterlánc öt db. karakterből álló tömb; az utolsó elem a karakterlánc végét jelzi
1.3. ábra
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.

Műveleti jel (Operátor)Értelmezés
+Két szám összeadása.
-Amennyiben egyetlen szám konstans vagy változó előtt áll, azaz a művelet egyoperandusos, akkor annak ellentettjét képzi. Kétoperandusos esetben kivonást eredményez.
*Két szám szorzatát képzi.
/Amennyiben mindkét operandus egész típusú, az eredmény az osztás egészrésze. Ellenkező esetben lebegőpontos osztást végez.
%Két egész operandus esetén az osztás maradékát adja meg.

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
6./4==1.5
6%4==2

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.

OperátorFunkció
!Tagadás, logikai nem
||(Megengedő) vagy
&&És

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.

ab!aa||ba&&b
00100
01110
10010
11011

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.

OperátorFunkció
>A bal operandus nagyobb, mint a jobb oldali.
>=A bal operandus nagyobb, vagy egyenlő a jobb oldalival.
<A bal operandus kisebb, mint a jobb oldali.
<=A bal operandus kisebb, vagy egyenlő a jobb oldalinál.
==A két operandus értéke egyenlő.
!=A két operandus értéke nem egyenlő.

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'
'a' < 'b' < 'c' < ... < 'z'
'A' < 'B' < 'C' < ... < 'Z'
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.

Függvény neveTevékenység
abs(x), fabs(x), labs(x)Abszolút érték képzése.
sin(f)Szinusz
cos(f)Koszinusz.
tan(f)Tangens.
pow(a, k)Hatványozás.
exp(x) e x meghatározása.
log(x)Természetes alapú logaritmus.
log10(x)10-es alapú logaritmus.
sqrt(x)Négyzetgyök vonása.

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.

{ [ ( 3+4 )2+5 ]9+7 }

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ő:

OperátorFunkció
( )függvényhívás
- !egyoperandusos műveletek: ellentett képzés, tagadás
* / %szorzás, osztás
+ -összeadás, kivonás
< <= > >= == !=különféle relációk
&&és
||vagy
=hozzárendelés
Tevékenységek

A számítógép három alaptevékenységet tud elvégezni:

  • Input tevékenység: adatok beolvasása változókba. A C nyelvben ez (szándékosan) nem alaptevékenységként jelenik meg, hanem függvények segítségével valósítják meg.
  • Output tevékenység: a konstansként, változóval vagy kifejezéssel adott adatok kiírása, melynek során mindig egy érték jelenik meg. A C nyelvben ez sem alaptevékenység.
  • Értékadó tevékenység: ennek során a számítógép a kiértékelt kifejezés értékét adott változóba írja. A változó és a kifejezés típusának azonosnak, vagy legalábbis automatikusan egymásra alakíthatónak (implicit típuskonverzió) kell lennie. (Aritmetikai típusok és karakterláncok között nincs lehetőség implicit típuskonverzióra.)

A számítógép háromféle vezérlő tevékenység végrehajtására képes:

  • Szekvencia: az utasításokat azok leírásának sorrendjében hajtja végre.
  • Szelekció: egy logikai kifejezés értékétől függően elágazik, végrehajtásra kiválaszt tevékenységeket.
  • Iteráció: egy logikai kifejezés (feltétel) teljesülésétől függően tevékenységeket ismétel.
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

  • melyek lesznek a kiindulási adatok,
  • mi lesz a végeredmény,
  • milyen részeredményeket szükséges/célszerű kiszámítani,
  • ezeket milyen változókkal kezeljük,
  • milyen adatok lesznek konstansok stb.

Az algoritmussal kapcsolatban azt kell meghatározni, hogy

  • melyek az elvégzendő tevékenységek,
  • és ezeket milyen sorrendben kell végrehajtani a kívánt cél elérése érdekében.

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

  • funkcióját: melyik adatot kezeli a változó
  • azonosítóját: ez a változó neve, ami célszerűen utal a funkcióra
  • típusát: az adat, a változó típusát, tárolásmódját határozza meg. Az összetett változót jellemző információ megadása (pl. egy tömb dimenzióinak száma) is itt történik meg.
  • jellegét: ez lehet kiindulási adat (input), végeredmény (output) vagy részeredmény (munka).

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:

FunkcióAzonosítóTípusJelleg
téglalap egyik oldalaavalósinput
szomszédos oldalbvalósinput
téglalap kerületeKvalósoutput
téglalap területeTvalósoutput

Egyszerű esetekben az algoritmus megadható szövegesen, pl. így:

1.Beolvasandók a téglalap szomszédos oldalainak hosszai!
2.Kiszámítandó a téglalap területe és kerülete!
3.Megjelenítendőek a kiszámított értékek!

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.

Kezdőpont és végpont jelei
1.4. ábra

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.

Értékadó tevékenység
1.5. ábra

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ő.

Input tevékenység
1.6. ábra

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.

Output tevékenység
1.7. ábra

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.

A téglalap kerületének és területének meghatározását megadó folyamatábra
1.8. ábra
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.

Szelekciós tevékenység
1.9. ábra

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 ( a x 2 +bx+c=0 ) megoldása.

FunkcióAzonosítóTípusJelleg
együtthatóka, b, cvalósinput
diszkriminánsdvalósmunka
gyökökx1, x2valósoutput
A másodfokú egyenlet gyökeit meghatározó algoritmus folyamatábrája
1.10. ábra
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.

Ciklusok megadásának módjai
1.11. ábra

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.

Elöltesztelő és növekményes ciklusok
1.12. ábra

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.

FunkcióAzonosítóTípusJelleg
valós értékek számanegészinput
eddigi legnagyobb valós értékmaxvalósinput/munka
aktuális valós értékavalósinput
ciklusváltozóiegészmunka
A legnagyobb valós érték keresése
1.13. ábra

Ö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.

Részalgoritmus kezdetének és végének jelölése a folyamatábrákon
1.14. ábra

A függvény visszatérési értékét a ki- és bemeneti tevékenységekhez hasonlóan lehet jelölni.

Függvény által visszaadott érték jelzése
1.15. ábra
Feladatok
1. Jelölje meg a változók három legfontosabb tulajdonságát!
Név.
Kezdeti érték.
Létrehozás időpontja.
Típus.
Memóriaterület.
2. Jelölje meg azokat a számábrázolási módszereket, amelyek alkalmasak a 0 érték tárolására!
Fixpontos számábrázolás (előjelkezelés nélkül).
Kettes komplemens alak.
Lebegőpontos számábrázolás.
3. Jelölje meg azokat a számábrázolási módszereket, amelyek alkalmasak a -1 érték tárolására!
Fixpontos számábrázolás (előjelkezelés nélkül).
Kettes komplemens alak.
Lebegőpontos számábrázolás.
4. Jelölje meg azokat a számábrázolási módszereket, amelyek alkalmasak a 0,5 érték tárolására!
Fixpontos számábrázolás (előjelkezelés nélkül).
Kettes komplemens alak.
Lebegőpontos számábrázolás.
5. Adja meg a fixpontos számábrázolással adott, 8 bites számok értékeit tízes számrendszerben!
Fixpontos alakÉrték 10-es számrendszerben
0110 1100
1010 1010
0000 1111
6. Írja fel a tízes számrendszerben adott számokat 8 biten, fixpontos számábrázolással!
Érték 10-es számrendszerbenFixpontos alak
42
112
1
7. Adja meg a kettes komplemens alakban adott, 8 bites számok értékeit tízes számrendszerben!
Kettes komplemens alakÉrték 10-es számrendszerben
1111 1011
0111 1111
0100 0000
8. Írja fel a tízes számrendszerben adott számokat 8 biten, kettes komplemens alakban!
Érték 10-es számrendszerbenKettes komplemens alak
-28
64
-128
9. Lehetséges-e kerekítési pontatlanságoktól mentesen megadni az 1/3 értéket lebegőpontos számábrázolással?
Igen.
Nem.
10. Hány bit alkot egy bájtot?
8
16
32
64
11. Legalább hány bájt memóriaterület szükséges egy 4 karakteres karakterlánc tárolásához?
3
4
5
6
12. Amennyiben T egy 16 elemű tömb, jelölje meg, hogy melyek a helyes indexelések!
T[-1]
T[0]
T[1]
T[15]
T[16]
T[17]
13. Mi lesz a műveletek eredménye?
KifejezésEredmény
1/2
1/4.0
1%2
14. Mi lesz a kifejezések értéke, ha A=0, B=1 és C=2?
KifejezésEredmény
A && B
B && C
A || B
A || !B
!A && C
A < C

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!

FunkcióAzonosítóTípusJelleg
A kör sugararValósInput
A kör kerületekValósOutput
A kör területetValósOutput
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?

FunkcióAzonosítóTípusJelleg
A faktoriális alapszáma, a sorozat utolsó elemének indexenEgészInput
A sorozat elemei, a sorozat utolsó elemeelemEgészMunka / Output
A kiszámítandó sorozatelem indexeiEgészMunka
Mit kellene a kérdőjel helyére írni, hogy a program helyesen működjön?
elem = 0; i = 0
elem = 0; i = 1
elem = 1; i = 0
elem = 1; i = 1

18. Az a szándékunk, hogy beolvassuk egy háromszög oldalhosszait növekvő sorrendben.

FunkcióAzonosítóTípusJelleg
Ciklusváltozó, a tömb indexeiEgészMunka
A háromszög oldalainak hosszát tároló tömbo[]Valós elemekből álló háromelemű tömbInput
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!

FunkcióAzonosítóTípusJelleg
A háromszög oldalainak hosszát tároló tömbo[]Valós elemekből álló háromelemű tömbMunka
Ciklusváltozó, az o[] tömb indexeiEgészMunka
A hsz. kerületekValósOutput
A hsz. területetValósOutput
A hsz. félkerülete, segédváltozósValósMunka