2.1 Conceptul de subalgoritm l6r15rs
Orice problema poate apare ca o subproblema S a unei probleme mai complexe C. Algoritmul de rezolvare a problemei S devine in acest caz un subalgoritm pentru algoritmul de rezolvare a problemei C.
Pentru a defini un subalgoritm vom folosi propozitia standard
SUBALGORITMUL nume (lpf) ESTE: unde nume este numele subalgoritmului definit, iar lpf este lista parametrilor formali. Acestia sunt formati din variabilele care marcheaza datele de intrare (cele presupuse cunoscute) si variabilele care marcheaza datele de iesire (rezultatele obtinute de subalgoritm).
Aceasta propozitie este urmata de textul efectiv al subalgoritmului, text care precizeaza calculele necesare rezolvarii subproblemei corespunzatoare. Descrierea se va incheia cu cuvantul SFSUBALGORITM sau SF-nume.
Dam ca exemplu un subalgoritm cu numele MAXIM, care gaseste maximul dintre componentele vectorului X = (x1,x2, ..., xn).
Datele cunoscute pentru acest subalgoritm sunt vectorul X si numarul n al componentelor vectorului X. Ca rezultat vom obtine maximul cerut, pe care-l vom nota cu max. Deci lista parametrilor formali contine trei variabile, n, X si max. Subalgoritmul este dat in continuare.
SUBALGORITMUL maxim(n,X,max) ESTE:
FIE max:=x1;
PENTRU i:=2;n EXECUTA
DACA xi>max ATUNCI max:=xi SFDACA
SFPENTRU
SF-maxim
In cadrul multor algoritmi este necesar calculul valorilor unei functii in diferite puncte. Este necesar sa definim functia printr-un subalgoritm de tip functie.
Pentru definirea unui subalgoritm de tip functie se foloseste un antet care precizeaza numele functiei si variabilele de care depinde ea. Subalgoritmul are forma:
FUNCTIA nume(lpf) ESTE: AAntetul functieiS text Acorpul functieiS
SF-nume Amarca de sfarsitS
In corpul functiei trebuie sa existe cel putin o atribuire in care numele functiei apare in partea stanga, deci prin care functia primeste o valoare.
Dam ca exemplu o functie numar : R --> A2,3,4,5S, definita matematic astfel:
In Pseudocod descrierea este urmatoarea:
FUNCTIA numar(x) ESTE:
DACA x<0.2 ATUNCI numar:=2 ALTFEL
DACA x<0.5 ATUNCI numar:=3 ALTFEL
DACA x<0.9 ATUNCI numar:=4
ALTFEL numar:=5
SFDACA
SFDACA
SFDACA
SF-numar

Am vazut ca definitia unei functii consta dintr?un antet si dintr?un bloc care va defini actiunile prin care se calculeaza valoarea functiei. In antet se precizeaza numele functiei si lista parametrilor formali.
In concluzie, exista doua categorii de subalgoritmi: de tip functie si subalgoritmi propriu-zisi, carora li se mai spune si proceduri. Importanta lor va fi subliniata prin toate exemplele care urmeaza in acest curs. In incheiere mentionam ca subprogramele de tip functie se folosesc in scopul definirii functiilor, asa cum sunt cunoscute ele din matematica, in timp ce subalgoritmii de tip procedura se refera la rezolvarea unor probleme ce apar ca subprobleme, fiind algoritmi de sine statatori.

2.2 Apelul unui subalgoritm
Am vazut ca un subalgoritm este dedicat rezolvarii unei subprobleme S a unei probleme mai complexe C. Algoritmul corespunzator problemei C va folosi toate operatiile necesare rezolvarii problemei S, deci va folosi ca parte intregul subalgoritm conceput pentru rezolvarea subproblemei S. Spunem ca el va apela acest subalgoritm.
In Pseudocod apelul unei functii se face scriind intr?o expresie numele functiei urmat de lista parametrilor actuali. Trebuie sa existe o corespondenta biunivoca intre parametrii actuali si cei formali folositi in definitia functiei. Desi denumirile variabilelor din cele doua liste pot sa difere, rolul variabilelor care se corespund este acelasi. Mai exact, parametrul formal si parametrul actual corespunzator trebuie sa se refere la aceeasi entitate, trebuie sa aiba aceeasi semnificatie, sa reprezinte aceeasi structura de date. Putem considera ca in timpul executiei algoritmului cei doi parametri devin identici.
Folosirea unui subalgoritm in cadrul unui algoritm se face apeland acest subalgoritm prin propozitia standard CHEAMA nume (lpa); unde nume este numele subalgoritmului apelat iar lpa este lista parametrilor actuali. Aceasta lista contine toate datele de intrare (cele cunoscute in subproblema corespunzatoare) si toate rezultatele obtinute in subalgoritm. Si in acest caz intre lista parametrilor formali din definitia subalgoritmului si lista parametrilor actuali din propozitia de apel trebuie sa existe o corespondenta biunivoca, ca si in cazul functiilor. Ca o prima verificare a respectarii acestei corespondente, subliniem ca numarul parametrilor actuali trebuie sa coincida cu numarul parametrilor formali.
Ca exemplu de apelare a functiilor, dam in continuare un program pentru a calcula a cata zi din anul curent este ziua curenta (zi,luna,an). El foloseste un subprogram de tip functie pentru a obtine numarul zilelor lunii cu numarul de ordine i si un altul pentru a verifica daca un an este bisect sau nu. Aceste doua functii sunt:
- NRZILE(i) furnizeaza numarul zilelor existente in luna i a unui an nebisect;
- BISECT(an) adevarata daca anul dintre paranteze este bisect.
Algoritmul este urmatorul:
ALGORITMUL NUMARAZILE ESTE:
CITESTE zi, luna, an;
FIE nr:=zi;
DACA luna>1 ATUNCI
PENTRU i:=1, Luna-1 EXECUTA nr:=nr+NRZILE(i) SFPENTRU
SFDACA
DACA luna>2 ATUNCI
DACA BISECT(an) ATUNCI nr:=nr+1 SFDACA
SFDACA
TIPARESTE nr;
SFALGORITM

Sa observam ca in proiectarea acestui algoritm nu este necesar sa cunoastem textul subalgoritmilor folositi, ci doar specificarea acestor subalgoritmi, numele lor si lista parametrilor formali. La acest nivel accentul trebuie sa cada pe proiectarea algoritmului care apeleaza, urmand sa se revina ulterior la proiectarea subalgoritmilor apelati, conform specificatiei acestora. In cazul de fata este necesara descrierea functiilor NRZILE(i) si BISECT(an). Lasam aceasta descriere ca tema pentru cititor.
Ca exemplu de apelare a unei proceduri vom scrie mai jos o procedura care efectueaza suma a doua polinoame.
Un polinom P(X) este dat prin gradul sau, m, si prin vectorul coeficientilor P = (p0, p1, ..., pm) (prin pi s-a notat coeficientul lui Xi).
Procedura SUMAPOL(m,P,n,Q,r,S) trebuie sa 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 in subalgoritm. Pentru efectuarea ei este utila o alta procedura care aduna la suma S(X) un alt polinom, T(X), de grad mai mic sau egal decat gradul polinomului S(X). O astfel de procedura se da in continuare.

SUBALGORITMUL SUMAPOL1(n,T,r,S) ESTE: An £ rS
AS(X):=S(X)+T(X)S
PENTRU i:=0;n EXECUTA si := si+ti
SFPENTRU
SF-SUMAPOL1
Subalgoritmul SUMAPOL apeleaza acest subalgoritm, asa cum se poate vedea in continuare.
SUBALGORITMUL SUMAPOL(m,P,n,Q,r,S) ESTE: AS(X):=P(X)+Q(X)S
DACA m<n
ATUNCI r:=n; S:=Q;
CHEAMA SUMAPOL1(m,P,r,S)
ALTFEL r:=m; S:=P;
CHEAMA SUMAPOL1(n,Q,r,S)
SFDACA
SF-SUMAPOL
Sa observam ca in textul acestui subalgoritm am extins semnificatia propozitiei de atribuire, permitand atribuirea S:=Q. Acest lucru este normal intrucat S noteaza un polinom, iar Q este un polinom cunoscut; prin atribuire S primeste o valoare initiala, cea data de polinomul Q.
Subliniem ca atribuirea v := u va fi corecta in cazul in care variabilele u si v reprezinta aceleasi obiecte matematice, deci au aceeasi semnificatie.

2.3 Alte exemple
Ca un al doilea exemplu de definire si folosire a subalgoritmilor, sa consideram urmatoarea problema:
Se dau trei multimi de numere:
A = A a1, a2, ... , am S
B = A b1, b2, ... , bn S
C = A c1, c2, ... , cp S
Se cere sa se tipareasca in ordine crescatoare elementele fiecarei multimi, precum si a multimilor A U B, B U C, C U A.
In rezolvarea acestei probleme se intalnesc urmatoarele subprobleme:
S1: Sa se citeasca elementele unei multimi;
S2: Sa se efectueze reuniunea a doua multimi;
S3: Sa se tipareasca elementele unei multimi;
S4: Sa se ordoneze crescator elementele unei multimi.
Presupunand ca 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 specificati mai jos (la locul definirii lor) prin comentarii, algoritmul de rezolvare a problemei de mai sus este dat in continuare. Intrucat operatiile respective se folosesc de mai multe ori (de 3 ori), am definit un subalgoritm TIPORDON(m,A) care ordoneaza mai intai elementele multimii A si apoi le tipareste.
ALGORITMUL OPER?MULTIMI ESTE: A A6: Subalgoritmi S
CHEAMA CITMUL(m,A);
CHEAMA CITMUL(n,B);
CHEAMA CITMUL(p,C);
CHEAMA TIPORDON(m,A);
CHEAMA TIPORDON(n,B);
CHEAMA TIPORDON(p,C);
CHEAMA REUNIUNE(m,A,n,B,k,R);
CHEAMA TIPORDON(k,R);
CHEAMA REUNIUNE(n,B,p,C,k,R);
CHEAMA TIPORDON(k,R);
CHEAMA REUNIUNE(p,C,m,A,k,R);
CHEAMA TIPORDON(k,R);
SFALGORITM

Subalgoritmii apelati mai sus sunt definiti in continuare.

SUBALGORITMUL CITMUL(n,M) ESTE: ACiteste n si MS
CITESTE n; An=nr. elementelor multimiiS
CITESTE (mi,i=1,n); AM=multimea cu elementele m1,m2,...,mnS
SF?CITMUL

SUBALGORITMUL ORDON(n,M) ESTE: AOrdoneaza crescator cele nS
REPETA Aelemente ale multimii MS
FIE ind:=0; ACazul M este ordonataS
PENTRU i:=1;n?1 EXECUTA
DACA mi>mi+1 ATUNCI Aschimba ordinea celorS
FIE t := mi; Adoua elementeS mi:=mi+1; mi+1:=t; ind:=1; ACazul M nu era ordonataS
SFDACA
SFPENTRU
PANACAND ind=0 SFREP
SF-ORDON
SUBALGORITMUL REUNIUNE(m,A,n,B,k,R) ESTE: A R := A U B S
A k = numarul elementelor multimii R S
FIE k:=m; R := A;
PENTRU j:=1,n EXECUTA
FIE ind:=0; AIpoteza bj nu e in AS
PENTRU i:=1;m EXECUTA
DACA bj=ai ATUNCI ind:=1 Abj este in AS SFDACA
SFPENTRU
DACA ind=0 ATUNCI k:=k+1; rk:=bj SFDACA
SFPENTRU
SF?REUNIUNE
SUBALGORITMUL TIPMUL(n,M) ESTE: A Tipareste cele n elemente S
PENTRU i:=1;n EXECUTA A ale multimii M S
TIPARESTE mi
SFPENTRU
SF?TIPMUL

SUBALGORITMUL TIPORDON(n,M) ESTE: A Ordoneaza si tipareste S
CHEAMA ORDON(n,M); A elementele multimii M S
CHEAMA TIPMUL(n,M);
SF?TIPORDON
Tot ca exemplu de folosire a subalgoritmilor, vom scrie un algoritm pentru rezolvarea urmatoarei probleme: dirigintele unei clase de elevi doreste sa obtina un clasament al elevilor in functie de media generala. In plus, pentru fiecare disciplina in parte doreste lista primilor sase elevi.
In rezolvarea acestei probleme este necesara gasirea ordinii in care trebuiesc tipariti elevii in functie de un anumit rezultat: nota la disciplina "j", sau media generala. Am identificat prin urmare doua subprobleme independente, referitoare la:

(1) aflarea ordinii in care trebuie tiparite n numere pentru a le obtine ordonate;
(2) tiparirea elevilor clasei intr?o anumita ordine.
Prima subproblema se poate specifica astfel:
Dandu?se numerele x1, x2, ... , xn, gasiti ordinea o1, o2, ..., on, in care aceste numere devin ordonate descrescator, adica xao1i ³ xao2i ³ ... xaoni .
Pentru rezolvarea ei vom da un subalgoritm ORDINE in care intervin trei parametri formali:
? n, numarul valorilor existente;
? X, vectorul acestor valori;
? O, vectorul indicilor care dau ordinea dorita.
Primii doi parametri marcheaza datele presupuse cunoscute, iar al treilea, rezultatele calculate de subalgoritm.
SUBALGORITMUL ORDINE(n,X,O) ESTE:
An, numarul valorilor existenteS
AX, vectorul acestor valoriS
AO, vectorul indicilor care dau ordinea doritaS
PENTRU i:=1; n EXECUTA oi :=i SFPENTRU
REPETA ind:=0;
PENTRU i:=1;n?1 EXECUTA
DACA xaoii < xaoi+1i ATUNCI
FIE ind:=1; t:=oi+1 ; oi+1 :=oi; oi :=t;
SFDACA
SFPENTRU
PANACAND ind=0 SFREP
SF?ORDINE
A doua subproblema se poate specifica astfel:
Dandu?se ordinea o1,o2, ..., on, a elevilor clasei, numele si mediile acestora, sa se tipareasca numele si mediile primilor k elevi in ordinea specificata.
Subalgoritmul TIPAR, dat in continuare, rezolva aceasta problema.
SUBALGORITMUL TIPAR(k, NUME, O) ESTE:
PENTRU i:=1;k EXECUTA
Tipareste datele elevului de rang oi.
SFPENTRU
SF?TIPAR
Variabilele folosite pentru problema data sunt urmatoarele:
? n reprezinta numarul elevilor clasei;
? m este numarul disciplinelor la care elevii primesc note;
? NUME este vectorul care retine numele elevilor: NUMEi este numele elevului cu numarul de ordine i;
? NOTE este matricea notelor elevilor, avand n linii si m coloane;
NOTEi,j este nota elevului cu numele NUMEi la disciplina cu numarul de ordine j;
NOTE.j este coloana a j?a a matricei NOTE si reprezinta notele elevilor la disciplina j;
? MEDII este vectorul mediilor generale.
Algoritmul se da in continuare:
ALGORITMUL CLASAMENT ESTE: A Algoritmul 7: Ordonare S
CITESTE m, Anumarul disciplinelor siS n, Aal elevilorS
NUMEi, i=1,n, Anumele elevilorS
NOTEi,j, j=1,m, i=1,n; Anotele elevilorS
PENTRU i:=1;n EXECUTA A calculeaza media generalaS
FIE S:=0; Aa elevului iS
PENTRU j:=1;m EXECUTA S:=S+NOTEi,j SFPENTRU
FIE MEDIIi:=S/m
SFPENTRU
CHEAMA ORDINE(n,MEDII,O);
CHEAMA TIPAR(n,NUME,O)
PENTRU j:=1;m EXECUTA
CHEAMA ORDINE(n,NOTE.j,O);
CHEAMA TIPAR(6,NUME,O);
SFPENTRU
SF?ALGORITM
2.4 Apel recursiv
In exemplele date se observa ca apelul unui subprogram se face dupa ce el a fost definit. Este insa posibil ca un subalgoritm sa se apeleze pe el insusi. Intr-un astfel de caz spunem ca apelul este recursiv, iar subalgoritmul respectiv este definit recursiv.
Ca exemplu, definim in continuare o functie care calculeaza recursiv valoarea n!. Se va folosi formula n! = n.(n?1)! in cazul n>0 si faptul ca 0!=1. Recursivitatea consta in faptul ca in definitia functiei Factorial de n se foloseste aceeasi functie Factorial dar de argument n-1. Deci functia Factorial se apeleaza pe ea insasi. Este important ca numarul apelurilor sa fie finit, deci ca procedeul de calcul descris sa se termine.
FUNCTIA Factorial(n) ESTE:
DACA n=0 ATUNCI Factorial:=1
ALTFEL Factorial:= n*Factorial(n?1)
SFDACA
SF-Factorial;
Tot ca exemplu de apel recursiv putem descrie o functie ce calculeaza maximul a n numere x1,x2,...,xn . Ea se bazeaza pe functia MAXIM2 care calculeaza maximul a doua numere, descrisa in continuare.
FUNCTIA MAXIM2(a,b) ESTE:
DACA a<b ATUNCI MAXIM2:=b
ALTFEL MAXIM2:=a
SFDACA
SF-MAXIM2
Functia MAXIM, care calculeaza maximul celor n numere este urmatoarea:
FUNCTIA MAXIM(n,X) ACalculeaza maximul a n numereS
ESTE: AX=vectorul cu numerele dateS
DACA n=1
ATUNCI MAXIM:=x1
ALTFEL MAXIM:=MAXIM2( MAXIM(n-1,X), xn)
SFDACA
SF-MAXIM