Programarea calculatoarelor -

Algoritmi

Semestrul 2

Modul 1

2

Cuprins 1. RECURSIVITATE

1. Noiuni introductive 2. Funcii recursive. ncrcarea stivei 3. Ieirea din recursivitate

2. METODE DE PROGRAMARE RECURSIVE SI NERECURSIVE

Metoda backtracking Metoda divide et impera

3. TEHNICI DE CUTARE I SORTARE Metode de cutare

Cutarea binar Metode de sortare

Metode simple de sortare Metode avansate de sortare Funcii de bibliotec de cautare si sortare

3

1. RECURSIVITATE 1.1. Noiuni introductive

Recursivitatea n matematic

Recursivitatea n programare

Algoritm recursiv:

Pn

Pn-1

Pk val

4

Exemple de algoritmi implementai recursiv

Factorialul:

n!= 1*2*3*...*n, definiie nerecursiv

n! = n * (n-1)!, definiie recursiv, tiind c 0! =1

irul lui Fibonacci:

fn = 0, dac n=0

fn = 1, dac n=1

fn = fn-1 + fn-2, dac n>= 2

5

cmmdc(m, n) =

m, dac n=0

n, dac m=0

cmmdc(n, m%n), dac m>n

cmmdc(m,n%m), dac n>m

cmmdc(m, n) =

m, dac m=n

cmmdc(m-n, n), dac m>n

cmmdc(m, n-m), dac m

6

Aranjamente de n luate cte k

A(n,k)=n!/ (n-k)!=n*(n-1)*(n-k+1)=n*[(n-1)**((n-1)-(k-1)+1)]= n*A(n-1, k-1)

A(n,1)=n; // conditia de iesire

Combinri de n luate cte k

C(n,k)=n!/ (k!*(n-k)!)=[n/ (n-k)]* C(n-1,k)

C(n,k)=n, daca k=1

C(n,k)=1 daca k=0 sau n=k

C(n,k) = C(n-1, k) + C(n-1, k-1)

Funcia lui Ackermann:

7

8

1.2. Funcii recursive

Recursivitatea n programare subprograme

n limbajul C/C++ - funcii

Funcie recursiv -> autoapel

Autoapel:

direct (recursivitate direct)

indirect (recursivitate indirect)

9

Factorialul n! = n * (n-1)!

int factorial(int n)

{

if (n == 0)

return 1;

else

return n*factorial(n-1); //adresa 2

}

void main(void)

{

cout

10

Cteva observaii !!!

La apelul recursiv al unei funcii se creeaz o nou instan de calcul pentru acea funcie.

La fiecare apel - pe stiva local funciei se pun un nou set de variabile locale (inclusiv parametrii

formali), cu aceleai nume, dar diferite ca zon de memorie i cu valori diferite la fiecare apel

n fiecare moment e accesibil doar variabila din vrful stivei

11

int factorial(int n) {

if (n == 0) return 1; else return n*factorial(n-1);

}

main()

factorial (3)

factorial (2)

factorial (1)

factorial (0)

12

La apelul unei funcii precum i la autoapelul ei, pe stiv se vor depune:

valorile parametrilor transmii prin valoare

adresele parametrilor transmii prin adres (referin, pointeri)

valorile tuturor variabilelor locale nestatice

adresa de revenire la instruciunea imediat urmtoare apelului

13

Evoluia stivei

Stiva program

adresa1

3

Stiva program

adresa2

2

adresa1

3

Stiva program

adresa2

1

adresa2

2

adresa1

3

Stiva program

adresa2

0

adresa2

1

adresa2

2

adresa1

3

factorial(3)

factorial(2)

factorial(0)

factorial(1)

14

irul lui Fibonacci f(n) = 0, dac n=0 f(n) = 1, dac n=1 f(n) = f(n-1) + f(n-2), dac n>= 2

int fib(int n)

{

if (n < 2)

return n;

else

return fib(n-1)+fib(n-2);

}

void main(void)

{

cout

15

Metoda este ns foarte ineficient, timpul de calcul fiind de ordinul (numit seciunea de aur), ce reprezint un timp exponenial,

Ineficiena este dat i de faptul c se evalueaz unele elemente ale irului de mai multe ori:

16

17

Observaii!

Orice algoritm recursiv poate fi transformat ntr-unul

iterativ i invers

Orice numr natural poate fi descompus ntr-o sum de termeni neconsecutivi ai irului lui Fibonacci (teorema lui Zeckendorf).

Codificarea Fibonacci orice numr natural n poate fi reprezentat printr-o secven de bii care se termin cu 11, dar n rest nu apar 2 bii consecutivi cu valoarea 1

18

Primele n numere din irul lui Fibonacci se pot calcula iterativ folosind un ir ajuttor :

void fib(int n, int *p)

{

int l=2;

p[0]=0; p[1]=1;

for(; l < n; l++)

p[l] = p[l-1] + p[l-2];

}

Acest algoritm rezolv aceeai problem ns ntr-un timp liniar i nu exponenial

19

Numerele din irul lui Fibonacci se pot calcula i fr irul ajuttor: //Solutia iterativa pentru generarea sirului lui Fibonacci pana la N dorit

#include

#include

using namespace std;

#include

void main(void)

{

int l=1, j=0, k, N;

coutN;

printf("f[0]= 0\n");

for(k=1; k < N; k++)

{

j=l+j;

l=j-l;

printf("f[%d]= %d\n",k, j);

}//end for

_getch();

}//main

20

Combinrile C(n,k) = C(n-1,k) + C(n-1,k-1)

int comb(int n, int k)

{

if(k==0) || (n==k) return 1;

if(k==1) return n;

return (comb(n-1, k) + comb(n-1, k-1));

}

i n acest caz se fac evaluri multiple: C(5,3) = C(4,3) + C(4,2)

C(4,3) = C(3,3) + C(3,2) C(3,2) = C(2,2) + C(2,1)

C(4,2) = C(3,2) + C(3,1) C(3,2) = C(2,2) + C(2,1)

21

c.m.m.d.c.

int cmmdc(int a, int b)

{

if(a==0) return b;

if(b==0) return a;

if(b>a) return cmmdc(a, b%a);

return cmmdc(b,a%b);

}

22

Concluzii: Un algoritm recursiv presupune mai multe

nivele

Pe fiecare nivel se ntmpl acelai lucru, dar la o dimensiune mai mic a problemei

Exist cel puin un nivel ce admite o rezolvare direct (fr proces recursiv)

D.p.d.v. al limbajului de programare apare un autoapel

23

1.3. Ieirea din recursivitate

Situaii care trebuie evitate n cazul recursivitii:

- ncrcarea excesiv a stivei stack overflow

- autoapelarea la infinit time out

Soluia: autoapelul s fie legat de ndeplinirea unei condiii care s asigure oprirea din acel ciclu de autoapeluri.

24

Posibiliti: se asociaz funciei recursive un parametru ntreg n i

apelul se face cu valorile (n-1), (n-2), ct timp n>0

se asociaz funciei recursive un parametru logic, iar apelul se face atta timp ct parametrul are valoarea TRUE

Utilizarea tehnicilor recursive nu conduce, de obicei, la soluii optime:

analiza eficienei soluiei iterative (nerecursive) i a celei recursive, alegndu-se soluia cea mai avantajoas

Soluia recursiv duce ns la soluii mai elegante i mai uor de urmrit

25

Ce trebuie luat n calcul la alegerea rezolvrilor cu ajutorul metodelor recursive?

necesarul de memorie

timpul de execuie

parametrii transmii (pentru a nu ncrca stiva se prefer s fie folosii parametrii globali acolo unde e posibil)

Cnd se prefer varianta recursiv?

- cnd nlocuirea recursivitii cu iteraia cere un efort deosebit, algoritmul pierzndu-i din claritate

- testarea i ntreinerea devin dificile

26

Exemplul 1: suma cifrelor unui numr ntreg Abordare:

Recursiv: suma cifrelor numrului din stnga + ultima cifr

Nerecursiv (iterativ): suma cifrelor (cifr cu cifr)

int suma_cifre_recursiv(int n)

{

if (n==0)

return 0;

else

return suma_cifre_recursiv(n/10)+n%10;

}

Exemplu:

suma_cifre_recursiv(1234);

ncrcarea stivei

27

n=1234

Adresa 1

n=123

Adresa 2

n=12

Adresa 2

n=1

Adresa 2

n=0

Adresa 2

Descrcarea stivei

28

n=1234

Adresa 1

n=123

Adresa 2

n=12

Adresa 2

n=1

Adresa 2

n=0

Adresa 2

0

0+1%10=1

1+12%10=3

3+123%10=6

6+1234%10=10

suma_cifre_recursiv(0)

suma_cifre_recursiv(12)

suma_cifre_recursiv(1)

suma_cifre_recursiv(123)

suma_cifre_recursiv(1234)

main()

29

Varianta iterativ

int suma_cifre_iterativ(int n)

{

int s=0;

while(n != 0) {

s += n%10;

n /= 10;

}

return s;

}

30

Exemplul 2: suma elementelor unui tablou unidimensional de tip numeric

Abordare: Recursiv: suma primelor (n-1) elemente + ultimul

element

Nerecursiv: suma, element cu element

int suma_elem_recursiv(int tab[ ], int n)

{

if (n==1)

return tab[0];

else

return suma_elem_recursiv(tab, n-1)+ tab[n-1];

}

31

Varianta nerecursiv

int suma_elem_iterativ(int tab[ ], int n)

{

int s=0;

for(int i=0; i

32

Exemplul 3: ir palindrom

Un ir este palindrom dac:

primul caracter este identic cu ultimul caracter

restul irului este un ir palindrom

exemple: rotor, madam

int mirror(char *s)

{

if (strlen(s)

unde funcia substr() este urmtoarea:

char* substr(char* s,int pi,int pf)

{

int k=0;

char *n=new char[pf-pi+1];

for(int i=pi;i

34

Tipuri de probleme care de obicei se rezolv cu ajutorul funciilor recursive:

metode de divizare, divide et impera;

metode de cutare cu revenire, backtracking;

metoda Greedy;

metoda programrii dinamice;

metode n care datele sunt definite recursiv, etc.