10. Ciklas.


Tą patį veiksmą dažnai tenka kartoti daug kartų. Sudarant algoritmus, kartojimo veiksmai išreiškiami ciklu. Ciklas - viena svarbiausių algoritmo konstrukcijų; reta programa gali be jo apsieiti.


Gyvenime labai dažnai tenka susidurti su tokiais veiksmais, kuriuos reikia atlikti daug kartų. Štai ruošiamės kepti bandeles. Minkome tešlą. Minkome tol, kol tešla nebelimpa prie rankų - tą patį veiksmą kartojame daug kartų.
Kitas pavyzdys - tarkim, norime nusipirkti priemiestinio traukinio bilietą. Į automatą turime įmesti tiek monetų, kad jame susikauptų tam tikra pinigų suma. Jei bilietas kainuotų 2 litus, o mes mestume po 20 centų, tai tektų dešimt kartų pakartoti tą patį veiksmą - įmesti monetą.
   

Judesių kartojimas - ciklinis procesas

Ciklinis  procesas.

Veiksmų kartojimas daug kartų vadinamas ciklu. Algoritmai, turintys ciklų, vadinami cikliniais algoritmais. 

Kiek kartų reikia kartoti kokį nors veiksmą, priklauso nuo konkrečių sąlygų. Tešlą minkysime tol, kol nustos lipti prie rankų. Monetas į automatą mesime tol, kol įmestų pinigų suma bus lygi bilieto kainai.
Ciklą sudarantys veiksmai kartojami tol, kol tenkinama jame nurodyta sąlyga.

Ciklas struktūrogramoje(paveikslėlis dešinėje) vaizduojamas kaip stačiakampis stačiakampyje, kurio viršuje nurodoma sąlyga, o vidiniame stačiakampyje - veiksmai, kuriuos reikia kartoti, kol tenkinama sąlyga. Kairiajame viršutiniame kampe užrašoma ciklo rūšis.

Ciklinius algoritmus žodžiais formulavome seniai, nuo pat pirmųjų algoritmavimo pamokų (prisiminkite Eratosteno rėtį). Kartojimo veiksmus esame įpratę daryti, ir jie niekuo nestebina.
Dabar atidžiau panagrinėkime keletą pavyzdžių.

1 pavyzdys.  Du vaikai žaidžia su pagaliukais, paeiliui imdami juos iš dviejų krūvelių. Kiekvienas žaidėjas gali paimti kiek nori pagaliukų iš bet kurios vienos krūvelės (net ir ją visą). Laimi tas, kuris paima paskutinį pagaliuką. Kuris iš jų turi neabejotiną galimybę laimėti?
Kai krūvelėse yra po vieną pagaliuką, laimės antrasis žaidėjas - tai akivaizdu. Kai yra daugiau pagaliukų, bet krūvelės lygios, taip pat laimės antrasis žaidėjas: kiek bepaimtų pirmasis žaidėjas pagaliukų iš kurios nors krūvelės, tokį pat skaičių pagaliukų turėtų imti antrasis iš kitos krūvelės. Ir taip turėtų daryti tol, kol krūvelėse liks po vieną pagaliuką.
Kai krūvelėse pagaliukų skaičius nevienodas, tai pirmasis žaidėjas pirmu ėjimu paima tiek pagaliukų, kad krūvelės pasidarytų lygios. Tada jis įgyja aukščiau aptartą pranašumą laimėti.
Vadinasi, jei krūvelės lygios, neabejotiną galimybę laimėti turi antrasis žaidėjas, jei nelygios - pirmasis. Pateikiame struktūrogramą, kaip turi žaisti pirmasis žaidėjas, kad jis, jei tik yra galimybė, laimėtų.

2 pavyzdys. Tikriausiai jau įsitikinote, kad sveikųjų skaičių dalybos operacijos: div - dalmuo ir mod - liekana - būna reikalingos daugelyje uždavinių. Dabar tarkime, kad šių operacijų nėra. Kaip tada reikėtų rasti dviejų natūraliųjų skaičių a ir b dalybos dalmenį ir liekaną? Pabandykime parašyti algoritmą.
Dalmenį ir liekaną galima rasti, iš skaičiaus a atiminėjant skaičių b. Atimtį reikia kartoti tol, kol tenkinama sąlyga a b. Kiek kartų galėjome atimti, bus dalmuo, o kas liko - liekana.

 


   
Užrašysime tą patį algoritmą Paskalio kalba. Ciklo schema Paskalio kalboje pateikta dešinėje esančiame paveikslėlyje. Šis ciklas dažnai vadinamas nežinomo kartojimų skaičiaus ciklu (arba while ciklu: while - “kol”). Lietuviškai jį galima būtų vadinti KOL ciklu.



Ciklo  KOL  schema

Ciklą pradeda antraštė: pirmas žodis while, toliau rašoma sąlyga (loginis reiškinys), o po jos - žodis do (“atlikti, daryti”), kuriuo užbaigiama antraštė. Toliau nurodomi ciklą sudarantys veiksmai - sakinys, kuris kartojamas tol, kol tenkinama antraštėje nurodyta sąlyga.

Ciklo antraštė valdo tik vieno (po jos einančio) sakinio kartojimą. Jeigu reikia kartoti kelis sakinius, tai jie jungiami į sudėtinį sakinį (apgaubiami žodžiais begin ir end, taip pat kaip ir sąlyginiuose sakiniuose).
2 pavyzdžio ciklas Paskalio kalba būtų užrašomas šitaip:

while  a >= b do
begin
a := a - b;
dalmuo := dalmuo + 1
end

turiu  jėgų 

begin
BĖGU! Bėgu kol turiu jėgų!
end

Kaip atliekamas ciklas? Pirmiausia tikrinama sąlyga. Jeigu ji netenkinama, tai sakiniai, esantys po do, neatliekami nė karto (2 pavyzdyje taip būtų, kai a < b). Jeigu sąlyga tenkinama, tai atliekami po antrašte einantys sakiniai ir vėl grįžtama prie sąlygos tikrinimo. Veiksmai kartojami tol, kol tenkinama sąlyga. Kai sąlyga netenkinama, ciklas baigiamas.
Panagrinėsime, kaip atliekamas ciklas, esant konkrečioms kintamųjų reikšmėms, pavyzdžiui,   a = 19   ir   b = 5.   Sąlyga tenkinama iš karto, nes   19 > 5. Todėl atliekami sakiniai a := a - b   ir   dalmuo := dalmuo + 1.   Dabar   a = 14   ir   dalmuo = 1.   Antrą kartą tikrinama sąlyga vėl tenkinama, nes   14 > 5.   Vėl atliekami sakiniai   a := a - b   ir   dalmuo := dalmuo + 1.   Dabar   a = 9,   dalmuo = 2.   Sąlyga dar tenkinama: 9 > 5.  Vėl atliekami sakiniai   a := a - b   ir   dalmuo := dalmuo + 1.  Dabar     a = 4   ir   dalmuo = 3.   Sąlyga nebetenkinama: 4 < 5.  Todėl   sakiniai     a := a - b  ir   dalmuo := dalmuo + 1   nebeatliekami, ir ciklas baigiamas. Rezultatai   a   ir   dalmuo   yra skaičiaus   a iš iš   b  dalijimo   liekana   ir   dalmuo.   Liekana gaunama pradinio duomens vietoje. Kad pradinė kintamojo a reikšmė nedingtų, liekanai žymėti galima pavartoti kitą kintamąjį.
Šio algoritmo atlikimo išsami schema pateikta apačioje esančiame paveiksle. Beje, programoje pradinė kintamojo a reikšmė negadinama: a reikšmę iš pradžių priskyrėme kintamajam liekana ir cikle atiminėjome iš jo.

Spausk čia, jei nori pradėti iš naujo.

Dalmens ir liekanos radimas (ciklinio algoritmo pavyzdys).

3 pavyzdys. Didžiausias bendrasis daliklis.  Tai bene populiariausias algoritmas. Jis dar vadinamas Euklido algoritmu, kadangi garsusis matematikas Euklidas  III a.pr.Kr.   išdėstė jį geometrine forma mūsų laikus pasiekusiame veikale “Pradmenys”. Išnagrinėsime jį atidžiau.
Sakykime, duoti du natūralieji skaičiai a > b. Reikia rasti šių skaičių didžiausią bendrąjį daliklį. Euklidas siūlė iš didesniojo atiminėti mažesnįjį tol, kol neliks liekanos arba kol liekana taps mažesnė už mažesnįjį skaičių. Vietoj atimties galima  a  dalyti iš  b, nes dalyba - tai daugkartinė atimtis. Pasinaudosime teorema, kuri teigia, kad dviejų skaičių didžiausias bendrasis daliklis lygus didžiausiam bendrajam dalikliui mažesniojo skaičiaus ir liekanos, gautos dalijant didesnįjį iš mažesniojo. Vadinasi, skaičių 30 ir 18 didžiausias bendrasis daliklis yra toks pat kaip ir skaičių 18 ir 12 (30 mod 18 = 12). Dar sykį pritaikę šią teoremą, gauname, kad 18 ir 12 didžiausias bendrasis daliklis yra toks pat kaip ir skaičių 12 ir 6 (18 mod 12 = 6). Kadangi 12 mod 6 = 0, tai didžiausias bendrasis daliklis yra 6. Taigi ir skaičių 30 ir 18 didžiausias bendrasis daliklis lygus 6. Užrašysime didžiausio bendrojo daliklio radimo algoritmą Paskalio kalba:

program daliklis;
var x, y, {pradiniai duomenys} dbd : integer; {didžiausias bendrasis daliklis}
begin
read (x, y);
while (x <> 0) and (y <> 0) do
if   x >= y
then  x := x  mod   y
else  y := y mod   x;
dbd := x + y;
writeln (dbd)
end.


    ciklas     ciklo antraštė
    ciklinis algoritmas     ciklo sąlyga
    nežinomo kartojimų skaičiaus ciklas     while
    KOL ciklas     do