Gyakorlat, 4. hét: tételek és tömbök

A megoldás terve

• A gép nem tudja magától, hogy melyik hónap hány napos, ezt nekünk kell megadni.
• Hozzunk létre egy tömböt, tároljuk el a hosszakat!

#include <stdio.h>

int main(void) {
    /* a program altal hasznalt tablazat */
    int honapok[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    /* a felhasználó által megadott */
    int melyik;
    
    printf("Melyik hónap?\n");
    scanf("%d", &melyik);
    printf("A(z) %d. hónap %d napos.\n", melyik, honapok[melyik-1]);
    
    return 0;
}

Figyelni kell itt, hogy mindig a hónap-1 indexet használjuk a tömbön, mivel a január, az 1. hónap adata a 0. indexű elemben van, tehát honapok[hónap száma - 1] = hónap hossza módon használhatjuk az adatszerkezetünket.

Ezt úgy is meg lehetne oldani, ha a 0. indexű elembe betennénk egy helytartót, pl. egy 0 értéket. Mert akkor a januárhoz tartozó 31-es szám az 1. indexre kerülne, a február 28-a a 2. indexre stb. A példamegoldás nem ilyen.

int honapok[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

A megoldás terve

• Össze kell adni az eltelt hónapokat, és az adott napot. Például március 5. = 31 (január) + 28 (február) + 5 (ötödike) = az év 64. napja.
• A hónapok hosszait az előző programban már eltároltuk egy tömbben. Annak az elejét kell majd összegezni.
• Szökőéveknél a február 29 napos. Ezt akkor kell figyelembe venni, ha a február eltelt.

#include <stdio.h>
#include <stdbool.h>

int main(void) {
    /* a program altal hasznalt tablazat */
    int honapok[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    
    /* ehhez fogja kiszamolni a napot */
    int ev = 2024, honap = 11, nap = 21;

    /* az adott honapnal mar nem kell hozzaadni a napok szamat,
       ezert i<honap. A tomb viszont 0-tol szamozodik, ezert
       kivonok az indexbol mindig 1-et! Ha a januar napjait adom
       hozza epp, akkor a 0-s indexu elem kell. */
    int hanyadik = 0;
    for (int i = 1; i < honap; i += 1)
        hanyadik += honapok[i-1];
    /* akkor szokoev, ha oszthato 400-zal VAGY (oszthato 4-gyel ES
       nem oszthato 100-zal). ha szokoev van, es a februar mar eltelt,
       akkor +1 nap (mert csak 28-at adtunk hozza, de 29-et kellene */
    bool szokoev = ev%400==0 || (ev%100!=0 && ev%4==0);
    if (szokoev && honap > 2)
        hanyadik += 1;
    /* vegul a mostani honapbol eltelt napok */
    hanyadik += nap;

    printf("%4d.%02d.%02d. az ev %d. napja.\n", ev, honap, nap, hanyadik);

    return 0;
}

A megoldáshoz vezető ötletek

• Biztosan kell egy ciklus, amelyik a számokat olvassa be.
• Minden pontszámhoz tartozik egy számláló, amit növelni kell akkor, ha hozzá tartozó számot látunk.
• A számlálók és a beolvasott számok között egy megfeleltetést kell létrehozni: melyik számhoz melyik számláló tartozik.

A sok számlálóhoz létrehozhatunk egy tömböt. Mivel tízféle szám van, azokhoz tíz számláló kell tartozzon, a tömb elemszáma is tíz lesz. A megszámolandó számok egész számok, ezért könnyű egy szám–tömbelem hozzárendelést kitalálni: egy adott számhoz pont az annyiadik tömbelemet használjuk, amennyi a szám értéke. Mivel a beérkező számok az 1…10 tartományban vannak, a tömb viszont 0…9 tartományban indexelődik, ezért az indexeléshez mindig a szám−1 értéket használjuk. (Hogy mindenhol ugyanilyen legyen az indexelés, és jobban érthető legyen a program, a számlálók nullázása és a kiírás is ezt az elvet követi a lenti programban.) A kialakított adatszerkezet a táblázatban látható.

Lényegében a számlálás tételét kell megvalósítani, két különbséggel: 1) nem egy számláló lesz, hanem sok, 2) a számlálás feltétel nélküli.

#include <stdio.h>

int main(void) {
    int t[10];

    for (int i = 1; i <= 10; i += 1)        /* nullazas */
        t[i - 1] = 0;

    printf("Irj be 1 es 10 kozotti szamokat, aztan valamit, ami nem szam!\n");
    /* amig sikerul szamot beolvasni */
    int szam;
    while (scanf("%d", &szam) == 1) {
        if (szam >= 1 && szam <= 10)
            t[szam - 1] += 1;
        else
            printf("1 es 10 kozotti szamokat adj meg!\n");
    }

    for (int i = 1; i <= 10; i += 1)        /* kiiras */
        printf("%d: %d\n", i, t[i - 1]);

    return 0;
}

A scanf() a beolvasott számokon kívül is ad egy számot vissza. Ezt ellenőrizve megtudhatjuk, hogy hány konverzió sikerült. A lenti kódban egy konverzió van (%d, egy szám); ha az sikerül, akkor a scanf() értéke 1 lesz. Vagyis a ciklus addig fut, amíg van beolvasott szám. Ha betűkkel találkozik, ez az érték 0 lesz: így jelzi, hogy bár lenne mit beolvasni, de az nem értelmezhető számként. Fájl vége jelnél a kapott érték az EOF konstanssal egyezik meg, mivel nincs már beolvasott szám. Írhatunk is ilyet: while (scanf("%c", &c) != EOF).

A megoldás terve

A megoldás menete adja magát: az algoritmus adott, csak le kell kódolni. Az adattárolás módját kell csak meghatároznunk: hogyan tároljuk el azt, hogy ki lett-e húzva már egy szám, vagy nem?

Az adatszerkezetről. A tömb elemei itt logikai értékek. A tömböt pedig mindig magával a számmal indexeljük; prim[2] pl. azt tárolja, hogy a 2 prímszám-e. Az első két elemet így ugyan nem használjuk, de a program egyszerűbb, mert a tömbindex megegyezik magával a számmal. (Lehetne úgy is, mint a statisztikás feladatban.) A prim[1000] méretű tömbben így 999-ig lehet megkeresni a prímeket.

Az algoritmus futása után tehát a tömbünk így néz ki:

Az első két helyen (0, 1 indexek) az igaz érték változatlan maradt; a 4, 6, 8, 9, … helyekre pedig az algoritmus hamis értékeket tett, mert nem prímszámok.

A kereső ciklust egyébként elég lenne a táblázat méretének gyökéig futtatni, mert az afölötti osztóknak azalatti párja is van (pl. 1000-nél 2×500, 4×250 és így tovább).

Ha megvan az adatszerkezet, egy adott szám vizsgálatához nem kell mást tenni, ki kell csak olvasni az eredményt a táblázatból: prim[x].

#include <stdio.h>
#include <stdbool.h>

int main(void) {
    bool prim[1000];

    /* uresen indulunk - mindent primszamnak tekintunk */
    for (int sz = 0; sz < 1000; sz += 1)
        prim[sz] = true;

    /* a szita */
    for (int sz = 2; sz < 1000; sz += 1) {    /* megyunk a szitan */
        if (prim[sz]) {                 /* es amit talalunk primet */
            for (int t = sz*2; t < 1000; t += sz)
                prim[t] = false;
        }
    }
    
    /* vegeredmeny kiirasa */
    for (int sz = 2; sz < 1000; sz += 1)
        if (prim[sz])                   /* amiknel megmarad a jeloles */
            printf("%d ", sz);
    printf("\n");
    
    /* adott szam vizsgalata */
    printf("Adj egy szamot! ");
    int x;
    scanf("%d", &x);
    if (prim[x])
        printf("%d primszam.\n", x);
    else
        printf("%d nem primszam.\n", x);

    return 0;
}

A többszörösök kihúzására ilyen ciklus is elképzelhető:

for (int szorzo = 2; i * szorzo < 1000; szorzo += 1)
    prim[i * szorzo] = false;   /* a tobbszorosei nem primek. */

A megoldásban csökkenő sorrendben vizsgáljuk a címleteket, és mindegyikből kiadunk annyit, amennyit csak lehet. A csökkenő sorrendet úgy állítjuk elő, hogy a tömböt, amely a címleteket tartalmazza, eleve csökkenő sorrendbe rendezve építjük be a programba. Ez egy ún. mohó algoritmus – mindig a legnagyobbat próbálja lépni a megoldás felé.

#include <stdio.h>

int main(void) {
    /* nullaval jelzem a tomb veget */
    int penzek[] = {20000, 10000, 5000, 2000, 1000, 500,
                    200, 100, 50, 20, 10, 5, 0};
    int mennyit;
    printf("Mennyi a visszajaro? ");
    scanf("%d", &mennyit);

    printf("Az automata kiadja:\n");
    /* feltetelezzuk, hogy a tombben csokkeno sorrendben vannak
       benne a bankjegyek. eloszor a legnagyobbol probalunk adni. */
    for (int i = 0; penzek[i] != 0; i += 1) {
        int db = mennyit/penzek[i];
        if (db > 0) {
            printf("%d db %d Ft-os.\n", db, penzek[i]);
            /* a darabot visszaszorozva megvan az osszeg,
               amit kiadtunk ebben a lepesben */
            mennyit -= db*penzek[i];
        }
    }
    if (mennyit != 0)
        printf("Nincs mar ilyen kicsi erme: %d Ft\n", mennyit);
    return 0;
}

Egy tömbről általában nekünk kell megjegyeznünk a méretét, vagyis hogy hány elemet tartalmaz. Itt azonban nincs erre szükség. A tömb utolsó eleme egy nullás szám, az jelöli meg a végét. A ciklus futási feltétele penzek[i] != 0, amelyben nem szerepel a tömb mérete. Azért tudjuk ezt megtenni, mert a nulla ebben a tömbben értelmetlen adat: nincs nulla forintos címlet. Ugyanígy a −1 is jó lenne, vagy bármi, amit az értékes adatoktól meg tudunk különböztetni.

A mennyit/penzek[i] kifejezés értéke egy egész szám, pl. 2100/1000=2. Az egész/egész osztás C-ben egész számot eredményez! Ezt ki is használjuk a programban. Csinálhatnánk úgy is, hogy az adott címletet egyesével vonogatjuk le az összegből, amíg lehet, és számláljuk, hányszor sikerült – de így sokkal egyszerűbb.