|
nicoletast89
Administrator
Inregistrat: acum 20 ani
Postari: 104
|
|
CAPITOLUL AL II-LEA.
SUBALGORITMI
2.1 Conceptul de subalgoritm
Orice problemă poate apare ca o subproblemă S a unei probleme mai complexe C. Algoritmul de rezolvare a problemei S devine în acest caz un subalgoritm pentru algoritmul de rezolvare a problemei C.
Pentru a defini un subalgoritm vom folosi propoziţia standard
SUBALGORITMUL nume (lpf) ESTE:
unde nume este numele subalgoritmului definit, iar lpf este lista parametrilor formali. Aceştia sunt formaţi din variabilele care marchează datele de intrare (cele presupuse cunoscute) şi variabilele care marchează datele de ieşire (rezultatele obţinute de subalgoritm).
Această propoziţie este urmată de textul efectiv al subalgoritmului, text care precizează calculele necesare rezolvării subproblemei corespunzătoare. Descrierea se va încheia cu cuvântul SFSUBALGORITM sau SF-nume.
Dăm ca exemplu un subalgoritm cu numele MAXIM, care găseşte maximul dintre componentele vectorului X = (x1,x2, ..., xn).
Datele cunoscute pentru acest subalgoritm sunt vectorul X şi numărul n al componentelor vectorului X. Ca rezultat vom obţine maximul cerut, pe care-l vom nota cu max. Deci lista parametrilor formali conţine trei variabile, n, X şi max. Subalgoritmul este dat în continuare.
SUBALGORITMUL maxim(n,X,max) ESTE:
FIE max:=x1;
PENTRU i:=2;n EXECUTĂ
DACĂ xi>max ATUNCI max:=xi SFDACĂ
SFPENTRU
SF-maxim
ÃŽn cadrul multor algoritmi este necesar calculul valorilor unei funcţii în diferite puncte. Este necesar să definim funcţia printr-un subalgoritm de tip funcţie.
Pentru definirea unui subalgoritm de tip funcţie se foloseşte un antet care precizează numele funcţiei şi variabilele de care depinde ea. Subalgoritmul are forma:
FUNCŢIA nume(lpf) ESTE: {Antetul funcţiei}
text {corpul funcţiei}
SF-nume {marca de sfârşit}
ÃŽn corpul funcţiei trebuie să existe cel puţin o atribuire în care numele funcţiei apare în partea stângă, deci prin care funcţia primeşte o valoare.
Dăm ca exemplu o funcţie numar : R --> {2,3,4,5}, definită matematic astfel:
ÃŽn Pseudocod descrierea este următoarea:
FUNCŢIA numar(x) ESTE:
DACĂ x<0.2 ATUNCI numar:=2 ALTFEL
DACĂ x<0.5 ATUNCI numar:=3 ALTFEL
DACĂ x<0.9 ATUNCI numar:=4
ALTFEL numar:=5
SFDACĂ
SFDACĂ
SFDACĂ
SF-numar
Am văzut că definiţia unei funcţii constă dintr un antet şi dintr un bloc care va defini acţiunile prin care se calculează valoarea funcţiei. ÃŽn antet se precizează numele funcţiei şi lista parametrilor formali.
ÃŽn concluzie, există două categorii de subalgoritmi: de tip funcţie şi subalgoritmi propriu-zişi, cărora li se mai spune şi proceduri. Importanţa lor va fi subliniată prin toate exemplele care urmează în acest curs. ÃŽn încheiere menţionăm că subprogramele de tip funcţie se folosesc în scopul definirii funcţiilor, aşa cum sunt cunoscute ele din matematică, în timp ce subalgoritmii de tip procedură se referă la rezolvarea unor probleme ce apar ca subprobleme, fiind algoritmi de sine stătători.
2.2 Apelul unui subalgoritm
Am văzut că un subalgoritm este dedicat rezolvării unei subprobleme S a unei probleme mai complexe C. Algoritmul corespunzător problemei C va folosi toate operaţiile necesare rezolvării problemei S, deci va folosi ca parte întregul subalgoritm conceput pentru rezolvarea subproblemei S. Spunem că el va apela acest subalgoritm.
ÃŽn Pseudocod apelul unei funcţii se face scriind într o expresie numele funcţiei urmat de lista parametrilor actuali. Trebuie să existe o corespondenţă biunivocă între parametrii actuali şi cei formali folosiţi în definiţia funcţiei. Deşi denumirile variabilelor din cele două liste pot să difere, rolul variabilelor care se corespund este acelaşi. Mai exact, parametrul formal şi parametrul actual corespunzător trebuie să se refere la aceeaşi entitate, trebuie să aibă aceeaşi semnificaţie, să reprezinte aceeaşi structură de date. Putem considera că în timpul execuţiei algoritmului cei doi parametri devin identici.
Folosirea unui subalgoritm în cadrul unui algoritm se face apelând acest subalgoritm prin propoziţia standard CHEAMĂ nume (lpa);
unde nume este numele subalgoritmului apelat iar lpa este lista parametrilor actuali. Această listă conţine toate datele de intrare (cele cunoscute în subproblema corespunzătoare) şi toate rezultatele obţinute în subalgoritm. Şi în acest caz între lista parametrilor formali din definiţia subalgoritmului şi lista parametrilor actuali din propoziţia de apel trebuie să existe o corespondenţă biunivocă, ca şi în cazul funcţiilor. Ca o primă verificare a respectării acestei corespondenţe, subliniem că numărul parametrilor actuali trebuie să coincidă cu numărul parametrilor formali.
Ca exemplu de apelare a funcţiilor, dăm în continuare un program pentru a calcula a câta zi din anul curent este ziua curentă (zi,luna,an). El foloseşte un subprogram de tip funcţie pentru a obţine numărul zilelor lunii cu numărul de ordine i şi un altul pentru a verifica dacă un an este bisect sau nu. Aceste două funcţii sunt:
- NRZILE(i) furnizează numărul zilelor existente în luna i a unui an nebisect;
- BISECT(an) adevărată dacă anul dintre paranteze este bisect.
Algoritmul este următorul:
ALGORITMUL NUMĂRĂZILE ESTE:
CITEŞTE zi, luna, an;
FIE nr:=zi;
DACĂ luna>1 ATUNCI
PENTRU i:=1, Luna-1 EXECUTĂ nr:=nr+NRZILE(i) SFPENTRU
SFDACĂ
DACĂ luna>2 ATUNCI
DACĂ BISECT(an) ATUNCI nr:=nr+1 SFDACĂ
SFDACĂ
TIPĂREŞTE nr;
SFALGORITM
Să observăm că în proiectarea acestui algoritm nu este necesar să cunoaştem textul subalgoritmilor folosiţi, ci doar specificarea acestor subalgoritmi, numele lor şi lista parametrilor formali. La acest nivel accentul trebuie să cadă pe proiectarea algoritmului care apelează, urmând să se revină ulterior la proiectarea subalgoritmilor apelaţi, conform specificaţiei acestora. ÃŽn cazul de faţă este necesară descrierea funcţiilor NRZILE(i) şi BISECT(an). Lăsăm această descriere ca temă pentru cititor.
Ca exemplu de apelare a unei proceduri vom scrie mai jos o procedură care efectuează suma a două polinoame.
Un polinom P(X) este dat prin gradul său, m, şi prin vectorul coeficienţilor P = (p0, p1, ..., pm) (prin pi s-a notat coeficientul lui Xi).
Procedura SUMAPOL(m,P,n,Q,r,S) trebuie să efectueze suma S(X) = P(X)+Q(X),
unde P este un polinom de gradul m, iar Q este un polinom de gradul n, date. Suma lor, S, va fi un polinom de gradul r calculat în subalgoritm. Pentru efectuarea ei este utilă o altă procedură care adună la suma S(X) un alt polinom, T(X), de grad mai mic sau egal decât gradul polinomului S(X). O astfel de procedură se dă în continuare.
SUBALGORITMUL SUMAPOL1(n,T,r,S) ESTE: {n r}
{S(X):=S(X)+T(X)}
PENTRU i:=0;n EXECUTĂ
si := si+ti
SFPENTRU
SF-SUMAPOL1
Subalgoritmul SUMAPOL apelează acest subalgoritm, aşa cum se poate vedea în continuare.
SUBALGORITMUL SUMAPOL(m,P,n,Q,r,S) ESTE: {S(X):=P(X)+Q(X)}
DACĂ m<n
ATUNCI r:=n; S:=Q;
CHEAMĂ SUMAPOL1(m,P,r,S)
ALTFEL r:=m; S:=P;
CHEAMĂ SUMAPOL1(n,Q,r,S)
SFDACĂ
SF-SUMAPOL
Să observăm că în textul acestui subalgoritm am extins semnificaţia propoziţiei de atribuire, permiţând atribuirea S:=Q. Acest lucru este normal întrucât S notează un polinom, iar Q este un polinom cunoscut; prin atribuire S primeşte o valoare iniţială, cea dată de polinomul Q.
Subliniem că atribuirea v := u
va fi corectă în cazul în care variabilele u şi v reprezintă aceleaşi obiecte matematice, deci au aceeaşi semnificaţie.
2.3 Alte exemple
Ca un al doilea exemplu de definire şi folosire a subalgoritmilor, să considerăm următoarea problemă:
Se dau trei mulţimi de numere:
A = { a1, a2, ... , am }
B = { b1, b2, ... , bn }
C = { c1, c2, ... , cp }
Se cere să se tipărească în ordine crescătoare elementele fiecărei mulţimi, precum şi a mulţimilor A U B, B U C, C U A.
ÃŽn rezolvarea acestei probleme se întâlnesc următoarele subprobleme:
S1: Să se citească elementele unei mulţimi;
S2: Să se efectueze reuniunea a două mulţimi;
S3: Să se tipărească elementele unei mulţimi;
S4: Să se ordoneze crescător elementele unei mulţimi.
Presupunând că pentru rezolvarea acestor subprobleme am conceput subalgoritmii:
CITMUL(m,A);
REUNIUNE(m,A,n,B,k,R);
TIPMUL(m,A);
ORDON(m,A);
care sunt specificaţi mai jos (la locul definirii lor) prin comentarii, algoritmul de rezolvare a problemei de mai sus este dat în continuare. ÃŽntrucât operaţiile respective se folosesc de mai multe ori (de 3 ori), am definit un subalgoritm TIPORDON(m,A) care ordonează mai întâi elementele mulţimii A şi apoi le tipăreşte.
ALGORITMUL OPER MULTIMI ESTE: { A6: Subalgoritmi }
CHEAMĂ CITMUL(m,A);
CHEAMĂ CITMUL(n,B);
CHEAMĂ CITMUL(p,C);
CHEAMĂ TIPORDON(m,A);
CHEAMĂ TIPORDON(n,B);
CHEAMĂ TIPORDON(p,C);
CHEAMĂ REUNIUNE(m,A,n,B,k,R);
CHEAMĂ TIPORDON(k,R);
CHEAMĂ REUNIUNE(n,B,p,C,k,R);
CHEAMĂ TIPORDON(k,R);
CHEAMĂ REUNIUNE(p,C,m,A,k,R);
CHEAMĂ TIPORDON(k,R);
SFALGORITM
Subalgoritmii apelaţi mai sus sunt definiţi în continuare.
SUBALGORITMUL CITMUL(n,M) ESTE: {Citeşte n şi M}
CITEŞTE n; {n=nr. elementelor mulţimii}
CITEŞTE (mi,i=1,n); {M=mulţimea cu elementele m1,m2,...,mn}
SF CITMUL
SUBALGORITMUL ORDON(n,M) ESTE: {Ordonează crescător cele n}
REPETĂ {elemente ale mulţimii M}
FIE ind:=0; {Cazul M este ordonată}
PENTRU i:=1;n 1 EXECUTĂ
DACĂ mi>mi+1 ATUNCI {schimbă ordinea celor}
FIE t := mi; {două elemente}
mi:=mi+1; mi+1:=t;
ind:=1; {Cazul M nu era ordonată}
SFDACĂ
SFPENTRU
PÂNĂCÂND ind=0 SFREP
SF-ORDON
SUBALGORITMUL REUNIUNE(m,A,n,B,k,R) ESTE: { R := A U B }
{ k = numărul elementelor mulţimii R }
FIE k:=m; R := A;
PENTRU j:=1,n EXECUTĂ
FIE ind:=0; {Ipoteza bj nu e in A}
PENTRU i:=1;m EXECUTĂ
DACĂ bj=ai ATUNCI ind:=1 {bj este in A} SFDACĂ
SFPENTRU
DACĂ ind=0 ATUNCI k:=k+1; rk:=bj SFDACĂ
SFPENTRU
SF REUNIUNE
SUBALGORITMUL TIPMUL(n,M) ESTE: { Tipăreşte cele n elemente }
PENTRU i:=1;n EXECUTĂ { ale mulţimii M }
TIPĂREŞTE mi
SFPENTRU
SF TIPMUL
SUBALGORITMUL TIPORDON(n,M) ESTE: { Ordonează şi tipăreşte }
CHEAMĂ ORDON(n,M); { elementele mulţimii M }
CHEAMĂ TIPMUL(n,M);
SF TIPORDON
Tot ca exemplu de folosire a subalgoritmilor, vom scrie un algoritm pentru rezolvarea următoarei probleme:
dirigintele unei clase de elevi doreşte să obţină un clasament al elevilor în funcţie de media generală. ÃŽn plus, pentru fiecare disciplină în parte doreşte lista primilor şase elevi.
ÃŽn rezolvarea acestei probleme este necesară găsirea ordinii în care trebuiesc tipăriţi elevii în funcţie de un anumit rezultat: nota la disciplina "j", sau media generală. Am identificat prin urmare două subprobleme independente, referitoare la:
(1) aflarea ordinii în care trebuie tipărite n numere pentru a le obţine ordonate;
(2) tipărirea elevilor clasei într o anumită ordine.
Prima subproblemă se poate specifica astfel:
Dându se numerele x1, x2, ... , xn, găsiţi ordinea o1, o2, ..., on, în care aceste numere devin ordonate descrescător, adică
x[o1] x[o2] ... x[on] .
Pentru rezolvarea ei vom da un subalgoritm ORDINE în care intervin trei parametri formali:
n, numărul valorilor existente;
X, vectorul acestor valori;
O, vectorul indicilor care dau ordinea dorită.
Primii doi parametri marchează datele presupuse cunoscute, iar al treilea, rezultatele calculate de subalgoritm.
SUBALGORITMUL ORDINE(n,X,O) ESTE:
{n, numărul valorilor existente}
{X, vectorul acestor valori}
{O, vectorul indicilor care dau ordinea dorită}
PENTRU i:=1; n EXECUTĂ oi :=i SFPENTRU
REPETĂ ind:=0;
PENTRU i:=1;n 1 EXECUTĂ
DACĂ x[oi] < x[oi+1] ATUNCI
FIE ind:=1; t:=oi+1 ;
oi+1 :=oi; oi :=t;
SFDACĂ
SFPENTRU
PANÂCÂND ind=0 SFREP
SF ORDINE
A doua subproblemă se poate specifica astfel:
Dându se ordinea o1,o2, ..., on, a elevilor clasei, numele şi mediile acestora, să se tipărească numele şi mediile primilor k elevi în ordinea specificată.
Subalgoritmul TIPAR, dat în continuare, rezolvă această problemă.
SUBALGORITMUL TIPAR(k, NUME, O) ESTE:
PENTRU i:=1;k EXECUTĂ
Tipăreşte datele elevului de rang oi.
SFPENTRU
SF TIPAR
Variabilele folosite pentru problema dată sunt următoarele:
n reprezintă numărul elevilor clasei;
m este numărul disciplinelor la care elevii primesc note;
NUME este vectorul care reţine numele elevilor: NUMEi este numele elevului cu numărul de ordine i;
NOTE este matricea notelor elevilor, având n linii şi m coloane;
NOTEi,j este nota elevului cu numele NUMEi la disciplina cu numărul de ordine j;
NOTE.j este coloana a j a a matricei NOTE şi reprezintă notele elevilor la disciplina j;
MEDII este vectorul mediilor generale.
Algoritmul se dă în continuare:
ALGORITMUL CLASAMENT ESTE: { Algoritmul 7: Ordonare }
CITEŞTE m, {numărul disciplinelor şi}
n, {al elevilor}
NUMEi, i=1,n, {numele elevilor}
NOTEi,j, j=1,m, i=1,n; {notele elevilor}
PENTRU i:=1;n EXECUTĂ { calculează media generală}
FIE S:=0; {a elevului i}
PENTRU j:=1;m EXECUTĂ S:=S+NOTEi,j SFPENTRU
FIE MEDIIi:=S/m
SFPENTRU
CHEAMĂ ORDINE(n,MEDII,O);
CHEAMĂ TIPAR(n,NUME,O)
PENTRU j:=1;m EXECUTĂ
CHEAMĂ ORDINE(n,NOTE.j,O);
CHEAMĂ TIPAR(6,NUME,O);
SFPENTRU
SF ALGORITM
2.4 Apel recursiv
ÃŽn exemplele date se observă că apelul unui subprogram se face după ce el a fost definit. Este însă posibil ca un subalgoritm să se apeleze pe el însuşi. ÃŽntr-un astfel de caz spunem că apelul este recursiv, iar subalgoritmul respectiv este definit recursiv.
Ca exemplu, definim în continuare o funcţie care calculează recursiv valoarea n!. Se va folosi formula n! = n.(n 1)! în cazul n>0 şi faptul că 0!=1. Recursivitatea constă în faptul că în definiţia funcţiei Factorial de n se foloseşte aceeaşi funcţie Factorial dar de argument n-1. Deci funcţia Factorial se apelează pe ea însăşi. Este important ca numărul apelurilor să fie finit, deci ca procedeul de calcul descris să se termine.
FUNCTIA Factorial(n) ESTE:
DACĂ n=0 ATUNCI Factorial:=1
ALTFEL Factorial:= n*Factorial(n 1)
SFDACĂ
SF-Factorial;
Tot ca exemplu de apel recursiv putem descrie o funcţie ce calculează maximul a n numere x1,x2,...,xn . Ea se bazează pe funcţia MAXIM2 care calculează maximul a două numere, descrisă în continuare.
FUNCŢIA MAXIM2(a,b) ESTE:
DACĂ a<b ATUNCI MAXIM2:=b
ALTFEL MAXIM2:=a
SFDACĂ
SF-MAXIM2
Funcţia MAXIM, care calculează maximul celor n numere este următoarea:
FUNCŢIA MAXIM(n,X) {Calculează maximul a n numere}
ESTE: {X=vectorul cu numerele date}
DACĂ n=1
ATUNCI MAXIM:=x1
ALTFEL MAXIM:=MAXIM2( MAXIM(n-1,X), xn)
SFDACĂ
SF-MAXIM
|
|
