Filiera teoretică, profilul real, specializarea științe ale naturii
Enunțul subiectelor precum și baremul de corectare pot fi descărcate de pe site-ul Ministerului Educației Naționale.
SUBIECTUL I (30 de puncte)
Acest subiect este identic cu cel de la specializarea matematică-informatică.
SUBIECTUL II (30 de puncte)
1. Subiectul urmărește să verifice cunoașterea funcțiilor predefinite din limbajul C/C++ (abs) precum și abilități cu privire la rezolvarea unor probleme.
Pentru x ∈ [45, 55], valorile pe care le poate lua expresia x/10 sunt 4 (pentru x ∈ [45, 49]) sau 5 (pentru x ∈ [50, 55]) iar ale expresiei x%10 pot fi cuprinse între 0 (pentru x=50) și 9 (pentru x=49). Așadar, diferența maximă dintre cele două expresii (în modul) poate fi 5, aceasta obținându-se atât pentru x=49 (abs(4-9)=5) cât și pentru x=50(abs(5-0)=0).
Răspunsul corect este b.
2. Prin acest exercițiu se dorește să se verifice capacitatea de înțelegere a unui algoritm precum și posibilitatea de completare a acestuia.
În enunț se precizează faptul că m>n, cu alte cuvinte m-n>0. De asemenea, se observă că pe fiecare iterație a instrucțiunii repetitive cu test final x este incrementat cu 1, y este decrementat cu 1, astfel încât diferența x-y va fi incrementată cu 2. Pentru a se satisface condiția de terminare a ciclului repetitiv (x<y ⇔ x-y<0), trebuie să se realizeze un număr de iterații egal cu:
a) (m-n)/2, dacă n-m este par, astfel încât diferența inițială (negativă) n-m (valoarea lui x-y) să fie anulată (la sfârșitul ciclului repetitiv cu test final x=y)
În aceste condiții r=m-n (după înmulțirea cu 2) numai dacă r reflectă numărul de iterații ale ciclului repetitiv cu test final, adică r = r + 1
b) (m-n)/2 + 1, dacă n-m este impar, astfel încât diferența inițială (negativă) n-m (valoarea lui x-y) să fie devină pozitivă (la sfârșitul ciclului repetitiv cu test final x = y + 1)
În aceste condiții r=m-n(+1) (după înmulțirea cu 2 și decrementarea în urma testului de egalitate dintre x și y – din rezultat ar fi trebuit să se scadă 2 și nu 1) numai dacă r reflectă numărul de iterații ale ciclului repetitiv cu test final, adică r = r + 1
Răspunsul corect este c.
3. Acest subiect reprezintă o variantă a celui omolog de la specializarea matematică-informatică, propunându-și să verifice capacitatea unui elev de a elabora un algoritm relativ simplu. Nu este testată capacitatea elevului de a lucra cu structuri de date.
Și pentru această problemă trebuie tratate cele trei cazuri:
a) minutul de start este mai mic decât minutul de stop (momentul de start este anterior momentului de stop) ⇒ rezultat acceptat;
b) minutul de start este egal cu minutul de stop:
1. secunda de start este mai mică decât secunda de stop (momentul de start este anterior momentului de stop) ⇒ rezultat acceptat;
2. secunda de start este egală sau mai mare decât secunda de stop (momentul de start coincide cu momentul de stop sau este ulterior momentului de stop) ⇒ rezultat respins.
c) minutul de start este mai mare cu minutul de stop (momentul de start este ulterior momentului de stop) ⇒ rezultat respins.
using namespace std;
#include <iostream>
int main() {
int minut_start, secunda_start, minut_stop, secunda_stop;
cout<<“start”<<endl;
cout<<“minut:”; cin>>minut_start;
cout<<“secunda:”; cin>>secunda_start;
cout<<“stop”<<endl;
cout<<“minut:”; cin>>minut_stop;
cout<<“secunda:”; cin>>secunda_stop;
if (minut_start<minut_stop)
cout<<“acceptat”<<endl;
else if (minut_start==minut_stop) {
if (secunda_start<secunda_stop)
cout<<“acceptat”<<endl;
else
cout<<“respins”<<endl;
} else if (minut_start>minut_stop)
cout<<“respins”<<endl;
return 0;
}
4. Acest subiect este identic cu cerința 3, subiectul III de la specializarea matematică-informatică, cu excepția faptului că nu se solicită scrierea programului C/C++ corespunzător ci descrierea algoritmului în pseudocod, fără utilizarea de subprograme.
a) Este evident că trebuie respectate simultan condițiile:
- n! ∈ [a, b]
- (n-1)! ∉ [a, b]
- (n+1)! ∉ [a, b]
- b-a maxim
de unde rezultă automat faptul că a = (n-1)! + 1 și b=(n+1)! – 1.
Algoritmul în pseudocod este următorul:
citește n
factorial ← 1
pentru contor = 2, n-1
factorial ← factorial * contor
a ← factorial + 1
b ← factorial * n * (n + 1) – 1
afișează a, b
b) Datele de intrare sunt n, care trebuie să respecte condiția de a face parte din intervalul [2, 10].
Datele de ieșire sunt a și b, reprezentând limita inferioară, respectiv limita superioară a intervalului factorial.
A fost utilizată o variabilă contor, pentru a indica iterația curentă în ciclul repetitiv cu număr cunoscut de pași și variabila factorial, în care se calculează valoarea (n-1)!, utilizată ulterior pentru determinarea limitei inferioare, respectiv a limitei superioare a intervalului factorial.
Având formulele pentru limita inferioară, respectiv limita superioară determinate mai sus, algoritmul nu trebuie decât să calculeze (n-1)! (printr-un algoritm iterativ, folosind un ciclu repetitiv cu număr cunoscut de pași – factorial = 1 * 2 * … * (n-1)) și pe baza sa a (n+1)! care sunt ulterior incrementate, respectiv decrementate pentru a se obține valorile dorite.
SUBIECTUL III (30 de puncte)
1. Interclasarea a doi vectori presupune introducerea elementelor unui vector neordonat între elementele unui vector ordonat (de obicei crescător), astfel încât după această operație să se mențină proprietatea de ordine între elementele vectorului rezultat (xi < xj, ∀i<j).
În cazul de față se cunosc A = (4, 11, 14, 18, 21) și A ∪ B = (3, 4, 8, 11, 14, 14, 17, 18, 21, 46). Pentru determinarea vectorului B, trebuie realizată operația de diferență dintre A ∪ B și A.
Procedând astfel, se obține că B = (A ∪ B) \ A = (3, 4, 8, 11, 14, 14, 17, 18, 21, 46) \ (4, 11, 14, 18, 21) = (3, 8, 14, 17, 46). Acestea sunt valorile pe care vectorul B trebuie să le conțină, nu neapărat în această ordine, întrucât sortarea se realizează în cadrul operației de interclasare, fiecare element din B fiind plasat în A ∪ B pe poziția corespunzătoare, astfel încât să se mențină proprietatea de ordine.
Dintre toate variantele de răspuns, se observă că doar varianta b conține toate elementele vectorului B și numai pe cele aparținându-i acestuia.
2. Exercițiul reprezintă o problemă clasică de căutare a unei valori într-o mulțime neordonată.
În secvența dată se citesc 10 valori de la tastatură și se cere ca variabila ok să rețină rezultatul căutării (0 dacă valoarea nu face parte din mulțime, 1 dacă aceasta este identificată printre elementele mulțimii).
Prin urmare, valoarea ok va fi inițializată cu 0 (inițial, valoarea nu a fost găsită), urmând ca în ciclul repetitiv cu număr cunoscut de pași să se modifice valoarea acesteia (în 1) în condițiile în care, în urma unui instrucțiuni de tip decizional, elementul citit este identificat ca fiind cel căutat.
ok = 0; // elementul nu a fost gasit printre valorile citite
for(i = 1; i <= 10; i++) {
cin>>x;
if (x == 2014)
ok = 1; // elementul a fost gasit printre valorile citite
}
3. Subiectul vizează verificarea modului de lucru cu tablouri (citire, scriere, indexare, modificare a valorilor conform unei condiții). De asemenea, deși baremul nu o precizează explicit, ar trebui urmărit modul de alocare / dealocare (dinamică) a memoriei pentru tablou, respectiv verificarea restricțiilor precizate în enunț pentru datele de intrare (n și x cuprinse între anumite valori, elementele vectorului de maxim 4 cifre, minim un element par în vector).
Prin urmare, algoritmul:
- va citi variabila n, urmărind respectarea restricțiilor specificate în enunț;
- va aloca tabloul dinamic (pentru fix atâtea elemente câte urmează să fie citite);
- va citi fiecare element al tabloului, într-o secvență repetitivă cu număr cunoscut de pași, verificând, pentru fiecare în parte, dacă a fost respectat criteriul de validare
- pentru fiecare element al tabloului în parte, să aibă maxim 4 cifre (să fie mai mic decât 10000);
- doar la ultimul element, să fie existat anterior cel puțin un element par (restul împărțirii la 2 să fie 0) – întânirea unui astfel de element se face pentru fiecare element al tabloului care respectă criteriul de validare;
- va citi variabila x, urmărind respectarea restricțiilor specificate în enunț;
- va parcurge tabloul, scăzând valoarea x din elementul curent în cazul în care acesta este par;
- va scrie fiecare element al tabloului, acesta fiind separat de celelalte printr-un spațiu;
- va dealoca spațiul de memorie rezervat pentru tablou.
using namespace std;
#include <iostream>
int main() {
int n, *vector, x, contor, par = 0;
do {
cout<<“n=”;
cin>>n;
} while (n <= 2 || n >= 50);
vector = new int[n];
for (contor=0; contor < n; contor++) {
int conditie = 0;
do {
cout<<“vector[“<<(contor+1)<<“]=”;
cin>>vector[contor];
if (vector[contor] < 10000) {
if (vector[contor] % 2 == 0)
par = 1;
if (contor == (n – 1)) {
if (par)
conditie = 1;
}
else
conditie = 1;
}
} while (!conditie);
}
do {
cout<<“x=”;
cin>>x;
} while (x <= 0 || x >= 10);
for (contor = 0; contor < n; contor++)
if (vector[contor] %2 == 0)
vector[contor] -= x;
for (contor = 0; contor < n; contor++)
cout<<vector[contor]<<” “;
cout<<endl;
delete vector;
return 0;
}
4. Acest subiect reprezintă o variantă simplificată a celui omolog de la specializarea matematică-informatică, solicitându-se identificarea cifrelor cu apariție maximă, nu a subnumerelor (de 2 cifre).
a) Se determină toate cifrele unui număr (ca rest al împărțirii la 10 al acestuia), eliminându-se succesiv ultima cifră (prin împărțirea sa la 10) până când acesta devine nul (nu mai conține cifre). Valorile cifrelor și numărul de apariții al fiecărui subnumăr va fi contorizat în cadrul a doi vectori, unul care reține valorile (cifre), iar celălalt care stochează numărul de apariții (ocurente). De fiecare dată se verifică, prin căutare, dacă cifra respectivă există anterior. (S-ar fi putut inițializa un vector cu 10 elemente corespunzătoare fiecărei cifre de la 0 la 9, eliminându-se altfel vectorul care reține cifrele propriu-zise precum și căutarea care se realizează de fiecare dată pentru a se verifica dacă cifra respectivă există sau nu). Se determină maximul numărului de ocurențe și valoarea (valorile) corespunzătoare acestui maxim se afișează.
Complexitatea algoritmului propus este O(n) întrucât vectorul este parcurs de 2 ori, odată pentru determinarea cifrelor și odată pentru determinarea maximului numărului de ocurențe (stocarea valorilor cifrelor în vector presupune și ea o parcurgere pentru căutare, însă și aceasta se realizează tot în timp liniar și poate fi eliminată prin varianta amintită).
b)
Soluția 1:
using namespace std;
#include <iostream>
#include <fstream>
#define MAX 10 // pot fi maxim 10 cifre, insa nu este obligatoriu ca toate sa se regaseasca in fisier
int main() {
long numar;
// vectori ce contin
// – valorile cifrelor aferente numerelor din fisier
// – numarul de aparitii pentru fiecare cifra
int *cifre, *ocurente, dimensiune = 0;
// alocare memorie
cifre = new int[MAX];
ocurente = new int[MAX];
// deschidere fisier
ifstream fisier(“bac.txt”);
if (fisier.is_open()) {
// citire numar din fisier
while (fisier>>numar) {
while (numar != 0) {
// determinare cifra
int cifra = numar % 10, gasit = 0;
// cautare cifra in vector
for (int contor = 0; contor < dimensiune && !gasit; contor++)
// cifra a fost gasita in vector, se incrementeaza numarul de ocurente
if (cifre[contor] == cifra) {
ocurente[contor]++;
gasit = 1;
}
// cifra nu a fost gasit in vector, se stocheaza (numarul de ocurente este 1)
if (!gasit) {
cifre[dimensiune] = cifra;
ocurente[dimensiune] = 1;
dimensiune++;
}
numar /= 10;
}
}
// inchidere fisier
fisier.close();
}
// determinare numar maxim de ocurente
int maxim = 1;
for (int contor = 0; contor < dimensiune; contor++)
if (ocurente[contor] >= maxim)
maxim = ocurente[contor];
// afisarea subnumerelor care apar de cele mai multe ori
for (int contor = 0; contor < dimensiune; contor++)
if (ocurente[contor] == maxim)
cout<<cifre[contor]<<” “;
cout<<endl;
// dealocare memorie
delete cifre;
delete ocurente;
cin>>maxim;
return 0;
}
Soluția 2:
using namespace std;
#include <iostream>
#include <fstream>
#define MAX 10 // pot fi maxim 10 cifre, insa nu este obligatoriu ca toate sa se regaseasca in fisier
int main() {
long numar;
// vector ce contine numarul de aparitii pentru fiecare cifra
// ocurente[i] – numarul de aparitii pentru cifra i, i=0..9
int *ocurente, dimensiune = 0;
// alocare memorie
ocurente = new int[MAX];
for (int contor = 0; contor < MAX; contor++)
ocurente[contor] = 0;
// deschidere fisier
ifstream fisier(“bac.txt”);
if (fisier.is_open()) {
// citire numar din fisier
while (fisier>>numar) {
while (numar != 0) {
// determinare cifra
int cifra = numar % 10;
// incrementarea numarului de ocurente pentru cifra curenta
ocurente[cifra]++;
numar /= 10;
}
}
// inchidere fisier
fisier.close();
}
// determinare numar maxim de ocurente
int maxim = 1;
for (int contor = 0; contor < MAX; contor++)
if (ocurente[contor] >= maxim)
maxim = ocurente[contor];
// afisarea subnumerelor care apar de cele mai multe ori
for (int contor = 0; contor < MAX; contor++)
if (ocurente[contor] == maxim)
cout<<contor<<” “;
cout<<endl;
// dealocare memorie
delete ocurente;
return 0;
}
