| CATEGORII DOCUMENTE |
DOCUMENTE SIMILARE |
|
TERMENI importanti pentru acest document |
|
Intr-un limbaj de programare, o subrutina este o functie sau o procedura. In algoritmica, prin procedura se intelege o functie care nu returneaza nici o valoare. Un subprogram recursiv este un subprogram care se autoapeleaza. Recursivitatea este un mecanism utilizat in elaborarea programelor pentru algoritmii recursivi. Deci, recursivitatea a aparut, in special, din necesitatea transcrierii directe a formulelor matematice recursive.
Pentru a putea implementa recursivitatea se foloseste structura de date stiva. Stiva este folosita atat in cazul apelurilor nerecursive, cat si in cazul apelurilor recursive. De data aceasta, stiva este gestionata de limbaj. La apelul recursiv al unei subrutine se depun in stiva :
valorile parametrilor transmisi prin valoare;
adresele parametrilor transmisi prin referinta;
valorile variabilelor locale (declarate la nivelul subprogramului).
Problema R1
Sa luam ca prim exemplu functia factorial, a carei definitie matematica recurenta este:
f1(n) = 
Rezolvare
In pseudocod, aceasta functie se transcrie astfel :
FUNCTIE f1(n);
BEGIN
IF n = 0 THEN
f1 := 1
ELSE
f1 := n* f1(n-1);
ENDIF;
END;
Se observa in linia (6) apelul recursiv al functiei (apelul din corpul functiei tot la ea, pana cand conditia n = 0 este indeplinita). Sa vedem functionarea functiei pentru n = 3; prin s notam stiva :
iteratia 1: n := 3, s := (3);
iteratia 2: n := 2, s := (2, 3);
iteratia 3: n := 1, s := (1, 2, 3);
iteratia 4: n := 0, s := (0, 1, 2, 3);
f1 = 1 si 0 este eliminat din stiva; f1 = 1*1 = 1 si 1 este eliminat din stiva; f1 = 2*1 = 2 si 2 este eliminat din stiva; f1 = 3*2 = 6 si 3 este eliminat din stiva; s = si se revine in programul apelant.
Codul sursa al programului este:
#include<stdio.h>
int factorial(int n)
void main()
Varianta iterativa a factorialului este urmatoarea:
In pseudocod se transcrie astfel :
FUNCTIE f1(n);
BEGIN
f1 := 1;
IF n > 0 THEN
FOR i := 2 TO N DO
f1 := f1 i;
ENDFOR;
ENDIF;
END;
Codul sursa al programului este:
#include<stdio.h>
int factorial(int n)
void main()
Problema R2
Sa se determine al n-lea element al sirului lui Fibonacci, care este definit recurent astfel:
Rezolvare
In pseudocod formula de mai sus se transcrie in modul urmator:
FUNCTIE f2(n);
BEGIN
IF n = 0 THEN f2 := 1
ELSE
IF n = 1 THEN f2 := 1
ELSE f2 := f2(n-1) + f2(n-2);
ENDIF;
ENDIF;
END;
Textul sursa al programului este:
#include<stdio.h>
int fibo(int n)
void main()
Sa vedem modul in care se realizeaza calculul recursiv al celui de-al n-lea element al sirului lui Fibonacci pentru n = 5. Modul de calcul este reprezentat sugestiv pe arborele binar din figura 4.1
Pentru calculul lui f2(5) este necesar sa se cunoasca f2(4) si f2(3). Parametrii acestor doua functii sunt depusi in stiva. Procedeul continua pana cand este calculat f2(4) (subarborele stang al nodului radacina etichetat cu 8 = f2(5)), apoi se reia calculul pentru f2(3) (subarborele drept al nodului radacina). Este evident ca multe calcule se repeta inutil. De aceea, cand avem de rezolvat o astfel de problema este bine sa analizam oportunitatea folosirii unei metode recursive sau a uneia iterative. In cazul sirului Fibonacci este recomandat sa se foloseasca un program care calculeaza f2(n) iterativ. Varianta iterativa este urmatoarea:
FUNCTIE f2(n) ;
BEGIN
IF n = 0 THEN f2 := 1
ELSE
IF n = 1 THEN f2 := 1
ELSE
BEGIN
f20 := 1; f21 := 1;
FOR i := 2 TO n DO
f2 := f20 + f21; f20 := f21; f21 := f2;
ENDFOR;
END;
ENDIF;
ENDIF;
END;
Codul sursa al programului este:
#include<stdio.h>
int fibo(int n)
return f2;
void main()
In algoritmica exista urmatorul rezultat de exceptie: pentru orice algoritm iterativ, exista unul recursiv echivalent (rezolva aceeasi problema) si invers, pentru orice algoritm recursiv, exista unul iterativ echivalent.
Sunt probleme pentru care elaborarea unui algoritm recursiv duce la un timp de calcul foarte mare, iar daca se elaboreaza un algoritm iterativ, timpul necesar de calcul este cu mult mai mic, asa cum s-a vazut in exemplul anterior. Pe de alta parte, implementarea unui algoritm recursiv conduce la un text sursa extrem de scurt si de cele mai multe ori, clar. Depinde de priceperea programatorului daca pentru o problema data elaboreaza un algoritm recursiv, sau unul iterativ.
Recursivitatea poate fi utilizata si in elaborarea algoritmilor recursivi care nu descriu formule matematice recurente. Sa consideram urmatorul exemplu:
Problema R3
Trecerea unui numar natural n, n ≥ 2, din baza 10 in baza 2.
Rezolvare
Dupa cum se stie n se imparte la 2 si se retine restul; catul se imparte la 2 si se retine restul, si asa mai departe se retin resturile obtinute prin impartirea catului la 2 pana cand catul devine 0. Numarul n in baza 2 se obtine considerand toate resturile in ordinea inversa a impartirilor.
Formula recursiva este urmatoarea:
t(n) = t(n div 2) + w(n div 2)
unde w inseamna WRITE.
In pseudocod aceasta formulare se transcrie astfel:
FUNCTIE t(n);
BEGIN
r := n mod 2;
IF n > 0 THEN
t(n div 2);
WRITE r;
ENDIF;
END;
Codul sursa al programului este:
#include<stdio.h>
void transf(int n)
void main()
Deoarece r este variabila locala, valorile ei vor fi salvate in stiva.
Daca k log n + 1 atunci varianta iterativa a problemei se transcrie in pseudocod astfel:
FUNCTIE t(n, k);
BEGIN
ARRAY r(k)
FOR i := 1 TO k DO
r[ k - i + 1 ] := n mod 2;
n := n div 2;
ENDFOR;
WRITE r;
END;
Codul sursa al programului este:
#include<stdio.h>
#include<math.h>
void t(int n, int k)
for(i=1;i<=k;i++)
printf('%d',r[i]);
void main()
Problema R4
Se da o matrice A cu n linii si n coloane. Sa se afiseze parcurgerea matricei in spirala dupa cum se vede in figura urmatoare.
Rezolvare
O matrice de dimensiune n are (n + 1) div 2 patrate concentrice. Fiecare patrat va fi parcurs in felul urmator: linia de sus de la stanga spre dreapta, coloana din dreapta de sus in jos, linia de jos de la dreapta spre stanga, coloana din stanga de jos in sus. Fiecare din cele patru parcurgeri se face in cate un subprogram recursiv. Parcurgerea in spirala a matricei se realizeaza tot intr-un subprogram recursiv.
In pseudocod aceste subprograme se transcriu astfel:
SUBPROGRAM SUS(I, J);
BEGIN
IF J ≤ N - I + 1 THEN
WRITE AIJ ;
SUS(I, J + 1);
ENDIF;
END;
SUBPROGRAM DREAPTA(I, J);
BEGIN
IF I ≤ J THEN
WRITE AIJ ;
DREAPTA(I + 1, J);
ENDIF;
END;
SUBPROGRAM JOS(I, J);
BEGIN
IF J ≥ N - I + 1 THEN
WRITE AIJ ;
JOS(I, J - 1);
ENDIF;
END;
SUBPROGRAM STANGA(I, J);
BEGIN
IF I ≥ J + 1 THEN
WRITE AIJ ;
STANGA(I - 1, J);
ENDIF;
END;
SUBPROGRAM SPIRALA(K);
BEGIN
IF K ≤ (N + 1) DIV 2 THEN
SUS(K, K);
DREAPTA(K + 1, N - K + 1);
JOS(N - K + 1, N - K);
STANGA(N - K, K);
SPIRALA(K + 1);
ENDIF;
END;
Codul sursa al programului este:
#include<stdio.h>
void sus(int a[20][20], int n, int i, int j)
void dreapta(int a[20][20], int n, int i, int j)
void jos(int a[20][20], int n, int i, int j)
void stanga(int a[20][20], int n, int i, int j)
void spirala(int a[20][20], int n, int k)
void main()
spirala(a, n, 1);
|
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 1229
Importanta: 
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved
