Gyakorlat, 14. hét: generikus algoritmusok

Czirkos Zoltán · 2021.12.04.

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

Felkészülés a gyakorlatra:

1. Numerikus integrálás

Integráljunk egy függvényt egy korlátos intervallumon numerikusan! Vagyis számítsuk 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>
#include <stdio.h>

double integral(double (*f)(double), double ettol, double eddig, double dx) {
    double osszeg = 0.0;
    for (double 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.

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

Írjunk C függvényt, amelyik egy sztringben megszámolja, 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. A predikátumfüggvény char paraméterű (vizsgált karakter), és logikai visszatérési értékű (teljesül-e rá a vizsgált tulajdonság vagy nem).

Ha használni szeretnénk a könyvtári islower, isspace stb. függvényeket, akkor figyelembe kell vennünk, hogy azoknak int paramétere és int visszatérési értéke van, történelmi okokból. Legszebb megoldás az, ha írunk egy másik függvényt, az általunk használt, modern fejléccel: bool ___(char), és abból meghívjuk a megfelelő könyvtári függvényt. Olyan, mintha a my_isspace, my_islower nem csinálna semmit, de ez nincs így: ez végzi char→int és az int→bool konverziókat.

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

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

bool my_isspace(char c) {
    return isspace(c);      /* char->int, int->bool konverzió! */
}

bool my_islower(char c) {
    return islower(c);      /* char->int, int->bool konverzió! */
}

/* A feladat megoldasa ez a fuggveny. */
/* A "feltetel" parameter: egy darab char parameteru, bool
   visszateresi ertekkel rendelkezo fuggvenyre mutato pointer. */
int karakter_szamol(char *str, bool (*feltetel)(char)) {
    int darab = 0;
    for (int 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("A szoveg: [%s]\n", szoveg);
    printf("%d e vagy E betu\n", karakter_szamol(szoveg, e_betu_e));
    printf("%d space\n", karakter_szamol(szoveg, my_isspace));
    printf("%d kisbetu\n", karakter_szamol(szoveg, my_islower));

    return 0;
}

3. Monte Carlo

Mennyi a valószínűsége annak, hogy…

  • kockával 6-ost dobunk? (1/6)
  • egy (-1…1; -1…1) véletlenszerűen választott pont az egységkörbe esik? (π/4)
  • fejet vagy írást dobunk? (1/2)

Határozzuk meg ezeket Monte-Carlo-módszerrel! Végezzük el a kísérletet ezerszer, és nézzük meg, hányszor sikerült (pl. lett a pénzfeldobás eredménye írás, vagy a kocka 6-os). Programban ezt úgy tudjuk megfogalmazni, hogy véletlenszámot generálunk, és azt vizsgáljuk.

Oldjuk meg előbb az első két feladatot (kocka és egységkör) külön, majd a megoldások összevetése alapján általánosítsunk, adjunk generikus megoldást!

Megoldás

Kockával dobás:

double kocka_montecarlo(void) {
    int hanyszor = 0;
    for (int i = 0; i < 1000; ++i)
        if (rand() % 6 + 1 == 6)
            hanyszor += 1;
    return hanyszor / 1000.0; /* nem egész osztás! */
}

Vegyük észre, hogy ha a fej vagy írásra vagyunk kíváncsiak, ugyanerre a függvényre van szükség, csak az if-hez írt feltétel más. Ha az egységkörbe eső pontokra, akkor is. Ezért az elvégzendő kísérletet kell paraméterként átvenni! A kísérletnek, mint függvénynek bemenő adata nincsen (void paraméterű), a visszatérési értéke egy logikai, igaz/hamis érték (bool típus). A kísérlet függvényre mutató pointer típusa:

bool (*kiserlet)(void);

A montecarlo() függvény:

double montecarlo(bool (*kiserlet)(void)) {
    int hanyszor = 0;
    for (int i = 0; i < 1000; ++i)
        if (kiserlet())
            hanyszor += 1;
    return hanyszor / 1000.0; /* nem egész osztás! */
}

Példa kísérlet függvény: mekkora a valószínűsége annak, hogy a (0…1; 0…1) véletlenszerűen választott pont az egységkörbe esik?

bool egysegkorbe(void) {
    double x = rand() / (double)RAND_MAX;
    double y = rand() / (double)RAND_MAX;
    return x*x + y*y < 1;
}

4. Összeg, szorzat: akkumuláció

Írjunk függvényt, amely paraméterként kap két számot (a és b), és összegzi az így meghatározott intervallumban lévő egész számokat (beleértve a-t és b-t is).

Megoldás
int osszeg(int a, int b) {
    int szum = 0;
    for (int 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;
   for (int 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));
}

Hogyan fogalmazható meg a faktorialis(n) függvény az akkumulal() használatával?

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

int faktorialis(int n) {
    return akkumulal(2, n, szorzo, 1);
}

int main(void) {
    printf("10 faktoriálisa: %d\n", faktorialis(10));
}

5. További feladatok

Írjunk generikus rendezést, amely valós számok tömbjét rendezi a megadott rendezési reláció szerint!

Általánosítsuk az algoritmust tetszőleges típusú tömbelemre!