Subiectul I
Pentru itemul 1, scrieți pe foaia de examen litera corespunzătoare răspunsului corect.
1. Indicați care dintre expresiile C/C++ de mai jos exprimă corect relația de apartenență x ∈ [1, 7] ∩ [3, 9].
a) !(x < 3 && x > 7)
b) !(x < 3 || x > 7)
c) x >= 3 || x <= 7
d) x > 3 && x < 7
Răspuns corect: varianta b).
2. Se consideră algoritmul alăturat, descris în pseudocod:
citeste a, b
(numere naturale)
daca a < b atunci
interschimba a cu b
c -> 0
cat timp b != 0 atunci
c
a) Scrieți valoarea returnată de algoritm dacă secvența de intrare este formată din numerele 78 și 770
a = 78
b = 770
a < b atunci a = 770, b = 78
c = 0
b != 0 atunci c = 68, a = 78, b = 68
b != 0 atunci c = 10, a = 68, b = 10
b != 0 atunci c = 8, a = 10, b = 8
b != 0 atunci c = 2, a = 8, b = 2
b != 0 atunci c = 0, a = 2, b = 0
b = 0
return a = 2
Răspuns corect: a = 2.
b) Care este cea mai mică valoare pe care o poate lua variabila a în intervalul [20, 100] și cea mai mare valoare pe care o poate lua variabila b în același interval, astfel încât rezultatul returnat de algoritm să fie 7.
După cum observăm algoritmul de mai sus calculează cmmdc-ul celor două numere. Deci pentru variabila a avem cea mai mica valoare din intervalul [20, 100] divizibilă cu 7 și anume 7*3 = 21, iar pentru variabila b avem cea mai mare valoare din acest interval divizibila cu 7 adica 7*7*2 = 98.
Verificăm cele două valori:
a = 21
b = 98
a < b atunci a = 98, b = 21
c = 0
b !=0 atunci c = 14, a = 21, b = 14
b !=0 atunci c = 7, a = 14, b = 7
b !=0 atunci c = 0, a = 7, b = 0
b = 0
return a = 7.
Valoarea returnată este 7 deci răspunsul corect este: a = 21, b = 98.
c) Scrieți în pseudocod un algoritm care să nu folosească operatorii aritmetici % (modulo) și / (împărțire) și care să fie echivalent cu cel dat.
citeste a, b
(numere naturale)
cat timp a != b atunci
daca a > b atunci
a = a - b
altfel
b = b - a
returneaza a
d) Scrieți programul C/C++ corespunzător algoritmului de mai sus.
#include
using namespace std;
int cmmdc(int a, int b)
{
int c, aux;
if(a < b)
{
aux = a;
a = b;
b = aux;
}
c = 0;
while(b != 0)
{
c = a%b;
a = b;
b = c;
}
return a;
}
void main()
{
int a, b;
cout<<"Dati a: ";
cin>>a;
cout<<"Dati b: ";
cin>>b;
cout<<"Valoarea returnata este: "<<cmmdc(a, b)<<endl;
}
Subiectul II
Pentru fiecare dintre itemii 1 și 2, scrieți pe foaia de examen litera corespunzătoare răspunsului corect.
1. Se consideră graful neorientat complet cu 10 vârfuri. Numărul de muchii ce pot fi eliminate astfel încât graful parțial rezultat să fie arbore este:
a) 36
b) 38
c) 46
d) 81
Răspuns corect: varianta a)
2. Câte frunze are arborele cu rădăcină, cu 8 noduri numerotate de la 1 la 8, al cărui vector de părinți este: (7, 5, 5, 5, 0, 2, 3, 7)?
a) 1
b) 2
c) 3
d) 4
Răspuns corect: varianta d)
Scrieți pe foaia de examen răspunsurile pentru fiecare dintre cerințele următoare:
3. Se consideră 3 stive: s1, s2 și s3. Prima stivă conține trei elemente, în timp ce celelalte două stive sunt vide. Să se scrie o secvență de instrucțiuni ce utilizează apeluri ale funcțiilor push și pop pentru a muta elementele stivei s1 în stiva s2, folosind stiva s3 ca stivă auxiliară. La final, ordinea elementelor în stiva s2 va fi aceeași cu ordinea inițială a elementelor în stiva s1.
Funcția push(s, x) inserează elementul în vârful stivei x. Funcția pop(s) returnează elementul din vârful stivei s și îl elimină de pe stivă.
Rezolvare: push(s
3, pop(s
1)), push(s
3, pop(s
1)), push(s
3, pop(s
1)), push(s
2, pop(s
3)), push(s
2, pop(s
3)), push(s
2, pop(s
3)).
4. Scrieți un program C/C++ care citește din fișierul standard de intrare (tastatura) un șir de caractere format doar din litere mici ale alfabetului englez și afișează numărul de apariții al fiecărei litere din cuvântul introdus. Datele de intrare se consideră a fi corecte.
Exemplu: dacă la intrare s-a introdus cuvântul abecedare atunci pe ecran se afișează:
a: 2
b: 1
c: 1
d: 1
e: 3.
#include
#include
void main()
{
//cei doi vectori pentru frecvente si pentru sirul citit
int frecvente[128];
char sir[256];
printf("Dati sirul\n");
//citim sirul
scanf("%s",sir);
//initializam vectorul de frecvente cu 0
for(int i = 0;i < 128; i++)
frecvente[i] = 0;
//incrementam frecventa de aparitie a fiecarui caracter din sir
for(int i = 0;i < strlen(sir); i++)
frecvente[sir[i]]++;
//daca frecventa este mai mare ca 0 atunci afisam caracterul si frecventa sa.
//consideram i ca fiind codul ascii pentru caracterul in curs.
for(int i = 0;i < 128; i++)
if(frecvente[i])
printf("%c: %d\n",i, frecvente[i]);
}
5. Scrieți un program C/C++ care citește din fișierul standard (tastatura) de intrare un număr natural n (n >= 2) și construiește o matrice pătratică nxn în care pe fiecare linie și pe fiecare coloană apar toate numerele de la 1 la n.
Exemplu: dacă la intrare s-a introdus n = 4, atunci un posibil rezultat este:
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
#include
void main()
{
//declaram matricea, n si variabilele auxiliare
int a[10][10], n, i, j;
//incercam sa citim un n >= 2
do
{
printf("Dati n: ");
scanf("%d",&n);
}while(n < 2);
//contruim matricea dupa model
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
int c;
c = (i+1+j)%n;
if(c)
a[i][j] = c;
else
a[i][j] = n;
}
}
//afisam matricea pe ecran
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
printf("%d ",a[i][j]);
}
printf("\n");
}
}
Subiectul III
Pentru itemul 1, scrieți pe foaia de examen litera corespunzătoare răspunsului corect.
1. În câte dintre permutările elementelor mulțimii {L, I, M, B, A, J}, litera A apare pe poziția a doua?
a) 720
b) 360
c) 180
d) 120
Răspuns corect: varianta d).
Scrieți pe foaia de examen răspunsul pentru fiecare dintre cerințele următoare.
2. Pentru funcția de mai jos ce valoare va returna apelul F(11)?
int F(int x)
{
if(x == 0) return 1;
if(x%2 == 0) return F(x/2)*F(x/2);
return 2*F((x-1)/2)*F((x-1)/2);
}
Observăm ca F este o funcție recursivă. Apelul F(11) va returna valoarea 2048.
F(11) = 2 * F(5) * F(5) =
= 2 * 2 * F(2) * F(2) * 2 * F(2) * F(2) =
= 2 * 2 * F(1) * F(1) * F(1) * F(1) * 2 * F(1) * F(1) * F(1) * F(1) =
= 2 * 2 * 2 * F(0) * F(0) * 2 * F(0) * F(0) * 2 * F(0) * F(0) * 2 * F(0) * F(0) * 2 * * 2 * F(0) * F(0) * 2 * F(0) * F(0) * 2 * F(0) * F(0) * 2 * F(0) * F(0) =
= 2 * 2 * 2 * 1 * 1 * 2 * 1 * 1 * 2 * 1 * 1 * 2 * 1 * 1 * 2 * 2 * 1 * 1 * 2 * 1 * 1 * 2 * 1 * 1 * 2 * 1 * 1
= 2048
3. Se consideră ecuația liniară a0x0 + a1x1 + .... + anxn = b, unde atât b cât și coeficienții ecuației sunt numere întregi. Fiecare dintre variabilele ecuației poate lua valori întregi doar din intervalul [inf, sup] același pentru toate variabilele (inf < sup, deasemenea numere întregi).
a) Descrieți în limbaj natural o metodă pentru rezolvarea ecuației în cazul în care
n = 2 și parametrii
a0, a1, b, inf, sup sunt cunoscuți.
În cazul în care n = 2 și cunoaștem și restul variabilelor putem aplica soluția naivă, adică pentru fiecare x
0 și pentru fiecare x
1 se luau valori apoi se verifica ecuația pentru a vedea dacă perechea aleasă reprezintă soluție.
b) Scrieți în limbajul C/C++ două funcții min și max care primesc ca argumente numărul n, tabloul coeficienților a, valoarea b, marginile inf și sup și un index k, k < n și returnează cea mai mică și cea mai mare sumă posibilă oricare ar fi x din intervalul [inf, sup].
Pentru a înțelege mai bine ce se vrea de la această problemă funcția min va returna cea mai mică sumă posibilă indiferent de variabilele x
1, ..., x
n, adică în cazul în care un coeficient este pozitiv suma va fi egală cu acel coeficient înmulțit cu marginea inferioară pentru a obține cea mai mica valoare iar dacă coeficientul este negativ atunci el va trebui înmulțit cu marginea superioară a intervalului pentru a obține o valoare minimă. Pentru funcția max se face la fel doar că se va schimba situația, adică coeficientul negativ va fi înmulțit cu marginea inferioară iar cel pozitiv cu marginea superioară.
int min(int n, int a[], int b, int inf, int sup, int k)
{
int sum_min = 0;
int i;
int coeficient;
for (i = k; i < n; ++i)
{
coeficient = a[i];
if (coeficient > 0)
{
sum_min += coeficient * inf;
}
else
{
sum_min += coeficient * sup;
}
}
return sum_min;
}
int max(int n, int a[], int b, int inf, int sup, int k)
{
int sum_max = 0;
int i;
int coeficient;
for (i = k; i < n; ++i)
{
coeficient = a[i];
if (coeficient > 0)
{
sum_max += coeficient * sup;
}
else
{
sum_max += coeficient * inf;
}
}
return sum_max;
}
c) Scrieți în limbajul C/C++ o funcție care primește ca argument numărul n, tabloul coeficienților a, valoarea b, marginile inf și sup și returnează un tablou cu n elemente conținând o soluție a ecuației date sau NULL dacă ecuația nu are nicio soluție. Folosiți funcțiile min si max definite mai sus pentru a eficientiza procesul de căutare a soluțiilor.
#include
#include
int min(int n, int a[], int b, int inf, int sup, int k)
{
int sum_min = 0;
int i;
int coeficient;
for (i = k; i < n; ++i)
{
coeficient = a[i];
if (coeficient > 0)
{
sum_min += coeficient * inf;
}
else
{
sum_min += coeficient * sup;
}
}
return sum_min;
}
int max(int n, int a[], int b, int inf, int sup, int k)
{
int sum_max = 0;
int i;
int coeficient;
for (i = k; i < n; ++i)
{
coeficient = a[i];
if (coeficient > 0)
{
sum_max += coeficient * sup;
}
else
{
sum_max += coeficient * inf;
}
}
return sum_max;
}
int* solutie(int n, int a[], int b, int inf, int sup)
{
static int* t = NULL;
if (!t)
t = (int*)malloc((size_t)n * sizeof(int));
static int pos = 0;
static int sum = 0;
int i;
for (i = inf; i <= sup; i++)
{
int sumaCurenta = sum + i * a[pos];
t[pos] = i;
if (pos == n - 1)
{
if (sumaCurenta == b)
{
return t;
}
}
else
{
if (b >= (sumaCurenta + min(n,a,b,inf,sup,pos + 1)) &&
b <= (sumaCurenta + max(n,a,b,inf,sup,pos + 1)))
{
int sumaAnterioara = sum;
sum = sumaCurenta;
pos++;
int* rez = solutie(n, a, b, inf, sup);
if (rez) return rez;
--pos;
sum = sumaAnterioara;
}
}
}
return NULL;
}
int main()
{
int n, b, inf, sup,a[100];
printf("Dati n: ");
scanf("%d",&n);
printf("Dati marginea inferioara a intervalului: ");
scanf("%d",&inf);
printf("Dati marginea superioara a intervalului: ");
scanf("%d",&sup);
printf("Dati rezultatul ecuatiei: ");
scanf("%d",&b);
for(int i = 0;i < n;i++)
{
printf("Coeficientul %d este: ", i);
scanf("%d",&a[i]);
}
int *ret;
ret = solutie(n, a, b, inf, sup);
if (ret)
{
printf("Rezultatul ecuatiei este:\n");
for (int i = 0; i < n; i++)
printf("x%d: %d\n", i, ret[i]);
}
else
printf("Nu exista solutie.\n");
return 0;
}
