1. Emlékeztető: feladatok és eszközök

Szekvencia

printf("Mi a szám? ");
scanf("%d", &a);
a = a*a;
printf("Négyzete: %d", a);

Elágazás

if (szam > 0)
    printf("pozitív");
else
    printf("nem pozitív");

Ciklus

for (i = 0; i < 10; i = i+1)
   printf("i = %d\n", i);

Algoritmus

  • Programozó: algoritmust tervez a feladat megoldására
  • Többé-kevésbé általános
  • Véges számú lépésben fut

Vezérlési szerkezetek

  • Számítási folyamat leírása: mi a lépések sorrendje
  • Már ismeritek a működést, sejtitek, mi lesz az eredmény

Példák az általánosság fogalmához:

  • Prímszámok: szám → igaz/hamis. Első 100 prímet tudja? Jó, de nem elég általános. Osztók próbálgatása: ez jobb megoldás!
  • Böngészőprogram: leíró kód → megjelenített oldal. Bemenet: szöveg, színek, margók, betűméretek, … Kimenet: a formázott oldal képe.

2. Az állásinterjús kérdés: fizz buzz

Az alábbi feladatot gyakran állásinterjúkon is feladják, és meglepő, hogy mennyiszer elrontják a jelentkezők. (Lásd itt és itt.) Hogyan függenek össze a feltételek? Hogyan kell egymásba tenni a vezérlési szerkezeteket? Jó-e az, ha leírjuk a három vizsgálatot (3-mal, 5-tel, mindkettővel), mindenhova közé else-t téve? Nem lenne jó itt felsorolni az összes rossz megoldást, és megmagyarázni mindegyikről, hogy mi a bajuk – az egy egyszerű nyomkövetéssel észrevehető. Mindenki kipróbálhatja magának!

fizz
buzz
11
fizz
13
14
fizzbuzz
16
1
2
fizz    
4
buzz
fizz
7
8

Fizz buzz: a feladat

Mondjuk sorban a számokat, de ha

  • 3 többszöröse, a szám helyett: „fizz”
  • 5 többszöröse, akkor „buzz”
  • mindkettőé, akkor „fizzbuzz”

Az oszthatóság vizsgálata

==
egyenlő-e
%
maradék
/* osztható? a maradék nulla? */
if (szam % 3 == 0)
    printf("fizz\n");

3. Fizz buzz: 3-mal és 5-tel is

&&
„és”: mindkét
feltétel teljesül
/* 3-mal és 5-tel is osztható */
if (szam % 3 == 0 && szam % 5 == 0)
    printf("fizzbuzz\n");

Vigyázat! Melyik feltétel is teljesül 15-nél???


A fizzbuzz probléma Karnaugh-táblája
Az „és” kapcsolat

Azért kell vigyázni, mert az egyes kiírások (fizz, buzz, fizzbuzz, szám) feltételei átfedik egymást. Ha egy szám 3-mal és 5-tel is osztható, akkor igaz az a kijelentés is, hogy 5-tel osztható. A feltételek nem zárják ki egymást! Így a programban két lehetőségünk van: vagy leírjuk azokat a feltételeket, amelyek teljesen kizárják egymást (pl. 3-mal és 5-tel is osztható; 3-mal igen, de 5-tel nem osztható stb.), vagy olyan vezérlési szerkezetet írunk, amely figyelembe veszi a halmaz–részhalmaz kapcsolatokat. Az utóbbi esetben az sem mindegy, hogy az elágazásokban melyik feltételt vizsgáljuk előbb. Ha a két oszthatóság együtt nem teljesül, még mindig lehet, hogy külön-külön valamelyik igen!


Az utóbbi elven működő megoldás:

Fizz buzz döntések struktogramja
#include <stdio.h>

int main(void) {
   int szam;

   for (szam = 1; szam <= 20; szam = szam+1)
      if (szam % 3 == 0 && szam % 5 == 0)
         printf("fizzbuzz\n");
      else
         if (szam % 3 == 0)
            printf("fizz\n");
         else
            if (szam % 5 == 0)
               printf("buzz\n");
            else
               printf("%d\n", szam);

   return 0;
}

Néhány C nyelvtani apróság a fenti programmal kapcsolatban. Mivel minden feltétel igaz és hamis ágában csak egy további utasítás van (egy következő if is egy utasításnak számít), ezért itt nem volt szükség az utasítások {} blokkba helyezésére.

A C szabályai szerint az else utasítás mindig az azt megelőző, legközelebbi if-hez tartozik. Ha ezt módosítani szeretnénk, az természetesen lehetséges, az utasítások megfelelő {} blokkba helyezésével. Így:

if (feltétel1) {
   if (feltétel2)
      printf("akkor, ha feltétel1 és feltétel2");
} else
   printf("akkor, ha nem feltétel1");

Sokan egyébként az önálló utasításokat is blokkba teszik, és nem írnak a fentihez hasonló kódot. Néha hosszabb kicsit úgy, de sok előnye van.

Nevezetes algoritmusok

Avagy: programozási tételek.

5. Sorozatok és tételek

Programozási tételek

Általánosságban megfogalmazott algoritmusok; mindig kicsit átalakítjuk a konkrét feladatunkhoz.

Vannak bizonyos alapvető algoritmusok, amelyeket nagyon gyakran használunk, és amelyek olyan fontosak, hogy külön nevet is kaptak. Ezeket nevezetes algoritmusnak, vagy más néven programozási tételnek szoktuk nevezni. Ezek általában valamiféle sorozatokon, nagy mennyiségű adaton dolgoznak.


Sorozatok (nem a Dallas)

Ezek a tételek általában sorozatokkal, sok feldolgozandó elemmel szoktak foglalkozni, pl. számsorok, névsorok, kirajzolandó alakzatok. A bemutatáshoz ezért most választunk egy konkrét példát: számsorokkal fogunk foglalkozni.

Az elemszám kétféleképpen lehet adott.

  • Adott hosszúságú. A sorozat hossza előre adott.
    Pl. 4 elem: 9, 1, 3, 5
  • Végjeles. A sorozat végét egy speciális érték jelöli.
    Pl. 9, 1, 3, 5, −1

6. Összegzés tétele

Összesítsük a rendeléseket!

Írjunk programot, amely összegzi a fogyasztásunkat: a felhasználótól kapott pozitív, egész számokat összegez. Addig, amíg −1-et nem kap.

2 sör + 3 sör + 1 sör = ?

Összegzés tétele

összeg = 0                      akkumulátor
CIKLUS AMÍG van még szám, ADDIG
    szám = következő elem
    összeg = összeg + szám
CIKLUS VÉGE

Az „akkumulátor” változó az, amelyikben összegyűlik, akkumulálódik az eredmény. Ezt először nullázzuk, utána minden feldolgozott számot hozzáadjuk. Minden iteráció végén az addig látott számok összegét fogja így tartalmazni. Ha esetleg egyszer sem ment volna be a ciklusba, akkor pedig nullát.

A végjeles sorozat kezelése: a beolvasás helye

  • A ciklus feltétele ez lesz: AMÍG szám ≠ −1, …
  • Ez a beolvasott számtól függ → már az első előtt lennie kell beolvasásnak
  • De mindig kell egy új szám → a cikluson belül is

Helyes megoldás (a tétel alkalmazása)

„az első
különleges”
összeg = 0
BE: szám              első
CIKLUS AMÍG szám ≠ −1, ADDIG
   összeg = összeg+szám
   BE: szám           következő (többi)
CIKLUS VÉGE

Ez egy nagyon fontos rész. Itt a ciklus működését meg kell érteni! A ciklus egy utasítássorozatot ismétel, amíg egy feltétel fennáll. A ciklusfeltétel ellenőrzi azt, hogy a kapott szám −1-e, vagy nem. Mivel ez egy elöltesztelő ciklus, ezért ennek a feltételnek az ellenőrzése a ciklusba belépés előtt fog megtörténni. Ez azt jelenti, hogy a ciklus első elérésekor már rendelkeznünk kell egy számmal, ami a felhasználótól származik, vagyis kell lennie egy beolvasásnak a ciklus előtt.

Namármost, ha a feltétel igaz, akkor bekerül a végrehajtás a ciklus belsejébe. Ilyenkor éppen van egy számunk, amit a billentyűzetről kaptunk, és ami nem −1, ezért azt hozzá kell adnunk az összeghez. Itt azt általánosan megfogalmazott összegzés tételét át kell alakítanunk a jelenlegi, konkrét feladatunkhoz, hiszen a ciklustörzs nem egy beolvasással kezdődik. Helyette az összeadással, mert a számunk már megvan.

A ciklustörzs egy újabb beolvasással végződik. Ami első ránézésre olyan, mintha a következő beolvasott számmal már nem csinálnánk semmit, de ez nincs így! A ciklustörzs végrehajtása után a vezérlés újra a ciklusfeltétel ellenőrzéséhez kerül. Ilyenkor már az új számot fogja ellenőrizni a feltétel újbóli kiértékelése – és ha igaznak adódott, vagyis ha a szám nem −1, akkor már az új szám fog az összeghez hozzáadódni. A ciklustörzs végén álló beolvasás a következő iteráció számára készíti elő a terepet. Vegyük észre, hogy ilyenkor a „terep” pont ugyanúgy néz ki, mint az első végrehajtás előtt. Van egy számunk, amit meg kell vizsgálni, hogy −1-e, és ha nem, akkor hozzáadni az összeghez.

A fentiek végiggondolását kezdő és haladó programozóknak is ajánljuk. Ennek a problémának ez A Szép Megoldása.

!=
nem egyenlő
C rövidítések:
a=a*b → a*=b
a=a+b → a+=b
stb.
#include <stdio.h>

int main(void) {
   int szam;
   
   printf("Kérem a számokat, -1: vége\n");
   scanf("%d", &szam);
   
   int osszeg = 0;          // elején nulla
   while (szam != -1) {
      osszeg += szam;       // összeg = összeg+szám
      scanf("%d", &szam);
   }

   printf("Összeg: %d\n", osszeg);

   return 0;
}

Másik példa az „összegzésre”: faktoriális számítása

Mi a különbség az összegzés és a faktoriális számítása között programozási szempontból? Szinte semmi! Algoritmikai szempontból a kettő tökéletesen ugyanaz. Más a művelet, de ugyanaz az elv: ciklusban akkumulálunk. Csak lecseréljük:

  • A kezdeti értéket 0-ról 1-re
  • Az összeadást szorzásra
  • A ciklust számlálásosra (1→n, ez előre adott hosszúságú sorozat), mert úgy szebb.
#include <stdio.h>

int main(void) {
    int n;
    printf("Melyik szám a faktoriálisa? ");
    scanf("%d", &n);

    int szorzat = 1;
    int i;
    for (i = 1; i <= n; i += 1)
        szorzat *= i;       // szorzat = szorzat*i

    printf("%d faktoriálisa %d\n", n, szorzat);

    return 0;
}

7. Számlálás tétele: osztók száma

Feladat

Számoljuk meg, egy számnak hány osztója van (1 és saját maga is.)

1  2  3  4  5  6  7  8  9  10  11  12

Megoldás gondolatmenete

  • Legegyszerűbb: próbálgatás
  • CIKLUS 1-től a számig
  • HA osztható, AKKOR növelünk egy számlálót
  • A számláló kezdeti értéke 0

Vegyük észre: ez egy előre adott hosszúságú sorozat. 1-től az adott számig kell eljutni.


Számlálás tétele

db = 0
CIKLUS AMÍG van még szám, ADDIG
    szám = következő elem
    HA igaz a feltétel szám-ra, AKKOR    melyikeket?
        db = db+1
    FELTÉTEL VÉGE
CIKLUS VÉGE

További példák

  • Hány páros számot gépeltek be?
  • Hány osztója van egy számnak?
  • Hány „e” betű van benne?
#include <stdio.h>

int main(void) {
   int szam;
   printf("Kérem a számot: ");
   scanf("%d", &szam);

   int db = 0;            // kezdetben 0
   int oszto;
   for (oszto = 1; oszto <= szam; oszto += 1)
      if (szam % oszto == 0)
         db += 1;         // ha ez osztója, +1

   printf("Összesen %d osztója van.\n", db);

   return 0;
}

8. A karakter típus – feladat

Feladat

Számoljuk meg, a begépelt szövegben hány „e” betű van!


    0123456789

 30   ␣!"#$%&'
 40 ()*+,-./01
 50 23456789:;
 60 <=>?@ABCDE
 70 FGHIJKLMNO
 80 PQRSTUVWXY
 90 Z[\]^_`abc
100 defghijklm
110 nopqrstuvw
120 xyz{|}~

Karakterek (character)

  • Betű → kódszám hozzárendelés
  • Minden betűhöz, számjegyhez, írásjelhez egy kódszámot rendelnek
  • A gépnek szám: belső ábrázolás, nekünk betű: külső ábrázolás
  • Többféle kódolás létezik, gyakori a Unicode, ASCII („eszki”, American Standard Code for Information Interchange)
  • Pl. A→65, a→97, !→33, 0→48, de vezérlő kódok is: sortörés (\n), oldaltörés stb.
  • Nem kell tudni fejből a kódszámokat!
  • A számjegyek és a betűk sorban vannak

9. A karakterek kezelése C-ben

'
aposztróf
„apostrophe”
char betu;

betu = 'A';             // betu = 65

betu += 1;              // következő: A→B

x = 'c'-'a';            // távolság: 2, mert a→b→c

if (betu >= 'a' && betu <= 'z') {
   printf("Ez egy kisbetű!\n");
   betu = betu-'a'+'A';       // nagybetű lesz belőle
}

printf("%c betű kódja %d", 88, 88); // „X betű kódja 88”
printf("%c betű kódja %d", 'X', 'X');
scanf("%c", &betu);

A karakterek a számítógép számára csak számok (belső ábrázolás), nekünk jelennek meg betűkként (külső ábrázolás). A szokványos operátorok így használhatók rajtuk, és a kódolási táblázat úgy van kialakítva, hogy ezek értelmes dolgot csináljanak: a < operátor megmondja, hogy előrébb van-e az egyik betű a másiknál az ábécében, a - operátor pedig a távolságot adja meg. A printf() pedig mindkét formát meg tudja jeleníteni: a printf %c betűt ír ki, a printf %d pedig ugyanannak a betűnek kiírja a karakterkódját.

10. Számlálás tétele: „e” és „E” betűk

||
„vagy”: valamelyik
feltétel teljesül
(elég az egyik)
A „vagy” kapcsolat
#include <stdio.h>

int main(void) {
   char c;
   int db = 0;
   int sikeresen = scanf("%c", &c);
   while (sikeresen == 1) {    // amíg !vége
      if (c == 'e' || c == 'E')
         db += 1;                  // ha megfelel, növeli
      sikeresen = scanf("%c", &c);
   }
   printf("%d darab e betű volt.\n", db);

   return 0;
}

A programban kihasználjuk azt, hogy a scanf() jelzi a beolvasás sikerességét is. A kért karakteren kívül ugyanis ad még egy számot (ezt tárolják el a sikeresen = scanf(...) sorok), amelynek az értéke 1, ha sikerült az egy karakter a beolvasása. Ha a program eljut a bemenet végéhez (amit fájl végének is szoktunk nevezni), akkor már nem 1 lesz ez az érték. Az 1-es szám onnan jön, hogy a sikeresen beolvasott értékek számát adja vissza a scanf(). Mivel itt csak egy adat beolvasását kértük (egy darab karakterét), ezért ennek az értéke 1 lesz, ha minden rendben volt.

A program a két feltételét (kis „e” betű-e, nagy „E” betű-e) VAGY kapcsolatba hozva használtuk. Ez azt jelenti, hogy bármelyik megfelel számunkra. Akár kis „e” betű van, akár „E” betű, a számlálót megnöveljük. A pongyolán megfogalmazott feladatkiírás szólhatna úgy, hogy „számoljuk meg a kicsi és a nagy E betűket” – hiába tudjuk, hogy nem lehet egy betű egyszerre kicsi és nagy is.

A programok írásakor a logikai VAGY és logikai ÉS kapcsolatok közötti különbséget mindig pontosan át kell gondolni. Azért fontos ez, mert a köznapi beszédben a kettőt sokszor pont fordítva használjuk. Például elhangozhat egy tankörben a következő mondat: „Tegye fel a kezét, aki Budapesten és Debrecenben született!” Nyilvánvaló, hogy senki nem születhetett egyszerre Budapesten ÉS (logikai ÉS) Debrecenben. Egyszerűen csak ezt a gondolatot rövidítjük: „Tegye fel a kezét mindenki, aki Budapesten született, és tegye fel a kezét az is, aki Debrecenben született!” A matematikailag, és ezért a programjainkban is korrekt változat élő beszédben szokatlanul hangzana: „Tegye fel a kezét mindenki, aki vagy Budapesten, vagy Debrecenben született!”

11. Szélsőérték keresése: a leg…

Melyik a legmagasabb rakéta?

Olvassunk be a billentyűzetről a magasságokat! Hány darabot – kérdezzük a felhasználótól! Melyik volt a legnagyobb közülük?


Szélsőértékkeresés tétele

legnagyobb = első elem      első
CIKLUS AMÍG van még szám, ADDIG
   szám = következő elem    többi
   HA szám > legnagyobb, AKKOR
       legnagyobb = szám
   FELTÉTEL VÉGE
CIKLUS VÉGE

Vigyázat! Az első „tippet” is a sorozatból kell venni! Általános esetben elvi hibás a legnagyobb=−1000 kezdetű vagy hasonló megoldás! (Ha az összes szám kisebb lenne −1000-nél, akkor hibás lenne az eredmény.)

A maximumkeresés C kódrészlete

printf("Hány szám lesz? ");
scanf("%d", &db);

printf("1. szám: ");
scanf("%lf", &aktualis);
max = aktualis;                // az első külön

for (i = 2; i <= db; i += 1) { // a többit ciklusban
   printf("%d. szám: ", i);
   scanf("%lf", &aktualis);
   if (aktualis > max)         // nagyobb az eddigieknél?
      max = aktualis;
}

printf("Maximum: %f\n", max);

12. Eldöntés tétele

Feladat (általános megfogalmazásban)

Megvizsgálni, szerepel-e egy bizonyos tulajdonságú elem a sorozatban.
Például: prímszám-e. Ahogy találunk egy osztót, tudjuk, hogy nem az.


Az eldöntés tétele

találat = HAMIS
CIKLUS AMÍG van elem ÉS NEM találat
   szám = következő elem
   HA szám = keresett, AKKOR
      találat = IGAZ                megvan: leáll a keresés
   FELTÉTEL VÉGE
CIKLUS VÉGE

A ciklus után a találat változó tartalmazza az eredményt: igaz v. hamis.

13. A logikai típus C-ben

Logikai típus

  • Lehetséges értékei: IGAZ, HAMIS; műveletek: és, vagy, tagadás.
  • A típus neve: bool, az igazat a true, a hamisat a false jelöli.
  • Az #include <stdbool.h>-t kell használnunk hozzá a programunk elején.

!
tagadás
#include <stdbool.h>

bool kisebb, piros;

kisebb = x < y;            // kisebb-e?
if (kisebb)
   printf("x kisebb, mint y");

piros = false;             // hamis, igaz
piros = true;
if (!piros)
   printf("nem piros, hanem más színű");

A logikai típusú értékre kiértékelődő kifejezések (! – tagadás, && – és kapcsolat, < – kisebb, mint stb.) épp ilyen típusú értéket állítanak elő.

Ha logikai kifejezéseket írunk, nem szokás, és nem is szabad az == true-et és != false-t odaírni. Egyszerűen fölösleges, redundáns, nem tesz hozzá semmit a programhoz.

Egy kis történelem

Nagyon régen, a C 1989-es változatában még nem volt külön bool típus, hanem egyszerűen int-eket használtak a logikai értékek tárolására is. A 0 a hamissal azonos jelentésű, az igaz értéke 1, de az 1-en kívül minden más, nullától különböző számot is igaz értékűnek tekint a nyelv. A legtöbb ma használatos programozási nyelv (pl. C++, Java, C#, PHP, Python, ...), sőt, a táblázatkezelők is hasonlóképp viselkednek.

Érdemes tudni róla, hogy történelmi okok miatt egy fölösleges ==true kiírása akár hibás programot is eredményezhet. Pl. az #include <ctype.h> beírásával számos karaktereket kezelő függvényt kapunk. Az egyik ezek közül az islower(), amelyik akkor ad igazat, ha kisbetűt adunk neki. Ennek a függvénynek a visszatérési értéke bool kellene legyen, de abból az időből származik, amikor még nem volt külön bool típus, hanem csak az int. És ezért nem garantált, hogy igaz érték esetén pont 1 lesz a visszatérési érték.

#include <ctype.h>
#include <stdio.h>
#include <stdbool.h>

int main(void) {
    if (islower('a') == true)   // HIBÁS!!
        printf("Kisbetu\n");
    else
        printf("Nem kisbetu\n");
    return 0;
}
#include <ctype.h>
#include <stdio.h>
#include <stdbool.h>

int main(void) {
    if (islower('a'))           // HELYES
        printf("Kisbetu\n");
    else
        printf("Nem kisbetu\n");
    return 0;
}

Az bal oldali változat azt mondja az a betűre, hogy nem (!) kisbetű. Azért hibás itt a program, mert az islower() nem feltétlenül ad 1-et, ha azt akarja mondani, hogy IGAZ. Csak az biztos, hogy egy nem 0 számot ad. A helyes változat a jobb oldalon látható: ==true nélkül.

14. Eldöntés: prímszám-e (C kód)

int szam;
printf("Kérem a számot: ");
scanf("%d", &szam);

bool vanoszto = false;
int oszto = 2;
while (oszto < szam && !vanoszto) {
   if (szam % oszto == 0)
      vanoszto = true;
   oszto += 1;
}

if (vanoszto)            // volt találat?
   printf("Nem prím.\n");
else
   printf("Prím.\n");

Ha el kell dönteni egy számról, hogy prímszám-e, sokkal értelmesebb dolog az eldöntés tételét alkalmazni, mint a számlálás tételét. Mondhatjuk ugyan, hogy megszámoljuk a szám osztóit, és ha csak kettő (egy és saját maga), akkor az egy prímszám. De miért kellene a kérdés megválaszolásához megvizsgálni az összes osztót? Miért ne állnánk meg már az elsőnél, azt mondva, hogy kérem szépen, ez nem prímszám?! (Az osztókat amúgy elég lenne a szám feléig vizsgálni, hiszen ha osztója a fele, akkor osztója 2 is. Sőt elég lenne a gyökéig, ugyanemiatt.)

A DeMorgan-féle szabály

A ciklusba belépésnek két feltétele van, 1) hogy nem értünk a számok végére, ÉS 2) nem találtunk még osztót. Mindkettőnek egyszerre teljesülnie kell, hogy bemenjünk a ciklusba. Ha nem mentünk be, akkor valamelyik nem teljesült: VAGY az egyik, VAGY a másik. Ezt vizsgáljuk a ciklus után: tudnunk kell, hogy melyik feltétel miatt lett vége a ciklusnak.

Itt jól látható a Digitből is tanult DeMorgan azonosság: ha az együttes feltétel tagadását tagonként írjuk fel, akkor az ÉS-t VAGY-ra kell cserélnünk. Bemegyünk a ciklusba, ha IGAZ az első feltétel ÉS IGAZ a második feltétel; NEM megyünk be a ciklusba, ha HAMIS az első feltétel VAGY HAMIS a második feltétel.

Ebben a konkrét esetben: !(oszto < szam && !vanoszto) azonos az oszto >= szam || vanoszto kifejezéssel. Az is tudható, hogy ha a ciklusból kilépve oszto < szam még mindig igaz, akkor a kilépés a !vanoszto nem teljesülése miatt következett be, azaz, ha oszto < szam, akkor biztos, hogy vanoszto.

Tömbök

16. Tíz darab szám

Feladat

Kérjen a felhasználótól 10 számot, és utána írja ki őket fordított sorrendben!


Megoldás – sorminta???

int a, b, c, d, e, f, g, i, j, k;

scanf("%d", &a);
scanf("%d", &b);
scanf("%d", &c);
…
printf("%d\n", c);
printf("%d\n", b);
printf("%d\n", a);

Mire lenne itt szükség?

Az eddigi programjainkban:

  • Csak néhány nevesített változóval dolgoztunk, amelyeknek mind kitüntetett szerepe volt
  • Nem tudtuk azt mondani, hogy „sok”
  • Csak a beérkezés sorrendjében tudtuk feldolgozni az adatokat

Ami hiányzik:

  • Jó lenne egyszerre több elemet is tárolni
  • Az elemeket sorszámozva hivatkozni (első szám, második szám…), mert akkor egy ciklus végigmehetne az elemeken
  • Az elemeket tetszőleges sorrendben elérni, mert akkor kiírhatnánk fordított sorrendben

17. A tömb

Tömb (array)

  • Egyforma típusú változókból álló, fix méretű tároló (container).
  • Az elemek sorszámozva vannak, indexelhetőek.
a0a1a2a3a4a5
99713-454712

A tömb elemei egyforma típusúak kell legyenek, de ez a típus bármi lehet. Létrehozhatunk egészek, valósak, karakterek, akár logikai típusú változók tömbjét is. C-ben az elemek számozása 0-tól történik, és ez a legtöbb másik programozási nyelvben is így van.


Szóhasználat

  • Tömb más néven: vektor (vector).
  • Egyszerű/beépített adattípusok: egész, valós, karakter, …
  • Összetett/származtatott adattípus: pl. a tömb (több egészből)

18. A tömbök kezelése I. – hogyan igen

Tömb létrehozása: elemtípus név[méret];. Kezdeti érték: {} között.

int tomb[10];
double t[5] = {9.3, 7.5, 3.7, 0, 4.2};

Ha adunk meg kezdeti értéket – ez nem kötelező –, akkor legalább egy elemet írnunk kell a kapcsos zárójelek közé. Viszont ha egyáltalán nem adunk meg kezdeti értéket, akkor a tömb elemei inicializálatlanok, nem lehet tudni előre, milyen számokat tartalmaznak! (Erről még lesz pár szó.)

Inicializáláskor, ha van kapcsos zárójelek közötti rész, a meg nem adott tömbelemek értéke nulla lesz. Így a double t[5] = {1.2}; sorral nem egy olyan tömböt adunk meg, amelynek összes eleme 1.2, hanem egy olyat, amelynek első eleme 1.2, a többi pedig nulla. Tehát az alábbi két sor egyenértékű:

double t[5] = {1.2};
double t[5] = {1.2, 0, 0, 0, 0};

Elem elérése: indexelés/címzés (indexing) szögletes zárójellel (bracket).

A tömb indexelése (indexing), más néven címzése szögletes zárójellel (bracket) történik. A művelet által megkapjuk a tömb egyetlen egy elemét, amely ugyanúgy használható, mint egy önálló változó. Új érték adható neki, de szerepelhet akár egy printf() vagy egy scanf() paramétereként is.

tomb[9] = 3;
printf("%d", tomb[6]);
scanf("%d", &tomb[4]);

A tömb feldolgozása: ciklussal. Az index tartománya: 0-tól méret−1-ig!

A tömböket gyakran ciklussal dolgozzuk fel. Ilyenkor figyelni kell arra, hogy a tömbindexek tartománya 0-tól méret−1-ig-ig terjed. A lenti egy tipikus tömbös ciklus. Nullától indul az iterátor (ez a tömb legelső eleme), és egyesével növekszik.

Dijkstra
for (i = 0; i < 10; i += 1)
   tomb[i] = 0;

A ciklusban maradás feltételében a „kisebb” relációt szokás használni, nem pedig a „kisebb vagy egyenlő” relációt. Mégpedig azért, mert így a tömb mérete szerepelhet a kódban. Bár i<10 és i≤9 ugyanazt jelenti, de az i<10 forma ebben az esetben sokkal egyszerűbb! Nem kell figyelni arra, hogy kivonjunk egyet a tömb méretéből, hanem magát a méretet lehet odaírni. Szokjuk meg ezt a formát a tömbökhöz, az egész világon így csinálják!

Érdekesség: Edsger W. Dijkstra holland matematikus, programozó volt. Fontosnak tartotta a levelezést és a tapasztalatcserét kollégáival. Ezért a gondolatait, megfigyeléseit, útjairól szóló írásait számozva, fénymásolt kéziratok formájában küldte el nekik. A fentiekkel kapcsolatban álljon itt egy rövid írása (EWD831).

19. A tömbök kezelése II. – hogyan ne

Van néhány dolog, amit nem szabad csinálni a tömbökkel.

A tömb elemeit csak egyesével lehet kezelni.

Helytelen
int a[10], b[10];
a = b;
Helyes:
for (i = 0; i < 10; i += 1)
   a[i] = b[i];

Az a=b értékadás helytelen voltának mélyebb okai vannak. Erről később lesz szó.


A tömb méretét meg kell adni a program írásakor.

Helytelen:
/* „elég nagy”? */
double tomb[];
Helyes, de vigyázni vele:
scanf("%d", &db);
double tomb[db];

A tömbre mint fix méretű tárolóra kell gondolnunk elsősorban. Egy tömb nem fog magától megnyúlni, sem összemenni: akkora marad, annyi számot tud tárolni, amennyit a létrehozásakor megadtunk. Emiatt a meg nem adott méretű tömböt definiáló programsor (int tomb[];) teljesen értelmetlen, és nagyon súlyos hibának számít.

A C nyelv újabb változata (C99) elfogadja azt, ha a tömb méretét változóval adjuk meg, mint fent a scanf()-es példában. Ezzel azonban óvatosan kell bánni, ilyet csak ellenőrzött körülmények között szabad csinálni. Mi történik akkor, ha a felhasználó negatív számot ad meg? És akkor, ha egy óriási pozitív számot, amennyi memóriája nincs a gépnek? Ezek olyan kérdések, amelyekkel most, a félév elején még nem foglalkozunk, hanem majd később.

20. Tíz darab szám – és fordítva

1. szám: 1.23
2. szám: 3.14
3. szám: 5

…

3. szám: 5
2. szám: 3.14
1. szám: 1.23
#include <stdio.h>

int main(void) {
   double szamok[10];
   int i;

   /* beolvasás */        // 0-tól 9-ig
   for (i = 0; i < 10; i += 1) {
      printf("%d. szám: ", i + 1);
      scanf("%lf", &szamok[i]);
   }

   /* kiírás */           // 9-től 0-ig
   for (i = 9; i >= 0; i -= 1)
      printf("%d. szám: %f\n", i + 1, szamok[i]);

   return 0;
}

A fenti megoldásban mindig hozzáadunk egyet a tömbindexhez, amikor a felhasználónak szóló szövegben a sorszámot hivatkozzuk. Így a programban a tömbindexek tartománya 0…9 (ez kötelező, a C nyelv tömbje miatt), de a képernyőn 1…10 látszik.

21. Tételek megvalósítása tömbökön

Tömb másolása

double forras[5] = {9, 2, 4, 1, 5}, cel[5];
int i;

for (i = 0; i < 5; i += 1)
    cel[i] = forras[i];

Természetesen ennek a tételnek is meg lehet adni a pszeudokódját általánosságban:

CIKLUS AMÍG van még szám, ADDIG
    szám = következő elem
    KI: szám
CIKLUS VÉGE

A fenti kód ennek a tételnek a megvalósítása abból a célból, hogy egy tömb tartalmát egy másikba lemásoljuk. A cél tömb legalább akkora kell legyen, mint a forrás tömb, vagyis amennyi elemet másolunk.


Tömb elemeinek összegzése

int tomb[5] = {9, 2, 4, 1, 5};
int osszeg, i;

osszeg = 0;
for (i = 0; i < 5; i += 1)
    osszeg += tomb[i];
printf("Összeg: %d\n", osszeg);

Ez teljesen analóg az előzővel. Ezzel a ciklussal sokat fogunk találkozni.

22. Tételek: kiválogatás két tömbbe

Negatívak az egyik tömbbe, nem negatívak a másikba.

int szamok[20] = { 3, -2, /* ... a számok ... */ };

int neg[20], nemneg[20];          // ezekbe válogatja szét
int db_neg, db_nemneg, i;

db_neg = 0;
db_nemneg = 0;
for (i = 0; i < 20; i += 1) {        // összes elem
    if (szamok[i] < 0) {
        neg[db_neg] = szamok[i];       // ha igaz rá, hogy…
        db_neg += 1;
    } else {
        nemneg[db_nemneg] = szamok[i]; // ha nem igaz
        db_nemneg += 1;
    }
}
printf("%d nemnegativ, %d negativ.\n", db_nemneg, db_neg);

Ez az algoritmus egy adott tulajdonság szerint szétválogatja a tömb elemeit. Amelyek rendelkeznek egy bizonyos tulajdonsággal (itt: negatívak), azokat bemásolja az egyik tömbbe, a többit pedig a másikba. Az eredeti tömb változatlanul marad.

A két cél tömb mérete ugyanakkora, mint az eredeti tömbbé, hiszen előfordulhat, hogy az utóbbiban pl. csak negatív számok vannak. Minden egyes esetben, amikor valamelyik tömbbe beírunk egy elemet, akkor az ahhoz a tömbhöz tartozó számlálót megnöveljük. Először így a 0. indexű helyre kerül az elem, utána az 1. indexűre és így tovább. A két számláló így egyben azt is tartalmazza, hogy az egyes tömbökbe hány elem került – azaz hogy hány negatív és hány nemnegatív elem volt. A db_neg+db_nemneg összeg a ciklus lefutása után értelemszerűen az eredeti tömb méretével egyezik meg, mert mindegyik számnak kerülnie kellett valahova.

Érdemes más programokban is ezt az elvet követni. Ezért is hasznos az, hogy az indexelés nullától indul: mert így a darabszám egyenlő a következő elem indexével, ami pedig egyenlő azzal a tömbmérettel, amelyben elférnek az eddigi adatok.

23. Tömbök vs. nem tömbök

Tipp: emlékezni
kell az összes
elemre → tömb

Tömb használata: példák

  • Fordított sorrendű kiírás,
  • Növekvő sorrendbe rendezett kiírás,
  • Átlagnál nagyobb számok kiírása.

Miért is kell eltárolnunk az összes számot, ha az a feladat, hogy írjuk ki a beolvasott számok közül az átlagnál nagyobbakat? Azért, mert az átlaguk akkor derül ki, amikor már láttuk az összeset. Ha pedig már megvan az átlag, csak akkor tudjuk eldönteni az elsőről, hogy ki kellett volna-e írni, a másodikról úgyszint, és így tovább. Tehát emlékeznünk kell, mik voltak a számok.


Kell tömb vagy nem kell?

  • Tipikus hiba tömböt használni, amikor nincs rá szükség, pl. hasraütésszerűen 1000 elemű tömbbe beolvasni számokat.
  • Összeg, keresés, szélsőérték: ezekhez nem kell, nem kell emlékezni a régiekre és sorrendben kell feldolgozni őket.

Hasraütésszerűen amúgy sem választhatunk a programban tömbméretet: csak akkor mondhatjuk, hogy 1000 elemű legyen a tömb, ha ez a feladat specifikációjából következik.

24. Kis kitérő: az álvéletlenszámok

Feladat: két kockával dobás összegét vizsgáljuk. Melyik összeg, milyen gyakran fordul elő?

A következő programban azt fogjuk megvizsgálni, hogy két dobókockával dobva, a két kockán látható számok összegének milyen eloszlása van. Mert az egy kockával dobással ellentétben ennél nem egyenletesen jön ki mindegyik összeg. A kockadobások szimulálásához véletlenszámokat fogunk használni.


A jól megírt programok determinisztikusak. Kérdés: akkor honnan lesznek véletlenszámaink?

A determinisztikusság azt jelenti, hogy egy adott programot ugyanazzal a bemenettel futtatva mindig ugyanazt a kimenetet kapjuk. A legtöbb esetben ez természetesnek tűnik, éppen ezt a megbízhatóságot várjuk a számítógéptől. Azonban bizonyos alkalmazásoknál ez korlátot jelent. Elképzelhetjük, elég unalmas lenne egy olyan kártyajáték, amelyben mindig ugyanazt a leosztást kapjuk. Mégis ha a számítógép determinisztikus természetű, hogyan lehetne olyan programot írni, amelynél nem minden futásnál ugyanaz az eredmény? Hogyan tudunk a programból feldobni egy pénzt, fej vagy írás, vagy kockával egy 1 és 6 közötti számot dobni?

A megoldás egy álvéletlenszám-generátor (vagy más néven: pszeudovéletlenszám-generátor) alkalmazása. Ez egy olyan matematikai műveletsort jelent, amelynek az eredménye egy össze-visszának tűnő számsor. Annyira össze-visszának, hogy az már véletlenszerűnek fogadjuk el. Ha pl. az x=(5*x+1)%16 kifejezést újra és újra kiértékeljük, az x változó a 1, 6, 15, 12, 13, 2, 11, 8, 9, 14, 7, 4, 5, 10, 3, 0, … értékeket veszi fel, amelyben nem nagyon látunk szabályosságot. (Ha tovább folytatjuk, akkor persze igen, mert a számsor elkezd ismétlődni.)

A C nyelv rand() függvénye a fentihez hasonló, de bonyolultabb módon előállított véletlenszámokat ad, méghozzá a 0 és a RAND_MAX konstans közötti egész számot. A RAND_MAX konstans értéke a C fordítónk típusától függ, és számítógépenként változhat. Adott tartományban lévő számot legegyszerűbben egy osztás maradékaként állíthatunk elő ebből. Ha például azt nézzük, hogy az előállított véletlenszám páros vagy páratlan, pénzfeldobást szimulálhatunk:

if (rand() % 2 == 0)
    printf("fej");
else
    printf("írás");

Kockadobást pedig úgy tudunk szimulálni, ha a véletlenszámot elosztjuk hattal, és az így kapott, 0 és 5 közé eső maradékhoz még egyet adunk:

kocka = rand()%6 + 1;

Fontos, hogy az álvéletlenszámok determinisztikusak. Vagyis a program többszöri indítására mindig újra ugyanaz a számsor áll elő. Ezt elkerülendő, a véletlenszám-generátort inicializálni, azaz indítani kell. Az indítást az srand(x) utasítással tehetjük meg, ahova az x helyére egy tetszőleges egész számot írhatunk. Ugyanaz az x érték ugyanazt a számsort állítja elő újra, míg egy másik x érték teljesen más számsort ad. Tehát már semmi más nem kell, csak egy olyan x érték, amely a program minden futtatásánál más és más, mert ebből fog kiindulni a generátor. A probléma megoldásához azt a trükköt szoktuk használni, hogy lekérdezzük a gép óráját: a time(0) kifejezés az 1970. január 1. éjfél óta eltelt másodpercek számát adja. Ezzel indítva a véletlenszám-generátort mindig más számsort fogunk kapni.

srand(time(0));  // a program elején egyszer!

Ezt az inicializálást nem kell, sőt nem is szabad minden új szám generálásánál elvégezni, hanem csakis a program futásának elején, egyszer kell megtenni! Az alábbi program tíz egymás utáni kockadobás eredményét írja a képernyőre. Figyeld meg, hogy míg a rand()%6 + 1 kifejezés többször is kiértékelődik a ciklusban, addig az srand() csak egyszer, a program elején! Próbáld ki, mi történik akkor, ha a ciklus belsejébe mozgatod az srand()-ot is!

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void) {
    srand(time(0));  // csak egyszer!
 
    int i;
    for (i = 0; i < 10; i += 1)
        printf("%d\n", rand()%6 + 1);
 
    return 0;
}

A rand() és az srand() függvény, továbbá a RAND_MAX konstans használatához az stdlib.h fájlt kell a programkód elején beilleszteni. A time()-hoz a time.h szükséges. A time() működéséről és az ott lévő 0 szerepéről később lesz szó.

25. Az adatszerkezet

Adatszerkezet

Az adataink strukturális elrendezése a programban.


Példa: számlálók a 2…12 dobásösszegekhez

A kockadobások lehetséges összegei 1+1=2 és 6+6=12 között vannak. Minden összeghez rendelünk egy számlálót; a dobás után az adott számlálóhoz húzunk egy strigulát.

ezt szeretnénk
eltárolni
23456789101112
||||||||||||||||||||||||||

Az összegek közül a legkisebb az 2, a legnagyobb a 12. Ezért a gyakoriságokat tároló tömbünk 12-2+1 = 11 elemű kell legyen. Ennek a tömbnek az indexei a 0…10 tartományban lesznek, ezért a dobások összegéből 2-t le kell vonni: 2…12 - 2 = 0…10, úgy kapjuk az adott dobás gyakoriságát tároló tömbelem indexét.


így jelenik meg
a programban
t0 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10
11334523121

A jelenlegi adatszerkezet működése:

t[összeg - 2] → számláló az adott összeghez

26. Kockadobások összege

Alább látható a programrészlet, amely elvégzi a kísérletet.

int dobas[12-2+1] = { 0 };
int i;

srand(time(0));

/* kísérletek */
for (i = 0; i < 1000; i += 1) {
    int kocka1 = rand() % 6 + 1;     /* 1-6 */
    int kocka2 = rand() % 6 + 1;
    int osszeg = kocka1 + kocka2;
    dobas[osszeg-2] += 1;      // 2-12 → 0-10
}

/* eredmény */
for (i = 2; i <= 12; i += 1) {
    printf("a+b=%2d: %3d alkalom\n", i, dobas[i-2]); // !
}

Az adatszerkezet működése, nevezetesen hogy egy adott összeghez az összeg - 2 indexű tömbelem tartozik, legjobban a felkiáltójellel jelölt sorban látszik.

Programozási hibák

28. Kontraszt

kifejezésjelentés
3.14
3, 14
tizedespont, a π közelítő értéke
vessző, elválasztás, pl. pow(3, 14)=314
x == y
x = y
vizsgálat: x egyenlő-e y-nal
értékadás: x legyen egyenlő y-nal
x = b
x = 'b'
x vegye fel a b változó értékét
x legyen a b betű karakterkódja
x = 1
x = '1'
x legyen 1
x legyen az 1-es számjegy karakterkódja
printf("%d", 65)
printf("%c", 65)
írd ki 65-öt, mint szám: "65"
írd ki a 65-ös kódú karaktert: "A"
"a"
'a'
szöveg (sztring), amely egy betűt tartalmaz
egyetlen karakter


If blue is the sky…

Az értékadás és az egyenlőségvizsgálat keverése miatt gyakran szokták tanácsolni, hogy a feltételeket fordítva írjuk. Így nem lehet összekeverni a kettőt, hiszen ebben a kódrészletben = értékadás használata esetén szintaktikai hibát kapunk, ami fordítási hibához vezet. Sajnos a fordított feltétel az olvashatóságot csökkenti, néha zavar a kód megértésében. Ezért mi nem javasoljuk a használatát. A programozó folklór egyébként ezt a stílust Yoda-feltételnek nevezi, mert Yoda az eredeti Csillagok háborúja szinkronban így beszél (pl. „if blue is the sky”-t mond „if the sky is blue” helyett.)

29. A fordítók figyelmeztetései

  • Enable all compiler warnings (-Wall)
  • Enable warnings demanded by strict ISO C (-pedantic)

A Code::Blocks Settings menüjében találunk egy Compiler and debugger… menüpontot. Ezt megnyitva a fordítóprogram beállításaihoz jutunk. A fent látható két opciót nagyon erősen javasolt engedélyezni az otthoni gépeteken. Ilyenkor ugyanis a fordító minden gyanús, szokatlan kódrészletre figyelmeztetést ad (-Wall), illetve a nem szabványos, esetleg más fordítókkal nem működő nyelvi fordulatokat nem engedi használni (-pedantic). Ezeket beállítva sokkal hatékonyabb, könnyebb a tanulás és a gyakorlás! Például az előbb említett x=y és x==y összekeverésére is legtöbbször figyelmeztetni tud.

30. Néhány szó a kezdeti értékekről

double pi = 3.14;       // inicializált változó

int i, osszeg;          // inicializálatlan változó

Ha nem kap kezdeti értéket, inicializálatlan lesz → memóriaszemét


Coding Horror logo

Az inicializálatlan változók

  • Súlyos hiba egy inicializálatlan változó értékét használni!
  • Lehet, hogy nulla, lehet, hogy nem. Lehet, hogy mindig más az értéke, lehet, hogy nem. Lehet, hogy működik a program, lehet, hogy nem
  • Misztikus, megjósolhatatlan hibajelenségek!

Vigyázat: a lentiek nem jelentik azt, hogy görcsösen adjunk kezdeti értéket minden változónak, akkor is, ha felesleges! Például egy ciklusváltozót felesleges inicializálni a létrehozásakor, hiszen a for() fejlécében úgyis fog értéket kapni. Egy összegzést végző programrész osszeg=0 utasítását is érdemes a ciklus elé tenni közvetlenül, hiszen ahhoz a programrészlethez tartozik logikailag!

Ezt a kódrészletet mindenki ki tudja próbálni a saját gépén. A legmeglepőbb dolgok történhetnek, mivel a működése az inicializálatlan változók miatt nem definiált.

#include <stdio.h>

int main(void) {
    int t[15];  /* inicializálatlan */
    int i;
    
    for (i = 0; i < 15; i += 1)
        printf("%d\n", t[i]);
    
    return 0;
}

31. Tömbök túlindexelése

Túlindexelés: súlyos hiba!

  • A C nem ellenőrzi a megadott tömbindexeket
  • int t[10] tömb túlindexelése: t[-1], t[10], t[234]
  • Misztikus hibák, elvesző változóértékek, lefagyó programok

Az indexhatárok nem ellenőrzésének az oka egyszerű: a hatékonyság. A C nyelv sok modern programozási nyelvvel ellentétben arra való, hogy a lehető leggyorsabban futó programokat írjuk vele. A helyesen megírt programban sehol nincsen tömb túlindexelés, ezért felesleges is lenne a program futása közben ellenőrizni, hogy van-e benne ilyen hiba! A helyes program írása így aztán nem másnak a feladata, mint a programozónak.

„Ki itt belépsz, hagyj fel minden reménnyel.”

Nem definiált működés (undefined behaviour): hibás program, nincs meghatározva, hogy minek kellene történnie. Nincs garantálva semmi.


Ezt is érdemes kipróbálni.

#include <stdio.h>

int main(void) {
  double t[10];
  int a = 1, b = 2, c = 3;

  printf("a=%d\nb=%d\nc=%d\n", a, b, c);

  /* túlindexelés */
  t[-1] = 0.2;
  t[10] = 0.3;
  printf("\n");

  printf("a=%d\nb=%d\nc=%d\n", a, b, c);

  return 0;
}
Ördög