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

Czirkos Zoltán · 2017.08.14.

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. Negatív elemek indexei

Adott egy valós számokat tartalmazó tömb, benne vegyesen mindenféle előjelű számokkal.

A feladat egy olyan programot írni, amelyik kigyűjti egy másik tömbbe a negatív tömbelemek indexeit. Miután ez megvan, egy olyan programrészt kell írni, amelyik az indexek ismeretében kiírja, hogy mik voltak a negatív számok.

Rajzoljunk ábrát, amely a tömböket, a tömbelemekben tárolt számokat, és az azok közötti összefüggéseket ábrázolja! Hány elemű kell legyen az a tömb, amelyik az indexeket tárolja? Honnan fogja tudni a negatív elemeket kiíró programrész, hogy hány negatív elem volt?

Összesen 10 szám van.
[0]=2.5 [1]=-69 [2]=5.4 [3]=-8 [4]=-7.7 [5]=6 [6]=2.9 [7]=-10 [8]=-3 [9]=9.8 

Ebből 5 szám negatív.
[1]=-69 [3]=-8 [4]=-7.7 [7]=-10 [8]=-3 

Megoldás

Az adatszerkezetünk az alábbi:

A szamok[] tömb tartalmazza a vizsgálandó valós számokat. Fölötte a tömb indexei láthatóak. A neg_idx[] tömb az, amelybe a negatív számok indexei kerültek. Hasonlítsuk össze a benne tárolt számokat a fent látható indexekkel! Látszik, hogy a kékkel jelölt elemek sorszámai kerültek az alsó tömbbe.

A neg_idx[] tömb önmagában nem túl hasznos, a benne lévő indexek nem mondanak semmit. A szamok[] tömbbel együtt azonban az indexeknek jelentése van: minden index hivatkozik egy negatív számra a fenti tömbből. Az alsó tömb mondanivalója tehát: „a felső tömb 1., 3., 4., 7. és 8. indexű eleme kisebb nullánál”. Valóban, szamok[1], szamok[3], szamok[4], szamok[7] és szamok[8] mind negatívak. Valóban, ezek pont a kék elemek.

Az indexeket tároló tömb méretét felülről tudjuk becsülni: legfeljebb annyi index lesz benne, ahány szám az eredeti tömbben volt. Ilyen akkor fordulhat elő, ha az eredeti csak negatív számokat tartalmazott. Miközben vizsgáljuk az eredeti tömböt, szükség van egy számlálóra. Ez a számláló fogja tárolni azt, hogy hány negatívat találtunk. Ugyanezt a kiválogatás közben indexelésre is használhatjuk, ahogyan azt eddig is láttuk hasonló algoritmusoknál.

#include <stdio.h>

int main(void) {
    double szamok[10] = { 2.5, -69, 5.4, -8, -7.7, 6, 2.9, -10, -3, 9.8 };
    int i;

    /* Az eredeti tömb kiírása */
    printf("Összesen %d szám van.\n", 10);
    for (i = 0; i < 10; ++i) {
        printf("[%d]=%g ", i, szamok[i]);   // 1
    }
    printf("\n\n");

    /* Negatívak indexeinek kigyűjtése */
    int neg_idx[10];
    int neg_db = 0;
    for (i = 0; i < 10; ++i) {
        if (szamok[i] < 0) {
            neg_idx[neg_db] = i;
            ++neg_db;
        }
    }

    /* Negatívak kiírása */
    printf("Ebből %d szám negatív.\n", neg_db);
    for (i = 0; i < neg_db; ++i) {
        printf("[%d]=%g ", neg_idx[i], szamok[neg_idx[i]]);   // 2
    }
    printf("\n");

    return 0;
}

Érdemes összehasonlítani az 1-es és 2-es jelű sorokat. Mindkettő arra hivatott, hogy kiírjon egy tömbindexet és a tömbbeli elemet a program kimenetére. De míg az első esetben a teljes tömböt kiírjuk, a másodikban már csak a negatív számokat. Ilyenkor a kiírandó indexet (sorszámot) is a neg_idx[] tömbből vesszük, és a szamok[] tömböt is olyan sorszámmal indexeljük meg, amelyet a neg_idx[] tömbből vettünk ki.

4. 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, 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.

Az adatszerkezetet a jobb oldalon látható ábra mutatja. A struktúrát a kék elem mutatja. Ilyenekből épül fel a teljes tömb, amelynek indexei pedig az elemek mellett láthatóak.

A teljes adatszerkezet tehát olyan tömb, amely struktúrákat tartalmaz. A tömböt előbb indexelni lehet, hogy egy struktúrához jussunk, utána pedig annak egy adattagját választhatjuk ki, hogy egy konkrét értékhez. Például a szamjegyek[1].ertek az 50-hez vezet, szamjegyek[0].romai pedig az XC sztringhez. (A sztring maga is tömb, de ezt most nem boncolgatjuk.)

#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ő */
};

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