Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  

CATEGORII DOCUMENTE





loading...

AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Recursivitate - Recursivitate in cascada

algoritmi

+ Font mai mare | - Font mai mic







DOCUMENTE SIMILARE

Trimite pe Messenger
PROGRAMARE LINIARA
Inteligenta artificiala - Definitii ale inteligentei artificiale
Exemple de scheme logice
SISTEME CU PROCESOARE MULTIPLE
Arbori - Proprietati ale arborilor
Metoda „greedy”
Generarea grafica a curbei lui Koch
Evaluarea corectitudinii algoritmilor
Arbori binari,parcurgerea arborilor binari
Introducere in ModelSIM

Recursivitate

I.1          Clasificarea definitiilor recursive

In functie de modul in care o definitie (functie) se autoapeleaza, avem urmatoarele tipuri de recursii:

I.      recursie directa: are loc atunci cand o functie se autoapeleaza pe ea insasi. Exista mai multe forme de autoapelari:

I.1.           recursie liniara: este intalnita in cazul in care evaluarea functiei intr-un punct presupune evaluarea unei alte valori a functiei. Functiile recursive liniare se dezvolta pe un singur nivel.

De exemplu, varianta recursiva a factorialului, unde:

Evaluarea termenului f(3), presupune evaluarea termenului f(2), care la randul sau va evalua pe f(1) samd. pana cand succesiunea de reapelari se opreste, n fiind 0. Altfel spus,

f(3)=3*f(2)=3*2*f(1)=3*2*1*f(0)= 3*2*1*1=6.

Succesiunea de autoapelari este liniara: f(3) ← f(2) ← f(1) ← f(0), de unde si denumirea de recursie liniara.

I.2.    recursie neliniara, care la randul ei poate avea mai multe forme:

I.2.1.        recursie in cascada: evaluarea functiei intr-un punct necesita evaluarea mai multor valori ale functiei.

De exemplu, sirul lui Fibonacci descris prin functia de mai jos:

Sirul lui Fibonacci este un exemplu de recursie in cascada deoarece evaluarea celui de-al n-lea termen Fib(n) comporta evaluarea celor doi termeni imediat anteriori: Fib(n-1) si Fib(n-2).

Reprezentarea arborescenta a modului in care este evaluat un anumit termen sugereaza o cascada, de unde si denumirea metodei. O abordare recursiva a problemei va duce la completarea arborelui in maniera top-down.

Fig. II1. Recursivitate in cascada

I.2.2.        recursie de tip impachetat: evaluarea functiei intr-un punct presupune evaluari repetate, imbricate ale functiei in alte puncte.

De exemplu, functia Manna-Pnueli M(x), de forma:

Un alt exemplu de functie recursiva de tip impachetat este functia lui Ackermann, , definita mai jos:

Recursia neliniara (in cascada sau de tip impachetat) duce adeseori la recalculare de termeni: se observa imediat in figura II.1. ca in procesul de evaluare a lui Fib(n-1) se ajunge la evaluarea lui Fib(n-2), care va fi apoi reevaluat la nivelul lui Fib(n). Recalcularea unor valori ale functiei face ca implementarea recursiva sa fie ineficienta ducand la timpi indelungati de calcul chiar si pentru valori moderate ale lui n. In aceasta situatie se recomanda metode alternative asa cum vom vedea mai departe in cadrul acestei sectiuni.

II.      recursie indirecta, are loc atunci cand o functie se autoapeleaza (indirect)apeland o alta functie, care la randul sau o apeleaza pe prima. De exemplu, sirurile:



I.2          Mecanismul de functionare

In scopul realizarii unui algoritm recursiv, trebuie sa se aiba in vedere urmatoarele doua principii:

function factR(integer n)

if n=0 then factR←1

else factR←n*factR(n-1)

endif

end

In limbajul C++, functia recursiva va fi:

double factR(int n)

Sa urmarim evolutia stivei atunci cand functia factR este apelata pentru n=2.

Se aloca pe stiva un segment in care se incarca parametrul n cu valoarea de la apel (2) si adresa de revenire in functia apelanta. Se executa functia. Intrucat n nu este 0, se executa a doua linie, care presupune un reapel al functiei factR, pentru n=1.

rev=adresa 2

n=1

rev=adresa 1

n=2

Se reapeleaza factR, cu n=1. Se aloca pe stiva parametrul n cu valoarea 1 si adresa de revenire in functia factR (la apelul anterior), adresa2. Intrucat n nu este 0, se reapeleza din nou factR, pentru n mai mic cu o unitate: n=0.

rev=adresa 3

n=0

rev=adresa 2

n=1

rev=adresa 1

n=2

Se reapeleaza factR, cu parametrul n=0. Se aloca pe stiva un nou segment, unde sunt incarcati parametrul n, cu valoarea 0 si adresa de revenire: adresa3. De aceasta data, pentru ca n este nul, se va executa prima linie de cod, care asigura revenirea in recursivitate, cu o valoare direct calculabila: valoarea 1. Odata ce s-a executat instructiunea return 1, care determina incheierea executiei (apelului curent al) functiei, segmentul de stiva corespunzator este sters si se revine in punctul imediat urmator apelului anterior, la adresa adresa1.



rev=adresa 2

n=1

rev=adresa 1

n=2

In acest moment valoarea curenta a variabilei n este 1, deci se va evalua expresia 1*1 si se va returna apelului anterior valoarea 1, in punctul adresa2, dupa ce va sterge segmentul corespunzator de stiva.

rev=adresa 1

n=2

Acum valoarea variabilei n este 1, ceea ce va determina returnarea apelului anterior a valorii 2*1, in punctul adresa1, care corespunde functiei principale. In acest moment stiva este complet distrusa.


I.3          Iterativitate sau recursivitate

function Fib (integer n)

if n=0 or n=1 then Fib←1

else Fib← Fib(n-1)+Fib(n-2)

end if

end

Recalcularea termenilor face ca implementarii recursiva sa i se asocieze o complexitate de ordin exponential. Intr-adevar, daca T(n) este numarul de autoapelari ale functiei necesar evaluarii termenului n, atunci:

Prin inductie matematica se poate arata imediat ca :

Relatia se verifica pentru n=2 si n=3 si

asadar, varianta recursiva este de complexitate exponentiala .

Evident, un algoritm mai eficient ar evita recalcularea termenilor. In cazul functiei lui Fibonacci, o solutie alternativa ar fi realizarea unei implementari iterative:

function Fib(integer n)

integer F0←1, F1←1, F2←1

for i=2 to n do

F2←F1+F0

F0←F1

F1←F2

next i

Fib← F2

end


I.4          Metoda tabelarii

if (termenul a fost deja evaluat)

then [ intoarce valoarea corespunzatoare din tabela]

else

[calculeaza noua valoare]

[memoreaza valoarea in tabela]

[intoarce valoarea noua]

end if

Scopul memorarii valorilor deja calculate este acela de a reduce complexitatea algoritmului.

In cazul functiei Fibonacci sevor retine intr-un vector cu n+1 componente valorile functiei, pe masura ce sunt calculate.

function Fib(integer n, integer Table[0..n])

if (Table[n] <> 0 /*neincarcat*/ ) then

Fib← T[n]

else

Table[n] ←Fib(n-1, Table[0..n])+Fib(n-2, Table[0..n])

Fib← Table[n]

end if

end

Table[0] ←1

Table[1] ←1

for i=2 to n do

Table[i] ←0

next i

function Fib(integer n)

integer Table[0..n]

Table[0] ←1

Table[1] ←1




for i=2 to n do

Table[i] ← Table[i-1]+Table[i-2]

next i

Fib←Table[n]

end


I.5          Aplicatii

I.5.1         Procedura pentru factorial recursiv

procedure (integer n, ref integer f)

if (n<>0) then fact(n-1,f*n)

end

In limbajul C/C++ a fost creata o functie care nu intoarce valoare:


Procedura pentru factorial recursiv


#include<iostream.h>

void fact(int n, double &f)

void main()


I.5.2         Inversarea sirului de caractere

I.5.3         Siruri - Recursivitate indirecta

Sa se exemplifice modul de utilizare a recursivitatii indirecte, generand valorile sirurilor an si bn, definite mai jos, pentru a, b si n introduse la tastatura:

I.5.4         Algoritmul lui Euclid

P1. [Aflarea restului] - se determina restul impartirii lui a la b si se depune in r;

P2. [Testarea continuarii] – daca r este 0, algoritmul se incheie, cel mai mare divizor comun fiind b; daca r nu este 0, algoritmul continua cu pasul 3;

P3. [Reducerea] – a devine b, b devine r si se reia pasul 1.

Solutie:


Algoritmul lui Euclid pentru cmmdc


#include<iostream.h>

int cmMdcI(int a, int b)

return a;

}

int cmMdcR(int a, int b)

main()

while(a);

cout<<'cmMdc al sirului este '<<cmMdc;

return 0;

}


Observatie:

I.5.5         Triunghiul lui Pascal

Sa se calculeze coeficientii binomiali Cnk, pentru n<N (N dat) si in varianta recursiva si sa se utilizeze pentru a afisa Triunghiul lui Pascal.

Celebrul triunghi poarta numele matematicianului francez Blaise Pascal pentru ca a fost prezentat in tratatul acestuia „Traite du Triangle Arithmetique”, aparut in anul 1653. Cu toate acestea, coeficientii binomiali au o istorie mult mai indelungata: ei apar mai intai in scrierile grecesti si latine in interpretare geometrica pentru valori mici ale lui n si k. O prezentare detaliata a lor apare in jurul anului 1150 intr-o lucrare hindusa. Triunghiul „lui Pascal” a aparut si el cu mult inaintea vremii celui al carui nume il poarta si anume in sec. XIV, in lucrarea „Pretioasa oglinda a celor patru elemente” apartinand unui matematician chinez.

Indicatie:

Formula de calcul este:

sau in varianta recursiva:

Pentru ca implementarea recursiva a functiei de mai sus duce la recalculare de termeni, se va utiliza metoda tabelarii. Fiecare valoare Cnk, odata calculata, va fi retinuta in componenta Table[n][k]; astfel, masivul Table va fi bidimensional cu N linii, fiecare linie n avand n+1 componente (masivul va fi incarcat numai pe jumatate: ).

Solutie:


Triunghiul lui Pascal


#include <iostream.h>

int C(int n,int k,int**Table)

main()

}

for(n=0;n<N;n++)

delete[]Table[n];

delete[]Table;

return 0;

}


Pentru N=7, aplicatia va afisa:

I.5.6         Problema crescatorului de iepuri

Un taran isi propune sa cumpere o pereche de iepuri tineri. Presupunand ca o pereche de iepuri se inmulteste odata in fiecare luna si are un singur pui care devine fertil dupa o luna, in plus, iepurii nu mor, cate perechi de iepuri va avea taranul dupa un an?



Asadar, la inceput taranul are o singura pereche de iepuri, in luna a doua perechea devine fertila si se inmulteste, astfel ca la inceputul lunii a treia taranul va avea doua perechi de iepuri, in a patra luna va avea trei perechi (perechea de o luna inca nu s-a inmultit), in cea de-a 5-a luna vor fi 5 perechi samd.

Aceasta problema a fost imaginata in sec. XIII, de catre cel mai mare matematician european al evului mediu, italianul Leonardo Fibonacci (fiul lui Bonaccio), referit si ca Leonardo Pisano (Leonardo din Pisa), si publicata in lucrarea sa Liber Abaci – Cartea Abacului, ca o introducere a celebrului sir de numere care ii poarta numele: 1, 1, 2, 3, 5, 8, 13, 21, 34 in care un termen este suma celor doi imediat anteriori. Proprietatile deosebite ale acestor numere au facut ca ele sa fie obiectul de interes al invatatilor tuturor timpurilor, astfel ca sirul fusese descris cu mult inainte de savanti indieni, interesati de tiparele muzicale ritmice formate ca succesiuni de batai simple sau duble.

Generarea termenilor sirului lui Fibonacci


#include<iostream.h>

typedef unsigned long INT;

INT *Table;

INT FibR(int n)

INT FibI(int n)

return Fib2;

}

INT FibRT(int n)

INT FibIT(int n)

main()


Observatie: Desi implementarea recursiva necesita un efort minim de programare, ea conduce la o recursie in cascada, de aceea variantele alternative sunt mult mai eficiente. Testati separat cele patru versiuni pentru n=25. Apoi incercati n=50. Ce observati? Evaluati complexitatea celor patru variante si comparati-le.

I.5.7         Functia lui Ackermann

Sa se genereze valoarea functiei lui Ackermann, intr-un punct dat.

Solutie:


Functia lui Ackermann


#include<iostream.h>

long Ack(int m, int n)

main()


I.5.8         Comparare alfanumerica siruri

Comparare alfanumerica


#include<iostream.h>

int strcmp(char *a, char *b)

main()

cout<<a<<rez<<b;

return 0;

}


I.5.9         Suma puterilor

Daca sisunt solutiile ecuatiei de gradul II: cu coeficienti reali, sa se calculeze sumapentru un n numar natural dat.

Indicatie:

Se va incerca gasirea unei formule recursive pentru suma ceruta. Astfel, daca sisunt solutiile ecuatiei, atunci ele o verifica:

.

Inmultind prima relatie cu si pe a doua cu :

obtinem ca:.

Adunand cele doua relatii si punand , obtinem relatia de recurenta dorita:

.

De aici incolo scrierea unei functii recursive este imediata.

Solutie:


Suma puterilor radacinilor


#include<iostream.h>

double S=4.,P=4.;

double Suma(int n)

main()


I.5.10     Ridicarea la putere - Optimizarea recursivitatii

Sa se realizeze functii, in doua variante, una iterativa si alta recursiva. pentru ridicarea la putere (intreaga) a unui numar oarecare.

Indicatie: Cazul in care n este negativ se reduce imediat la situatia cu exponent pozitiv: .

Solutie:


Ridicare la putere


#include<iostream.h>

#include<math.h>

double PowR(double x, int n)

double PowI(double x, int n)

main()


Cele doua variante, iterativa si recursiva, sunt similare din punctul de vedere al timpului de executie, exprimat prin numarul de inmultiri efectuate: pentru n pozitiv avem n inmultiri in ambele situatii. In varianta recursiva este utilizata stiva, rezulta ca pentru valori foarte mari ale lui n se poate produce depasirea memoriei.

Varianta recursiva este un exemplu de utilizare a metodei de programare Divide et Impera, in care rezolvarea unei probleme de dimensiune n a fost redusa la rezolvarea unei sub-probleme de dimensiune n-1. Solutia de programare poate fi imbunatatita simtitor daca sub-problema la care reducem va fi de dimensiune n/2.Pentru n este pozitiv vom considera utiliza relatia:

Prin [n/2] am inteles partea intreaga a impartirii (care in limbajul C se scrie simplu, n/2, avand in vedere ca cei doi operanzi sunt numere intregi), iar prin n%2 restul impartirii lui n la 2.

In aceasta varianta, stiva va avea k niveluri, atunci cand . Asadar, numarul de niveluri , este imbunatatit simtitor fata de varianta anterioara, cu n niveluri ale stivei.


Ridicare optimizata la putere


double PowR2(double x, int n)



loading...






Politica de confidentialitate

DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 2993
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2019 . All rights reserved

Distribuie URL

Adauga cod HTML in site