Gyakorlat, 14. hét: generikus algoritmusok

Czirkos Zoltán · 2017.07.13.

Függvényekre mutató pointerek. Generikus algoritmusok.

Függvényekre mutató pointerek. A gyakorlat első felében a generikus gondolkodást bemutató feladatok vannak – magas szinten.

Állapotgépek. A feladatok megoldásának lényege az, hogy az állapotátmeneti táblát és a tevékenyságtáblát megalkotjuk: az állapotgépet megtervezzük. Ha ez megvan, akkor onnantól a kódolás már mechanikus. Egy olyan feladatnál, ahol több állapotátmenet is van, nem lehet csak úgy nekiugrani a kódolásnak! Ha a táblázat megalkotása után fejből írunk valami kódot, nem a tábla alapján, annak sincs semmi értelme. Az is értelmetlen, ha a kettőt fordított sorrendben csináljuk meg…

A tervezés után az állapotgépet mindenképpen le kell tisztázni egy állapottáblával. A gráfot nézve ugyan jobban lehet mélázgatni az állapotátmeneteken, a táblázat sokkal áttekinthetőbb, és biztosítja azt is, hogy semelyik átmenetet sem hagytuk ki. A kódolás során pedig kifejezetten jobb abból dolgozni.

Felkészülés a gyakorlatra:

1. Karakterek számlálása típusok szerint

Írjunk C függvényt, amelyik egy sztringben meg képes számolni, hogy hány bizonyos tulajdonsággal rendelkező karakter van (pl. kisbetűk vagy számjegyek, esetleg írásjelek). Hogy mi ez a tulajdonság, az is a függvény paramétere legyen!

Megoldás

A sztringen végiglépkedés, a karakterek számlálásának módja független attól, hogy konkrétan milyen karaktert keresünk. Az „e” betűs függvény a karaktert int-ként veszi át, a logikai értéket pedig int-ként adja vissza, hogy kompatibilis legyen az islower() és hasonló függvényekkel. Az a függvény történelmi okokból ilyen. (Ez könnyen ellenőrizhető bármelyik C referenciában, vagy a C puskában.)

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

int e_betu_e(int c) {
    return c == 'E' || c == 'e';
}

/* A feladat megoldasa ez a fuggveny. */
/* A "feltetel" parameter: egy darab int parameteru (c), int
   visszateresi ertekkel rendelkezo fuggvenyre mutato pointer. */
int karakter_szamol(char *str, int (*feltetel)(int c)) {
    int darab = 0;
    int i;
    for (i = 0; str[i] != 0; ++i)
        if (feltetel(str[i]))
            darab++;
    return darab;
}

int main(void) {
    char szoveg[] = "Ernoke 4 eves (jovore 5 lesz).";

    printf("%d e vagy E betű\n", karakter_szamol(szoveg, e_betu_e));
    printf("%d space\n", karakter_szamol(szoveg, isspace));
    printf("%d kisbetű\n", karakter_szamol(szoveg, islower));
    printf("%d számjegy\n", karakter_szamol(szoveg, isdigit));

    return 0;
}

2. Numerikus integrálás

Integráljunk egy függvényt egy korlátos intervallumon numerikusan! Vagyis számoljuk ki az alatta lévő területet. Közelítsük ezt téglalapokkal! Írjunk generikus algoritmust, amely bármely függvényen képes dolgozni!

Megoldás

  • Az x tengelyen dx lépésközzel haladunk.
  • Mindenhol kiszámítjuk f(x) értékét.
  • Így meghatározható a rajzon látható téglalapok területe.
  • Az integrál közelítő értéke ezek összege: ∑f(x)*dx.

Az integrálandó f(x) függvényt paraméterként vesszük át. Mivel ez a példában egy egyváltozós, valós függvény, C-ben egy olyan függvényként jelenik meg, amelynek egy double paramétere, és double visszatérési értéke van. A paraméter típusa tehát:

double (*f)(double)

Az ezt megvalósító függvény pedig az alábbi. (A dx-szel való szorzást kiemelhettük a szummán kívülre, hogy gyorsabb legyen a program.)

#include <math.h >

double integral(double (*f)(double), double ettol, double eddig, double dx) {
    double osszeg = 0.0, x;
    for (x = ettol; x < eddig; x += dx)
        osszeg += f(x);             // ∑f(x)

    return dx * osszeg;            // dx * ∑f(x)
}

double sajatf(double x) {
    return 5 * x * x + 2 * x - 24.3;
}

int main(void) {
    double t;

    t = integral(sajatf, 14.3, 29.2, 0.1);
    printf("sajatf -> %g\n", t);
    t = integral(sin, 0, 3.1415927, 0.05);
    printf("sin -> %g\n", t);

    return 0;
}

Természetesen akár a könyvtári sin() függvényt is integrálhatjuk, hiszen annak is double sin(double) a típusa.

3. Összeg, szorzat: akkumuláció

Írjunk függvényt, amely paraméterként kap két egész számot (a és b), és összegzi a két intervallum közötti számokat (beleértve a-t és b-t is).

Megoldás

int osszeg(int a, int b) {
    int szum = 0;
    int i;
    for (i = a; i <= b; i += 1)
        szum = szum + i;

    return szum;
}

Alakítsuk át ezt úgy, hogy ne csak összegezni, hanem szorozni is lehessen vele. Ehhez az összeadást ki kell cserélnünk egy akkumuláló műveletre, és természetesen a kezdeti értéket is ki kell cserélnünk egy paraméterre (hiszen 0-nál a szorzat mindig 0 lenne).

Megoldás

int akkumulal(int a, int b, int (*akkum)(int, int), int kiindul) {
   int akk = kiindul;
   int i;
   for (i = a; i <= b; i += 1)
      akk = akkum(akk, i);
   
   return akk;
}

Gondoljunk bele: így olyan összegzések is megvalósíthatóak (pl. kivonás, osztás, négyzetösszeg, stb.), amikre az összegzés függvény megírója eredendően nem is gondolt. A függvény tovább általánosítható lenne, ha az i+=1 lépést is egy függvényre cserélnénk le.

Számoljuk ki ezzel a függvénnyel az 1…6 számok összegét és az 1…6 számok szorzatát (faktoriális)!

Megoldás

int osszegzo(int a, int b) {
    return a + b;
}

int szorzo(int a, int b) {
    return a * b;
}

int main(void) {
    printf("1-tol 6-ig osszeg: %d\n", akkumulal(1, 6, osszegzo, 0));
    printf("1-tol 6-ig szorzat: %d\n", akkumulal(1, 6, szorzo, 1));
}

4. Mondatok nagybetűsítője

Írjunk állapotgépes programot, amely a beírt, csupa kisbetűkből álló szöveget úgy javítja ki, hogy minden mondat elején álló első betűt nagybetűre cseréli!

Megoldás

Mondat végét jelző írásjel után a következő betű nagybetű, de csak akkor, ha szóköz is jött. Figyelni kell, hogy az utána lévő szóköztől nem váltunk kisbetűs módra még! A gép alapállapota a nagybetűsítés, hiszen a bejövő szöveg legelső karaktere biztosan mondat elején van.

. ! ?szóköz, \negyéb
nagybetűki: cki: cki: toupper(c)
→kisbetű
kisbetűki: c
→mondatvége?
ki: cki: c
mondatvége?ki: cki: c
→nagybetű
ki: c
→kisbetű
#include <stdio.h>
#include <stdbool.h>
#include <ctype.h>

bool mondatvege_jel(int c) {
    return c == '!' || c == '.' || c == '?';
}

int main(void) {
    enum allapot {
        nagybetu,
        kisbetu,
        mondatvege
    } all;
    all = nagybetu;     /* kiindulo allapot */

    int c;
    while ((c = getchar()) != EOF) {
        switch (all) {
        case nagybetu:
            putchar(toupper(c));
            if (!mondatvege_jel(c) && !isspace(c))
                all = kisbetu;
            break;
        case kisbetu:
            putchar(c);
            if (mondatvege_jel(c))
                all = mondatvege;
            break;
        case mondatvege:
            putchar(c);
            if (isspace(c))
                all = nagybetu;
            else if (!mondatvege_jel(c))
                all = kisbetu;
            break;
        }
    }

    return 0;
}

5. Zárójeles szöveg

Írjunk állapotgépes programot, amelyik egy adott szövegből eltávolítja a (zárójelezett részeket). Előfordulhat, hogy a zárójelek tetszőleges mélységben egymásba vannak ágyazva (például így, mint ez a (zárójeles) szó).

Megoldás

Nem lehet megoldani véges számú állapotot tartalmazó állapotgéppel. Minden bezáró zárójel „)” esetén tudni kellene, hogy hány be nem zárt zárójel van még; ez annyiféle „(” utáni állapotot feltételez. A feladat szövege szerint pedig ezekből tetszőlegesen sok lehetne. Ellenben állapotváltozónak használhatunk egy int-et, amit növelünk és csökkentünk. Feltételezve, hogy az int nem csordul túl, így megoldható a feladat – de ez nem véges automata, nem rajzolható fel egy véges állapotátmeneti gráffal vagy állapottáblával.