111

Lect. univ. dr. Adrian Runceanu

PROIECTAREA

ALGORITMILOR

Universitatea Constantin Brncui din Trgu-JiuFacultatea de Inginerie

Departamentul de Automatic, Energie i Mediu

122Proiectarea Algoritmilor - curs

Cteva precizri

Structura cursului

2 ore curs titular curs Lector dr. Adrian Runceanu

2 ore laborator titular aplicaii practice Lector dr. Adrian Runceanu

133Proiectarea Algoritmilor - curs

Cteva precizri

Forme de examinare:

Examen final 60% Evaluare pe parcursul

semestrului a activitii de laborator 30%

Prezen curs i laborator 10%

144Proiectarea Algoritmilor - curs

Cteva precizri

Bibliografia necesar cursului:

1. Dogaru, O., Tehnici de programare, Editura MIRTON, Timioara, 2002, 2004

2. Creu, V., Structuri de date i algoritmi, vol.1 Structuri de date fundamentale, Editura Orizonturi Universitare, Timioara, 2000

3. Livovschi, L.,Georgescu, H., Sinteza i Analiza algoritmilor, Editura tiinific i Enciclopedic, Bucureti, 1986

4. Wirth, N., Algorithms and Data Structures, Prentice Hall,

Inc.,Englewood, New Jersey, 1986

5. Dr. Kris Jamsa & Lars Klander, Totul despre C si C++ - Manualul

fundamental de programare n C si C++, ed. Teora, 1999-2006

155Proiectarea Algoritmilor - curs

Cteva precizri

Bibliografia necesar cursului:

6. Liviu Negrescu, Limbajele C si C++ pentru nceptori, vol. II, Limbajul C++, ed. MicroInformatica, 1995

7. A.Runceanu, Metode si tehnici de programare indrumar de laborator, Editura Academica Brancusi Targu-Jiu, 2003

8. Horia Ciocrlie, Tehnici fundamentale de programare, Ed. Orizonturi Universitare, 2002

9. Pagina web pentru curs:

http://www.runceanu.ro/adrian

166Proiectarea Algoritmilor - curs

Cteva precizri

Referinele bibliografice nr. 1 i 7 se pot mprumuta de la Biblioteca Facultii de Inginerie, Str. Geneva nr.3, Etaj I lng Decanat.

1. Suport curs - varianta electronic disponibil pe siteul:

http://www.runceanu.ro/adrian

2. ndrumar de laborator - varianta electronic disponibil pe site pentru fiecare lucrare de laborator.

Not: Actualizarea site-ului se face sptmnal.

177Proiectarea Algoritmilor - curs

Coninutul cursului

n cadrul acestui curs se vor studia metode i tehnici de programare pentru elaborarea eficient a algoritmilor.

Exemplificrile de la curs i implementrile de la laborator se vor efectua cu ajutorul

limbajului de programare - C++.

Mediul de dezvoltare utilizat la aplicatiile practice este MinGW.

188Proiectarea Algoritmilor - curs

Capitolele cursului

1. Recursivitate

2. Alocarea dinamic de memorie n C++3. Liste simplu i dublu nlnuite4. Elemente de teoria grafurilor

5. Algoritmi pentru prelucrarea grafurilor

6. Arbori. Arbori binari

7. Metoda Greedy de elaborare a algoritmilor

8. Metoda Divide et Impera de elaborare a

algoritmilor

9. Metoda Backtracking de elaborare a algoritmilor

10. Combinatoric

199Proiectarea Algoritmilor - curs

Curs 1

Recursivitate

11010

Coninutul cursului

1. Conceptul de recursivitate

2. Recursivitate direct

3. Recursivitate indirect

4. Relaia dintre recursivitate i iteraie

5. Exemple de programe recursive

Proiectarea Algoritmilor - curs

11111

1. Conceptul de recursivitate

Un obiect sau un fenomen este definit n modrecursiv dac n definitia sa se face referire la elnsusi.

Conceptul de recursivitate ofer posibilitateadefinirii unei infinitti de obiecte printr-un numrfinit de relatii.

O functie este recursiv atunci cnd executareaei implic cel putin nc un apel ctre ea nssi.

Proiectarea Algoritmilor - curs

11212

1. Conceptul de recursivitate

Tipuri de recursivitate:

1.Recursivitate direct apelul recursiv se face chiar din functia invocat.

2.Recursivitate indirect (mutual) apelul recursiv se realizeaz prin intermediul mai multor functii care se apeleaz circular.

Proiectarea Algoritmilor - curs

11313

Exemplul 1

Definirea numerelor naturale:

1 este numr natural

succesorul unui numr natural este un numrnatural

Se presupune cunoscut definiiasuccesorului unui numr: acel numr obinut dinnumrul dat prin adugarea unei uniti.

Proiectarea Algoritmilor - curs

11414

Exemplul 2

Algoritm de calcul pentru factorialul unui

numr n. (notatie n!):

dac n = 0 atunci n! = 1

dac n > 0 atunci n! = n * (n-1)!

Astfel spus, factorialul unui numr n > 0 se obineprin nmulirea numrului cu factorialulpredecesorului.

Proiectarea Algoritmilor - curs

11515

Coninutul cursului

1. Conceptul de recursivitate

2. Recursivitate direct

3. Recursivitate indirect

4. Relatia dintre recursivitate si iteratie

5. Exemple de programe recursive

Proiectarea Algoritmilor - curs

11616

Recursivitate direct

n limbajul C++ functiile se pot apela peele nsele, adic sunt direct recursive.

Pentru o functionare corect (din punct devedere logic), apelul recursiv trebuie s fieconditionat de o decizie care, la un moment

dat n cursul executiei, s mpiedicecontinuarea apelurilor recursive si s permitastfel revenirea din sirul de apeluri.

Proiectarea Algoritmilor - curs

11717

Recursivitate direct

Lipsa acestei conditii sau programarea ei

gresit va conduce la executarea unui sir deapeluri a crui terminare nu mai este controlatprin program si care, la epuizarea resurselor

sistemului, va provoca o eroare de executie:

Depsirea stivei de date.

Proiectarea Algoritmilor - curs

11818

Exempluvoid p (list de parametri){lista variabile locale

...

p(list de parametri);}

Conditia care trebuie testat este specific problemei de rezolvat.

Programatorul trebuie s o identifice n fiecare situatie concret si, pe baza ei, s redacteze corect apelul recursiv.

Revenirea din apeluri se face n ordine invers.

if (cond) p(list de parametri) ... sau:while (cond) { ...p(list de parametri) } sau:do ... p(list de parametri)... while (cond)

11919

Coninutul cursului

1. Conceptul de recursivitate

2. Recursivitate direct

3. Recursivitate indirect

4. Relatia dintre recursivitate si iteratie

5. Exemple de programe recursive

Proiectarea Algoritmilor - curs

12020

Recursivitate indirect

Un subprogram S, n corpul cruia apar apeluri la S (la el nsui) se numete subprogram direct recursiv iar un subprogram P, pentru care exist un subprogram Q, astfel nct P face apeluri la Q, iar Q conine apelul la P se numete subprogram indirect recursiv.

n acest ultim caz, subprogramele P i Q se mai numesc i mutual recursive.

Proiectarea Algoritmilor - curs

12121

Recursivitate indirect

Funcie direct recursiv

functia S;

{

S; // apel la functia S

}

Funcii mutual recursivefunctia P;

{

Q ; // apel la functia Q

}

functia Q;

{

P ; // apelul functiei P

}

Proiectarea Algoritmilor - curs

12222

Coninutul cursului

1. Conceptul de recursivitate

2. Recursivitate direct

3. Recursivitate indirect

4. Relatia dintre recursivitate si iteratie

5. Exemple de programe recursive

Proiectarea Algoritmilor - curs

12323

Relaia dintre recursivitate iiteraie - Comparaie

Iteraia

executia repetat a uneisecvente de instructiuni

o nou iteratie se execut doarn urma evalurii unei conditii(la nceput sau sfrsit)

fiecare iteratie se execut pnla capt si apoi se trece,eventual, la o nou iteratie

se recomand atunci cndalgoritmul de calcul esteexprimat printr-o formuliterativ

Recursivitatea

executia repetat a unei functii

un nou apel recursiv se execut tot n urma evalurii unei conditii (pe parcurs)

functia recursiv se apeleazdin nou, nainte de terminareaapelului precedent

se recomand doar atunci cndproblema este prin definitie

recursiv (recursivitateaconsum resurse n exces)

Proiectarea Algoritmilor - curs

12424

Coninutul cursului

1. Conceptul de recursivitate

2. Recursivitate direct

3. Recursivitate indirect

4. Relatia dintre recursivitate si iteratie

5. Exemple de programe recursive

Proiectarea Algoritmilor - curs

12525

Probleme rezolvate

1. Se dau doua numere intregi a si b si se cere sa se calculeze cel mai mare divizor comun. (Algoritmul lui EUCLID prin mpriri repetate).

Formularea recursiv, n cuvinte, a algoritmului:

Dac unul dintre numere este zero, c.m.m.d.c. al lor este cellalt numr.

Dac nici unul dintre numere nu este zero, atuncic.m.m.d.c. nu se modific dac se nlocuieste unul dintre numere cu restul mprtirii sale cu cellalt.

Proiectarea Algoritmilor - curs

12626

Probleme rezolvate

Algoritmul poate fi implementat sub forma

urmtoarei functii recursive:

int cmmdc (int n, int m)

{

if (n==0) return m;

else return cmmdc(n, m % n);

}

Proiectarea Algoritmilor - curs

12727

Probleme rezolvate

Codul sursa al implementarii (varianta prin scaderi succesive) este urmatorul:

#include

int cmmdc(int a,int b)

{

if(a==b) return a;

else if(a>b) return cmmdc(a-b, b);

else return cmmdc(a, b-a);

}

Proiectarea Algoritmilor - curs

12828

int main(void)

{

int a, b;

char c;

do

{

couta;

coutb;

cout

12929

Executia programului pentru cateva date de test:

Proiectarea Algoritmilor - curs

13030

Probleme rezolvate

2. S se calculeze suma primelor n numerenaturale.

Soluia este dat de relaia de recuren:

suma(1, 2, . . . , n) =

suma(n, suma(1, 2, . . . , n-1))

Proiectarea Algoritmilor - curs

13131

#include

long int suma(long int i)

{

if(i==1) return 1;

else return suma(i-1)+i;

}

int main(void)

{

long int n;

coutn;

cout

13232

Executia programului pentru o valoare de test:

Proiectarea Algoritmilor - curs

13333

Probleme rezolvate

3. S se afle elementul maxim dintr-un vector dat.

Soluia este dat de relaia de recuren:

maxim(a1, a2 , . . . ,an) =

maxim(an, maxim(a1, a2, . . . , an-1))

Proiectarea Algoritmilor - curs

13434

#include

int a[100],n,i;

int max(int x, int y)

{

if(x > y) return x;

else return y;

}

int maxim(int a[ ],int n)

{

if(n==1) return a[1];

else return max(a[n],maxim(a,n-1));

}

int main(void)

{

coutn;

for(i=1;i

13535

Executia programului pentru cateva valori de test:

Proiectarea Algoritmilor - curs

13636

Probleme rezolvate

4. Sa se transforme un numar n, dat in baza

10, intr-o alta baza b (2

13737

#include

int n,b;

void baza(int n)

{

if(n

13838

Executia programului pentru cateva valori de test:

Proiectarea Algoritmilor - curs

13939

Probleme rezolvate

5. Se citeste un numar intreg ca un sir de

caractere cu cel mult 255 cifre.

Sa se afiseze numarul cu cifrele in ordine

inversa.

Proiectarea Algoritmilor - curs

14040

#include

#include

char n[255],i,l;

void invers(int i)

{

if(i

14141

Executia programului pentru o valoare de test:

Proiectarea Algoritmilor - curs

14242

Probleme rezolvate

6. Suma puterilor rdcinilor

Fie ecuaia x2 - Sx + P = 0 cu S, P R si x1, x2 rdcinile ecuaiei.

S se calculeze Sn= x1n + x2

n , n N.

Proiectarea Algoritmilor - curs

14343

Cutm relaia de recuren pentru Sn, tiind c x1, respectiv x2 sunt rdcinile ecuaiei date i deci ndeplinesc relaiile:

x12 - Sx1 + P = 0 | * x1

n-2

x22 - Sx2 + P = 0 | * x2

n-2

nmulim aceste relaii cu x1n-2 i x2

n-2 i adunm relaiile obinute i rezult:

Sn = x1n + x2

n =

= S * (x1n-1 + x2

n-1 ) P * (x1n-2 + x2

n-2 ) =

= S * Sn-1 - P * Sn-2

Proiectarea Algoritmilor - curs

14444

Astfel am obinut o relaie de recuren:

S0 = x11 + x2

1 = 1 + 1 = 2, pentru n=0

S1 = x11 + x2

1 = S, pentru n=1

Sn = S * Sn-1 - P * Sn-2, pentru n 2

Proiectarea Algoritmilor - curs

14545

#include

int n;

float s,p,r;

float suma(int n)

{

if(n==0) return 2;

else if(n==1) return s;

else return(s*suma(n-1)-p*suma(n-2));

}

int main(void)

{

cout

14646

Executia programului pentru un set de valori de test:

Proiectarea Algoritmilor - curs

14747

Probleme propuse spre rezolvare

1. S se scrie un program care s calculeze al n-lea termen din irul lui Fibonacci, care este definit recursiv astfel:

fib[1]=0

fib[2]=1

fib[n]=fib[n-1] + fib[n-2], pentru n>2

2. S se caute o soluie nerecursiv pentru irul lui Fibonacci.

Proiectarea Algoritmilor - curs

14848Proiectarea Algoritmilor - curs

ntrebri?