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

Czirkos Zoltán · 2016.08.28.

Programozási tételek használata az algoritmusokban. Tömbök létrehozása és kezelése.

Ez a gyakorlati óra a sorozatok témaköréhez kapcsolódik. Az egyes feladatoknál gondoljuk át a következőket:

  • Melyik programozási tételt (számlálás, eldöntés stb.) alkalmazzuk és miért?
  • Tömböknél: mit tárolunk és miért? Hogyan szervezzük a tárolást? Mekkora a tömb mérete, mi a legalsó és legfelső tömbindex jelentése?

Felkészülés a gyakorlatra:

1. Statisztika a számokról

1: 5 db
2: 3 db
3: 4 db
...

Írjunk programot, amelyik a szabványos bemenetről olvas számokat, ameddig csak tud. Számolja meg, hogy a beírt számok közül, amelyek 1 és 10 között vannak, melyik hányszor szerepelt! Írja ki ezt a szabványos kimenetre az oldalt látható formában!

Megoldás

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.
SzámSzámlálóÉrték
1t[0]5 db
2t[1]3 db
3t[2]4 db
xt[x-1]...

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 kialakuló 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], i;

    for (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) {       /* feldolgozas */
        if (szam >= 1 && szam <= 10)
            t[szam-1] += 1;
        else
            printf("1 es 10 kozotti szamokat adj meg!\n");
    }

    for (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 „fájl vége jel” fogalma az első laboron szerepelt.)

2. Eratoszthenész szitája

     2  3  4  5
  6  7  8  9 10
 11 12 13 14 15
 16 17 18 19 20
 21 22 23 24 25

Eratoszthenész szitája prímszámokat keres. A módszer a következő. Felírjuk a számokat valameddig. 2 prímszám, ezt megjegyezzük. Kihúzzuk a többszöröseit, mivel azok nem prímszámok. Ezután 3 a következő, ami még nincs kihúzva. Az is prímszám, mivel nem találtunk ezidáig osztót hozzá: a nála kisebb összes szám többszöröseit kihúztuk, nála nagyobb osztója pedig nem lehet. A többszörösei viszont nem prímek: kihúzzuk az összes 3-mal oszthatót. 4-et már kihúztuk (2×2). 5 a következő prím, kihúzzuk n×5-öt stb. Írjuk ki ez alapján a prímszámokat 999-ig!

Megoldás

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:

01234567891011
iiiihihihhh i

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

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

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

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

    /* a szita */
    for (sz = 2; sz < 1000; sz += 1) {    /* megyunk a szitan */
        if (prim[sz]) {                 /* es amit talalunk primet */
            for (t = sz*2; t < 1000; t += sz)
                prim[t] = false;
        }
    }
    
    /* vegeredmeny kiirasa */
    for (sz = 2; sz < 1000; sz += 1)
        if (prim[sz])                   /* amiknel megmarad a jeloles */
            printf("%d ", sz);
    printf("\n");

    return 0;
}

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

int szorzo;

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

A megtalált prímeket már a keresés közben is kiírhatnánk.

3. Az év napja

Írjunk programot, amely megkérdezi a felhasználótól egy hónap számát (pl. 3 = március), és utána kiírja, hány napos az a hónap!

Megoldás

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

01234567891011
312831303130313130313031

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

Írjunk programot, amelyik egy adott dátumról (év, hónap, nap) kiírja, hogy az év hányadik napja! Az év paraméterre a szökőévek miatt van szükség. Szökőév minden negyedik, nem szökőév minden századik, de szökőév minden 400-adik. 2000-ben ezért volt szökőév.

Megoldás

#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};
    /* segedvaltozok */
    int hanyadik, i;
    bool szokoev;
    /* ehhez fogja kiszamolni a napot */
    int ev = 2017, honap = 5, nap = 30;

    /* 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. */
    hanyadik = 0;
    for (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 */
    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;
}

4. Bankautomata

Pénzvisszaadós automatába kell egy olyan programrészt írnunk, amelyik a visszajárót számolja ki. Írjunk egy programrészt, amely egy adott pénzösszegről kiírja, hogy hogyan lehet azt a legkevesebb papírdarabbal/fémkoronggal kiadni!
Például: 1415 Ft = 1000 Ft + 2×200 Ft + 10 Ft + 5 Ft.

Megoldás

A megoldásban csökkenő sorrendben vizsgáljuk a címleteket, és mindegyikből kiadunk annyit, amennyit 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, i;

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

5. További feladatok