PRELEGEREA IIPROGRAMAREA CALCULATOARELOR ŞI LIMBAJE DE PROGRAMARE

Iniţiere în gîndirea algoritmică

I. Reprezentarea algoritmilor prin simboluri graficeSchema logică se reprezintă grafic cu ajutorul unor figuri geometrice numite simboluri

sau blocuri. Dintre figurile geometrice utilizate cel mai des în literatura de specialitate se menţionează: dreptunghiul, paralelogramul, elipsa, hexagonul, rombul şi cercul. Forma şi conţinutul acestora indică tipul operaţiei şi respectiv operaţia de executat.

Ordinea blocurilor într-o schemă logică nu este aleatoare, ci este în concordanţă cu cea din descompunerea metodei de rezolvare în operaţii acceptate de calculator. Astfel, structura schemei logice se obţine conectînd blocurile între ele prin săgeţi, fie pe orizontală, fie pe verticală.

Amintind faptul că nu există, pînă în prezent, teorii unitare şi cuprinzătoare asupra mecanismului de elaborare a unei scheme logice, de cele mai multe ori, această descompunere nu se realizează uşor. Succesul alcătuirii schemei logice va fi în funcţie de ingeniozitatea, competenţa şi experienţa programatorului şi de asemeni de modul în care acesta ştie să mînuiască diverse artificii de calcul. Cum procedeele specifice activităţii de programare nu sînt la îndemîna începătorilor, primele încercări de concepere a unor scheme logice se soldează, în majoritatea cazurilor, cu eşecuri.

Tipurile de operaţii care pot intervini într-o schemă logică sînt următoarele:- citire de date cu diverse tipuri;- scriere de date cu diverse tipuri;- evaluare expresie matematică;- verificare condiţie;- apelare procedură. Denumire şi conţinutul blocurilor prin care se simbolizează se

prezintă în cele ce urmează:1. Blocul delimitator de început de schemă logică. Acest bloc marchează punctul de

început în orice schemă logică şi se reprezintă printr-o elipsă.

2. Blocul delimitator de sfîrşit de schemă logică. Orice schemă logică se încheie cu delimitatorul de sfîrşit de schemă logică. Forma lui este tot o elipsă în care săgeata de ieşire se înlocuieşte cu o săgeată de intrare, iar conţinutul lui este determinat de vocabula STOP.

3. Blocul de intrare (citire, introducere) simbolizează operaţia de introducere a datelor cunoscute dintr-o problemă în memoria calculatorului. Acesta are forma unui paralelogram, prevăzut cu o intrare şi o ieşire. Cuvîntul CITEŞTE şi lista variabililor de intrare (adică, lista variabililor a căror valori se cunosc în enunţul problemei), separate prin virgulă, fixează conţinutul lui.

START

STOP

4. Blocul de ieşire. Simbolizarea operaţiei de scriere (afişare, tipărire, editare) a unor date stocate în memoria calculatorului pe suportul de ieşire se face prin blocul de ieşire. Acesta se deosebeşte de blocul de intrare numai prin conţinut.

Nu interesează tipul suporţilor de intrare/ieşire din configuraţia hardware a sistemului de calcul pe care urmează să se execute programul respectiv.

5. Blocul de calcul se utilizează la descrierea calculelor matematice ce urmează să se execute într-un anume context de rezolvare. Probabilitatea lui de apariţie într-o schemă logică este aproape sigură. Forma şi conţinutul blocului de calcul se prezintă în modul următor:

Expresia poate fi oricît de complicată, ordinea de evaluare a operaţiilor componente fiind cea cunoscută din matematică. Un calcul flexibil şi uşor de urmărit poate fi realizat prin utilizarea parantezelor.

Variabila din membru stîng al expresiei poate participa şi în membrul al doilea cu condiţia ca anterior să fi primit o valoare. Aceasta poate provini din diverse surse: ca rezultat al evaluării unei expresii matematice, printr-o asignare sau operaţie de citire.

Valoarea obţinută, prin evaluarea expresiei matematice din membrul al doilea, va înlocui prin suprascriere, în memoria calaculatorului, pe cea avută anterior de variabilă (deci, ce a fost înainte în celula de memorie se va distruge). Ulterior, aceasta urmează să fie folosită în diverse prelucrări, operaţii de scriere sau de atribuire.

6. Blocul de decizie. Verificarea unei condiţii sau punerea unei întrebării se reprezintă grafic prin blocul de decizie cu forma unui romb. Răspunsul poate fi afirmativ sau negativ, motiv pentru care blocul este prevăzut cu două ieşiri notate de la stînga la dreapta cu NU şi DA sau - şi respectiv +.

NU(-) DA(+)

Atît în schema logică, cît şi în programul corespunzător se prevăd rezolvări pentru ambele posibilităţi. În funcţie de răspuns, se va lua o singură decizie, adică se va parcurge ramura pozitivă sau ramura negativă a blocului de decizie după cum condiţia este adevărată sau falsă.

Numărul blocurilor de decizie determină gradul de ramificare şi de arborescenţă al unei scheme logice.

7. Blocul de tip procedură. Dacă o parte din operaţiile care intervin în algoritmul de rezolvare al unei probleme se repetă de mai multe ori, cu valori diferite pentru variabilile cu care se lucrează, atunci acea parte se poate organiza într-o schemă logică de sine stătătoare (numită

2

CITEŞTE a, b, c, ...

SCRIE a, b,

Variabilă = expresie_matematică

Condiţie

procedură sau schemă logică apelată), urmînd să fie apelată în schema logică principală (apelantă) ori de cîte ori este nevoie.

Apelarea procedurii se realizează cu ajutorul unui nume simbolic stabilit de către programator, cu care se identifică aceasta, urmat, eventual, de o listă de variabile prin care se face schimbul de date şi informaţii între cele două tipuri de scheme logice. Deci, blocul de de tip procedură va avea două roluri:

- unul în schema logică principală (cu o intrare şi o ieşire) pentru simbolizarea apelării unei proceduri, cu următoarea formă:

- al doilea, ca delimitator de început de procedură (doar cu o singura ieşire), cu o formă similară blocului de apelare procedură, însă cu un conţinut diferit:

Între parametri actuali (efectivi) şi cei formali (fictivi) trebuie să existe o corespondenţă de ordine, tip, număr şi dimensiune. O neconcordanţă între cele două liste de parametri este sancţionată, cu mesaje de eroare şi cu întreruperea execuţiei programului respectiv, de orice limbaj de programare. Coincidenţa de nume de variabile în componenţa celor două liste este acceptată de către calculator, chiar cu semnificaţii diferite, fără să se provoace ambiguităţi şi confuzii în interpretarea informaţiilor vehiculate de program.

Prin intermediul celor două liste de parametri se execută schimbul de informaţii între schema logică principală şi procedură, adică schema logică principală furnizează datele de intrare necesare rezolvării procedurii şi după execuţia ei în totalitate, procedura returnează la rîndul ei rezultatele obţinute. Datele de intrare pentru procedură se schimbă de la o apelare la alta şi depind de contextul de rezolvare al problemei. Revenirea în schema logică principală se face imediat după blocul de apelare a procedurii, datele furnizate de procedură urmînd să fie folosite în calcule, operaţii de tipărire, operaţii de asignare simple sau pot constitui, chiar, date de intrare pentru aceeaşi procedură sau alte proceduri.

Cu blocul delimitator de sfîrşit de schemă logică se încheie, grafic, orice procedură. 8. Blocuri de conectare. Simbolurile de conectare pe aceeaşi pagină de hîrtie au forma

unor cerculeţe, iar între pagini diferite sînt săgeţi de tip bloc. Ele pot avea o intrare, o ieşire sau şi una şi alta şi fac legătura între două blocuri ale unei scheme logice. Utilizarea este necesară, mai ales, în cazul unei scheme logice vaste care nu încape pe o pagină de hîrtie. Punctul de oprire se marchează printr-un conector cu un anumit conţinut, urmînd ca acelaşi conţinut să fie plasat şi în conectorul care marchează punctul (locul) de unde se continuă schema logică.

Grafic, cele două categori de blocuri de conectare se prezintă, astfel:

Conţinutul blocurilor de conectare se completează cu o cifră, o majusculă, o literă mică sau o combinaţie de două sau mai multe caractere dintre cele amintite.

3

Nume_subprogram (listă_parametri_actuali)

Nume_procedură ( listă_parametri_formali)

A1

bi

2k

II. Reguli de întocmireÎn această secţiune se vor prezenta cîteva reguli de elaborare a unei scheme logice, de înţelegerea şi respectarea cărora vor depinde corectitudinea, claritatea şi eficacitatea unei scheme logice. La prima vedere aceste reguli par simple, totuşi ele joacă un rol important în teoria schemelor logice în sensul că impun un standard, un şablon în întocmirea lor.

Printre regulile de întocmire a unei scheme logice se enumeră:1. Elaborarea unei scheme logice se face pe verticală, începînd cu delimitatorul de început

şi terminînd cu delimitatorul de sfîrşit. Deci, schema logică are un singur punct de intrare şi un singur punct de ieşire;

2. Cu excepţia delimitatorilor de început şi de sfîrşit de schemă logică, celelalte blocuri pot să apară oriunde şi ori de cîte ori este nevoie în schema logică;

3. Săgeata este elementul de legătură între blocurile componente ale unei scheme logice şi se urmăreşte de la sursă către ţintă;

4. O săgeată de ieşire a unui bloc se contopeşte cu săgeata de intrare a următorului bloc, determinînd astfel succesiunea logică a operaţiilor ce se vor executa;

5. Orice drum posibil în schema logică, începînd cu Start şi terminînd cu Stop, defineşte o structură sintactică acceptată.

III. Structuri de bazăSchema logică este un sistem complex care cuprinde, în diverse relaţii, multe construcţii sintactice elementare sau structuri de bază. Un asemenea sistem este considerat la început în părţile sale largi, prin stabilirea structurilor de bază şi a legăturilor dintre ele. Fiecare structură de bază, la rîndul ei, este analizată logic şi prezentată grafic în amănunt. La fel ca schema logică, o structură de bază are un singur punct (o săgeată) de intrare şi un singur punct (o săgeată) de ieşire.

1. Structura liniarăStructura cea mai des întîlnită într-o schemă logică este structura liniară, care se reprezintă printr-un bloc de calcul sau un grup de blocuri de calcul.

Figura 3.1.1.

Conţinutul blocurilor de calcul simbolizează evaluarea unor expresii aritmetice sau logice.

2. Structuri alternativePivotul principal al structurii alternative este blocul de decizie. Se execută rezoluţiile de pe o ramură sau alta în funcţie de modul cum este pusă condiţia, din interiorul blocului de decizieşi de contextul de rezolvare al problemei. Sînt cazuri cînd pe una din ramuri nu se ia nici o decizie.

Dacă ambele ramuri ale blocului de decizie conţin operaţii, structura alternativă se numeşte completă, în caz contrar structura alternativă este incompletă sau pseudoalternativă.

4

Schematic, cele două tipuri de structură alternativă se reprezintă în modul următor:a) - + b) - + - +

Figura 3.2.1Se menţionează că, ramurile trasate fără linii întrerupte nu conţin decizii.

3. Structuri repetitiveAtributul repetitiv evocă scopul acestei structuri într-o schemă logică şi anume, cel puţin o porţiune din schema logică se poate relua de un număr finit de ori. În funcţie de numărul de reluări structura repetitivă se clasifică în:

- structură repetitivă cu un număr fix (cunoscut) de paşi;- structură repetitivă cu un număr variabil (necunoscut) de paşi.La rîndul ei, structura repetitivă cu un număr variabil de paşi poate fi: cu precondiţie,

cu postcondiţie sau cu o condiţie internă.Cunoaşterea numărului de etape în execuţia unei structuri repetitive cu un număr fix de

paşi, cunoscută în literatura de specialitate şi sub denumirea de “ciclu”, presupune stabilirea unei variabile, numită contor (numărător de paşi, variabilă de control, variabilă de ciclare), care să ţină evidenţa numărului de paşi executaţi. În orice moment, din valoarea contorului se pot deduce numărul repetărilor produse şi numărul repetărilor ce urmează să se producă.

Stabilirea unui contor nu înseamnă numai fixarea unui nume simbolic pentru contor ci şi definirea elementelor care îl caracterizează, după cum urmează: valoare iniţială, valoare finală şi raţia de variaţie.

Pentru cele trei elemente se folosesc, în simbolizarea grafică a structurii repetitive cu un număr fix de paşi, notaţiile vi, vf şi respectiv vr, iar pentru contor c.

În construcţia acestui tip de structură repetitivă se disting trei porţiuni:- partea de început formată dintr-un bloc de calcul în care contorul primeşte valoarea vi şi

care constituie punctul de intrare în structură. În marea majoritate a cazurilor această valoare este 0 sau 1;

- secvenţa de schemă logică ce urmează să se repete de cel puţin două ori constituie corpul structurii repetitive repetitive cu un număr cunoscut de paşi. Acesta este format din diferite tipuri de blocuri, cu excepţia celor din categoria deliminatorilor;

- creşterea valorii contorului, cu raţia dată vr, se simbolizează tot printr-un bloc de calcul, plasat în finalul structurii. Acesta este urmat de un bloc de decizie în care apare întrebarea “ valoarea contorului este mai mică sau egală decît vf?”. Răspunsul la întrebare hotărăşte intrarea în repetare sau terminarea activităţii structurii repetitive. Aceste două blocuri încheie structura repetitivă cu un număr fix de paşi ;

În definirea structurii repetitive cu un număr fix de paşi, cele trei componente sînt înţelese în sens logic şi nu fizic, deoarece nu este obligatoriu ca blocul de decizie din finalul structurii să fie ultimul în construcţia acesteia.

5

C

c = v1

- +

În prezentarea grafică a structurii repetitive repetitive cu un număr cunoscut de paşi din figura de mai sus, corpul structurii se subînţelege în locul punctelor, nefiind prezentat în mod efectiv.

Controlul reluării unui grup de blocuri într-o structură repetitivă cu un număr variabil de paşi este dinamic avînd la bază o decizie care verifică îndeplinirea unei condiţii privitoare la terminarea repetărilor. Într-o astfel de structură se evidenţiază doar două componente:

- corpul structurii, cu aceeaşi caracterizare ca în cazul unei structuri repetitive cu un număr fix de paşi;

- partea de final este formată dintr-un bloc de decizie cu o condiţie de ieşire (C) din repetare.

Poziţia condiţiei de ieşire faţă de corpul structurii defineşte tipul structurii repetitive cu un număr variabil de paşi. Aceasta poate să preceadă, să succeadă sau să apară în interiorul corpului structurii. În această ordine au fost prezentate, mai jos, cele trei tipuri de structuri repetitive cu un număr variabil de paşi, adică cu precondiţie, cu postcondiţie şi cu o condiţie interioară.

- + +

- + - +

4 Structura de tip procedurăStructura de tip procedură are atributele unei scheme logice de sine stătătoare. Părţile componente ale unei structurii de tip procedură sînt:

- delimitatorul de început de procedură;- corpul proceduri;- delimitatorul de sfîrşit de procedură.Grafic, structura de tip procedură se reprezintă astfel:

6

c = c+vr

c≤vf

C C

C

Nume procedură ( parametrii

Corpul procedurii este format din ansamblul operaţiilor care se efectuează într-o anume subproblemă şi care se axează pe structurile discutate în secţiunile anterioare.

Vom vedea în secţiunea 1.6 punctul c1), că o schemă logică principală poate apela mai multe structuri de tip procedură.

Observaţie. Într-o schemă logică pot interveni mai multe tipuri de structuri de bază sau mai multe forme ale aceluişi tip. Acestea pot să apară separat sau, cum este cazul structurilor alternative şi repetitive, una în interiorul celeilalte, adică imbricat.

III. Clasificarea schemelor logiceS-a arătat că schema logică este un element intermediar între problemă şi calculator, care facilitează schimbul de informaţie între programatori, uşurează înţelegerea metodei de rezolvare a problemei de către alţi informaticieni sau chiar permite şi celui care a scris programul, după scurgerea unei perioade mai mare de timp de la rezolvarea problemei, să facă mult mai rapid intervenţii în program.Faptul că în orice moment calculatorul trebuie să se afle în situaţii precise în rezolvarea unei probleme şi de asemenea, problemele care se rezolvă cu ajutorul unui calculator fiind de un grad mare de complexitate, necesită o analiză logică minuţioasă şi o descriere completă a tuturor situaţiilor existente şi a relaţiilor dintre acestea. De aceea, chiar programatorii cu experienţă nu pot face schema logică dintr-o dată, ci aceasta se tratează în trepte, de la general la particular, de la complex la simplu şi de la liniar la neliniar. Un asemenea sistem complex este considerat, la început, în părţile sale largi în relaţii uşor de înţeles. În aceasta fază se depistează componentele mari care intervin în schema logică, urmînd ca ulterior acestea să fie înţelese şi dezvoltate, în detaliu, în operaţii acceptate de calculator.Un surplus de siguranţă în întocmirea unei scheme logice se obţine atunci cînd de la început se ştie categoria din care face parte schema logică respectivă.Există mai multe criterii de clasificare a schemelor logice, şi anume:

- nivelul de aprofundare;- modul de prezentare;- gradul de complexitate.

După nivelul de aprofundare schemele logice se clasifică în:- scheme logice de principiu;- scheme logice de program.

În schemele logice de principiu se prezintă un mod general de tratare al problemei, prin fixarea componentelor mari ale acesteia şi a relatiilor dintre ele. Conţinutul blocurilor ce alcătuiesc schema de principiu este mai mult narativ şi precizează unele lucruri cu privire la modul principial de tratare al problemei.Schemele logice de principiu sînt independente de limbajul de programare în care se va scie programul respectiv şi sînt obligatorii pentru problemele ample şi complicate. Ele constituie o primă fază în întocmirea schemei logice de program.Schemele logice de program pătrund în intimitatea fiecărei componente, concretizînd operaţiile elementare ce urmează să fie executate de calculator.

7

STOP

Acestea conţin blocuri cu un conţinut de operaţii simple, cu un grad ridicat de detaliere.În general, schemele logice de program sînt direcţionate după un anumit limbaj de programare şi constituie materialul de bază în scrierea programului ce urmează să fie executat cu un sistem de calcul electonic. În continuare vor fi abordate doar schemele logice de program care vor fi numite simplu, scheme logice. Pentru înţelegerea şi asimilarea acestora se vor considera exemple adecvate.

b) După modul de prezentare grafic, schemele logice se clasifică în două mari categorii: 1) liniare;

2) neliniare. La rîndul lor schemele logice neliniare pot fi: 3) neliniare propriu-zise sau 4) cu structuri repetitive. Ultima clasă de scheme logice poate să conţină următoarele tipuri de scheme logice:

5) cu structuri repetitive cu un număr fix (cunoscut) de paşi; 6) cu structuri repetitive cu un număr variabil (necunoscut) de paşi;cu structuri repetitive combinate.Observaţie. Criteriile de clasificare stabilite pentru schemele logice se aplică neschimbat şi în cazul reprezentării unui algoritm de rezolvare în limbajul pseudocod prin formulări standard. b1) Schemele logice liniare se întîlnesc mai puţin în practică şi sînt fie scheme logice de principiu, fie scheme logice de program care rezolvă probleme foarte simple, cum ar fi evaluarea unor expresii matematice. Singura structură de bază componentă este structura liniară. Pe lîngă operaţiile de intrare/ieşire, operaţiile de evaluare a unor expresii aritmetice şi logice formează baza activităţii unei scheme logice liniare.Aceste scheme logice nu conţin ramificaţii, întocmirea lor se face numai pe verticală, după cum se observă în exemplul prezentat în cele ce urmează. Exemplu 1. Fie expresiile: E1 = a2 + (b + c)i

E2 = (a + b + c3)5 – 5abcE3 = (E1 –E2)j - a2i + b/5.

Să se determine E1, E2 şi E3, ştiind că a, b, c, i şi j primesc ca valori numere reale. Deşi problema este foarte simplă se observă că , se pot evidenţia trei etape în rezolvarea ei: - prezentarea datelor cunoscute (adică, a, b, c, i şi j) calculatorului, în vederea depozitării lor în celule corespunzătoare de memorie şi utilizării lor în prelucrările ulterioare executate de calculator; - evaluarea celor trei expresii matematice; - cererea de afişare a rezultatelor. De asemenea se remarcă şi faptul că, ordinea de evaluare a celor trei expresii aritmetice nu este chiar oarecare, ci evaluarea expresiei E3 trebuie să succeadă pe cele cu privire la primele două.

În maniera de reprezentare prin blocuri, schema logică apare sub forma următoare:

8

START

E1=a2+(b+c)i

Citeşte a,b,c,i,j

Figura 2.3.1

Se observă că schema logică nu este unică. Pentru acest exerciţiu pot fi întocmite şi alte variante cum ar fi, schimbînd ordinea de evaluare a expresilor E1 şi E2 sau însoţind fiecare bloc de calcul cu un bloc de ieşire. b3) Schemele logice neliniare propriu-zise conţin cel puţin o structură alternativă. De asemenea, apar în mod frecvent structuri liniare şo operaţii de citire/scriere. Exemplu 2. Să se determine:

F =

≤+≤>+++

>>++−

.0,7

;00)/()5(

;00),/()5(

3

3

3

yxdacăxy

yşiyxdacăyxyx

yşiyxdacăyxyx

Etapele care se parcurg în aflarea valorii lui F sînt:- citirea valorilor variabililor x şi y;- determinarea lui F în funcţie de condiţiile impuse în enunţul problemei;- scrierea valorii lui F.Schema logică se reprezintă astfel :

9

START

E2=(a+b+c3)5+5abc

E3=(E1+E2)j-c2i+b/3

Scrie

STOP

- +

- +

Figura 2.3.2

b4) Schemele logice cu structuri repetitive sînt foarte des întîlnite în rezolvarea problemelor din orice domeniu de activitate şi dau sens existenţei lucrului pe calculator. Structura de bază componentă este structura repetitivă, fie cu un număr fix de paşi, fie cu un număr variabil de paşi, după cum este posibil faptul de a preciza sau nu numărul de reluări a unui anumit ansamblu de calcule care se efectuează în cadrul unui pas de rezolvare. În afara structurilor repetitive, în alcătuirea schemei logice pot interveni, de asemenea, un număr arbitrar de structuri liniare, structuri alternative şi operaţii de intrare/ieşire. b5) Am văzut că variabila care controlează o structură repetitivă cu un număr fix de paşi se numeşte contor. Acesta joacă un rol deosebit în structură, în sensul că poate îndeplini diverse atribuţii şi de modul cum este mînuit depinde siguranţa calculelor din corpul structurii repetitive.Elementele definitorii ale contorului rezultă din contextul problemei şi se referă la, prima valoare pe care o poate lua, ultima valoare care o poate atinge şi raţia cu care variază de la un pas la altul.Ştiind raţia de variaţie, se poate indica cu precizie lista valorilor primite de contor pe parcursul rezolvării unei structuri repetitive cu un număr fix de paşi. Incrementarea sau decrementarea contorului cu raţia dată se face în locul unde se pregăteşte pasul următor.Dintre celelalte funcţiuni ale contorului se amintesc:- participarea efectivă la calculele ce se fac într-un pas de rezolvare, cu condiţia ca să nu i se modifice valoarea;- precizarea unor valori pentru prelucrările care se fac în corpul structurii repetitive.Reprezentarea propiu-zisă a unei structuri repetitive cu un număr fix de paşi, prin blocuri sau prin formulări, nu este o sarcină dificilă dacă se reuşeşte delimitarea celor două elemente definitorii: - totalitatea operaţiilor ce formează corpul structurii repetitive, operaţii care se reiau de cel puţin două ori, cu valori diferite pentru variabilile cu care se lucrează;- contorul, împreună cu valorile ce-l caracterizează (valoarea iniţială, valoarea finală şi raţia de variaţie).

10

CITEŞTE x,

x+y

F=7xy3

y>0

F=(x3+5y)/(x+y)

F=(x3-5y)/(x+y)

SCRIE F

STOP

Avînd cele două elemente la dispoziţie, reprezentarea structurii repetitive, într-o formă sau alta, devine o muncă de rutină.Numărul structurilor repetitive cu un număr fix de paşi nu este limitat, acestea pot să apară separat, una după alta, sau imbricat, una în interiorul celeilalte. Dacă se notează cu s1i, cu i = k,1

, k fiind fixat, structurile repetitive cu un număr fix de paşi independente şi cu s2i, i = 7,1 , cele imbricate atunci, reprezentarea din figura 1.6.4 este corectă, ceea ce nu se întîmplă cu cea din figura 1.6.5.

S11

S1i

S2i

S1k

S27... S22 S21

Figura 2.3.3

Ordinea de execuţie, în figura 2.3.3, a structurilor repetitive cu un număr fix de paşi, de tipul s1i, i = k,1 , este cea naturală, iar a celor de tipul s2i, cu i = 7,1 , este din interior către exterior.Exemlu 3. Fie A = (aij)i,j=

n,1 o matrice de ordinul n cu elemente reale. Se cere: a) media aritmetică a elementelor strict pozitive din A;

b) numărul elementelor egale cu zero din A; c) produsul elementelor strict negative din A.Rezultatele se notează cu S, NZ şi respectiv P, iar cu i şi j indicii care fixează poziţia unui element generic din A. Numărul elementelor care intervin în media aritmetică se notează cu m. Valorile iniţiale ale variabililor S, NZ şi m sînt 0, iar a lui P este 1.Parcurgerea matricei A poate fi făcută, sistematic, în mai multe sensuri:- din colţul stînga sus către colţul dreapta jos în ordinea liniilor sau a coloanelor, indicii i şi j variind de la 1 pînă la n cu raţia 1; - din colţul dreapta jos către colţul stînga sus în ordinea liniilor sau a coloanelor, indicii i şi j variind de la n pînă la 1 cu raţia -1; - combinînd cele două sensuri de parcurgere prezentate mai sus.Fixînd un indice la o valoare anume din lista lui de variaţie şi impunînd ca celălalt indice să-şi parcurgă, în întregime, lista de valori, se obţine indiferent de sensul de parcurgere ales, o linie sau o coloană. Trecerea în revistă a tuturor valorilor pe care le ia indicele fixat, determină acoperirea în totalitate a matricei respective.În continuare, valorile variabililor de ieşire se obţin prin tratarea, pe rînd, a elementelor lui A, parcurgînd matricea, în ordinea liniilor, din colţul stînga sus către colţul dreapta jos. Cu fiecare element aij din A se execută operaţii similare, astfel:

- se compară aij cu zero;

11

- dacă elementul aij este strict pozitiv, atunci S creşte cu cantitatea aij (S = S + aij), iar m cu 1 (m = m + 1);

- dacă elementul aij este nul, atunci NZ se incrementează cu 1 (NZ=NZ+1); - dacă elementul aij este strict negativ, atunci P se înmulţeşte cu aij

(P = P * aij).În cadrul unei linii, aceste operaţii vor fi repetate de n ori, iar în cadrul matricei de n2 ori. Deci, structura de bază utilizată este cea repetitivă cu un număr fix de paşi.Deoarece indicele j fixează elementele pe linii, iar indicele i fixează liniile în matrice, aceştia pot fi utilizaţi drept contori în două structuri repetitive cu un număr fix de paşi. Aceste structuri repetitive sînt imbricate, cea interioară fiind gestionată de contorul j.În concluzie, etapele care se parcurg în rezolvarea exemplului 4 sînt:

- citirea matricei A;- iniţializarea variabililor intermediare şi de ieşire;- tratarea liniei i;- pentru o linie i, tratarea elementelor aij, cu j=

n,1 ;- scrierea rezultatelor (S, NZ şi P).

Reprezentarea grafică prin blocuri este dată în figura 2.3.4:

12

Start

Citeşte

S=0

1

j≤ 2

Figura 2.3.4

EXEMPLU 4. Să se afle numărul termenilor din şirul Fibonacci strict mai mici decît un număr dat M (M > 1).Termenii şirului Fibonacci se obţin printr-o lege de recurenţă de forma:

xi+1= xi + xi-1 , unde x0 = 0, x1 = 1 şi i = 2, 3, ... .Aplicînd legea de definire, termenii şirului Fibonacci pot fi generaţi uşor, cu ajutorul unui calculator, prin sumarea ultimilor doi termeni consecutivi cunoscuţi din şir. Astfel, şirul Fibonacci se prezintă după cum urmează:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... .În operaţiile care conduc la rezultatul căutat, I şi J vor desemna notaţiile generice ale termenilor consecutivi ce intră într-o sumare la un moment dat, K termenul care se generează la acel momentul, iar N variabila rezultat. Ţinînd cont că memoria este conservativă, generarea unui termen din şirul Fibonacci cuprinde două etape. În prima etapă se determină un termen din şir cu formula K=I+J, iar în a doua se pregăteşte terenul pentru generarea următorului termen din şir, schimbînd valorile locaţiilor de memorie afectate variabilelor I şi J prin atribuiri de forma I = J şi J = K. Iniţial, I = 0 şi J = 1. Deoarece primii doi termeni se cunosc şi cum aceştia sînt strict mai mici decît M (M >1), rezultă că N trebuie să se iniţializeze cu valoarea 2. Deci, fiecare pas de rezolvare cuprinde trei operaţii distincte :

- generarea unui termen nou (prima etapă ); - compararea termenului generat cu M;

13

NZ=0

P = 1

M = 0

i = 1

j = 1

aij

m=m+1

S=S+aij

aij

NZ=NZ+1

P=P.aij

j=j+1

1

2

i=i+1

i≤n

3

3

m

S=S/m

Scrie S

Scrie “N.E.M.”

Scrie P,NZ

Stop

- dacă termenul este strict mai mic decât M, atunci se operează cu N = N + 1 şi se execută a doua etapă. În caz contrar, se scrie rezultatul N. Se execută un număr mai mic sau mai mare de paşi în funcţie de valoarea lui M, dar cu siguranţă acest număr este finit deoarece şirul este pozitiv şi crescător.Schema logică se prezintă mai jos:

- +

Figura 2.3.5

14

Citeşte M

I = 0

J = 0

N = 2

K = I + J

K < M

N = N + 1

I = J

J = K

Scrie N

Stop