Structura repetitivă Repetiţia necondiţionată Repetiţia condiţionată iniţial Repetiţia condiţionată final Probleme propuse Soluţiile problemelor propuse

Capitolul

4 În multe situaţii este necesar să reluăm o anumită operaţie (un anumit set de in-strucţiuni). În asemenea situaţii îşi arată utilitatea structurile repetitive. Repetiţia unei operaţii se poate executa în două moduri: Necondiţionat – ştim exact de câte ori trebuie să reluăm secvenţa de instrucţiuni; Condiţionat – se reia secvenţa în funcţie de valoarea de adevăr a unei condiţii. Atunci când avem o reluare condiţionată a unei secvenţe de operaţii, condiţia de re-luare ar putea fi verificată înainte sau după executarea operaţiei. În acest sens vom vorbi despre structura repetitivă cu test iniţial, respectiv structura repetitivă cu test final. În descrierea prin scheme logice a algoritmilor nu există blocuri (figuri geometrice) utilizate pentru a indica existenţa unei repetiţii. Pentru a marca repetiţia vom redirecţi-ona săgeţile, astfel încât să indicăm existenţa unei reveniri la o instrucţiune anterior efectuată. 4.1. Repetiţia necondiţionată Vom utiliza o asemenea instrucţiune atunci când cunoaştem cu exactitate numărul de repetări necesar pentru finalizarea operaţiei. Forma generală a instrucţiunii în pseudocod o vom nota: pentru contor=iniţial,final execută: secvenţa { instrucţiuni reluate } sfârşit pentru Schema logică generală a instrucţiunii repetitive cu număr cunoscut de paşi în cazul în care variabila contor este incrementată:

38 4. Structura repetitivă

Singura instrucţiune permisă la revenire este cea de incrementare/decrementare a contorului. În Pascal vom avea două forme sub care o astfel de instrucţiune se poate imple-menta: for contor:=initial to final do instrucţiune şi for contor:=initial downto final do instrucţiune Această instrucţiune se execută după cum urmează: deoarece iniţial şi final sunt ex-presii, mai întâi se evaluează valorile lor. Apoi, se verifică relaţia dintre valoarea ini-ţial şi final. În cazul formei cu to, dacă iniţial are valoare mai mare decât final, se iese din instrucţiune, în cazul formei cu downto se consideră instrucţiunea terminată dacă iniţial are valoare mai mică decât final. În cazul ambelor forme, dacă nu s-a ieşit din instrucţiune, se atribuie variabilei contor valoarea iniţială şi se execută instrucţiune. După fiecare reluare se testează dacă variabila contor a atins exact valoarea finală. Da-că nu, atunci se modifică acest contor şi se repetă instrucţiunile de executat. Dacă valoarea iniţială este mai mică decât valoarea finală atunci contorul se incre-mentează (se măreşte). Altfel, contorul se decrementează (se micşorează). În schema logică, vom utiliza în al doilea caz instrucţiunea contor:=contor-1. În Pascal, modul de modificare a contorului este precizat prin utilizarea cuvântului cheie to pentru incrementare, respectiv downto pentru decrementare. Dacă aveţi de reluat două sau mai multe instrucţiuni în cadrul buclei for, sintaxa limbajului vă obligă să utilizaţi instrucţiunea compusă.

4. Structura repetitivă 39 Pentru a nu avea probleme legate de imposibilitatea ieşirii din această buclă vă recomandăm să nu utilizaţi niciodată printre instrucţiunile de repetat instrucţiuni care modifică în mod explicit valoarea variabilei contor. Structura repetitivă necondiţionată utilizează o variabilă contor care „numără” repetiţiile şi care este modificată implicit. 4.2. Repetiţia condiţionată iniţial Se utilizează acest mod de reluare a unei secvenţe de instrucţiuni atunci când nu cu-noaştem numărul de reluări necesare în rezolvare, însă ştim cu exactitate ce condiţie trebuie să se verifice pentru a relua secvenţa de instrucţiuni. Forma generală în reprezentare cu schemă logică:

cât timp condiţie execută secvenţă { instrucţiuni reluate } sfârşit cât timp

while condiţie do instrucţiune

Această instrucţiune se execută după cum urmează: mai întâi se evaluează condiţie. Dacă este verificată, atunci se execută secvenţa de instrucţiuni şi se testează din nou condiţia etc... În momentul în care valoarea de adevăr a condiţiei devine falsă, se încheie repetiţia şi se iese din instrucţiune. Observaţie Numărul minim de repetiţii ale secvenţei este 0, deoarece se poate întâmpla ca de la început să nu se verifice condiţia. Aveţi grijă, trebuie ca în urma execuţiei secvenţei de instrucţiuni să se modifice cel puţin una dintre variabilele care apar în condiţie. În caz contrar, este posibil ca odată intraţi în structura repetitivă să nu o mai puteţi părăsi (caz în care spunem că am pro-vocat o buclă infinită). În Pascal, instrucţiune poate fi orice instrucţiune, iar dacă dorim să se execute mai multe, le vom grupa într-una compusă.

40 4. Structura repetitivă 4.3. Repetiţia condiţionată final Acest tip de structură repetitivă este asemănător primului şi se utilizează atunci când dorim să verificăm dacă mai este necesar să reluăm secvenţa de instrucţiuni după ce am parcurs-o odată. Forma ei, reprezentată cu schemă logică:

repetă secvenţă { instrucţiuni reluate } până când condiţie

repeat secvenţă de instrucţiuni until condiţie

Această instrucţiune se execută după cum urmează: mai întâi se execută secvenţa de instrucţiuni apoi se evaluează condiţia. Dacă nu este verificată, atunci se execută secvenţa de instrucţiuni şi se testează din nou condiţie etc... În momentul în care se condiţie devine adevărată, se încheie repetiţia şi se iese din instrucţiune. Observaţie Numărul minim de repetiţii ale secvenţei este 1. 4.4. Probleme propuse 4.4.1. Ani bisecţi O problemă importantă în astrologie este determinarea anilor bisecţi (ani cu 366 de zile). Un an se consideră „bisect” dacă este multiplu de 4, dar nu este multiplu de 100. Dintre anii eliminaţi conform acestui criteriu sunt consideraţi „bisecţi” cei care sunt multipli de 400. Scrieţi un program care determină şi afişează toţi anii bisecţi între an1 şi an2. Date de intrare De la tastatură se vor citi valorile an1 şi an2. Date de ieşire Se vor afişa anii bisecţi din intervalul de ani [an1..an2], separaţi prin câte un spaţiu.

4. Structura repetitivă 41 Restricţii şi precizări • 1600 ≤ an1, an2 ≤ 2200. Exemple Intrare an1=1990 an2=2005 an1=1890 an2=1904

Ieşire 1992 1996 2000 2004 1892 1896 1904

Explicaţie 1992, 1996 şi 2004 sunt multipli de 4 şi nu sunt multipli de 100. 2000 este multiplu de 400.

1892, 1896 şi 1904 sunt multipli de 4 şi nu sunt multipli de 100. 1900 nu este an bisect, deoarece este multiplu de 100 şi nu este multiplu de 400.

4.4.2. Tabără Într-o tabără de vară participă b băieţi şi f fete. În această tabără se organizează diverse jocuri şi concursuri. Pe noi ne interesează un anumit joc, la care trebuie să participe un număr cât mai mare de echipe, formate din băieţi şi fete. Toate echipele trebuie să fie formate din acelaşi număr nrb de băieţi şi acelaşi număr nrf de fete. Trebuie să scrieţi un program care determină numărul maxim de echipe care se pot forma şi numărul nrb de băieţi, respectiv numărul nrf de fete, care intră în componenţa fiecărei echipe. Pen-tru ca jocul să poată fi organizat trebuie să se formeze cel puţin două echipe identice. Date de intrare Se vor citi numărul b de băieţi şi numărul f de fete, participanţi la tabără. Date de ieşire Pe prima linie se va afişa numărul de echipe care se pot forma, iar pe linia următoare se vor afişa două valori întregi, reprezentând numărul nrb de băieţi, respectiv numărul nrf de fete care intră în componenţa fiecărei echipe. Cele două valori vor fi separate prin spaţiu. Dacă nu se pot forma cel puţin două echipe identice se va afişa mesajul: 'Nu ne putem juca :-('. Restricţii şi precizări • 10 ≤ b, f ≤ 200; • Datele de intrare sunt întotdeauna corecte. Exemple Intrare b=10 f=15 b=12 f=25

Ieşire 5 2 3 Nu ne putem juca :-(

Explicaţie Se pot forma cel mult 5 echipe din nrb = 2 băieţi şi nrf = 3 fete

Nu se pot forma două echipe identice.

42 4. Structura repetitivă 4.4.3. Suma mai multor numere naturale Să presupunem că aveţi n cutii şi cunoaşteţi masa fiecărei cutii (în kilograme), fără să vă intereseze ce conţine. Trebuie să determinaţi capacitatea minimă de transport a unui autovehicul care ar fi în stare să transporte într-un singur drum toate aceste cutii. Capacitatea de transport a unui autovehicul este egală cu masa maximă a încărcă-turii pe care acesta o poate transporta. Date de intrare Se dă numărul n a cutiilor şi masa fiecărei cutii. Date de ieşire Veţi afişa capacitatea minimă a vehiculului care poate efectua transportul. Restricţii şi precizări • 1 ≤ n ≤ 10; • Fiecare cutie are masa între 0 şi 1000 kg. • Dacă masa unei cutii nu se află în intervalul precizat se va afişa mesajul: 'Cutie periculoasă!' şi se va opri execuţia programului. Exemplu Intrare n=5 700 500 800 100 600

Ieşire 2700

Explicaţie Vehiculul trebuie să poată transporta în total cel puţin 2700 kg.

4.4.4. Bile colorate Am inventat pentru voi un joc. Pe masă aveţi bile de n culori şi cunoaşteţi numărul de bile existente din fiecare culoare. Singura operaţie permisă este extragerea a k bile de aceeaşi culoare din grămadă. Vă dau voie să determinaţi o singură dată valoarea lui k şi apoi, la fiecare operaţie de extragere, să luaţi de pe masă k bile, toate de aceeaşi cu-loare. Trebuie să luaţi toate bilele de pe masă, folosind cât mai puţine operaţii de ex-tragere. Pentru ca să accept soluţia voastră trebuie să îmi spuneţi două lucruri: 1. Câte bile de aceeaşi culoare veţi lua de pe masă la o extragere? 2. Câte operaţii de extragere veţi efectua? Date de intrare Se dă numărul de culori n şi numărul de bile din fiecare culoare. Date de ieşire Veţi afişa numărul de bile de aceeaşi culoare extrase într-o operaţie şi numărul opera-ţiilor efectuate. Cele două valori le veţi afişa pe aceeaşi linie, separate prin spaţiu.

4. Structura repetitivă 43 Restricţii şi precizări • 2 ≤ n ≤ 10; • Numărul de bile din fiecare culoare este un număr întreg din intervalul [1,1000]. • Odată determinată valoarea k, nu mai aveţi voie să o modificaţi. • Datele de intrare sunt întotdeauna corecte. Exemplu Intrare n=5 14 63 42 56 77

Ieşire 7 36

Explicaţie Se vor extrage la fiecare operaţie câte 7 bile de ace-eaşi culoare. Numărul de extrageri este egal cu 36.

4.4.5. Şirul lui Fibonacci Unul dintre şirurile de termeni de o importanţă deosebită în matematică este şirul lui Fibonacci. Acest şir este definit astfel: • primii doi termeni ai săi sunt egali cu 1; • începând cu al treilea termen, fiecare termen este egal cu suma celor mai mari doi termeni de rang mai mic decât al său. Se dă numărul natural strict pozitiv n. Calculaţi şi afişaţi al n-lea termen al şirului Fibonacci! Date de intrare Se dă un număr natural strict pozitiv n. Date de ieşire Se va afişa valoarea termenului de rang n din şirul lui Fibonacci. Restricţii şi precizări • 1 ≤ n ≤ 20; • Prin rang se înţelege numărul de ordine al termenului în şir (al câtelea termen este). • Datele de intrare sunt întotdeauna corecte. Exemple Intrare n=5 n=2

Ieşire 5 1

Explicaţie Termenul de rang 5 are valoarea 5.

Termenul de rang 2 are valoarea 1.

44 4. Structura repetitivă 4.5. Soluţiile problemelor 4.5.1. Ani bisecţi Conform enunţului, se vor afişa ca ani bisecţi anii care sunt multipli de 4, dar nu sunt multipli de 100 şi anii care sunt multipli de 400. Deci, vom avea o condiţie mixtă în care vom verifica divizibilităţile (resturile împărţirilor pe mulţimea numerelor întregi): ((an mod 4=0) and (an mod 100<>0)) or (an mod 400=0)

Prima idee de a rezolva problema este de a genera cu o instrucţiune repetitivă de tip pentru toţi anii, începând cu an1 până la an2 şi de a verifica proprietatea de an bisect pentru fiecare valoare a contorului an. Dacă vrem să reducem numărul anilor de verificat, deci implicit şi timpul de execu-ţie, putem să ne bazăm pe faptul că toţi anii bisecţi sunt multipli de 4 (dar nu toţi anii multipli de 4 sunt ani bisecţi). Observăm că dacă un anumit an (an) este bisect, atunci şi anul an + 4 este bisect cu condiţia să nu fie multiplu de 100. În concluzie, vom ve-rifica dacă an1 este sau nu bisect. În caz de răspuns negativ, vom căuta primul an bi-sect mai mare decât an1: Algoritm AnBisect: citeşte an1,an2 an ← an1 { căutăm primul an bisect care este ≥ an1 } cât timp nu (((an mod 4=0) şi (an mod 100≠0)) sau (an mod 400=0)) execută: an ← an + 1 sfârşit cât timp cât timp an < an2 execută: { dacă un an este multiplu de 100, dar nu şi de 400, } { atunci NU este considerat bisect şi îl sărim } dacă (an mod 100=0) şi (an mod 400≠0) atunci an ← an + 4 sfârşit dacă scrie an an ← an + 4 { trecem la următorul an bisect } sfârşit cât timp sfârşit algoritm Analizând numărul operaţiilor, observăm că în primul algoritm trebuie să verificăm an2 – an1 + 1 numere, ceea ce înseamnă evaluarea a 3⋅(an2 – an1 + 1) expresii logice. În al doilea algoritm avem cel mult trei paşi în primul cât timp (deci se evaluea-ză 3⋅3 expresii logice) şi 2⋅ ([(an2 – an1 + 1)/4] + 1) expresii de evaluat în al doilea cât timp.

4. Structura repetitivă 45 Reprezentarea algoritmului cu schemă logică:

4.5.2. Tabără Ultima restricţie precizează că datele de intrare sunt întotdeauna corecte adică, se află întotdeauna în intervalul precizat de primele două restricţii. Deci, am scăpat de prima problemă. Acum trebuie să analizăm textul problemei pentru a afla ce avem de calculat.

• Toate echipele trebuie să fie formate din acelaşi număr de băieţi. ⇒ Deci, numă-rul de echipe trebuie să fie printre divizorii lui b.

• Toate echipele trebuie să fie formate din acelaşi număr de fete. ⇒ Deci, numărul de echipe trebuie să fie printre divizorii lui f.

46 4. Structura repetitivă

• Numărul de echipe trebuie să fie maxim şi echipele trebuie să aibă componenţă identică. ⇒ Deci, trebuie să aflăm cel mai mare divizor comun al lui b şi f. Dacă cele două valori sunt prime între ele (au cmmdc = 1) se va afişa mesajul 'Nu ne putem juca :-('. Pentru determinarea celui mai mare divizor comun vom utiliza algoritmul lui Euclid care foloseşte o strategie bazată pe împărţiri repetate. Fie a şi b două numere naturale. Fără să restrângem generalitatea, putem presupune că a < b (Dacă nu este aşa, le putem interschimba...). 1. Dacă a se împarte exact la b, atunci b este cmmdc. 2. Dacă a nu se împarte exact la b, atunci putem scrie: a = q*b + r (*) unde: q = câtul împărţirii r = restul împărţirii

3. Observăm următoarea proprietate: cmmdc (fiind cel mai mare divizor al lui a şi b) acesta divide şi pe a şi b, dar divide şi pe r pe baza relaţiei (*). Cum r este mai mic decât b şi b este mai mic decât a, la pasul următor vom decide:

• Dacă r = 0, suntem în situaţia precizată la 1. ⇒ cmmdc = b • Dacă r ≠ 0, pe baza observaţiei de la 3. vom înlocui pe a cu b, pe b cu r şi vom

căuta cmmdc al noului a şi noului b. Prin urmare, problema aflării cmmdc dintre a şi b se reduce la problema aflării cmmdc dintre b şi r deci, vom reveni la pasul 1 cu a ← b şi b ← r.

4. Algoritmului se încheie atunci când la pasul 1 obţinem un rest egal cu 0. Ultimul rest nenul va reprezenta cmmdc dintre a şi b. Algoritm Euclid: citeşte a,b r ← rest[a/b] { primul rest al împărţirii întregi al lui a la b } cât timp r ≠ 0 execută: { cât timp restul nu este 0 continuăm împărţirile } a ← b b ← r { calculăm restul împărţirii întregi pentru noul a (fostul b) şi noul b (fostul r) } r ← rest[a/b] sfârşit cât timp scrie b sfârşit algoritm Observaţie Nu s-a verificat relaţia dintre a şi b, deoarece chiar dacă a < b, la prima împărţire a lui a la b se obţine rest egal cu a, şi cele două numere se interschimbă datorită algoritmului lui Euclid, fără ca noi să trebuiască să le interschimbăm explicit.

4. Structura repetitivă 47 Să descriem acum rezolvarea problemei utilizând schema logică:

4.5.3. Suma mai multor numere naturale Trebuie să determinaţi suma celor n valori întregi date, care reprezintă masele cutiilor. Însă, trebuie să fiţi atenţi la un lucru: dacă o cutie are o masă negativă sau prea mare (peste 1000 kg) nu trebuie doar să o neglijaţi, ci să opriţi execuţia programului afişând mesajul corespunzător ('Cutie periculoasă!'). Algoritm Suma: citeşte n s ← 0 { iniţializarea sumei cu 0 } pentru i=1,n execută: citeşte m { citirea pe rând a maselor cutiilor } dacă (m < 0) sau (m > 1000) atunci { dacă o cutie este „periculoasă” afişăm mesajul corespunzător } scrie 'Cutie periculoasa!' Oprire forţată algoritm { şi oprim execuţia programului } sfârşit dacă

48 4. Structura repetitivă { dacă execuţia programului ajunge aici, cutia este „în regulă” şi masa ei va fi } s ← s + m { adunată la masa totală a celorlalte cutii „încărcate” deja } sfârşit pentru scrie s sfârşit algoritm Reprezentarea algoritmului cu schemă logică:

Observaţii • Compilatorul Borland/Turbo Pascal iniţializează cu 0 toate variabilele numerice

(globale), dar această iniţializare automată nu se realizează de către toate compila-toarele.

• Oprirea execuţiei programului în limbajul Pascal se realizează cu ajutorul „instruc-ţiunii” Halt. Acesta este de fapt apelul unui subprogram care are ca efect întreru-perea programului. Studiaţi în Help rolul acesteia, precum şi a lui Break şi Exit. Determinaţi diferenţele dintre ele.

4. Structura repetitivă 49 4.5.4. Bile colorate Întotdeauna problema are o soluţie (k = 1) însă această soluţie nu garantează obţinerea numărului minim de extrageri. Pentru a obţine numărul minim de extrageri, trebuie să utilizaţi o valoare cât mai mare a lui k. Pe de altă parte, deoarece într-o extragere nu este permis să aveţi decât bile de aceeaşi culoare, înseamnă că pentru a elimina de pe masă toate bilele de o anumită culoare, trebuie ca numărul de bile de culoarea respecti-vă să fie multiplu de k (k să fie divizor al acestei valori). Deci, va trebui să determinaţi valoarea lui k care este simultan divizor al tuturor ce-lor n valori, reprezentând numărul de bile din fiecare culoare şi această valoare trebuie să fie maximă (adică, cel mai mare divizor comun al celor n valori). Observăm că această problemă este de fapt o generalizare a problemei 4.4.2. Pentru rezolvarea ei va trebui să utilizăm algoritmul lui Euclid în mod repetat: Pas 1. Determinăm cmmdc pentru primele două valori. Pas 2. Determinăm cmmdc dintre cmmdc obţinut la pasul 1 şi cea de a treia valoare. Pas 3. Determinăm cmmdc dintre cmmdc obţinut la pasul 2 şi valoarea a patra. … Pas n-1. Determinăm cmmdc dintre cmmdc obţinut la pasul n-2 şi valoarea a n-a.

50 4. Structura repetitivă Observaţie O rezolvare interesantă ar însemna să încercăm să reţinem toate cele n valori (divi-zori). Dintre aceste valori se determină minimul. Valoarea de calculat fiind cel mai mare divizor comun a celor n numere, acesta este, evident, şi cel mai mare divizor al minimului. Deci vom căuta cel mai mare divizor al minimului care totodată este şi di-vizor al celorlalte valori. Implementarea acestui algoritm va fi un exerciţiu util atunci când vom învăţa să lucrăm cu tablouri. 4.5.5. Şirul lui Fibonacci Deoarece primii doi termeni ai şirului sunt pozitivi, iar ceilalţi termeni se calculează ca sumă a doi termeni precedenţi, înseamnă că şirul Fibonacci este un şir crescător. Deci, fiecare termen va fi mai mare decât toţi termenii de rang mai mic decât el. Deducem de aici că va trebui să utilizăm următoarea formulă de calcul:

( )

−+−==

=restîn)2()1(

2sau1dacă1nfnf

nnnf

Să calculăm câţiva dintre termenii şirului Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … Vom utiliza următorul algoritm: Fiecare termen, odată calculat, intervine ca termenul de rang maxim în calculul ur-mătorului termen, iar termenul care avea rangul maxim în calcularea sa devine terme-nul de rang precedent (cu 1 mai mic) în calcul. Exemplu Fie n = 5, caz în care trebuie să obţinem pentru f(5) valoarea 5

i f1 f2 f3 = f1 + f2Valori iniţiale 1 1 2 3 1 2 3 4 2 3 5 5 3 5 5

Am putea rezuma algoritmul prezentat mai sus cu „formula” calculează-mută-mută: f1 reţine întotdeauna termenul de rang i – 2, f2 reţine termenul de rang i – 1, în f3 se efectuează calculul termenului de rang i, apoi se mută valoarea din f2 în f1 şi valoarea din f3 în f2. Algoritm Fibonacci: citeşte n f1 ← 1 f2 ← 1

4. Structura repetitivă 51 dacă n ≤ 2 atunci scrie f2 { dacă n = 1 sau n = 2, f1 = 1 şi f2 = 1 } altfel pentru i=3,n execută: f3 ← f1 + f2 { calculăm valoarea termenului curent } f1 ← f2 { mutăm valoarea lui f2 în f1 } f2 ← f3 { mutăm valoarea lui f3 în f2 } sfârşit pentru scrie f3 { afişarea rezultatului pentru n > 2 } sfârşit dacă sfârşit algoritm