Gyakorlat, 14. hét: generikus algoritmusok

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

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;
}

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;
}

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

    return szum;
}

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.

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));
}

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));
}