| CATEGORII DOCUMENTE |
DOCUMENTE SIMILARE |
|
TERMENI importanti pentru acest document |
|
| : | |
Functii. Transmiterea parametrilor. Recursivitate.
Functia reprezinta o unitate de sine statatoare a unui programului C, prin intermediul careia se descrie un subalgoritm de rezolvare a unei subprobleme.
Intr-un capitol precedent am subliniat importanta subalgoritmilor in descrierea unor metode de rezolvare a problemelor. Programele C permit o traducere a descrierilor algoritmice bazate pe subalgoritmi prin posibilitatea definirii unor functii utilizator care trateaza aspecte partiale ale rezolvarii. Un program C poate contine functia principala main dar si alte functii definite de catre programator sau functii predefinite din bibliotecile standard.
Limbajul C este suplimentat prin biblioteci care contin functii inrudite prin intermediul carora se realizeaza diferite operatii. Aceste functii de biblioteci pot fi apelate in programele dezvoltate daca in prealabil s-a inclus biblioteca corespunzatoare prin directive de preprocesare #include. (spre exemplu functiile standard scanf si printf ale bibliotecii stdio)
Functiile definite de utilizator au urmatoarea sintaxa:
<tip>NumeFunctie(<tip1><arg1>,.,<tipn><argn>)
Corpul functiei cuprinde intre acolade contine partea de declarare a variabilele locale functiei respective si partea de prelucrare a datelor: secventa de instructiuni prin care se prelucreaza variabilele locale sau altele cu caracter global.
In antetul unei functii este precizat tipul de data pe care il returneaza <tip>. Acesta poate fi void, caz in care functia nu returneaza nimic.
Parantezele rotunde (..) ce urmeaza numelui functiei delimiteaza lista argumentelor functiei.
Fiecarui argument ii este precizat tipul si numele sub care este referit in cadrul functiei curente.
Prototipul functiei: este format de antetul functiei din care poate sa lipseasca numele parametrilor formali:
<tip>NumeFunctie(<tip1>,.,<tipn>) ; //declararea unei functii
La definirea unei functii, argumentele precizate in antetul acesteia se numesc parametrii formali. La apelul functiei, parametrii formali sunt inlocuiti de parametrii actuali:
Apelul unei functii se face prin constructia:
NumeFunctie(pa1, pa2, . , pan);
Categorii de functii:
Functie fara tip si fara parametrii
Exista posibilitatea definirii de catre utilizator a unor functii care nu returneaza nimic si lista parametriolor acestora este vida:
void NumeFunctie ()
Apelul functiei se face printr-o constructie de forma:
NumeFunctie
Exemplu: Se defineste o functie Cifre care tipareste cifrele arabe. Functia va fi apelata in functia main.
#include <stdio.h>
void Cifre()
void main(void)
Functii cu tip
Daca unei functii ii este precizat tipul (diferit de void) acest lucru ne spune ca functia returneaza codului apelant o valoare de acest tip. In caz contrar, functia nu returneaza valoare. Tipul functiei reprezinta in fapt tipul de data al valorii pe care o returneaza. Instructiunea return, folosita in cadrul functiei cu tip definite, are sintaxa:
return <expresie>;
si are rolul de a reveni in programul apelant s de a returna acestuia o valoare de tipul precizat.
Functia poate fi apelata printr-o instructiune de asignare:
ValoareReturnata= NumeFunctie(); //membrul stang al instructiunii este o variabila de tipul returnat de functie
Exemplu: Programul C contine o functie CitireValoare, care citeste o valoare numerica intreaga de la tastatura si returneaza aceasta valoare functiei main apelanta, pe care aceasta o va afisa pe ecran.
#include <stdio.h>
int CitesteValoare()
|
void main(void) |
void main(void) //varianta compacta |
Functii parametrizate
Functiile cu parametri corespund acelor subalgoritmi care prelucreaza date de intrare reprezentand rezultate intermediare ale algoritmului general. Intrarile functiei sunt descrise prin lista parametrilor formali ce contine nume generice ale datelor prelucrate in corpul functiilor. Parametrii efectivi sunt transmisi la apelul functiilor, acestia inlocuind corespunzator parametrii generici specificati. In limbajul C transmiterea parametrilor actuali functiilor apelate se face prin valoare: intelegand prin aceasta ca valorile curente ale parametrilor actuali sunt atribuite parametrilor generici ai functiilor.
Exemplu:
int minim(int a, int b)
//apelul din functia main
int nr1,nr2, min;
nr1=7; nr2=6;
min=minim(nr1,nr2); // la apel a va primi valoarea 7 si b - valoarea 6
min=minim(nr2,nr1); // la apel a va primi valoarea 6 si b - valoarea 7
Fie functia:
tip NumeFunctie(tip1 pf1, tip2 pf2, . , tipn pfn)
La apelul:
NumeFunctie(pa1, pa2, . , pan);
se vor transmite prin valoare parametrii actuali si fiecare parametru formal din antetul functiei este inlocuit cu valoarea parametrului actual. Daca parametrul actual este o expresie, aceasta este evaluata la o valoare, ulterior este copiata in parametrul formal corespunzator.
Observatie: modificarile aduse parametrilor formali in cadrul functiei apelate nu afecteaza valorile parametrilor actuali. Exempul urmator evidentiaza acest aspect:
#include <stdio.h>
void putere(int n) //ridica la patrat valoarea n si afiseaza rezultatul
void main(void)
In multe situatii este necesar ca efectul operatiilor din corpul unei functii apelate asupra parametrilor de intrare sa fie vizibil si in corpul apelant. In exemplul anterior efectul dorit este acela ca variabila n dupa apel sa pastreze rezultatul ridicarii la patrat. Transmiterea prin valoare nu permite acest lucru. In schimb, transmiterea prin adresa realizata prin intermediul variabilelor de tip pointer asigura modificarea valorilor parametrilor actuali.
Pentru a intelege mecanismul transmiterii parametrilor prin adresa in limbajul C, vom defini in continuare notiunea de pointer.
Pointeri
Pointer = variabila care are ca valori adrese de memorie.
Sintaxa de declarare a unei variabile pointer:
tip * p; // variabila pointer spre tip
Prin aceasta declaratie s-a introdus o variabila ale carei valoare este adresa unei zone de memorie ce poate retine o data de tipul tip.
Fie x o variabila simpla de tipul tip:
tip x;
si p un pointer (variabila de tip pointer) care are ca valoare adresa variabilei x.
Pentru a face o atribuire unei variabile de tip pointer p se foloseste constructia:
p=&x // semnificatia: lui p i se atribuie adresa variabilei x.
Prin constructia &x ne referim la adresa variabilei x.
Prin constructia *p ne referim la valoarea variabilei x.
Operatorul * se numeste operator de indirectare
Operatorul & se numeste operator adresa
Expresia *&x are aceiasi semnificatie cu expresia x.
Transmiterea parametrilor prin adresa
Transmiterea prin adresa se realizeaza prin variabile de tip pointer si ne asigura de modificarea valorii parametrilor actuali.
Transmiterea prin prin adresa este realizata astfel:
1. Parametrii formali ai functiei se declara ca fiind de tip pointer;
tip NumeFunctie(tip1 *p1, tip2 *p2, . , tipn *pn)
2. La apel, argumentele functiei sunt adresele parametrilor actuali;
NumeFunctie(&p1, &p2, . , &pn)
Exemplu:
#include <stdio.h>
void putere(int *p) //ridica la patrat valoarea n si afiseaza rezultatul
void main(void)
Exercitiu: Sa se scrie o functie care interschimba valorile a doua variabile transmise ca parametrii.
Pentru construirea functiei cerute este utila transmiterea prin adresa, deoarece, efectul interschimbarii trebuie sa fie vizibil si in codul apelant. Prezentam in continuare doua variante de implementare, prima dintre acestea foloseste transmiterea implicita prin valoare, fapt pentru care nu corespunde rezultatului dorit. Cea de-a doua este varianta corecta, folosindu-ne de transmiterea parametrilor prin adresa (prin pointeri).
|
void interschimbare(int a, int b) |
void interschimbare(int *a, int *b) |
|
//Apelul: int x,y; x=1; x=2; interschimbare(x,y) |
//Apelul: int x,y; x=1; x=2; interschimbare(&x,&y) |
|
//Efectul Inainte de apel: x=1 y=2 Dupa apel: x=1 y=2 |
//Efectul Inainte de apel: x=1 y=2 Dupa apel: x=2 y=1 |
Probleme:
Dezvoltati un program C care determina minimul dintr-un sir de numere citite de la tastatura (fara a utiliza tablouri), punand in evidenta functia care determina minimul dintre doua valori.
-1, ecuatia nu este de gradul II
0 , ecuatia are solutii complexe
1, ecuatia are solutii reale
Primii trei parametrii se transmit prin valoare, ultimii doi - prin adresa.
RECURSIVITATE
Recursivitatea se obtine prin instructiunea de apel a unei functii in corpul definirii functiei respective:
<tip>NumeFunctie(<tip1><arg1>,.,<tipn><argn>)
La fiecare apel al functiei recursive, pe stiva programului sunt depuse noul set de variabile locale (parametrii). Chiar daca variabile locale au acelasi nume cu cele existente inainte de apelarea functiei, valorile lor sunt distincte, si nu exista conflicte de nume. Practic, ultimele variabile create sunt luate in considerare in operatiile continute de functie.
Problema 1: Sa se calculeze P(n)=n! printr-o functie recursiva.
Analiza problemei: Pornind de la observatia ca produsul P(n)=1*2*.(n-1)*n se mai poate formula ca:
P(n)=P(n-1) * n, vom defini o functie factorial care trateaza problema determinarii lui P(k) pe baza formulei anterioare, presupunand ca P(k-1) este calculabil dupa acelasi procedeu. P(k-1)=P(k-2)*(k-1).
Functia autoapelanta trebuie sa contina o conditie de terminare a recursivitatii. In problema calculului n!, conditia de terminare a recursivitatii se deduce din observatia ca 1! are valoarea 1, ceea ce nu mai necesita un calcul suplimentar.
Apelul initial al functiei factorial se va face pentru parametrul actual n- reprezentand data de intrare a programului. Functia returneaza la iesirea din apel rezultatul dorit n!.
int factorial(int k)
//apelul functiei
int p;
p=factorial(n);
Executia pas cu pas:
Consideram n=3
La apelul initial factorial(n) se transmite valoarea 3 parametrului formal k si se preda controlul functiei apelate
Din conditia adevarata 3>=1 rezulta amanarea revenirii din functie si un nou apel factorial(2); la iesirea din primul apel se va return 3*factorial(2).
Apelul factorial(2) va produce transmiterea valorii 2 la parametrul formal k si predarea controlului functiei apelate pentru valoarea curenta a parametrului
Conditia adevarata 2>=1 produce o noua apelare factorial(1) cu amanarea revenirii din apelul curent; la iesirea din acest al doilea apel se va return 2*factorial(1) .
Apelul factorial(1) va produce transmiterea valorii 1 la parametrul formal k si predarea controlului functiei apelate pentru valoarea curenta a parametrului
Din conditia falsa 1>1 rezulta ca la iesirea din acest apel se va return 1 si functia nu se mai apeleaza.
Revenirea din ultimul apel este urmata de revenirile in cascada din apelurile precedente in ordinea inversa, ceea ce conduce la rezultatul 3*2*1 = 6.
Recursivitatea poate fi de mai multe feluri, in functie de numarul de apeluri continute de functia (subalgoritmul) recursiva:
recursivitate liniara: functia contine cel mult un autoapel - exemplu functia factorial descrisa anterior
recursivitate neliniara: functia contine doua sau mai multe apeluri recursive - exemplu fibonacci descris in continuare
Problema 2: Se cere determinarea celui de-al n-lea termen din sirul lui Fibonacci.
Analiza problemei:
Se cunoaste ca:
primii doi termeni ai sirului sunt 0,1:
o Fibonacci(0)=0
o Fibonacci(1)=1
oricare termen este format prin insumarea celor doi termeni precedenti:
o Fibonacci(k)=Fibonacci(k-1)+ Fibonacci(k-2)
Functia recursiva este:
int Fibonacci(int k)
Problema 3. Determinarea celui mai mare divizor comun a doua numere a si b. (prin functie recursiva)
Analiza problemei:
cmmdc(a,b) poate fi:
a, daca b = 0
cmmdc(b, a mod b), daca b≠0
Prin a mod b se intelege restul impartirii intregi a lui a la b
Pe baza observatiei precedente, functia recursiva cmmdc se construieste astfel:
int cmmdc(int m, int n)
Recursivitatea este o tehnica costisitoare datorita spatiului de memorie blocat pentru retinerea variabilelor locale create la fiecare apel. Exista diferite metode de eliminare a recursivitatii din programele C, pentru a preintampina acest neajuns. Descriem in continuare procedura de eliminare a recursivitatii liniare:
Se utilizeaza o lista care se initializeaza ca fiind vida. In aceasta lista vor fi salvati parametrii formali si variabilele locale ale functiei recursive. Operatiile posibile cu lista folosita sunt: adaugarea unui nou element in capatul listei si extragerea unui element din capatul listei(vezi conceptul de stiva)
Cattimp conditia de continuare a recursivitatii este adevarata executa:
Adauga (salveaza) in lista valorile actuale pentru parametrii functiei recursive si variabilele locale
Executa instructiunile functiei recursive
Modifica valorile argumentelor functiei recursive (actualizarea parametrilor)
Daca la terminarea pasului 2 lista nu este vida, se extrage multimea de variabile din capatul acesteia, se calculeaza valoarea dorita si se executa instructiunile ce apar dupa apelul functiei recursive, apoi se trece la pasul 2. Daca lista este vida se termina executia algoritmului.
|
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 1893
Importanta: 
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved
