Gyakorlat, 6. hét: származtatott típusok

Czirkos Zoltán · 2016.08.28.

Származtatott típusok: tömbök és struktúrák. Összetett adatszerkezetek definíciója és kezelése.

Felkészülés a gyakorlatra:

1. A kapitány

NZH-n volt

A kapitány abban az évben született, amely 2016-hOz alulról a legközelebbi olyan szám, melynek osztói száma 8, és van benne 7-es számjegy. Hány éves a kapitány? Határozzuk meg algoritmikus módszerrel egy teljes C programban az évszámot! Írjuk ki ezt is, és azt is, hogy most hány éves!

Használjunk top-down tervezést! Ha jól csináljuk, a main() kb. 5 soros, és azt mondja: Az év változóban legyen 2015, és amíg nem igaz a vizsgált számra, hogy az osztóinak száma 8, és van benne 7-es számjegy, addig csökkentjük az év változó értékét.

(1978 a megoldás.)

Megoldás

#include <stdio.h>
#include <stdbool.h>
 
int osztokszama(int szam) {
    int db = 0;
    int i;
    for (i = 1; i <= szam; ++i)
       if (szam%i == 0)
           ++db;
    return db;
}
 
bool vanbenne(int szam, int mi) {
    while (szam > 0) {
       if (szam % 10 == mi)
           return true;
       szam /= 10;
    }
    return false;
}
 
int main(void) {
    int ev = 2016;
    while (!(osztokszama(ev)==8 && vanbenne(ev, 7)))
       --ev;
    printf("%d-ben született, %d éves", ev, 2016-ev);
 
    return 0;
}

2. Időpontok

Írjunk programot, amely egy struktúrában időpontot tárol: óra, perc. Írjunk függvényeket ehhez:

  • ido_kiir(i): kiírja az időpontot óra:perc formában.
  • ido_hozzaad(i, p): hozzáad p percet az i időponthoz, és visszatér az új időponttal. Pl. 15:15 + 45 = 16:00.
  • ido_eltelt(i1, i2): megmondja, hány perc telt el a két időpont között, pl. 16:30-15:15 = 75 perc. (A paraméterek sorrendje a kivonásnál megszokott: kisebbítendő, kivonandó.)
  • ido_kivon(i, p): kivon p percet az i időpontból, és visszatér az új időponttal. Pl. 15:45 - 30 = 15:15.

Megoldás

A 60 perc és a 24 óra kezelésére a percek hozzáadásánál nagyon jól használható a maradékképzés. Pl. 16:55+10 esetén: :55+10 = :65, ami helyett a következő óra :05 kellene. 65%60, vagyis a 60-nal osztás maradéka pont a percet adja, 65/60, maga az osztás pedig 1-et, amennyivel az órát meg kell növelni. Az órát utána egyszerűen 24-gyel modulózzuk, mert a napokkal már nem kell foglalkozni.

A kivonás nem megy ilyen egyszerűen, mert (5-10)%60 = (-5)%60 = -5. Ott sajnos külön kell kezelni a keletkező negatív értékeket.

#include <stdio.h>

/* Időpontot tárol egy napon belül: óra és perc. */
typedef struct Ido {
    int ora, perc;
} Ido;

/* Kiírja a paraméterként kapott időpontot óra:perc formában. */
void ido_kiir(Ido i) {
    printf("%02d:%02d", i.ora, i.perc);
}

/* Hozzáad a megadott i időponthoz p percet, és visszatér
 * az így kapott időponttal. p-nek pozitívnak kell lennie. */
Ido ido_hozzaad(Ido i, int p) {
    Ido uj;
    uj.perc = (i.perc + p) % 60;
    uj.ora = (i.ora + (i.perc + p)/60) % 24;
    return uj;
}

/* Kiszámolja, hány perc telt el i1-től i2-ig. A paraméterek
 * sorrendje a kivonásnál megszokott: i2-i1, rendre a
 * kisebbítendő és a kivonandó. Azzal a feltételezéssel ad
 * helyes eredményt, hogy a két időpont egy napon van. */
int ido_eltelt(Ido i2, Ido i1) {
    return i2.ora*60-i1.ora*60 + i2.perc-i1.perc;
}

/* Kivon valahány percet a megadott időpontból, és az így keletkező
 * új időponttal tér vissza. Negatív p-re helytelenül működik. */
Ido ido_kivon(Ido i, int p) {
    Ido uj;
    uj.perc = i.perc-p;
    uj.ora = i.ora;
    while (uj.perc < 0) {
        uj.perc += 60;
        uj.ora -= 1;
    }
    while (uj.ora < 0)
        uj.ora += 24;
    return uj;
}


int main(void) {
    Ido i1 = { 11, 50 }, i2 = { 12, 10 }, i3 = { 3, 30 };

    printf("i1 = "); ido_kiir(i1); printf("\n");
    printf("i2 = "); ido_kiir(i2); printf("\n");
    printf("i3 = "); ido_kiir(i3); printf("\n");

    printf("i2-i1 = %d\n", ido_eltelt(i2, i1));
    printf("i1+195 = "); ido_kiir(ido_hozzaad(i1, 195)); printf("\n");
    printf("i2-195 = "); ido_kiir(ido_kivon(i2, 195)); printf("\n");
    printf("i3-240 = "); ido_kiir(ido_kivon(i3, 240)); printf("\n");

    return 0;
}

3. Római számok II.

Elevenítsük fel a római számok kiírása programot! Ott a számok értéke szerint csökkenő sorrendben haladtunk. Valahogy így:

…
if (szam >= 5) { printf("V"); szam -= 5; }
if (szam >= 4) { printf("IV"); szam -= 4; }
while (szam >= 1) { printf("I"); szam -= 1; }
…

Figyelmesen vizsgálva a problémát rájöhettünk arra, hogy bármelyik feltétel kicserélhető ciklusra ebben a feladatban. Azért írtunk feltételt a szam>=5 kifejezéshez, mert tudjuk, hogy legfeljebb csak egyszer fog teljesülni – de akár írhattunk volna ciklust is.

Ha mindegyik helyre ciklus kerül, akkor így néz ki a kód:

…
while (szam >= 5) { printf("V"); szam -= 5; }
while (szam >= 4) { printf("IV"); szam -= 4; }
while (szam >= 1) { printf("I"); szam -= 1; }
…

Ez a sorminta már csak arra vár, hogy ciklust csináljunk belőle. Írjuk át a programot!

Megoldás

Minden római számhoz (pl. V, egy sztring C-ben) egy érték tartozik (pl. 5, egy egész szám C-ben), ez struktúrába való. A sok római szám struktúrái pedig tömbbe. Használhatjuk azt a trükköt, mint a lenti bankautomatánál is, hogy egy oda nem illő értékkel megjelöljük a tömb végét. Mivel a rómaiak nem használtak 0-t, a tömb végét jelölheti egy olyan elem, ahol az érték 0.

#include <stdio.h >

int main(void) {
    typedef struct Romai {
        char romai[5];
        int ertek;
    } Romai;
    Romai szamjegyek[] = {
        { "XC", 90 },
        { "L", 50 },
        { "XL", 40 },
        { "X", 10 },
        { "IX", 9 },
        { "V", 5 },
        { "IV", 4 },
        { "I", 1 },
        { "", 0 }      /* tömb végét jelző */
    };
    int szam;

    printf("Mi a szám? ");
    scanf("%d", &szam);
    if (szam < 1 || szam > 99)
        printf("Ez nekem már sok. Csak 99-ig tudom.\n");
    else {
        int i = 0;
        while (szamjegyek[i].ertek > 0) {
            while (szam >= szamjegyek[i].ertek) {
                printf("%s", szamjegyek[i].romai);
                szam -= szamjegyek[i].ertek;
            }
            ++i;  /* következő római szám */
        }

        printf("\n");
    }

    return 0;
}

A programba épített táblázat egy inicializált tömb a megfelelő római jelekkel és a hozzájuk tartozó értékkel. Ezt a függvényen belül is létrehozhatjuk, mivel máshol nem használjuk. A struktúra definícióját egybe is építhetjük a tömb változó létrehozásával. Ilyenkor még az is lehetséges, hogy a struktúra névtelen, mivel sehol máshol nem kell hivatkozni név szerint a típusra:

struct {
    char romai[5];
    int ertek;
} szamjegyek[] = {
    { "XC", 90 },
    { "L", 50 },
    { "XL", 40 },
    { "X", 10 },
    { "IX", 9 },
    { "V", 5 },
    { "IV", 4 },
    { "I", 1 },
    { "", 0 }      /* tömb végét jelző */
};

4. Bankautomata II.

Idézzük fel a múltkori bankautomatás feladatot! A feladatkiírás azt kérte, hogy írjunk egy programot, amely egy adott pénzösszeget a megadott névértékű bankjegyekre és érmékre bont le. Pl. 4200 Ft = 2×2000 Ft + 1×200 Ft.

Csavarjuk meg ezt! Az automata rekeszei végesek. Tároljuk el azt is, hogy melyik bankjegyből és érméből épp mennyi van! Írjuk meg a programot, amelyik úgy ad pénzt, hogy ezt figyelembe veszi!

Megoldás

Ez is egy kiváló példa a struktúra használatára. Összetartozó adat a rekeszben található címlet és a hozzá tartozó darabszám, pl. hogy 20000 forintosból 20 darab van. Hogy mindkettő egész szám (a forint és a darab), senkit ne tévesszen meg, ez nem tömb! Minden rekeszhez egy struktúra tartozik. A rekeszekből viszont sok van, és egyformák: ezért a rekeszeknek egy tömbje lesz. A használt adatszerkezet struktúrák tömbje: struct Rekesz penzek[].

A ciklusban először egy osztással kiszámoljuk, hogy mennyi kellene az adott címletből. Utána pedig megnézzük, van-e annyi egyáltalán. Ha nincs, akkor csak kevesebbet adunk ki.

#include <stdio.h>

int main(void) {
    typedef struct Rekesz {
        int ertek;
        int darab;
    } Rekesz;
    Rekesz penzek[]={
        {20000, 20},    /* huszezresbol 20 db */
        {10000, 0},     /* tizezres kifogyott */
        {1000, 10},
        {500, 50},
        {20, 197},
        {10, 123},
        {5, 19},
        {0, 0}          /* nullaval jelzem a tomb veget */
    };

    int mennyit;
    printf("Mennyit kene adni? ");
    scanf("%d", &mennyit);

    printf("Az automata kiadja:\n");
    int i;
    for (i = 0; penzek[i].ertek != 0; i++) {
       int hany_db = mennyit/penzek[i].ertek; /* ennyit kene */
       if (penzek[i].darab < hany_db)         /* nincs ennyi? */
           hany_db = penzek[i].darab;         /* jobb hijan... */

       if (hany_db > 0) { /* ha adunk ebbol (mert kell es mert van) */
          printf("%d db %d Ft-os.\n", hany_db, penzek[i].ertek);
          mennyit -= hany_db*penzek[i].ertek;
          penzek[i].darab -= hany_db;   /* innen kivesszuk. */
       }
    }
    if (mennyit != 0)
        printf("Nem tudok rendesen adni! Kene meg: %d Ft\n", mennyit);

    return 0;
}

A fenti algoritmus amúgy nem tökéletes. Pl. ha 6000-t kérünk, és van 5000-es és 2000-es, de nincs 1000-es, akkor ki akar adni egy 5000-est, és utána megáll – nem veszi észre, hogy 3 darab 2000-essel megoldható. A tökéletes megoldáshoz az ún. visszalépéses keresést kellene alkalmazni, amelyhez a tudnivalók majd később szerepelnek az előadáson.