Sesiunea iulie
Subiectul I
a)
// Complexitatea unui algortim consta in spatiul de memorie pe care il necesita pentru a rula si timpul de executare al acestuia.
// Complexitate ca timp de executare
int suma(int n)
{
int i,s=0;
for(i=1;i<=n;i++)
s=s+i;
return s;
}
// Subprogramul "suma" returneaza suma primelor n numere naturale. Aceasta este de tipul O(n) deoarece efectueaza "n" operatii.
// Complexitate ca spatiu de memorie utilizat
void tablou(int n,int a[100])
{
int i;
for(i=1;i<n;i++)
a[i]=i;
}
// Subprogramul "tablou" construieste un tablou "a" cu "n" elemente, folosindu-se de variabila ajutatoare "i".
// Acesta utilizeaza 100 de spatii de memorie pentru gestionarea tabloului "a". Pentru variabilele "i" si "n" se folosesc respectiv cate un spatiu.
int main()
{
cout << "Hello world!" << endl;
return 0;
}
b)
#include <iostream>
using namespace std;
// Un subprogram este o procedura care poate fi utilizata in programul principal.
int suma(int n) // definire subprogram
{
int i,s=0;
for(i=1;i<=n;i++) //variabilele "i", "s", "n" exista doar in cadrul subprogramului. In afara acestuia, acestea nu sunt definite.
s=s+i;
return s;
}
int main()
{
cout << "Hello world!" << endl;
int a;
cout<<"a=";cin>>a;
cout<<suma(a); // apel subprogram
return 0;
}
c)
#include <iostream>
using namespace std;
// Primul termen din sirul lui Fibonacci este t1=1, iar al doilea termen este t2=1.
// Incepand cu al treilea termen, fiecare termen este suma celorlalti doi precedenti.
// Sirul lui Fibonacci este urmatorul: 1,1,2,3,5,8,13,21...
int Fibo(int k)
{
int t1=1,t2=1,f=0,i=2;
if(k==1 || k==2)
return 1;
else
{for(i=3;i<=k;i++)
{
f=t1+t2;
t1=t2;
t2=f;
}
return f;
}
}
int main()
{
cout << "Hello world!" << endl;
int n;
cout<<"n=";cin>>n;
cout<<Fibo(n);
return 0;
}
Subiectul II
a)
se afiseaza 192
incepand cu al doilea numar, programul calculeaza cel mai mic multiplu comun pentru fiecare doua valori vecine
programul afiseaza cel mai mic multiplu comun al ultimei perechi
b)
4 1 1 1 1002
sirul incepe cu valoarea 4, deci sirul este compus din 5 valori
cel mai mic multiplu comun dintre 1 si 1002 este 1002
c)
3 25 1 225
sirul incepe cu valoarea 3, deci sirul este compus din 4 valori
cel mai mic multiplu comun dintre 1 si 225 este 225
Subiectul III
#include <iostream>
using namespace std;
void citire(int n,int X[500]) // suprogram citire sir
{
int i=0;
while(n!=0) // se citesc numere pana la citirea valorii 0
{
cout<<"nr=";cin>>n;
X[i]=n;
i++;
}
}
int prim(int n) // subprogramul care verifica daca un numar este prim
{
int i,s=0;
for(i=1;i<=n;i++)
if(n%i==0)
s++; // variabila "s" contorizeaza numarul de divizori
if(s==2) // daca numarul de divizori este 2, atunci numarul este prim
return 1;
else
return 0;
}
int sumacif(int n) // subprogramul care calculeaza suma cifrelor unui numar
{
int s=0; // in variabila "s" calculez suma cifrelor numarului "n"
while(n)
{
s=s+n%10;
n=n/10;
}
return s;
}
void afisare(int n,int X[1000]) // subprogam afisare sir
{
int i;
for(i=0;i<n;i++)
cout<<X[i]<<" ";
}
int main()
{
cout << "Hello world!" << endl;
int n,i,X[500],Y[1000],a[10000]={0},b[500],c[500],j=0,aux;
cout<<"n=";cin>>n; // citirea numarului de elemente ale sirului
citire(n,X); // citirea sirului prin apel subprogram
for(i=0;i<n;i++) // valoarea pozitii "k" din tabloul "a" reprezinta numarul de aparitii al lui "k"
if(prim(sumacif(X[i]))) // numarul de aparitii al lui yi se memoreaza pe pozitia yi
a[X[i]]++; // tabloul "a" este initializat de la inceput cu toate valorile 0 deoarece valorile din sir sunt intre 1 si 10000
for(i=1;i<=10000;i++)
if(a[i]!=0)
{
b[j]=i; // valoarea pozitii "i" din tabloul "b" reprezinta yi
c[j]=a[i]; // valoarea pozitii "i" din tabloul "c" reprezinta fi.
j++;
}
if(j!=0) // daca j nu are valoarea 0, inseamna ca tablourile "b" si "c" au elemente, deci "Y" nu este vid
{
aux=2*j; // numarul de elemente ale sirului "Y" este de doua ori valoarea lui "j", adica dimensiunea tablourilor "b"+"c"
j=0;
for(i=0;i<aux;i=i+2)
{
Y[i]=b[j];
Y[i+1]=c[j]; // perechea (yi,fi)
j++;
}
afisare(aux,Y);
}
else // in caz contrar, sirul este vid si se afiseaza mesajul corespunzator
cout<<"Sirul Y este vid";
return 0;
}