Proiect informatica-recursivitate
Pirvu Natalia-Elena
Clasa a XI-a B
1. Scrieţi definiția completă a subprogramului recursiv numarare, care primeşte
prin parametrul v un tablou unidimensional cu cel mult 100 de elemente întregi, iar
prin parametrul n numărul efectiv de elemente din v. Subprogramul returnează
numărul de perechi de elemente vecine din tabloul v care sunt egale.
int numarare(int v, int n)
if(n<2)
return 0;
else
return numarare(v,n-1)+(v[n-1]==v[n-2]);
2. Scrieți funcția recursivă având următorul antet:
int SC(char s[]). Funcția primește ca parametru un șir de caractere și returnează
suma tuturor cifrelor care apar în șir.
int SC(char s[])
if (s[0] == 0) return 0;
if ('0' <= s[0] && s[0] <= '9') return (s[0]-'0') + SC(s + 1);
return SC(s + 1);
}
3. Să se scrie o funcție C++ recursivă care citește de la tastatură un șir de valori
naturale și le afișează în ordine inversă, cu câte un spațiu între ele.
void afis()
{
int n;
cin>>n;
if(n==0)
cout<<0<<" ";
else
{
afis();
cout<<n<<" ";
}
}
4. Scrieţi definiția completă a subprogramului recursiv C++ multiplu care are 3
parametri: a, prin care primeşte un tablou unidimensional cu maximum 100 de
numere naturale mai mici decât 1000, n, numărul efectiv de elemente ale tabloului
şi k, un număr natural.
Subprogramul returnează numărul de elemente din tablou care sunt multipli ai
numărului k şi au ultima cifră egală cu k.
int multiplu(int v[],int n,int k)
{
if(n==0)
return 0;
if(n>0)
{
if(a[n-1]%k==0 and v[n-1]%10==k)
return 1+multiplu(v,n-1,k);
else
return multiplu(v,n-1,k);
}
}
5. Scrieţi definiția completă a unei funcții C++ recursive care are ca parametri un
număr natural n, un șir crescător X de numere reale având n elemente și un număr
real v și care returnează poziția pe care apare în șir valoarea v. În cazul în care v nu
apare în șir, se va returna valoarea -1. În cazul în care v apare în șir pe mai multe
poziții, se va returna una dintre acestea.
int cautare(int n, double v[], double a)
{
if(n==0)
return -1;
else
if(v[n-1]==a)
return n-1;
else
return cautare(n-1,v,a);
}
6. Scrieţi definiția completă a subprogramului C++ recursiv ordonare care
are 2 parametri: a, prin care primeşte un tablou unidimensional cu
maximum 1000 de numere naturale mai mici decât [Link] și n, numărul
efectiv de elemente ale [Link] ordonează crescător elementele
tabloului a, fără a returna valori.
void ordonare(int v[], int n)
{
if(n>1)
{
for(int i=0; i<n-1; i++)
{
if(v[i]>=v[n-1])
swap(v[i],v[n-1]);
}
ordonare(v,n-1);
}
}
7. Implementati in mod recursiv algoritmul de sortare prin insertie.
void generare (int n, int p)
{
if(n)
{
if(n % 2 == 1)
cout << p << " ";
generare(n / 2 , p * 2);
}
}
int main(){
int n;
cin >> n;
generare(n,1);
return 0;
}
8. Pentru o serie de activități foarte sofisticate, Gigel are nevoie de un fierăstrău
special, alcătuit din mai mulţi dinţi. Un fierăstrău de gradul n este format din două
fierăstraie de gradul n-1, între care se află un dinte de mărime n. Un fierăstrău de
gradul 1 are un singur dinte, de mărime 1. Afișați un fierăstrău de grad n.
void fierastrau(int n)
{
if(n > 0)
{
fierastrau(n-1);
cout << n << " ";
fierastrau(n-1);
}
}
int main(){
int n;
cin >> n ;
fierastrau(n);
return 0;
}
9. Descompuneti un numar natural n ca suma de termeni din sirul lui Fibonacci.
Scrieti functii recursive pentru toate prelucrarile necesare.
int fibo(int n, int x, int y)
{
if(x+y>n) return y;
else return fibo(n,y,x+y);
}
void desc(int n)
{
if(n>0)
{
int f=fibo(n,0,1);
cout<<f<<" ";
desc(n-f);
}
}
int main()
{
int n;
cin>>n;
desc(n);
return 0;
}
10. Implementati in mod recursiv algoritmul de sortare prin insertie.
void sort(int v[100], int n)
{
if(n>1)
{
sort(v,n-1);
int i=n,aux;
while(v[i]<v[i-1] && i>1)
{ aux=v[i];
v[i]=v[i-1];
v[i-1]=aux;
i--;
}
}
}
int main()
{
int v[100], n,i;
cin>>n;
for(i=1;i<=n;i++)
cin>>v[i];
sort(v,n);
for(i=1;i<=n;i++)
cout<<v[i]<<" ";
return 0;
}