Subprograme- recursivitatea în cascadă Să repetăm: ce înseamnă n! 3!=6 5!=120 dar 0!=1 ? (prin def.) Dar în C++ cum vom calcula factorialul? P:=1; For I:=1 to n do P:=p*i; Scrie p; RECURSIVITATEA ÎN CASCADA Sa analizam Algoritmul pentru calculul sirului lui Fibonacci în varianta iterativa si în varianta recursiva. Enunt : Sa se determine primele n numere ale sirului lui Fibonacci, unde n este este un numar natural citit de a tastatura. (exp: n=8, => {1, 1, 2, 3, 5, 8, 13, 21}) Fişa B Recursivitatea în cascadă Sa analizăm algoritmul pentru calculul şirului Fibonacci în varianta iterativa şi în varianta recursivă.
Transcript
Subprograme- recursivitatea în cascadă
Să repetăm: ce înseamnă n!
3!=6
5!=120
dar 0!=1 ? (prin def.)
Dar în C++ cum vom calcula factorialul?
P:=1;
For I:=1 to n do
P:=p*i;
Scrie p;
RECURSIVITATEA ÎN CASCADA
Sa analizam Algoritmul pentru calculul sirului lui Fibonacci în varianta iterativa si în varianta recursiva.
Enunt : Sa se determine primele n numere ale sirului lui Fibonacci, unde n este este un numar natural citit de a tastatura. (exp: n=8, => {1, 1, 2, 3, 5, 8, 13, 21})
Fişa B Recursivitatea în cascadă
Sa analizăm algoritmul pentru calculul şirului Fibonacci în varianta iterativa şi în varianta
recursivă.
Enunt : Sa se determine primele n numere ale sirului lui Fibonacci, unde n este este un numar natural
citit de a tastatura. (exp: n=8, => {1, 1, 2, 3, 5, 8, 13, 21})
Varianta iterativă
fibo1, fibo2 = elementele initiale
Date de intrare : n = câte elemente ale sirului lui Fibonacci vor fi calculate
Date intermediare : i = contor care numara elementele generate
Date de ieşire : fibo3 = elementul generat
Algoritmul constă în generarea celui de-al treilea element (fibo3) cunoscându-le pe precedentele două ( fibo1 si fibo2), după care fibo1 fibo2 si fibo2 fibo3
fibo(0) =0
fibo(1) =1
fibo(2)= fibo(0)+fibo(1)=0+1=1
fibo(3) =fibo(1)+fibo(2)=1+1=2
fibo(4)= fibo(2)+fibo(3)=1+2=3
………….
fibo(n) = fibo(n-2)+fibo(n-1)
Ite
rati
v
Re
curs
iv
PROGRAM C++ (varianta iterativa)
VARIANTA RECURSIVĂ
Se defineşte şirul lui Fibonacci, prin funcţia fibo:N N:
0 pentru n=0;
fibo(n)= 1 pentru n=1
fibo(n-1)+fibo(n-2) pentru i>1
#include<iostream>
using namespace std;
int main(){
int n, fibo1=1, f ibo2=1, fibo3, i;
cout<<"n="; cin>>n;
cout<<fibo1<<" "<<fibo2<<" ";
for (i=3; i<=n; i++) /*se repeta de n-3 ori generarea unui numar al sirului lui Fibonacci fibo3=fibo1+fibo2; se genereaza un nou element*/
{
cout<<fibo3<<" ";
fibo1=fibo2;
fibo2=fibo3;
} return 0; }
// n – numarul de elemente;
// i – contor i€[3,n], deoarece primele doua elemente sunt a1 1 si a2 1;
// fibo1, fibo2, fibo3 – elementele şirului lui Fibonacci
PROGRAM C++ (varianta recursiva)
O astfel de recursivitate se numeşte recursivitate în cascadă deoarece se reapelează.
#include<iostream>
using namespace std;
int n; //n- variabilă globală
int fibo(int n)
{ // n- este declarat variabila n ca variabilă locală
if (n==0) return 0;
else if (n==1)
return 1;
else return fibo(n-1)+fibo(n-2);
}
int main()
{ // n – numarul de elemente (variabila globala);
cout<<"n="; cin>>n;
cout<< "Termenul "<< n<< " al sirului lui Fibonacci este"<<f ibo(n);
return 0;
}
Observaţii:
Pentru calculul lui fibo(n) este necesar sa se cunoasca fibo(n-1) si fibo(n-2), deci se execută
autoapelul de două ori în cazul general.
Parametrii acestor functii sunt depusi în stivă. Procedeul continuă pâna când este calculat
fibo(n-1), apoi se reia calculul pentru fibo(n-2).
Acest lucru este extrem de ineficient pentru valori mari ale lui n.
Acest tip de recursivitate este un exemplu în care programul iterativ este mult mai eficient
decât programul recursiv.
Adâncimea recursivităţii pentru apelul fibo(4) este 9:
Dacă notăm cu ar(n) adâncimea recursivităţii pentru apelul fibo(n) observăm că:
ar(1)= ar(0)=1
ar(2)=1+ ar(1)+ ar(0)=1+1+1=3
fibo(4) fibo(3) fibo(2) fibo(1)=1
3 2
+
fibo(0)=0
+ fibo(1)=1
fibo(2) fibo(1)=1
1 +
fibo(0)=0
ar(3)=1+ ar(2)+ ar(1)=1+3+1=5
ar(4)=1+ ar(3)+ ar(2)=1+5+3=9
…….
ar(5)=1+ ar(4)+ ar(3)=1+9+5=15
ar(6)=1+ ar(5)+ ar(4)=1+15+9=25
ar(7)=1+ ar(6)+ ar(5)=1+25+15=41
……………
ar(n)=1+ ar(n-1)+ ar(n-2)
Temă :
1. Să se afişeze toţi termenii şirului lui Fibonacci mai mici decât un numar natural n introdus de la
tastatură. (inclusiv matricea de valori)
2. Să se scrie un algoritm pentru afişarea termenului n din urmatoarele şiruri :
an=an-1+bn-1;
bn=(bn-1)2-(an-1)2
Fişa C Fixare de cunoştinţe:
o Încercaţi parcurgerea următoarelor programe în C++ şi matricea de variaţie:
Analizaţi şi explicaţi rolul fiecărei linii
# include <iostream>
using namespace std;
void f1 ()
{
cout << "123 abc";
}
void main ()
{
f1();
}
#include <iostream>
using namespace std;
void f1 (int k)
{
for (int i=1; i<=k ; i++)
cout << "abc"<< " ";
}
int main ()
{
f1(5);
}
Se va afisa:
123 abc
Se va afişa:
abc abc abc abc abc
Funcţia nu returnează o valoare
Funcţia nu are parametri
Apelul funcţiei este o instrucţiune de
apel simplă
Funcţia nu returnează o valoare
Funcţia are un parametru formal de tip int
Apelul funcţiei este o instrucţiune de apel simplă şi se face cu ajutorul
unui parametru actual care este de acelaşi tip cu tipul parametrului
formal corespunzător
Să se testeze dacă un număr este prim sau nu
#include <iostream>
#include <math.h>
using namespace std;
int prim (int x)
{
int nr_div=0;
for (int i=2; i<=sqrt(x); i++)
if (x%i==0)
nr_div++;
if (nr_div==0)
return 1;
else
return 0;
}
int main ()
{
int N;
cout << "N="; cin >> N;
if (prim(N))
cout << "PRIM";
# include <iostream>
# include <math.h>
using namespace std;
int prim (int x)
{
for (int i=2; i<=sqrt(x); i++)
if (x%i==0)
return 0;
return 1;
}
int main ()
{
int N;
cout << "N="; cin >> N;
if (prim(N))
cout << "PRIM";
else
cout << "NU E PRIM";
}
else
cout << "NU E PRIM";
}
Funcţia returnează o valoare de tip
int
Funcţia are un parametru formal de
tip int
Rezultatul funcţiei este utilizat în
cadrul unei expresii de testare (IF)
În cazul în care se întâlneşte un divizor a lui x se execută
instrucţiunea return 0. Astfel apelul funcţiei se încheie.
Dacă x este număr prim, instrucţiunea return 0 nu se execută
niciodată şi în acest caz, după terminarea execuţiei instrucţiunii for, se
execută instrucţiunea return 1 (care determină încheierea execuţiei
funcţiei).
o Se citeşte un număr natural n. Să se calculeze utilizând varianta iterativă şi varianta
recursivă suma primelor n numere naturale.
(exp: n=4 => s=1+2+3+4=10)
În varianta iterativa definitia
functiei se face printr -o
expresie care contine numai
În varianta recursiva definitia functiei se face printr-
o expresie care contine însas i functia:
valori cunoscute.
0 pentru n=0;
Suma(n)=
1+2+3+…+n pentru
n!=0
0 pentru n=0;
Suma(n)=
n+Suma(n-1) pentru n!=0
PROGRAM C++ (varianta iterativa) PROGRAM C++ (varianta recursiva)
#include<iostream.h>
using namespace std;
int suma(int n){
int i, s=0 ;
if (n==0)
return 0;
else{
for (i=1 ; i<=n ; i++)
s+=i ; // s=s+i
return s ;
}
}
#include<iostream.h>
using namespace std;
int suma(int n){
if (n==0)
return 0;
else
return n+suma(n-1);
}
int main(){
int n;
cout<<"n="; cin>>n;
cout<<"Suma="<<suma(n)<<endl;
Observaţii varianta recursivă:
1. Recurenţa este realizată prin autoapelul functiei suma.
2. Pentru calcularea sumei sunt necesare doua elemente :
- Formula de recurenta : suma(n)=n+suma(n-1);
- O valoare iniţiala cunoscută : suma(0)=0;
3. Numele functiei poate sa apara si în membrul stâng al unei instructiuni de
atribuire.
4. Ideea de baza a recursivitatii este aceea ca fiecare nou apel al functiei
(autogenerarea unui nou proces de acelasii fel) ne apropie de solutia finala care
corespunde valorii initiale cunoscute.
int main(){
int n;
cout<<"n="; cin>>n;
cout<<"Suma="<<suma(n);
return 0;
}
return 0;
}
o Se citeşte un numar natural n. Să se calculeze utilizând varianta iterativă
şi varianta recursivă factorialul numarului n. (exp: n=4 => n!=1*2*3*4=24)
o
PROGRAM C++ (varianta iterativa) PROGRAM C++ (varianta recursiva)
#include<iostream.h>
using namespace std;
int fact(int n){
int i, p=1;
if (n==0)
return 1;
else{
for (i=1 ; i<=n ; i++)
p=p * i;
return p;
}
}
int main(){
int n;
cout<<"n="; cin>>n;
#include<iostream.h>
using namespace std;
int fact(int n){
if (n==0)
return 1;
else
return n*fact(n-1);
}
int main(){
int n;
cout<<"n="; cin>>n;
cout<<n<<"!="<<fact(n);
return 0;
}
o Se citeste un numar natural n. Să se calculeze utilizând varianta iterativă şi
varianta recursiva suma cifrelor numarului n.
(exp: n=1325 => s=1+3+2+5=11)
În varianta iterativa definitia functiei se face
printr -o expresie care contine numai valori
cunoscute.
0 pentru n=0;
S(n)=
s+(n%10); n=n/10; altfel
În varianta recursiva definitia functiei se face printr-o
expresie care contine însăşi functia:
0 pentru n=0;
S (n)=
n%10+S(n/10) altfel
cout<<n<<"!="<<fact(n);
return 0;
}
În varianta iterativa definitia functiei se face
printr -o expresie care contine numai valori
cunoscute.
1 pentru n=0;
Fact(n)=
1*2*3*…*n altfel
În varianta recursiva definitia functiei se face printr-o
expresie care contine însăşi functia:
1 pentru n=0;
Fact(n)=
n*Fact(n-1) altfel
PROGRAM C++ (varianta iterativă) PROGRAM C++ (varianta recursivă)
#include<iostream.h>
using namespace std;
int suma_cifre(int n){
int s=0 ;
while (n!=0){
s+=n%10; // s=s+n%10
n/=10; // n=n/10
}
return s ;
}
int main(){
int n;
cout<<"n="; cin>>n;
cout<<"Suma="<<suma_cifre(n);
return 0;
}
#include<iostream.h>
using namespace std;
int suma_cifre(int n)
{
if (n==0)
return 0;
else
return n%10+suma_cifre(n/10);
}
int main(){
int n;
cout<<"n="; cin>>n;
cout<<"Suma="<<suma_cifre(n);
return 0;
}
Test – Subprograme
1. Explicaţi noţiunile de parametrii locali, parametrii globali. (1p)
2. Stabiliti valoarea de adevar a fiecaruia dintre urmatoarele enunturi (1p)
a) Subprogramele reprezinta acele parti ale unui program ce corespund subproblemelor in care
este descompusa o problema complexa. (0,25p)
b) Parametri definiţi în antetul unui subprogram se numesc formali, iar cei care apar la apelul
subprogramului se numesc actuali (0,25p)
c) Corpul unui subprogram trebuie cuprins între {…} numai daca este alcatuit din cel puţin
două instrucţiuni distincte (0,25p)
d) La transmiterea prin valoare, parametri actuali pot fi: constante, variabile, valori ale unor
expresii, valori returnate de alte functii. (0,25p)
3. Folosind doua functii recursive, sa se calculeze valoarea functiilor matematice f(x) si g(x),
pentru o valoare a argumentului x introdusa de la tastatura. (1p)
f(x)= 1+ g(x), pentru x <= 3 g(x)= 5 ,pentru x<0
x*x , pentru x > 3, 2*x + f(x+1), pentru x >=0
4. Completează următoarele enunţuri cu cuvinte potrivite astfel încât să obţii afirmaţii adevărate:
a) Unitatea de bază a oricărui program C++ este ______________ . Acesta este încapsulat într-o instrucţiune
_____________ delimitată de caracterele ________ . (0,25p)
b) Blocul este format din ____ părţi: partea ____________ şi partea _______________. (0,25p)
c) Subprogramul este _______________________________________________________ ___ __
