Ismétléses vezérlés

Ismétléses vezérlések

Ha egy adott feltétel szerint egy műveletsort végrehajtását többször megismételjük, akkor ismétléses vezérlésről beszélünk. az ismétlési feltétel szerint ötféle ismétléses vezérlést különböztetünk meg:

• kezdőfeltételes,
• végfeltételes,
• számlálásos,
• hurok,
• diszkrét.

Az algoritmustervezés során a leginkább megfelelő ismétléses vezérlési formát használjuk, függetlenül attól, hogy a megvalósításra használt programozási nyelvben közvetlenül megvalósítható-e ez a vezérlési mód. Az ismétléses vezérlés képzését ciklusszervezésnek is nevezik, így az ismétlésben szereplő műveletet ciklusmagnak hívjuk.

Kezdőfeltételes ismétléses vezérlés

Kezdőfeltételes vezérlésről akkor beszélünk, ha a ciklusmag (ismételt) végrehajtását egy belépési (ismétlési) feltételhez kötjük.

Legyen F logikai kifejezés, M pedig tetszőleges művelet. Az F ismétlési feltételből és az M műveletből (a ciklusmagból) képzett kezdőfeltételes ismétléses vezérlés a következő vezérlési előírást jelenti:

1. Értékeljük ki az F feltételt és folytassuk a 2.) lépéssel.
2. Ha F értéke hamis, akkor az ismétlés és ezzel együtt az összetett művelet végrehajtása befejeződött.
3. Egyébként, vagyis ha az F értéke igaz, akkor hajtsuk végre az M műveletet, majd folytassuk az 1.) lépéssel.

Az ismétléses vezérléseket tartalmazó folyamatábrák jellemzője, hogy az ismétlés a gráfban egy körként jelentkezik. Amennyiben az F értéke kezdetben hamis, az M egyszer sem kerül végrehajtásra. Illetve ha az F kezdetben igaz, de M-nek nincs semilyen ráhatása az F feltételre, akkor végtelen ciklust kapunk, azaz az ismétlést sosem tudjuk befejezni.

A szerkezeti ábrán az ismétlés jelölésére valamilyen elipszis alakzatot használunk, amelybe beleírjuk azt a feltételt, amitől függ a ciklusmag újbóli végrehajtása:

A kezdőfeltételes ismétlés megvalósítására a while utasítás való a C nyelven. Ennek szintaxisa:

Ezzel a fenti kezdőfeltételes ismétlés megvalósítása:

while (F) {
    M;
}

Példa: számsorozat jellemzői

• Problémafelvetés:

  • A globális felmelegedés a nyakunkon van, ez egyre inkább érezhető. Vannak viszont, akiknek ez az "érzés" nem elegendő, csak a bizonyítékoknak hisznek. (És vannak, akik azoknak sem, de az már messze vezet.) A meteorológusok a több, mint száz éve rendszeresen naponta többször mért adatokból szeretnének statisztikákat összeállítani, amik a napi, heti, havi, negyedéves minimum, maximum és átlaghőmérsékleteket mutatják, hogy ezek változásával mutassák ki a jellemző trendeket. Egy-egy ilyen adathármas előállításához sok-sok (adott intervallumba eső) hőmérsékleti értéket kell feldolgozni, ezért ehhez számítógépes segítséget kérnek.
  • Kellene egy program, amely meghatározza egy valós számsorozat legkisebb és legnagyobb elemét, valamint a sorozat átlagát!

• Specifikáció:

  • A probléma inputja egy valós számokból álló sorozat.
  • Az input számsorozat végét egy végjel fogja jelezni, amit a felhasználó ad meg inputként, nyilván a számsorozat előtt.
  • Az output a sorozat legkisebb és legnagyobb eleme, valamint az átlaga.

• Algoritmustervezés első megközelítés:

  • Elsőre talán az tűnne a legegyszerűbb megoldásnak, ha beolvasnánk az összes számot, majd ezek között megkeresnénk a legkisebbet, legnagyobbat, majd kiszámolnánk az átlagot.
  • De hogyan is működne a három részalgoritmus?
    • Legyen kezdetben a minimum az első elem.
    • Vizsgáljuk sorban a sorozat elemeit. Ha a vizsgált elem kisebb a minimumnál, akkor ez lesz az új minimum. Az összes elem feldolgozása után a minimum a teljes sorozat minimuma lesz.
  • A maximális elem keresése ehhez teljesen hasonlóan megy.
  • Az átlagszámításhoz össze kell adni a sorozat összes elemét, majd a végén el kell osztani a sorozat elemeinek számával.
    • Legyen az osszeg és az elemszam kezdetben nulla.
    • Vizsgáljuk sorban a sorozat elemeit. Minden elemnél az elem értékét adjuk hozzá az osszeghez, és növeljük eggyel az elemszamot.

• Algoritmustervezés második megközelítés:

  • Ha végiggondoljuk, a három részalgoritmus összevonható.
  • soron következő elem feldolgozásával ki tudjuk számolni az eddigi sorozat minimumát, maximumát, összegét és elemszámát.
  • Ha ezt megtettük, a sorozat ezen elemére nincs többé szükség, azt nem kell eltárolni. Ennek előnye, hogy nem kell egy plusz adatszerkezetben (tömbben) eltárolni a sok-sok adatot, illetve olyan esetben is működik az algoritmus, amikor olyan sok adat van, ami már a memória kapacitását megterhelné.

• Algoritmustervezés szerkezeti ábrával:

/* Határozzuk meg egy valós számsorozat legkisebb
 * és legnagyobb elemét, valamint a sorozat átlagát!
 * 1997. Október 25.  Dévényi Károly, devenyi@inf.u-szeged.hu
 */

#include <stdio.h>

int main() {
    double vegjel, szam, osszeg, min, max, atlag;
    int db;                                 /* az összegzett elemek száma */

    printf("Ez a program valós számsorozat minimális,\n");
    printf("maximális elemét és átlagát számolja.\n");
    printf("Az input sorozatot végjel zárja.\n");
    printf("Kérem a végjelet!\n");                       /* inicializálás */
    scanf("%lf", &vegjel);
    printf("Kérem az input számsorozatot!\n");
    printf("? ");
    scanf("%lf", &szam);
    min = max = szam;
    osszeg = 0.0;
    db = 0;

    while (szam != vegjel) {                          /* a ciklus kezdete */
        osszeg += szam;                                      /* összegzés */
        ++db;                                         /* számláló növelés */

        if (szam < min) {                             /* min-max számítás */
            min = szam;
        } else if (szam > max) {
            max = szam;
        }
                                           /* a következő szám beolvasása */
        printf("? ");
        scanf("%lf", &szam);
    }                                                    /* a ciklus vége */

    if (db == 0) {
        printf("Üres számsorozat érkezett.\n");
    } else {
        atlag = osszeg / db;
        printf("Minimum  = %10.3f Maximum = %10.3f\n", min, max);
        printf("Az átlag = %10.3f\n", atlag);
    }
    return 0;
}

Bár maga a program implementálása a szerkezeti ábra alapján egyértelmű, magába a megvalósításba kerültek olyan részletek, amikről eddig nem volt szó. Ilyenek a 25-26. sorok utasításai. Nézzük meg ezeket alaposabban!

Az osszeg változóban tároljuk a már beolvasott számsorozat hosszát, a db változóban a számsorozat beolvasott elemeinek számát. Mind a kettő változót 0-ra inicializáltuk (21-22. sorok). (Mivel az osszeg valós típusú, így érdemes az inicializálásnál úgy megadni a 0 értéket, hogy annak számformátuma is valós legyen. Persze erről már volt szó.)

A 25. sor feladata, hogy növelje az osszeg változó értékét a cikluson belül az éppen aktuálisan feldolgozandó elem értékével. Ezt megtehetnénk az osszeg = osszeg + szam; utasítással is. Azonban az osszeg += szam; ugyanezt csinálja, tömörebb formában.

C-ben azokat az értékadó kifejezéseket, amik v = v ☉ e alakúak, azokat írhatjuk v ☉ = e alakban is.
Azaz például:

x = 5; x += 2; x == 7;
x = 5; x -= 2; x == 3;
x = 5; x *= 2; x == 10;
x = 5; x /= 2; x == 2;
x = 5; x %= 2; x == 1;

Magának az értékadó kifejezésnek az értéke a kiszámolt új érték lesz. Mivel kifejezés (nem utasítás), így elképzelhető, hogy maga az értékadó kifejezés egy másik kifejezésnek csak a része lesz.

A program 20. sorában csak szimpla értékadásokkal találkozunk ugyan (min = max = szam;), de látszódik, hogy egyik értékadásnak a másik része lesz. Mivel értéket mindig a bal oldalon álló kifejezésnek adunk, így szükséges, hogy előbb a jobb oldali kifejezés értékelődjön ki hamarabb, éppen ezért az értékadás jobb-asszociatív művelet lesz.

A 26. sornak a feladata, hogy az adott ciklusban a db változó értékét 1-gyel növelje, azaz a sor egyenértékű látszólag a db = db + 1, vagy db += 1 utasítással. Ilyen esetekben, amikor egy változó értékét 1-gye l szeretnénk növelni (csökkenteni), akkor használhatjuk az úgynevezett inkrementáló (dekrementáló) műveleteket. Ezek használhatóak prefix (azaz az adott változó előtt, pl.: ++i), vagy postfix (azaz az adott változó mögött, pl.: i--) alakban is. Prefix alakban a művelet, mint kifejezés értéke az operandus új értéke lesz, postfix alakban a művelet mint kifejezés értéke az operandus régi értéke lesz (de az operandus értéke a művelet után az új, módosított érték lesz). A prefix és postfix használat között akkor van különbség, ha nem csak a művelet inkrementáló/dekrementáló tulajdonságát, hanem a kifejezés értékét is felhasználjuk.

Ha az i kezdeti értéke 5, akkor az x = ++ikifejezésben az x értéke i új értéke, azaz 6 lesz. Az x=i++ kifejezésben azonban x az i eredeti értékét kapja, azaz 5 lesz az érték, és i értéke lesz csak 6.

Tip

A C szabvány szerint az aritmetikai részkifejezések kiértékelésének sorrendje tetszőleges.
Ha i értéke kezdetben 7, akkor a i--*i++ kifejezés értéke mi lesz?
Ha előbb a bal oldal értékelődik ki, akkor i értéke 6 lesz, és még ki kell még értékelni a 7*i++ kifejezést. Így a kifejezés értéke 42 lesz.
Ha előbb a jobb oldal értékelődik ki, akkor i értéke 8 lesz, és még ki kell értékelni a i--*7 kifejezést. Ezt befejezve 56-ot kapunk.
Bár van olyan gcc implementáció, ahol többféle optimalizálás után a 49-es eredmény is előfordul.

Fontos, hogy inkrementáló, dekrementáló művelet csak kizárólag úgynevezett l-value változókra alkalmazható, mint ahogy az értékadó kifejezések bal oldalán levő kifejezés is csak ilyen elem lehet, hisz maga az l-value, azaz "bal-érték" elnevezés is innen jön: olyan érték, ami értékadás bal oldalán állhat.

Az utolsó kis újdonság a programban a számsorozat jellemzőinek kiíratásakor látható: itt a %lf egészült ki. A %10.3f segítségével úgy tudjuk megjeleníteni a valós számot, hogy az 10 karakter hosszon lesz leírva, és 3 tizedes jegyet látunk belőle. Hogy pontosan mi mindent lehet még megoldani a formátum jelölők segítségével, azt a későbbiekben még pontosítjuk.

Végfeltételes ismétléses vezérlés

Elképzelhető, hogy nem azt kell tesztelnünk, hogy egy adott ciklust adott feltétel szerint újra és újra kiértékeljünk, hanem akkor kell azt megismételnünk, amíg a ciklus végrehajtása nem ér el egy kívánt feltételt. Azaz a ciklusmag elhagyását egy kilépési feltételhez kötjük.

Legyen F egy logikai kifejezés, M pedig tetszőleges művelet. Az F kilépési feltételből és az M műveletből (ciklusmagból) képzett végfeltételes ismétléses vezérlés a következő vezérlési előírást jelenti:

1. Hajtsuk végre az M műveletet majd folytassuk a 2.) lépéssel.
2. Értékeljük ki az F feltételt és folytassuk a 3.) lépéssel.
3. Ha F értéke igaz, akkor az ismétléses vezérlés és ezzel együtt az összetett művelet végrehajtása befejeződött.
4. Egyébként, vagyis ha az F értéke hamis, akkor folytassuk az 1.) lépéssel.

A leírás alapján a végfeltételes vezérlés folyamatábrája:

Ha az F értéke kezdetben hamis, és az M műveletnek nincs hatása az F-re, akkor végtelen ciklust kapunk. Független F kezdeti értékétől azonban az M művelet legalább egyszer végrehajtásra kerül.

A végfeltételes vezérlés szerkezeti ábráján a feltétel egy fél ellipszisbe van zárva. Ezzel tér el a kezdőfeltételes vezérlés szerkezeti ábrájától, ez jelzi, hogy itt kicsit azért másról van szó.

Jobban belegondolva a kezdő- és végfeltételes ismétléses vezérlések működésébe könnyen láthatjuk, hogy minden kezdőfeltételes vezérlés átírható végfeltételessé, és minden végfeltételes átírható kezdőfeltételessé.

Ami megkülönbözteti a két vezérlést az az, hogy kezdőfeltételes ismétlés esetén a ciklusmag első végrehajtása is függ a feltételtől, míg végfeltételesnél a ciklusmag legalább egyszer lefut, és csak az ismétlődések számát határozza meg a feltétel. Az algoritmus tervezésekor előfordulhat, hogy a kezdő- és végfeltételes vezérlés is alkalmasnak látszik a probléma megoldására. Ilyenkor érdemes megvizsgálni, hogy az F feltétel szükséges feltétele-e az M művelet végrehajtásának? Ha igen, akkor kezdőfeltételes ismétléses vezérlést kell választani.

A végfeltételes vezérlést a C nyelvben a do while utasítással tudjuk megvalósítani:

Mivel ez az utasítás nem blokkal záródik, így fontos, hogy itt ki kell tenni az utasítás végét jelentő ;-t. A szemantikája a C megvalósításnak annyival tér el a végfeltételes ismétlés formális megfogalmazásától, hogy az ismétlés addig tart, amíg a kifejezés igaz, amint hamissá válik, a ciklusmag újból nem kerül végrehajtásra.

Ennélfogva a C megvalósításakor a fenti szerkezeti ábrával adott végfeltételes vezérlésnek a feltétel tagadását kell tartalmaznia a while utáni kifejezésben:

do {
    M;
} while (!F);

Példa: \(sin(x)\) kiszámítása

• Problémafelvetés: Egy processzorgyártó cég az elhíresült Pentium FDIV bug óta különös figyelmet szentel a processzorok működésének átfogó tesztelésére. Jelenleg éppen a trigonometrikus számításokat ellenőrzik. Ezt úgy próbálják megtenni, hogy a \(sin(x)\) értékét az alapvető műveletekkel kiszámoltatják (adott pontosságon), és ezt majd összehasonlítják a dedikáltan ilyen számításokat végző műveletek eredményével. Ehhez kellene egy olyan program, ami képes kiszámolni a \(sin(x)\) közelítő értékét a 4 matematikai alapművelet segítségével, a processzorba épített trigonometrikus képességek használata nélkül.
• Specifikáció:
  • A probléma inputja egy \(x\) valós szám.
  • Az output a \(sin(x)\) közelítő értéke.
  • Az eredményt \(10^{-10}\) pontossággal kell kiszámítani.
  • A szinusz kiszámításához nem használhatjuk a beépített trigonometrikus függvényeket

• Algoritmustervezés

  • Ismeretes, hogy
  \[sin(x) = \sum_{i=0}^{\infty} -1^i \frac{x^{(2i+1)}}{(2i + 1)!}\]

  a \(sin(x)\) értéke közelíthető ezen sor egy véges kezdőszeletével. Aki ezt nem tudta eddig, az csak fogadja el ezt az alapfeltevést.

  • Akármekkora legyen is a sorfejtés következő tagja, az \(\frac{x-1}{2}\)-dik tag után a további tagok értéke monoton csökkenő lesz. Mivel alternáló összegről van szó, ha a következő tag értéke kisebb az elvárt pontosságnál, biztosak lehetünk benne, hogy \(sin(x)\) értékét legalább ilyen pontossággal megközelítettük, tehát befejezhetjük a számolást.
  • Nyilvánvalóan nem célszerű az összes tagot egyedileg kiszámolni, hiszen a következő tag viszonylag egyszerűen számolható az előzőből, és még időt is spórolunk az előző érték felhasználásával.
  • Ráadásul a tag számlálójának és nevezőjének külön számolása még pontatlanná is tenné a számítást, mert mindkettő gyorsan növekszik \(i\) függvényében.
  • A valós típus pontatlansága miatt még így is figyelni kell arra, hogy ne legyen túl nagy eltérés a számolás egyes részeredményei között. Ezt elérhetjük úgy, hogy kihasználva a szinusz periodikusságát, a lehető legkisebb abszolút értékű \(x\)-re számoljuk ki a \(sin(x)\) értékét úgy, hogy az eredeti érték szinuszával megegyező eredményt kapjuk.
  • Algoritmustervezés szerkezeti ábrákkal
  • A főprogram:
  • Inicializálás

/* sin(x) közelítő értékének kiszámítása a beépített sin(x)
 *   függvény alkalmazása nélkül.
 *   x értékét transzformáljuk a (-Pi,Pi) intervallumba.
 * 1997. Október 25.  Dévényi Károly, devenyi@inf.u-szeged.hu
 */

#include <stdio.h>
#include <math.h>

#define EPSZ    1e-10                           /* a közelítés pontossága */

int main() {
    double osszeg;                         /* a végtelen sor kezdőösszege */
    double tag;                          /* a végtelen sor aktuális tagja */
    double x;                                               /* argumentum */
    double x_orig;                    /* az argumentum értékének megőrzése*/
    double xx;                                                  /* sqr(x) */
    int j;                                     /* a nevező kiszámításához */

    printf("Kérem sin(x)-hez az argumentumot\n");
    scanf("%lg%*[^\n]", &x); getchar();            /* sor végéig olvasunk */
    x_orig = x;

    while (x < -M_PI) {                                 /* transzformálás */
        x += 2 * M_PI;
    }
    while (M_PI < x) {
        x -= 2 * M_PI;
    }

    osszeg = 0.0;
    j      = 2;                                          /* inicializálás */
    tag    = x;
    xx     = x * x;

    do {                                                /* ciklus kezdete */
        osszeg += tag;
        tag = -(tag * xx / j / (j + 1));                 /* következő tag */
        j += 2;
    } while (fabs(tag) >= EPSZ);              /* végfeltétel, ciklus vége */

    printf("sin(%8.5f)= %13.10f\n", x_orig, osszeg);
    return 0;
}

A kód egyik "újdonsága", hogy a forrás elején include-oljuk a math.h headert. Erre azért van szükség, mert a programkódban hivatkozni fogunk az M_PI konstants, amit hasonlóan definiál a math.h, mint mi az EPSZ konstanst a #define EPSZ 1e-10 sorban. Már láttunk makróra példát a minimax függvény esetében, ami ennél egy kicsit bonyolultabb volt. Ebben az esetben annyi történik, hogy ezen sor után minden helyen, ahol a proprocesszor az EPSZ szóval találkozik, kicseréli azt a 1e-10 valós literálra, ami egy nagyon kicsi értéket reprezentál. Ez lesz az az érték, aminél ha egy tag kisebb lesz, nem folytatjuk tovább a \(sin(x)\) sorfejtését.

Másik újdonsága a kódnak a 21. sor adatbeolvasása. Itt a scanf látszólag két értéket szeretne beolvasni, de csak egy változót ad a paraméterlistában. A %*[^\n]formátumleíróban a csillag az mondja, hogy a soron következő adatokat a scanf csak olvassa el, de ne tárolja el. A szögletes zárójelek között azt tudjuk megadni, hogy mik azok a karakterek, amiket olvasni kell. A ^ jel egy tagadást jelöl, a \n pedig egy sortörést, így ez azt jelenti, hogy minden karaktert be kell olvasni, ami különbözik a sortöréstől. A beolvasás addig tart, amíg egy sortörést nem olvasunk, ezt a scanf már nem olvassa be. Éppen ezért kell még egy getchar művelet, ami majd ezt is beolvassa, így könnyítve a következő beolvasás mintaillesztését.

A 40. sorban használt fabs függvényt a matematikai függvénykönyvtár definiálja, a M_PI mellett ezt is a math.h include-olásával használhatjuk. Ahhoz, hogy a végső bináris állományban a linker ezt a függvényhívást a megfelelő függvényre rá tudja irányítani az szükséges, hogy a a fordítási parancssorban a -lm kapcsolót is megadjuk (a -l utal arra, hogy a linkernek szól a kapcsoló, az m betű pedig arra, hogy a statikus matematikai könyvtárat kell linkelni).

Tip

Bár látszólag teljesen felesleges az xx változó felvétele abból a célból, hogy abban eltároljuk x*x értékét, mégis ez egy hasznos dolog, hiszen ha ezt a számítást ciklusmagon belül mindig újra is újra megismételnénk, azzal rontanánk a kódunk futásidejét. Az olyan számításokat, amik eredménye konstans a program egy adott futásában, érdemes cikluson kívül meghatározni.

Számlálásos ismétléses vezérlések

Számlálásos ismétléses vezérlésről akkor beszélünk, ha a ciklusmagot végre kell hajtani egy változó sorban minden olyan értékére (növekvő vagy csökkenő sorrendben), amely egy adott intervallumba esik.

Legyen a és b egész érték, i egész típusú változó, M pedig tetszőleges művelet, amelynek nincs hatása a,b és i értékére.

Az a és b határértékekből, i ciklusváltozóból és M műveletből (ciklusmagból) képzett növekvő számlálásos ismétléses vezérlés az alábbi vezérlési előírást jelenti:

1. Legyen i=a és folytassuk a 2.) lépéssel.
2. Ha b < i, akkor az ismétlés és ezzel együtt az összetett művelet végrehajtása befejeződött.
3. Egyébként, vagyis ha i <= b, akkor hajtsuk végre az M műveletet, majd folytassuk a 4.) lépéssel.
4. Növeljük i értékét 1-gyel, és folytassuk a 2.) lépéssel.

Az a és b határértékekből, i ciklusváltozóból és M műveletből (ciklusmagból) képzett csökkenő számlálásos ismétléses vezérlés** az alábbi vezérlési előírást jelenti:

1. Legyen i=b és folytassuk a 2.) lépéssel.
2. Ha i < a, akkor az ismétlés és ezzel együtt az összetett művelet végrehajtása befejeződött.
3. Egyébként, vagyis ha a <= i, akkor hajtsuk végre az M műveletet, majd folytassuk a 4.) lépéssel.
4. Csökkentsüki értékét 1-gyel, és folytassuk a 2.) lépéssel.

A növekvő számlálásos ismétlés folyamatábrája:

A csökkenő számlálásos ismétlés folyamatábrája:

Azaz mindkét vezérlésben először meg kell határozzuk a vezérlést meghatározó intervallum alsó és felső határát, majd inicializálnunk kell a ciklusváltozót, amely a növekvő számlálás esetében a kisebb, növekvő esetben a nagyobb határ érték.

A ciklusváltozó értékétől függ, hogy a ciklusmag végrehajtásra kerül-e. Növekvő számlálásnál azt vizsgáljuk, hogy a ciklusváltozó meghaladta-e már a ciklus felső határértékét, csökkenő esetben pedig azt vizsgáljuk, hogy a ciklusváltozó kisebb-e, mint az alsó határ értéke. A ciklusmag végrehajtása után növekvő esetben 1-gyel növeljük, míg csökkenő esetben csökkentjük a ciklusváltozó értékét.

Mivel ismétléses vezérlésekről van szó, így az ismétlést a szerkezeti ábrán jelezzük a szokásos ellipszis formával, illetve megadjuk egy nyíl segítségével, hogy a ciklusváltozó milyen irányban változik, és milyen határok között. Így a növekvő ismétléses vezérlés szerkezeti ábrája:

A csökkenő ismétléses vezérlés szerkezeti ábrája:

A határértékek alapján mindkét vezérlésnél előfordulhat, hogy az M műveletet egyszer sem hajtjuk végre.

Ha valamilyen műveletet sorban több értékére is végre kell hajtani, akkor a for utasítás (is) használható. C-ben a for utasítás szintaxisa:

C-ben a for utasítás általános alakja így néz ki: for(kif_1; kif_2; kif_3) utasítás;, ami egyenértékű a következő kóddal:

kif_1;
while (kif_2) {
    utasítás;
    kif_3;
}

A kif_1 és kif_3 többnyire értékadás vagy függvényhívás, kif_2 pedig relációs kifejezés.

A csökkenő és növekvő ismétléses vezérlés megvalósításán túl a for utasítás sokkal több lehetőséget tartogat. Bármelyik kifejezés elhagyható, de a pontosvesszőnek meg kell maradniuk a for utáni zárójelek között. A kif_2 elhagyása esetén a feltételt konstans igaznak tekintjük, ekkor a break vagy return utasításokkal lehet kiugrani a ciklusból.

Az is előfordulhat, hogy a kif_1 és kif_3 egyszerre több utasításból, azaz egész pontosan több egymás után (szekvenciálisan) végrehajtandó utasításból áll, mert például több ciklusváltozót szeretnénk használni. Ilyenkor a , operátor használatával tudjuk ezeket a kifejezéseket összekapcsolni, amely balról jobbra kiértékeli a két részkifejezést, majd a művelet eredménye a jobboldali kifejezés eredménye lesz.

Azaz a

for (kif_11, kif_12, kif_13;
     kif_2;
     kif_31,kif_32) {
    utasítás;     
}

szemantikailag egyenértékű a a következő kóddal:

kif_11; kif_12; kif_13;
while (kif_2) {
   utasítás;
   kif_31;kif_32;
}

Példa: "n alatt a k" kiszámítása

• Problémafelvetés: számítsuk ki "n alatt a k" értékét, azaz a \({n \choose k}\) kifejezést!

• Specifikáció:

  • A probléma bementete két egész szám: \(n\) és \(k\).

  • A probléma kimenete: \({n \choose k} = \frac{n!}{k!(n-k)!}\)

  feltételezve hogy ez értelmezhető \(n\)-re és \(k\)-ra, egyébként 0.

• Algoritmustervezés:

  • Készítsünk \({n \choose k}\) kiszámolására függvényt!

  • A specifikációban megadott képlet használható ugyan, de könnyen belátható, hogy nem célszerű a faktoriálisok számításával kezdeni, hiszen már elég kicsi n érték mellett kifuthatunk a C által ábrázolt egész típusok értékkészletéből.

  • Inkább a fenti képletet alakítsuk át egy kicsit:

  \[{n \choose k} = \frac{n!}{k!(n-k)!} \]
  \[ = \frac{n \cdot (n-1) \cdot \dots \cdot (n-k+1) \cdot (n-k) \cdot \dots \cdot 1}{k \cdot (k-1) \cdot \dots \cdot 1 \cdot (n-k) \cdot \dots \cdot 1} \]
  \[ = \frac{n \cdot (n-1) \cdot \dots \cdot (n-k+1)}{1 \cdot 2 \cdot \dots \cdot k} = \prod_{i=1}^{k} \frac{n-i+1}{i} \]
  • A \({n \choose k}\) értékét számító függvény szerkezeti ábrája:

/* n alatt k értékének kiszámítása egy nemrekurzív függvénnyel
 *   2014. május 7. Gergely Tamás, gertom@inf.u-szeged.hu
 */

unsigned long long int n_alatt_k(int n, int k) {
               /* n alatt k értékének kiszámítása nemrekurzív függvénnyel */
    int i;
    unsigned long long int nak;

    if (n < k || k < 0) {                          /* input adatok jók-e? */
        return 0ull;
    }
    for (i = 1, nak = 1ull; i <= k; ++i) {
        nak = nak * (n - i + 1) / i;
    }
    return nak;
}

Mivel már relatív kicsi n érték esetében is lehet a függvény visszatérési értéke olyan, hogy az túllép az int adattípus értelmezési tartományán, így a függvényünk visszatérési értékének adattípus megválasztásakor erre gondolni kell. Ezért int helyett long long int-et használunk. Mivel biztos nem negatív a visszatérési érték, így az unsigned jelzőt is kitehetjük, ez az előjeltelen módosító azt írja le, hogy az eltárolt adat nem lehet negatív. Mivel így nem kell az előjel bitként használt bitet az előjelre tartogatni, így gyakorlatilag kétszer akkora maximális értéket tudunk kifejezni az adattípussal.

Amikor konstansokat használunk, akkor figyelni kell arra, hogy a konstans adattípusa is megfeleljen annak az adattípusnak, amit az adott változó tárol, így nem kell elkerülhetőtípuskonverzióra késztetni a fordítót. Így ha 0 értékkel térünk vissza, az is legyen 0ull, azaz unsigned long long int, illetve a nak változó inicializálásakor is inicializáljuk azt 1ull-ként sima 1 helyett.

Példa: Pascal háromszög

• Problémafelvetés: rajzoljuk ki a Pascal háromszöget, amelynek pontjai a következőképpen alakulnak:

  

• Specifikáció:

  • A probléma inputja egy n nemnegatív egész szám.
  • Az output n + 1 darab sor piramis szerűen rendezve, rendre a Pascal háromszög sorai.

• Algoritmustervezés: a főprogram feladata a beolvasás, input ellenőrzése, majd a n_alatt_k függvényt alkalmas paraméterekkel aktivizálva a soronkénti kiíratás.

  

/* n alatt k értékének kiszámítása egy nemrekurzív függvénnyel és
 *   az értékek elrendezése a Pascal háromszögben.
 * 1997. Október 31.  Dévényi Károly, devenyi@inf.u-szeged.hu
 * 2013. Augusztus 29. Gergely Tamás, gertom@inf.u-szeged.hu
 * 2020. Július 30. Jász Judit, jasy@inf.u-szeged.hu
 */

#include <stdio.h>

#define SZAMSZ       5                     /* egy szám kiírási szélessége */
#define KEPSZ       80                           /* a képernyő szélessége */

int n_alatt_k(int n, int k) {
               /* n alatt k értékének kiszámítása nemrekurzív függvénnyel */
    int i, nak;

    if (n >= k && k >= 0) {                        /* input adatok jók-e? */
        nak = 1;                                         /* inicializálás */
        for (i = 1; i <= k; ++i)                                /* ciklus */
            nak = nak * (n - i + 1) / i;
    } else {
        nak = 0;
    }
    return nak;
}

int main() {
    int n;                                               /* a sorok száma */
    int i, j;                                           /* ciklusváltozók */

    printf("Kérem a Pascal háromszög sorainak számát\n");
    scanf("%d%*[^\n]", &n); getchar();                       /* beolvasás */
    if (0 <= n && n <= KEPSZ / SZAMSZ - 2) {     /* kifér-e a képernyőre? */
        for (i = 0; i <= n; ++i) {                        
            printf("%*c", KEPSZ / 2 - (i + 1) * SZAMSZ / 2 - 1, ' '); /* pozicionálás */
            for (j = 0; j <= i; ++j) {
                printf("%*d", SZAMSZ, n_alatt_k(i, j));               /* kiíratás */
            }
            putchar('\n');
        }
    } else {                                                /* hibaüzenet */
        printf("%d sor nem fér ki a  képernyőre\n", n);
    }
    return 0;
}

Ebben a feladatban n nem lehet túlságosan nagy (mivel látni fogjuk, hogy már kicsi n esetében is betelik a sor), így nem célunk, hogy túl nagy n_alatt_k értéket adjunk meg, így a jelen implementációban az is jó, ha a függvény "csak" int-ekkel dolgozik.

A program elején a 9-10. sorokban definiálunk két konstanst. A SZAMSZ megadja, hogy egy számot hány karakteren fogunk ábrázolni (ez az elrendezés miatt esztétikai szempontokból lesz fontos, hiszen ha minden szám ugyanannyi karakteren helyezkedik el, akkor a háromszög szépen fog kirajzolódni, független attól, hogy az egyes számok, amik alkotják, hány számjegyből állnak.)
A KEPSZ pedig most legyen 80 karakter, ez egy normál beállítás mellett működő terminál esetében az alapértelmezett sorhossz. Fontos, hogy itt akkora értéket állítsunk be, ami a saját terminálunk egy sorban megjeleníthető karaktereinek száma (vagy annál kisebb érték), a lényeg, hogy egy adott sor kiírása ne csússzon át a következő sorba.

A main program talán egyetlen érdekesebb utasítása talán az az utasítás, ami a pozícionálást végzi.
Nézzük meg ezt alaposabban!
printf("%*c", KEPSZ / 2 - (i + 1) * SZAMSZ / 2 - 1, ' ');

A scanf formátumleíróinak esetében már találkoztunk a * elemmel, ott azt jelentette, hogy valamilyen értéket beolvasunk ugyan, de azt nem tároljuk el semmilyen változóban. A printf esetében azt jelenti, hogy a soron következő kifejezés a paraméterlistában bekerül a csillag helyére. A fenti kiírásban tulajdonképpen annyit csinálunk, hogy egyetlen space karaktert írunk ki, KEPSZ / 2 - (i + 1) * SZAMSZ / 2 - 1 hosszon jobbra igazítva. Ezzel érjük el, hogy az első sorban az egyetlen szám középre kerül, miután annak kiírása a space kiírását követi.

Példa: "n alatt a k" kiszámítása (új megközelítéssel)

• Problémafelvetés: számítsuk ki "n alatt a k" értékét, azaz a \({n \choose k}\) kifejezést!

• Specifikáció:

  • A probléma bementete két egész szám: \(n\) és \(k\).

  • A probléma kimenete: \({n \choose k} = \frac{n!}{k!(n-k)!}\)

feltételezve hogy ez értelmezhető \(n\)-re és \(k\)-ra, egyébként 0.

• Algoritmustervezés: Készítsünk az \({n \choose k}\) kiszámolására egy rekurzív függvényt! Ehhez felhasználjuk, hogy a Pascal háromszög szélén lévő érték 1, a belsejében lévő érték pedig a felette lévő két érték összege:

Ennek megfelelően az n_allat_k szerkezeti ábrája a következőképp módosul:

Ha figyelembe vesszük a return utasítás tulajdonságait, akkor egy kicsit finomíthatunk ezen az ábrán:

Módosítsuk az implementációt ennek megfelelően! Mivel csak az n_alatt_k módosult, így ezt könnyen lecserélhetjük a programban. Általánosan igaz az, hogy egy-egy részalgoritmust érdemes külön függvénybe, eljárásba szervezni, így ha időközben javítanánk azt, sokkal egyszerűbb azt hibamentesen megtenni, ráadásul adott esetben tesztelni is könnyebb a módosítás hatásait.

/* n alatt k értékének kiszámítása egy rekurzív függvénnyel és
 *   az értékek elrendezése a Pascal háromszögben.
 * 1997. Október 31. Dévényi Károly, devenyi@inf.u-szeged.hu
 * 2013. Augusztus 29. Gergely Tamás, gertom@inf.u-szeged.hu
 * 2015. Október 11. Gergely Tamás, gertom@inf.u-szeged.hu
 * 2020. Július 30. Jász Judit, jasy@inf.u-szeged.hu
 */

#include <stdio.h>

#define SZAMSZ       5                     /* egy szám kiírási szélessége */
#define KEPSZ       80                           /* a képernyő szélessége */

int n_alatt_k(int n, int k) {
                  /* n alatt k értékének kiszámítása rekurzív függvénnyel */  
    if (n < k || k < 0) {                          /* input adatok jók-e? */
        return 0;
    }
    if (n <= 1 || n == k || k == 0) {                       /* alapesetek */
        return 1;
    }
    return n_alatt_k(n - 1, k - 1) + n_alatt_k(n - 1, k);   /* rek. hívás */
}

int main() {
    int n;                                               /* a sorok száma */
    int i, j;                                           /* ciklusváltozók */

    printf("Kérem a Pascal háromszög sorainak számát\n");
    scanf("%d%*[^\n]", &n); getchar();                       /* beolvasás */
    if (0 <= n && n <= KEPSZ / SZAMSZ - 2) {     /* kifér-e a képernyőre? */
        for (i = 0; i <= n; ++i) {                       
            printf("%*c", KEPSZ / 2 - (i + 1) * SZAMSZ / 2 - 1, ' ');  /* pozicionálás */
            for (j = 0; j <= i; ++j) {
                printf("%*d", SZAMSZ, n_alatt_k(i, j));               /* kiíratás */
            }
            putchar('\n');
        }
    } else {                                                /* hibaüzenet */
        printf("%d sor nem fér ki a  képernyőre\n", n);
    }
    return 0;
}

Hurok ismétléses vezérlés

Amikor a ciklusmag ismétlését a ciklusmagon belül vezéreljük úgy, hogy a ciklus különböző pontjain adott feltételek teljesülése esetén a ciklus végrehajtását befejezzük, hurok ismétléses vezérlésről beszélünk.

Legyenek \(F_i\) logikai kifejezések, \(K_i\) és \(M_j\) pedig tetszőleges (akár üres) műveletek \(1 \leq i \leq n\) és \(0 \leq j \leq m\) értékekre. Az \(F_i\) kijárati feltételekből, \(K_i\) kijárati műveletekből és az \(M_i\) műveletekből képzett hurok ismétléses vezérlés a következő előírást jelenti:

1. Az ismétléses vezérlés következő végrehajtandó egysége az M0 művelet.
2. Ha a végrehajtandó egység az \(M_j\) művelet, akkor ez végrehajtódik. \(j=n\) esetén folytassuk az 1.) lépéssel, különben pedig az \(F_j+1\) feltétel végrehajtásával a 3.) lépésben.
3. A végrehajtandó egység az \(F_i\) feltétel \(1 \leq i \leq n\) , akkor értékeljük ki. Ha \(F_i\) igaz volt, akkor hajtsuk végre a \(K_i\) műveletet, és fejezzük be a vezérlést. Különben a végrehajtás az \(M_i\) művelettel folytatódik a 2.) lépésben.

A hurok ismétléses vezérlés folyamatábrája:

A hurok ismétléses vezérlés szerkezeti ábrájában az ismétlést csak jelöljük a szokásos ellipszissel, a feltételeket pedig ott jelezzük, amikor azok ellenőrzésre kerülnek. Mivel a feltételek teljesülése esetén a ciklus végrehajtását megszakítjuk, így a jelölésmóddal, melyben a feltétel egy a ciklustól ellenkező irányba mutató háromszög próbáljuk jelezni, hogy a feltételek kijárati feltételei a ciklusnak.

Könnyű látni, hogy a kezdő és végfeltételes ismétlések speciális esetei a hurok ismétléses vezérlésnek:

A C nyelvben nincs olyan vezérlési forma, amellyel közvetlenül megvalósíthatnánk a hurok ismétléses vezérlést, de a kezdőfeltételes ismétléses vezérlés és egyszerű szelekció segítségével kifejezhetjük. Ez a megvalósítás nyelvfüggetlen. A megvalósítás lényege, hogy választunk egy logikai változót (legyen az atovabb), ez lesz az ismétlés feltétele. Továbbá a ciklusmagban a feltételes kijáratokat úgy alakítjuk át, hogyha a feltétel igaz, akkor a hozzá tartozó kijárati művelet végrehajtásra kerül és a tovabb hamis értéket kap, egyébként végrehajtódik a ciklusmag további része.

tovabb = 1;
while (tovabb) {
    M0;
    if (F1) {
        tovabb = 0;
        K1;
    } else {
        M1;
        ....
            if (Fn) {
                tovabb = 0;
                Kn;
            } else {
                Mn;
            }
    }
}

A C nyelvben a ciklusmag folyamatos végrehajtásának megszakítására két utasítás használható:

• break: megszakítja a ciklust, a program végrehajtása a ciklusmag utáni első utasítással folytatódik. Ahogy láttuk, ez az utasítás használható a switch utasításban is, hatására a program végrehajtása a switch utáni első utasítással folytatódik.
• continue: megszakítja a ciklusmag aktuális lefutását, a vezérlés a ciklus feltételének kiértékelésével (while, do while) illetve az inkrementáló kifejezés kiértékelésével (for) folytatódik.

A hurok ismétléses vezérlés így úgy is megvalósítható, hogy használjuk a C nyelv break utasítását. A break utasítás "megtöri" az aktuális ismétléses (vagy mint láttuk, esetkiválasztásos szelekciós) vezérlést, és a vezérlési szerkezet utáni első utasításnál folytatja a programot.

while(1) {
    M0;
    if (F1) {
        K1; break;
    }
    M1;
    ...
    if (Fn) {
        Kn; break;
    }
    Mn;
}

Példa: számsorozat legnagyobb közös osztója

• Problémafelvetés: számítsuk ki pozitív egész számok sorozatának legnagyobb közös osztóját!

• Specifikáció: a probléma inputja egy pozitív egész számokból álló sorozat, melyet a 0 zár, output a számsorozat elemeinek legnagyobb közös osztója.

• Algoritmustervezés: az algoritmus lényege egy olyan ismétléses vezérlés, amely ciklusmagjának egyszeri végrehajtása kiszámítja a már feldolgozott input számsor és a beolvasott következő szám legnagyobb közös osztóját. Ez azt jelenti, hogy minden cikluslépésben ki kell számolnunk két szám legnagyobb közös osztóját. Látható, hogy a ciklusmag ismétlését célszerű a ciklusmagban vezérelni, mert az ismétlés befejeződhet úgy, hogy végére értünk az inputnak, vagy feldolgozott sorozat legnagyobb közös osztója 1.

A fő program szerkezeti ábrája:

Látszik, hogy ahhoz, hogy a teljes programot meg tudjuk oldani, meg kell adjuk, hogyan lehet meghatározni két szám legnagyobb közös osztóját.

• Problémafelvetés: számítsuk ki két nemnegatív egész szám legnagyobb közös osztóját!

• Specifikáció: készítsünk egy függvényt, amelynek inputja két egész szám, outputja pedig a két szám legnagyobb közös osztója!

• Algoritmustervezés: Euklidesz algoritmusát valósítjuk meg, melynek alapja, hogy ha \(a \geq b \gt 0\), akkor \(lnko(a, b) = lnko(a − b, b)\), és \(lnko(a, 0) = a\), vagyis a nagyobbik számból a kisebbiket kivonogatva előbb-utóbb megkapjuk a két eredeti szám legnagyobb közös osztóját. A gyakorlatban az ismételt kivonogatás helyett maradékos osztást alkalmazunk, ami egyetlen lépésben megadja annak az \(a' − b\) kivonásnak az eredményét, amikor \(a' − b \lt b\) teljesül, vagyis b veszi át a nagyobb szám szerepét.

Az eredeti problémának a hurok ismétléses vezérlés részét megvalósíthatjuk a tovabb logikai változó és többszörös szelekció segítségével:

/* Pozitív egész számok legnagyobb közös osztójának meghatározása.
 *   A hurok ismétléses vezérlés megvalósítása ismert szerkezetekkel.
 * 1997. November 7.  Dévényi Károly, devenyi@inf.u-szeged.hu
 * 2006. Augusztus 8.  Gergely Tamás, gertom@inf.u-szeged.hu
 */

#include <stdio.h>

int lnko(int x, int y) {
    /* x és y legnagyobb közös osztójának meghatározása
     * Euklidesz algoritmusával.
     */
    int m;

    while (y != 0) {
        m = x % y;
        x = y;
        y = m;
    }
    return x;
}

int main() {
    int a, b;
    int tovabb;              /* logikai változó a ciklus megvalósításához */

    printf("A program pozitív egész számok legnagyobb\n");
    printf("közös osztóját számítja.\n");
    printf("Kérem a számok sorozatát, amit 0 zár!\n");
    printf("? ");
    scanf("%d%*[^\n]", &a); getchar();

    tovabb = !0;
    while (tovabb) {                           /*  a hurok ciklus kezdete */
        printf("? ");
        scanf("%d%*[^\n]", &b); getchar();

        if (b == 0) {                                     /* első kijárat */
            tovabb = 0;
        } else {
            a = lnko(a, b);
            if (a == 1) {                              /* második kijárat */
                tovabb = 0;
            }
        }
    }                                              /* a hurok ciklus vége */
    printf(" A számok legnagyobb közös osztója: %d\n", a);
    return 0;
}

De használhatjuk a break utasítást is a hurokismétlés megvalósítására:

/* Pozitív egész számok legnagyobb közös osztójának meghatározása.
 *   A hurok ismétléses vezérlés megvalósítása break utasítással.
 * 1997. November 7.  Dévényi Károly, devenyi@inf.u-szeged.hu
 * 2006. Augusztus 8.  Gergely Tamás, gertom@inf.u-szeged.hu
 */

#include <stdio.h>

int lnko(int x, int y) {
    /* x és y legnagyobb közös osztójának meghatározása
     * Euklidesz algoritmusával.
     */
    int m;

    while (y != 0) {
        m = x % y;
        x = y;
        y = m;
    }
    return x;
}

int main() {
    int a, b;

    printf("A program pozitív egész számok legnagyobb\n");
    printf("közös osztóját számítja.\n");
    printf("Kérem a számok sorozatát, amit 0 zár!\n");
    printf("? ");
    scanf("%d%*[^\n]", &a); getchar();

    while (1) {                                 /* a hurok ciklus kezdete */
        printf("? ");
        scanf("%d%*[^\n]", &b); getchar();
        if (b == 0) {                                     /* első kijárat */
            break;
        }
        a = lnko(a, b);
        if (a == 1) {                                  /* második kijárat */
            break;
        }
    }                                              /* a hurok ciklus vége */
    printf(" A számok legnagyobb közös osztója: %d\n", a);
    return 0;
}

Diszkrét ismétléses vezérlés

Diszkrét ismétléses vezérlésről akkor beszélünk, ha a ciklusmagot végre kell hajtani egy halmaz minden elemére tetszőleges sorrendben. Legyen x egy T típusú változó, H a T értékkészletének részhalmaza, M pedig tetszőleges művelet, amelynek nincs hatása x és H értékére. A H halmazból, x ciklusváltozóból és M műveletből (ciklusmagból) képzett diszkrét ismétléses vezérlés az alábbi vezérlési előírást jelenti:

1. Ha a H halmaz minden elemére végrehajtottuk az M műveletet, akkor vége a vezérlésnek.
2. Egyébként vegyük a H halmaz egy olyan tetszőleges e elemét, amelyre még nem hajtottuk végre az M műveletet, és folytassuk a 3.) lépéssel.
3. Legyen x=e és hajtsuk végre az M műveletet, majd folytassuk az 1.) lépéssel.

Mindez folyamatábrával:

A szerkezeti ábra most sem nélkülözi az ellipszist, amivel utalunk az ismétlésre:

Látszik, hogy a H halmaz számossága határozza meg, hogy az M művelet hányszor hajtódik végre. Ha a Haz üres halmaz, akkor a diszkrét ismétléses vezérlés az M művelet végrehajtása nélkül befejeződik.

A diszkrét ismétléses vezérlésnek nincs közvetlen megvalósítása a C nyelvben. A megvalósítás elsősorban attól függ, hogy az ismétlési feltételben megadott halmazt hogyan reprezentáljuk. Algoritmustervezés során szabadon használhatjuk a diszkrét ismétléses vezérlést, ha erre van szükség a probléma megoldásához. A halmaz reprezentálásáról pedig akkor döntünk, amikor elegendő információ áll rendelkezésünkre, hogy a legmegfelelőbbet kiválaszthassuk.

---

Utolsó frissítés: 2023-12-16 10:53:26