Filiera teoretică, profilul real, specializările matematică-informatică, matematică-informatică intensiv informatică.
Filiera vocațională, profilul militar, specializarea matematică-informatică.
Enunțul subiectelor precum și baremul de corectare pot fi descărcate de pe site-ul Ministerului Educației Naționale.
Pe
contul de GitHub poate fi consultat codul sursă corespunzător subiectelor care solicită elaborarea de programe C/C++.
SUBIECTUL I (30 de puncte)
1. Dacă variabila x este de tip întreg, operatorul % calculează restul împărțirii întregi dintre cei doi operanzi, iar la împărțirea cu 7 restul maxim care se poate obține este 6.
Precizarea faptului că variabila x poate memora un număr natural cu cel mult două cifre nu are nici un fel de relevanță pentru enunțul problemei. Aceasta ar fi putut să îl pună pe candidat în dificultate în condițiile în care acesta ar fi considerat că valoarea maximă a expresiei x%7 se obține pentru valoarea maximă a lui x (în acest caz 99), însă variantele de răspuns în aceste condiții ar fi trebuit să fie altele.
Răspunsul corect este a.
2. a) Este lesne de observat faptul că programul citește numere naturale în variabla x până la întâlnirea lui 0, verificând pentru fiecare în parte dacă face parte din șirul lui Fibonacci (xn = xn-1 + xn-2, x0=0, x1=1) și determinând numărul de ocurențe ale acestora.
n ← 0
1) x ← 10
a ← 0, b ← 1
iterația 1 a ciclului repetă … până când
c ← 1
a ← 1
b ← 1
iterația 2 a ciclului repetă … până când
c ← 2
a ← 1
b ← 2
iterația 3 a ciclului repetă … până când
c ← 3
a ← 2
b ← 3
iterația 4 a ciclului repetă … până când
c ← 5
a ← 3
b ← 5
iterația 5 a ciclului repetă … până când
c ← 8
a ← 5
b ← 8
iterația 6 a ciclului repetă … până când
c ← 13
a ← 8
b ← 13
încheierea ciclului repetă … până când (13 ≥ 10)
c ≠ x (13 ≠ 10) ⇒ n rămâne 0
2) x ← 8, se repetă primele 5 iterații ale ciclului repetă … până când de mai sus, c ← 8 și c = x, iar n devine 1
3) x ← 11, se repetă primele 6 iterații ale ciclului repetă … până când de mai sus, c ← 13 și c ≠ x, iar n rămâne 1
4) x ← 1, se repetă prima iterație a ciclului repetă … până când de mai sus, c ← 1 și c = x, iar n devine 2
5) x ← 21, se repetă primele 7 iterații a ciclului repetă … până când de mai sus, c ← 21 și c = x, iar n devine 3
6) x ← 0, se repetă prima iterație a ciclului repetă … până când de mai sus, c ← 1 și c ≠ x, iar n rămâne 3
Se afișează 3.
b) Trebuie identificate acele patru numere din intervalul [0, 9] care nu fac parte din șirul lui Fibonacci, astfel încât contorul care numără ocurențele numerelor cu această proprietate să rămână 0.
Numerele din șirul lui Fibonacci din intervalul [0, 9] sunt: 0, 1, 2, 3, 5, 8. Prin urmare, ar trebui citite 4, 6, 7, 9. De asemenea, poate fi citit și 0 întrucât valoarea minimă a lui c (pentru care se verifică apartenența la șirul lui Fibonacci) este 1.
c) Algoritmul se transformă foarte facil prin citirea lui x de două ori:
– inițial, în afara ciclului cât timp x≠0
– la fiecare iterație (la final) a ciclului cât timp x≠0 – când se citește o valoare nulă în variabila x nu mai este necesar să se execute instrucțiunile din cadrul ciclului pentru că acestea nu produc o modificare a rezultatului final (valoarea reținută în variabila n)
n ← 0
citește x (număr natural)
cât timp x≠0
a ← 0
b ← 1
repetă
c ← a + b
a ← b
b ← c
până când c ≥ x
dacă x=c atunci
n ← n + 1
citește x
scrie n
d) Pentru implementarea algoritmului C/C++ corespunzător, trebuie transformate condițiile ciclului repetitiv cu test final repetă … până când prin negarea lor logică, astfel încât să fie adecvate instrucțiunii do … while:
- c≥x devine c<x;
- x=0 devine x≠0.
using namespace std;
#include <iostream>
int main() {
int n = 0, x, a, b, c;
do {
cin >> x;
a = 0; b = 1;
do {
c = a + b;
a = b;
b = c;
} while (c < x);
if (x == c) n++;
} while (x != 0);
cout << n << endl;
return 0;
}
SUBIECTUL II (30 de puncte)
1. În Figura 1 sunt reprezentați arborii reprezentați prin vectorul de tați din variantele de răspuns, observându-se că structura de la varianta de răspuns b) nu este un arbore, ci un graf:
Figura 1
Răspuns corect b.
2. Numărul de muchii ale unui graf neorientat complet cu n noduri este n(n-1)/2.
În cazul de față, numărul de muchii al unui graf neorientat complet cu 9 noduri este 9*8/2 = 36 muchii.
Se va elimina un număr maxim de muchii în cazul în care graful neorientat complet se împarte în două componente conexe (la rândul lor grafuri neorientate complete) cât mai echilibrate.
În cazul de față, o componentă conexă va avea 5 noduri, deci 5*4/2 = 10 muchii, iar cealaltă 4 noduri, deci 4*3/2 = 6 muchii, în total 16 muchii. Se observă astfel că s-au eliminat 36 – 16 = 20 muchii, număr maxim de muchii ce pot fi eliminate cu păstrarea conexității și completitudinii componentelor obținute.
În Figura 2 sunt reprezentate atât graful inițial cât și cele două componente conexe ale grafului obținut prin eliminarea unui număr maxim de muchii:
Figura 2
Răspuns corect c.
3. Un drum elementar în graf între vârful 4 și vârful 6 este o secvență de vârfuri (x4, …, x6) cu proprietatea că între oricare două vârfuri xi și xj din secvență există o muchie și fiecare vârf xk este conținut o singură dată.
În Figura 3 este reprezentat graful precum și drumul elementar între vârful 4 și vârful 6: (4, 5, 2, 6).
Figura 3
4. strlen(s)=11, deci se afișează valoarea 11
i=0, s[0]=’B’, nu se gaseste in sirul “EAIOU”, si nu se realizeaza nici o modificare
i=1, s[1]=’A’, se gaseste in sirul “EAIOU”, la adresa s+2 se copiază șirul ALAUREAT ⇒ șirul s va conține BAALAUREAT (strlen(s)=10)
i=2, s[2]=’A’, se gaseste in sirul “EAIOU”, la adresa s+3 se copiază șirul AUREAT ⇒ șirul s va conține BAAAUREAT (strlen(s)=9)
i=3, s[3]=’A’, se gaseste in sirul “EAIOU”, la adresa s+4 se copiază șirul REAT ⇒ șirul s va conține BAAAREAT (strlen(s)=8)
i=4, s[4]=’R’, nu se gaseste in sirul “EAIOU”, nu se realizează nici o modificare
i=5, s[5]=’E’, se gaseste in sirul “EAIOU”, la adresa s+6 se copiază șirul T ⇒ șirul s va conține BAAARET (strlen(s)=7)
i=6, s[6]=’T’, nu se gaseste in sirul “EAIOU”, nu se realizează nici o modificare
se afișează BAAARET
Răspunsul corect este:
11BAAARET
5. Se generează toate numerele pare începând cu 2 (prin adunare cu 2), trecându-se la următorul număr par în cazul în care acesta este divizibil cu 5. Aceste valori sunt completate în matrice, în ordine, parcurgându-se liniile de la stânga la dreapta și coloanele de sus în jos.
Pentru afișarea cu format în C++ s-a utilizat biblioteca iomanip.
using namespace std;
#define SPACING 2
#include <iostream>
#include <iomanip>
int main() {
int m, n, **matrice, i, j, k, numar_curent=2;
do {
cout << "m=";
cin >> m;
} while (m < 2 || m > 20);
do {
cout << "n=";
cin >> n;
} while (n < 2 || n > 20);
matrice = new int*[m];
for (k = 0; k < m; k++)
matrice[k] = new int[n];
for (i = 0; i < m; i++)
for (j = 0; j < n; j++) {
while (numar_curent % 5 == 0)
numar_curent += 2;
matrice[i][j] = numar_curent;
numar_curent += 2;
}
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++)
cout << setw(SPACING) << matrice[i][j] << " ";
cout << endl;
}
for (k = 0; k < m; k++)
delete[] matrice[k];
delete[] matrice;
return 0;
}
SUBIECTUL III (30 de puncte)
1. O variantă mai facilă de abordare a acestui subiect este de a vedea care sunt soluțiile generate prin metoda backtracking imediat după fiecare dintre variantele de răspuns propuse, verificând care dintre acestea corespund soluției din enunț.
a) (rock, jazz, house, latino, pop) – se observă că nu este soluție întrucât genul latino nu precede genul house;
b) (rock, jazz, latino, house, pop)
Următoarea soluție se obține inversând ordinea ultimelor două genuri de muzică din vârful stivei: (rock, jazz, latino, pop, house), care nu coincide însă cu soluția din enunț.
c) (pop, latino, rock, house, jazz)
Următoarea soluție se obține reconstruind valorile aflate pe ultimele trei niveluri din vârful stivei.
Pe poziția 3, următoarea valoare (în ordinea celor din mulțimea inițială, care nu au fost încercate încă) este house (imediat următoare după rock – din soluția anterioară).
Pe pozițiile 4 și 5 se trec valorile rămase, în ordinea în care apar în mulțimea inițială: jazz, rock.
Următoarea soluție este așadar (pop, latino, house, jazz, rock), care coincide cu soluția din enunț.
d) (pop, rock, latino, house, jazz)
Următoarea soluție se obține reconstruind valorile aflate pe ultimele patru niveluri din vârful stivei.
Pe poziția 2, următoarea valoare (în ordinea celor din mulțimea inițială, care nu au fost încercate încă) este latino (imediat următoare după rock – din soluția anterioară).
Pe pozițiile 3, 4 și 5 se trec valorile rămase, în ordinea în care apar în mulțimea inițială: jazz, rock, house.
Următoarea soluție este așadar (pop, latino, jazz, rock, house), care nu coincide însă cu soluția din enunț.
Răspuns corect c.
2. Este evident că funcția f calculează cel mai mare divizor comun dintre numerele a și b folosind algoritmul lui Euclid (implementarea recursivă), varianta împărțirii succesive lui a la b.
Prin urmare, problema cere determinarea unui număr x ∈ [1, 50] astfel încât cmmdc(30, x)=5.
Astfel, valori posibile ale lui x sunt: 5, 25, 35.
3. Se genereză perechi de numere (x, y) cu x ∈ [0, n] și y ∈ [x+1, n] (pentru a se asigura relația de precedență x<y), după care se verifică dacă există un z (y<z) care să verifice relația x*y+y*z=n.
Cu alte cuvinte, z = (n – x * y) / y, trebuie să fie număr întreg (restul împărțirii lui n – x * y la y trebuie să fie 0) și trebuie să fie mai mare decât y.
using namespace std;
#include <iostream>
void triplete(int n) {
int x, y, z;
for (x = 0; x <= n; x++)
for (y = x + 1; y <= n; y++)
if ((n - x * y) % y == 0 && (n - x * y) / y > y)
cout << "(" << x << "," << y << "," << (n - x * y) / y << ")" << endl;
}
int main() {
int n;
do {
cout << "n=";
cin >> n;
} while (n < 2 || n>10000);
triplete(n);
return 0;
}
4. a) O soluție eficientă trebuie să țină cont de formatul datelor din fișier, și anume puteri ale lui 10 mai mici sau egale cu 9. În acest sens, se poate construi un vector care să rețină, pentru fiecare putere în parte, numărul de ocurențe. Ulterior, numărul aflat pe poziția cerută este puterea pentru care suma ocurențelor de până la el este mai mică sau egală cu poziția respectivă.
Astfel, complexitatea algoritmului propus este O(1) – întrucât se parcurge un vector cu 10 elemente. În situația în care datele din fișier ar fi fost stocate ca atare într-un vector și s-ar fi aplicat un algoritm de sortare clasic (quick-sort, de exemplu), complexitatea ar fi fost în medie O(nlogn) sau O(n2) în cazul cel mai defavorabil. De remarcat faptul că eficiența se manifestă nu doar în privința timpului de execuție, ci și a memoriei folosite întrucât se folosește un vector de întregi de 10 elemente (10*2octeți = 20 octeți); dacă s-ar fi reținut toate numerele din fișier, s-ar fi putut utiliza până la 106 * 4 octeți (variabile de tip long) ≅ 4 MB de memorie.
b) Algoritmul nu pune probleme de implementare.
S-au definit două funcții ajutătoare:
- numar_putere – determină ce putere a lui 10 este un numar n dat ca parametru sau -1 dacă numărul nu este putere a lui 10;
- putere_numar – determină numărul obținut prin ridicarea lui 10 la puterea dată ca parametru.
După citirea numerelor din fișier și construirea vectorului de ocurențe, se caută poziția la care suma ocurențelor de până la ea depășește indexul citit pentru a se determina numărul din șirul ordonat căutat.
using namespace std;
#define MAX 10
#include <iostream>
#include <fstream>
int numar_putere(long n) {
int rezultat = 0;
while (n != 1)
if (n % 10 == 0) {
rezultat++;
n /= 10;
}
else
return -1;
return rezultat;
}
long putere_numar(int putere) {
int rezultat = 1;
while (putere) {
rezultat *= 10;
putere--;
}
return rezultat;
}
int main() {
long n, numar_curent;
int index, total = 0, *ocurente = new int[MAX];
for (index = 0; index < MAX; index++)
ocurente[index] = 0;
// deschidere fisier
ifstream fisier("bac.txt");
if (fisier.is_open()) {
fisier >> n;
while (fisier >> numar_curent) {
// determinare putere p a numarului de forma 10^p citit din fisier
index = numar_putere(numar_curent);
if (index != -1) { // numarul citit din fisier are forma corecta
// incrementare numar de ocurente a numarului citit din fisier
ocurente[numar_putere(numar_curent)]++;
// total de numere citite din fisier
total++;
}
}
// inchidere fisier
fisier.close();
}
if (total < n)
cout << "Nu exista" << endl;
else {
index = 0;
total = 0; // total de numere pana la indexul curent
while (total < n) // nu s-a ajuns la pozitia cautata
// adaugare numar de ocurente de pe pozitia curenta
total += ocurente[index++];
cout << putere_numar(--index) << endl;
}
delete[] ocurente;
return 0;
}
