programarea calculatoarelor m7
TRANSCRIPT
8/8/2019 Programarea Calculatoarelor M7
http://slidepdf.com/reader/full/programarea-calculatoarelor-m7 1/7
Programarea Calculatoarelor (limbajul C)
Curs 7 – FuncŃii şi Recursivitate
Universitatea “Politehnica” din BucureştiFacultatea de Electronică, TelecomunicaŃii şi
Tehnologia InformaŃiei
Ş.l. Bogdan IONESCUProf. Dragoş BURILEANUProf. Claudius DAN
2010-20112
Cuprins
7.1. FuncŃii
7.2. Recursivitate
Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 1/36
Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 2/36
7.1. FuncŃii
Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 3/36
Definirea funcŃiilor
> Pentru rezolvarea unor probleme complexe de calcul,acestea trebuie descompuse în sub-probleme mai simple.
> Descompunerea fizică a codului în porŃiuni, ce realizeazăanumite sub-probleme de calcul, se face cu ajutorul funcŃiilor .
“divide et impera” ar spune romanii.
modulare program (fiecare modul se ocupă deanumite operaŃii).
> Pe lângă structurarea programului, funcŃia are avantajul de afi scrisă o singură dată, dar folosită de câte ori este nevoie,evitând astfel rescrierea codului aferent de fiecare dată.
5Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 4/36
Subprograme – funcŃii (continuare)
> Ce înseamnă o funcŃie ?
> Din punct de vedere matematic:
f(x,y) = sin(x*y)
numelefuncŃiei
argumentefuncŃie (variabile)
corpul funcŃiei(calculul realizat)valoarea
returnată
> Din punct de vedere al programării în C, funcŃia îşipăstrează sensul matematic (programare funcŃională).
6Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 5/36
Definirea funcŃiilor (continuare)
> Astfel, în limbajul C, funcŃiile îşi păstrează sensulmatematic:
Formă generală:
<tip_dată> <nume>(<var1>,...,<varN>){<secvenŃă instrucŃiuni 1>;<secvenŃă instrucŃiuni 2>;...<secvenŃă instrucŃiuni M>;[return <expresie>;]
} [ ] = opŃional
• <tip_dată>: reprezintă tipul datelor returnate de funcŃie,AtenŃie: o funcŃie nu poate returna decât o singură valoare.
8/8/2019 Programarea Calculatoarelor M7
http://slidepdf.com/reader/full/programarea-calculatoarelor-m7 2/7
7Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 6/36
Definirea funcŃiilor
(continuare)
<tip_dată> <nume>(<var1>,...,<varN>){<secvenŃă instrucŃiuni 1>;<secvenŃă instrucŃiuni 2>;...<secvenŃă instrucŃiuni M>;[return <expresie>;]
}
• <nume>: reprezintă identificatorul funcŃiei pe baza căruiaaceasta va fi apelată pe parcursul rulării programului.
• (var1,...,varN): reprezintă variabilele de intrare, pe care leprimeşte funcŃia din programul, sau sub-programul în care esteapelată. Este posibil ca funcŃia să nu primească date de intrare,caz în care lista este vidă: <nume>(), sau se poate folositipul void: <nume>(void).
• <tip_dată>: dacă funcŃianu returnează nici o valoare
atunci se specifică tipulvoid procedură.
Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 7/36
> ObservaŃie: o funcŃie chiar dacă nu primeşte variabile,
aceasta poate interacŃionacu programul pe bazavariabilelor globale din program (vizibile pentru orice funcŃie)
Definirea funcŃiilor
(continuare)
<tip_dată> <nume>(<var1>,...,<varN>){<secvenŃă instrucŃiuni 1>;<secvenŃă instrucŃiuni 2>;...<secvenŃă instrucŃiuni M>;[return <expresie>;]
}
de evitat , deoarece funcŃia nu mai este independentăde program, portabilitatea într-un alt program fiind redusă.
• { secvenŃe instrucŃiuni }: corpul funcŃiei (ceea ce se execută)este specificat între “{” şi “}”. Acesta poate fi văzut, el însuşi caun program.
9Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 8/36
• return <expresie>:funcŃia return este folosităpentru a returna valoareadorită.
Definirea funcŃiilor
(continuare)
<tip_dată> <nume>(<var1>,...,<varN>){<secvenŃă instrucŃiuni 1>;<secvenŃă instrucŃiuni 2>;...<secvenŃă instrucŃiuni M>;[return <expresie>;]
}
> Efect : funcŃia se încheie în momentul în care se executăcomanda return, iar <expresia> specificată este returnată cadată de ieşire a funcŃiei.
dacă aceasta nu corespunde tipului specificat (<tip_dată>),conversie la acesta, dacă nu este posibilă, atunci eroare.
> ObservaŃie: folosirea funcŃiei return este opŃională chiar dacăs-a specificat că funcŃia trebuie să returneze ceva (warning).
10Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 9/36
Definirea funcŃiilor (continuare)
Exemplu de funcŃie:
int adunare((((int a,a,a,a, int b)b)b)b)
{{{{
int r;
r=a+b;
return r;
}}}}
-am definit funcŃia adunare careprimeşte două numere întregi şireturnează un număr întreg,
-calculează suma în variabila r şi returnează valoarea lui r .
Optimizare:int adunare((((int a,a,a,a, int b)b)b)b)
{{{{
return a+b;}}}}
-funcŃia return poate primi oexpresie şi nu neapărat o singurăvariabilă.
> Cum se poate rescrie funcŃia mai eficient ???
11Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 10/36
Definirea funcŃiilor (continuare)
> Unde se definesc funcŃiile.
Formă generală program:
#include<stdio.h>...
int main(){
…}
comenzi depreprocesare
programulprincipal (main)
int adunare((((int a,a,a,a, int b)b)b)b)
{{{{
return a+b;}}}}
Varianta 1: funcŃiile pot fi definite înaintea funcŃiei main, acesteafiind scrise integral.
12Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 11/36
Definirea funcŃiilor (continuare)
> Unde se definesc funcŃiile (continuare).
Formă generală program:
#include<stdio.h>...
int main(){
…}
comenzi depreprocesare
programulprincipal (main)
Varianta 2: funcŃiile pot fianunŃate înaintea funcŃiei main,(prototip), acestea fiind descriseintegral după funcŃia main.
int adunare((((int a,a,a,a, int b)b)b)b)
{{{{
return a+b;}}}}
int adunare((((int a,a,a,a, int b)b)b)b);
8/8/2019 Programarea Calculatoarelor M7
http://slidepdf.com/reader/full/programarea-calculatoarelor-m7 3/7
13Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 12/36
Definirea funcŃiilor (continuare)> Unde se definesc funcŃiile (continuare).
Exemplu:
#include<stdio.h>#include<stdlib.h>
double factorial(int n){int i; double fact=n;for (i=n-1; i>0; i--)fact=fact*i;
return fact;}
int main(){
printf (“20!=%lf”, factorial(20) );}
-am definit funcŃia factorial carecalculează factorialul unui număr întreg n şi returnează această
valoare sub forma unui double ?
-funcŃiile se apelează în modidentic cu modul de apelare alfuncŃiilor disponibile în C.
factorial(20)-n=20,-se efectuează calculele,-factorial(20) devine val.specificată de return.
14Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 13/36
Definirea funcŃiilor (continuare)> Unde se definesc funcŃiile (continuare).
Altă variantă:
#include<stdio.h>#include<stdlib.h>
double factorial(int n);int main(){
printf (“20!=%lf”, factorial(20) );}
double factorial(int n){int i; double fact=n;for (i=n-1; i>0; i--)fact=fact*i;
return fact;}
-am anunŃat funcŃia şi amspecificat prototipul acesteia.
-corpul funcŃiei este detaliat dupăprogramul principal.
-în cazul în care funcŃiile nu suntevidente (complexe), iar conceperea lor necesită un timpsemnificativ , putem scrie mai întâi programul principal, ca şicum funcŃiile există deja.
15Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 14/36
Definirea funcŃiilor (continuare)
> Vizibilitatea variabilelor în cadrul funcŃiilor
double factorial(int n){int i; double fact=n;for (i=n-1; i>0; i--)fact=fact*i;
return fact;}
int main(){
printf (“%d, %lf”, i, factorial(20) );}
Exemplu:
• variabilele declarate în corpul unei funcŃii sunt valabile doar în acesta, şi doar pe parcursul execuŃiei funcŃiei respective.
-variabila i este o variabilă localăa funcŃiei factorial ce va fialocată în memorie doar cândfuncŃia este apelată.
- variabila i şi fact nu există încadrul celorlalte funcŃii, inclusivmain().
eroare!
16Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 15/36
Definirea funcŃiilor (continuare)
> Vizibilitatea variabilelor în cadrul funcŃiilor
• variabilele declarate în afara programului principal main(), în secŃiunea de variabile globale, sunt vizibile peste tot înprogram: în funcŃia main(), în toate funcŃiile definite, etc.
#include<stdio.h>
int offset=3;
float produs(float a, float b){
return a*b+offset;}
int main(){
printf (“%d, %f”, offset, produs(5,6) );}
Exemplu: -variabila offset este definitădupă comenzile de preprocesare,dar înaintea definirii funcŃiilor programului,
-aceasta este astfel vizibilă atât în procedura produs cât şi înmain.
>3, 5*6+3=33
17Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 16/36
Definirea funcŃiilor (continuare)
> Vizibilitatea variabilelor în cadrul funcŃiilor
#include<stdio.h>
float produs(float a, float b){return a*b+offset;
}int offset=3;
int main(){
printf (“%d, %f”, offset, produs(5,6) );}
Exemplu: -variabila offset este definitădupă definirea proceduriiprodus, ce se întâmplă ???
eroare!
> Principiu: o declaraŃie de variabile sau de funcŃii este vizibilăpentru toate funcŃiile ce sunt definite după aceasta.
variabila offset este vizibilă deaici în jos.
18Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 17/36
Definirea funcŃiilor (continuare)
> Vizibilitatea variabilelor în cadrul funcŃiilor
#include<stdio.h>float produs(float a, float b){int offset=4;return a*b+offset;
}int offset=3;
int main(){
printf (“%d, %f”, offset, produs(5,6) );}
Exemplu:-ce valoare va returna funcŃiaprodus ???
>3, 30+4=34.00
-în funcŃie, variabila offset estedefinită local şi are valoarea 4.
-în main(), variabila offset estecea definită global, cea dinfuncŃie neexistând decât îninteriorul fcŃ. produs (execuŃie).
offsetoffset
offset
offset
8/8/2019 Programarea Calculatoarelor M7
http://slidepdf.com/reader/full/programarea-calculatoarelor-m7 4/7
19Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 18/36
Definirea funcŃiilor (continuare)
> Vizibilitatea variabilelor în cadrul funcŃiilor
#include<stdio.h>
int offset=3;float produs(float a, float b){int offset=4;return a*b+offset;
}
int main(){
printf (“%d, %f, %d”, offset, produs(2,3), offset );}
Exemplu: -ce valoare va returna funcŃiaprodus ???
>3, 2*3+4=10.00, 3
-cu toate că variabila offset este definită global şi estevizibilă şi în funcŃia produs,redefinirea ei local, duce laignorarea variabilei globale .
offsetoffset
offset
offset offset
20Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 19/36
Definirea funcŃiilor (continuare)
PEnunŃ : să se realizeze o funcŃie care permiteafişarea pe ecran a unei matrice pătratice de numere întregi. Matricea se va afişa pe linii şi coloane.
Variabile de intrare/lucru:
int M[100][100];
Variabile de ieşire:
nu
int dim;int i, j;void AfisareM (int dim, int M[100][100]);
program principalmain()
definiŃie funcŃieAfisareM()
21Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 20/36
Definirea funcŃiilor (continuare)
#include<stdio.h>#include<stdlib.h>/* procedura este definita inaintea funcŃiei main */void AfisareM(int dim, int M[100][100]){int i,j;
printf ("\n");for (i=0; i<dim; i++) // parcurgere linii{
for (j=0; j<dim; j++) // parcurgere elemente de peprintf ("%8d",M[i][j]); // coloaneprintf ("\n");
}}
22Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 21/36
Definirea funcŃiilor (continuare)
int main(){
int M[100][100], i, j, dim;
printf ("dim="); scanf ("%d",&dim);for (i=0; i<dim; i++)
for (j=0; j<dim; j++){
printf ("M[%d][%d]=",i,j);
scanf ("%d",&M[i][j]);}
AfisareM(dim, M);}
-în felul acesta funcŃiaAfisareM poate fi folosită ori
de câte ori avem nevoie săafişăm pe ecran o matricepătratică.
23Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 22/36
7.2. Recursivitate
24Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 23/36
FuncŃii recursive
> Recursivitatea unei funcŃii în programare, reprezintăprocesul prin care funcŃia se autoapelează.
> Pentru ca procesul să nu se repete la infinit, autoapelarea
se încheie de regulă pe baza unei condiŃii de oprire.
Efectul Droste: Sierpinski triangle:etc.
8/8/2019 Programarea Calculatoarelor M7
http://slidepdf.com/reader/full/programarea-calculatoarelor-m7 5/7
25Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 24/36
FuncŃii recursive (continuare)
> Astfel, un obiect sau un fenomen se defineşte în modrecursiv dacă în definiŃia sa există o referire la el însuşi.
Exemple:
definirea numerelor întregi:0∈Ndacă i∈N atunci i+1∈N
definirea funcŃiei factorial:
>−⋅
==
0)!1(
01!
ndacă nn
ndacă n
definirea şirului Fibonacci:
>−+−
=
=
=
1)2()1(
11
00
)(
ndacă n fibn fib
ndacă
ndacă
n fib
0, 1, 1, 2, 3, 5, 8, 13, 21, ...
26Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 25/36
FuncŃii recursive (continuare)
> O funcŃie recursivă trebuie să fie bine formată:
- o funcŃie nu se poate defini doar în funcŃie de sine însăşi,
- o funcŃie recursivă se poate folosi numai de noŃiuni deja
definite anterior,
- orice şir de apeluri de funcŃii recursive trebuie să seoprească (nu va genera un calcul infinit).
exemplu : f(n) =2+f(n) greşit, se execută la ∞∞∞∞
exemplu : f(n)=f(n+1)-2 greşit (valoare inexistentă f(n+1)),
exemplu : f(0)=1, f(n)=f(n-1)+3,f(3)=f(2)+3=f(1)+3+3=f(0)+3+3+3=1+3+3+3=10
27Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 26/36
FuncŃii recursive (continuare)
> În general distingem:
- un caz de bază: pentru care funcŃia este definită direct,de exemplu: f(0)=1
- un pas inductiv (recursivitatea propriu-zisă): funcŃiaeste definită folosind aceeaşi funcŃie, dar pe un caz maisimplu, de exemplu: f(n+1)=f(n)*PI
> În limbajul C crearea de funcŃii recursive nu necesită oanumită sintaxă sau folosirea unui anumit cuvânt cheie,aceasta reiese automat din modul de definire al funcŃiei.
Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 27/36
FuncŃii recursive (continuare)
int Factorial(int n){if (n==0)
return 1;else
return n*Factorial(n-1);}
- funcŃia primeşte valoarea n şireturnează valoarea calculată afactorialului.
Exemplu: funcŃia factorial
- condiŃia de oprire a recursivităŃii:dacă n a ajuns la valoarea 0, sereturnează 1 (0!)
- pasul inductiv: relaŃia de calculrecursiv ce depinde de valorilede rang inferior ale funcŃiei:Factorial(n-1), Factorial(n-2) …
n=11==0 Falsreturn 1*Factorial(1-1)
iteraŃia 2
Factorial(1)
int main(){
printf (“%d”, Factorial(2) );}
iteraŃia 1
n=22==0 Falsreturn 2*Factorial(2-1)
Factorial(2)
Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 28/36
FuncŃii recursive (continuare)
Modul de execuŃie
int Factorial(int n)
{ if (n==0)return 1;
elsereturn n*Factorial(n-1);
}
> FuncŃia returnează valoarea: 1*1*2
n=00==0 Adevăratreturn 1
iteraŃia 3
Factorial(0)
30Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 29/36
FuncŃii recursive (continuare)
Exemplu: o funcŃie recursivă care numără de la a la b în senscrescător, şi invers.
void printnum(int a, int b){printf ("%d ",a);if (a<b)printnum(a+1,b);
printf ("%d ",a);}
- funcŃia primeşte valoarea a şirespectiv b şi nu returnează nimic(rezultatul este afişat pe ecran)
- se afişează valoarea lui a şi apoise apelează recursiv funcŃia pentru aafişa în ordine crescătoare valorile.
- profită de închiderea în sensinvers a procedurilor lansatepentru diverse valori ale lui apentru afişarea în ordine inversă.
8/8/2019 Programarea Calculatoarelor M7
http://slidepdf.com/reader/full/programarea-calculatoarelor-m7 6/7
31Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 30/36
FuncŃii recursive (continuare)
Mod de execuŃie:
void printnum(int a, int b){printf ("%d ",a);if (a<b)
printnum(a+1,b);printf ("%d ",a);
}
int main(){
printnum(2,4);}
iteraŃia 1
printf ("%d ",2);
printnum(2,4)
iteraŃia 2
printf ("%d ",3);
printnum(3,4)
iteraŃia 3
printf ("%d ",4);
printnum(4,4)
if (2<4)
printf ("%d ",2);
if (3<4)
printf ("%d ",3);
if (4<4) Fals
printf ("%d ",4);
32Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 31/36
FuncŃii recursive (continuare)
PSe dă o imagine binară (valori 0 şi 1) sub forma unei
matrice bidimensionale. În aceasta, obiectele sunt
reprezentate cu valori de 1, iar fundalul cu valori de 0.
Să se realizeze o funcŃie recursivă care permite calculul suprafeŃei unui obiect (metoda “flood fill”).
1100
0111
0010
1000Exemplu:
obiect = mulŃime de valoride 1 vecine (conexe).
obiect de suprafaŃă 1
suprafaŃă ~ număr valori de 1
33Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 32/36
FuncŃii recursive (continuare)
> Pentru a determina care valori de 1 sunt vecine, şi astfel
aparŃin obiectului curent, se va folosi conectivitatea cu 4 vecini:
1100
0111
0010
1001
V
V V V
V 4 connectivity
Problemă obiecte (continuare)
câte obiecte sunt în imagine ?
34Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 33/36
FuncŃii recursive (continuare)
Problemă obiecte (continuare)
Strategie: “flood fill”
void SuprafataObiect(int matrice[20][20], int dim, int x, int y)
int matrice[20][20];int dim;int suprafata; (var.globală)
nu returneazănimic,suprafaŃaeste stocatăglobal
primeşte matriceapentru a verificavalorile
primeşte dimpentru a nu ieşidin matrice lacalcul
(x,y) indicăpoziŃia curentăanalizată dinmatrice
10
35Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 34/36
FuncŃii recursive (continuare)
Problemă obiecte (continuare)void SuprafataObiect(int matrice[20][20], int dim, int x, int y){
}
condiŃie de oprire:(x,y) fundal sau(x,y) a fost dejaluat în calcul (-1)
if ((matrice[x][y]==0) || (matrice[x][y]==-1)) return;
(x,y) este luat încalcul la suprafaŃăşi apoi marcat,
suprafata++; matrice[x][y]=-1;
vecin Sud
if (x+1<dim)if (matrice[x+1][y]==1)
SuprafataObiect(matrice, dim, x+1,y);
vecin Est
if (y+1<dim)if (matrice[x][y+1]==1)
SuprafataObiect(matrice, dim, x,y+1);
vecin Nord
if (x-1>=0)if (matrice[x-1][y]==1)
SuprafataObiect(matrice, dim, x-1,y);
vecin Vest
if (y-1>=0)if (matrice[x][y-1]==1)
SuprafataObiect(matrice, dim, x,y-1);
36Curs Programarea C alculatoarelor, Ş.l. Bogdan I ONESCU, 2010-2011 35/36
FuncŃii recursive (continuare)
Problemă obiecte (continuare)Mod de execuŃie:
0100
0111
0010
0000
int Suprafata;
…int main(){
int dim, matrice[20][20];…Suprafata=0;SuprafataObiect(matrice, dim, 1,1);
}
x=1, y=1Suprafata=1lansare Sudlansare Estlansare Nordlansare Vest
x=2, y=1Suprafata=2lansare Sudlansare Estlansare Nordlansare Vest
x=2, y=2Suprafata=3lansare Sudlansare Estlansare Nordlansare Vest
x=3, y=2Suprafata=4lansare Sudlansare Estlansare Nordlansare Vest
x=2, y=0Suprafata=5lansare Sudlansare Estlansare Nordlansare Vest