Gyakorlat, 14. hét: generikus algoritmusok

Czirkos Zoltán · 2018.08.22.

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

Felkészülés a gyakorlatra:

1. Ellenőrző feladat

A feladat segít felmérni, hogy állsz a tanulással. A szövege csak a többi megoldással együtt jelenik meg. Óra után pedig rögzítsd a pontszámod az admin portálon – a dolgozat nálad marad.

Feladat

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.

Mintamegoldás és pontozási útmutató
#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

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

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!