Subalgoritmi

SUBALGORITMI

1 Conceptul de subalgoritm

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 = (x₁,x₂, , x_n).

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:=x₁;

PENTRU i:=2;n EXECUTA

DACA x_i>max ATUNCI max:=x_i 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:

text

SF-nume  

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 --> , 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 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 = (p₀, p₁, , p_m) (prin p_i s-a notat coeficientul lui Xⁱ).

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:   

PENTRU i:=0;n EXECUTA

s_i := s_i+t_i

SFPENTRU

SF-SUMAPOL1

Subalgoritmul SUMAPOL apeleaza acest subalgoritm, asa cum se poate vedea in continuare.

SUBALGORITMUL SUMAPOL(m,P,n,Q,r,S) ESTE:

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.

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 =

B =

C =

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:

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:  

CITESTE n;   

CITESTE (m_i,i=1,n);

SF‑CITMUL

SUBALGORITMUL ORDON(n,M) ESTE:   

REPETA

FIE ind:=0;

PENTRU i:=1;n‑1 EXECUTA

DACA m_i>m_i+1 ATUNCI

FIE t := m_i;

m_i:=m_i+1; m_i+1:=t;

ind:=1;

SFDACA

SFPENTRU

PANACAND ind=0 SFREP

SF-ORDON

SUBALGORITMUL REUNIUNE(m,A,n,B,k,R) ESTE:

FIE k:=m; R := A;

PENTRU j:=1,n EXECUTA

FIE ind:=0;

PENTRU i:=1;m EXECUTA

DACA b_j=a_i ATUNCI ind:=1 SFDACA

SFPENTRU

DACA ind=0 ATUNCI k:=k+1; r_k:=b_j SFDACA

SFPENTRU

SF‑REUNIUNE

SUBALGORITMUL TIPMUL(n,M) ESTE:

PENTRU i:=1;n EXECUTA

TIPARESTE m_i

SFPENTRU

SF‑TIPMUL

SUBALGORITMUL TIPORDON(n,M) ESTE:   

CHEAMA ORDON(n,M);   

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 x₁, x₂, , x_n, gasiti ordinea o₁, o₂, , o_n, in care aceste numere devin ordonate descrescator, adica

x[o₁] x[o₂] x[o_n] .

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:

PENTRU i:=1; n EXECUTA o_i :=i SFPENTRU

REPETA ind:=0;

PENTRU i:=1;n‑1 EXECUTA

DACA x[o_i] < x[o_i+1] ATUNCI

FIE ind:=1; t:=o_i+1 ;

o_i+1 :=o_i; o_i :=t;

SFDACA

SFPENTRU

PANACAND ind=0 SFREP

SF‑ORDINE

A doua subproblema se poate specifica astfel:

Dandu‑se ordinea o₁,o₂, , o_n, 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 o_i.

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: NUME_i este numele elevului cu numarul de ordine i;

‑ NOTE este matricea notelor elevilor, avand n linii si m coloane;

NOTE_i,j este nota elevului cu numele NUME_i 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:

CITESTE m,   

n,

NUME_i, i=1,n,

NOTE_i,j, j=1,m, i=1,n;

PENTRU i:=1;n EXECUTA

FIE S:=0;

PENTRU j:=1;m EXECUTA S:=S+NOTE_i,j SFPENTRU

FIE MEDII_i:=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

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 x₁,x₂,,x_n . 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)

ESTE:

DACA n=1

ATUNCI MAXIM:=x₁

ALTFEL MAXIM:=MAXIM2( MAXIM(n-1,X), x_n)

SFDACA

SF-MAXIM