Gyakorlat, 14. hét: generikus algoritmusok

Integrálj egy függvényt egy korlátos intervallumon numerikusan, vagyis számítsd ki az alatta lévő területet, közelítve téglalapokkal!

Írj generikus algoritmust, amely bármely double paraméterű, double visszatérési értékű függvényen képes dolgozni! Mutass példát a függvény hívására, amellyel a sin függvényt integrálod 0 és π között!

A feladat megoldására 10 perc áll rendelkezésre.

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

int main(void) {
    double t = integral(sin, 0, 3.1415927, 0.05);
    printf("sin -> %g\n", t);
}

Mindegyik tétel 1 pontos:

• Függvény paraméterei: határok (lépésközt nem kellett külön, de jó ha van)
• Függvény paramétere fv. pointer: double (*f)(double) vagy double f(double) is jó
• Ciklus a két határ között
• Területek összegzése
• A paraméterként átvett függvény hívása
• Főprogram: integráló függvény hívása, sin és &sin is jó, de kerek zárójel operátor a sin után nem lehet
• Eredmény kiírása

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