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 ellipszis 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:

while (F) {
    M;
}

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.

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

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.

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

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

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.

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.