Metode si Tehnici de programare - limbajul C++
Adrian Runceanu
Capitolul 1 - ALGORITMI RECURSIVI
A.Consideratii teoretice
Numim program recursiv un program care contine cel putin un subprogram recursiv. Un subprogram se numeste recursiv daca in cadrul definitiei sale se autoapeleaza. Din matematica, multe definitii utilizeaza construirea unor concepte prin aceasta metoda speciala numita recursie. Astfel se pot defini numerele naturale sau unele functii:
- 1 este un numar natural
- succesorul unui numar natural este tot un numar natural (bineinteles mai trebuie definita apoi notiunea de succesor)
- functia lui ACKERMANN, ack(m,n)=:
- n+1 daca m=0;
- ack(m-1,1) daca n=0;
- ack(m-1,ack(m,n-1)) altfel;
B.Exemple de programe
Prezentam in continuare cateva programe simple cu solutii recursive pentru :
1. Calculul celui mai mare divizor comun. (algoritmul lui EUCLID).
2. Calculul lui n!. (n factorial)
3.Sa se calculeze suma primelor n numere naturale.
4. Sa se genereze partitiile unui numar natural n, doua partitii diferind fie prin valorile elementelor din partitie, fie prin ordinea acestora.
Solutie: Generarea partitiilor presupune alegerea primului termen din partitie - pi, si apoi generarea tuturor partitiilor numarului n-pi.
5. Suma puterilor radacinilor
Fie ecuatia x2 - Sx + P = 0 cu S, P R si x1, x2 radacinile ecuatiei. Sa se calculeze Sn= x1 + x2, n <= N.
6. Sa se afle elementul maxim dintr-un vector dat.
7. Sa se genereze toate submultimile unei multimi.
8. Sa se transforme un numar n, dat in baza 10, intr-o alta baza b (2<=b<=10).
9. Se citeste un numar intreg cu cel mult 255 cifre. Sa se afiseze numarul cu cifrele in ordine inversa.
10. Se dau doi vectori x si y cu n componente de tip cifra. Se cere sa se calculeze suma x[0]^y[0] + x[1]^y[1] + . . . + x[n-1]^y[n-1].
Se vor utiliza doua functii recursive pentru calculul unui numar a la puterea b si respectiv suma componentelor unui vector.
C.Exercitii si teme
1. Sa se ruleze cele zece programe, urmarind apelurile si valorile parametrilor de apel.
2. Sa se scrie un program care sa 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]
3. Sa se caute o solutie nerecursiva pentru sirul lui Fibonacci.
4. Sa se calculeze functia Manna-Pnueli, data de relatia f(x)=:
- | x-1, daca x>=12
- | f(f(x+2)), daca x<12
5. Sa se scrie un program recursiv care sa compare doua siruri de caractere.
6. Sa scrie un program recursiv care sa verifice daca doua siruri de caractere sunt anagrame. Doua cuvinte sunt anagrame daca contin aceleasi litere dar in ordine diferita. Exemplu: sirul "DARIAN" este anagrama pentru sirul "ADRIAN".