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 al II-lea (30 de puncte)
1. Vom analiza, pe rând, fiecare dintre expresiile propuse spre evaluare:
a) x = sqrt(x);
Această expresie este corectă din punct de vedere sintactic, întrucât variabilei reale x (x > 0), inițializată anterior, i se asociază o valoare egală cu rădăcina sa pătrată.
b) x = sqrt(sqrt(16));
Această expresie este corectă din punct de vedere sintactic, întrucât în urma evaluării expresiei, variabila reală x va fi inițializată cu valoarea 2.0 (sqrt(16) = 4.0, sqrt(4.0) = 2.0), pierzându-se astfel valoarea stocată anterior;
c) cin >> sqrt(4); sau scanf(“%f”, &sqrt(4));
Această expresie este incorectă din punct de vedere sintactic, întrucât expresia sqrt(4) este o constantă (evaluată la valoarea 2.0), astfel încât nu poate fi citită, de la tastatură, o altă valoare care să fie atribuită ulterior acesteia. Atribuirea de valori de la tastatură este posibilă numai pentru variabile, aceasta constituind o modalitate pentru inițializarea sa.
d) cout << sqrt(4)+1; sau printf(“%f”, sqrt(4)+1);
Această expresie este corectă din punct de vedere sintactic, întrucât, în urma execuției acesteia, pe monitor se va afișa valoarea 3.0 (expresia sqrt(4) este evaluată ca fiind 2.0, ulterior această valoare fiind incrementată).
Răspunsul corect este c.
2. Pentru determinarea celui mai mare divizor comun, se folosește de regulă algoritmul lui Euclid, care este disponibil în două variante (prin scăderi și împărțiri succesive), implementarea putând fi atât iterativă, cât și recursivă.
În exemplele din problemă, sunt prezentate variantele iterative, prin scăderi și împărțiri succesive:
a) prin scăderi succesive:
if (x == 0) {
x = y;
}
while (y != 0) {
if (x > y) {
x = x - y;
} else {
y = y - x;
}
}
b) prin împărțiri succesive:
while (y != 0) {
aux = y;
y = x % y;
x = aux;
}
Se observă că secvența S1 este echivalentă cu algoritmul de la punctul a).
Se observă că secvența S2 NU este echivalentă cu algoritmul de la punctul b), întrucât valoarea reținută de variabila x se pierde, odată ce se stochează în ea restul împărțirii lui x la y, stocarea lui y în variabila temporară z neavând nici un sens, de vreme ce aceasta nu mai este utilizată ulterior. De asemenea, y primește valoarea lui x, astfel că ciclul repetitiv se va termina după cel mult 2 iterații.
Prin urmare, răspunsul corect este a.
3. În urma majorării cu 50%, cartea va avea următorul preț:
preț = preț + preț * 50% = preț + preț * 0,5 = preț * (1 + 0,5) = preț * 1,5 = preț * 3 /2
Așadar, instrucțiunile C/C++ prin care valoarea unei variabile reale p (declarată ca float p; sau double p; și inițializată corespunzător) pot fi:
a) p = p * 1.5;
b) p = p * 3/2;
4.
a) Întrucât se cere algoritmul de rezolvare în pseudocod, este mai facil ca soluția pentru această problemă să fie iterativă și să nu se folosească de alte funcții ajutătoare (pentru determinarea unui element din șirul lui Fibonacci sau pentru verificarea parității unui număr).
Astfel, într-un ciclu repetitiv, se vor calcula termenii șirului lui Fibonacci, începând cu f(1). Dacă un termen din șir este impar, atunci se scade din valoarea lui n o unitate, semn că un număr dintre cele care îndeplinesc condiția solicitată a fost găsit, căutarea terminându-se în momentul în care n ajunge 0. Calcularea unui termen din șirul lui Fibonacci (dacă pasul curent din iterație este k, se va calcula fibonacci(k)) se face reținând în permanență cele 2 valori anterioare: fibonacci(k-1) și fibonacci(k-2) astfel încât să se poată aplica formula de recurență cunoscută: fibonacci(k) = fibonacci(k-1) + fibonacci(k-2).
intreg n, k = 1, fibonacci1, fibonacci2, fibonnaci
citeste n
cat timp n > 0 executa
daca k = 1 atunci
fibonacci1 = 1
fibonacci = 1
altfel daca k = 2 atunci
fibonacci2 = 1
fibonacci = 1
altfel
fibonacci = fibonacci1 + fibonacci2
fibonacci1 = fibonacci2
fibonacci2 = fibonaaci
sfarsit daca
daca fibonacci % 2 != 0 atunci
n = n - 1
sfarsit daca
k = k + 1;
sfarsit cat timp
afiseaza fibonacci
Implementarea în C/C++ a algoritmului în pseudocod prezentat anterior este:
using namespace std;
#include <iostream>
int main() {
int n, k = 1, fibonacci1 = 0, fibonacci2 = 0, fibonacci;
cout << "n = "; cin >> n;
while (n > 0) {
switch (k) {
case 1:
fibonacci1 = 1;
fibonacci = 1;
break;
case 2:
fibonacci2 = 1;
fibonacci = 1;
break;
default:
fibonacci = fibonacci1 + fibonacci2;
fibonacci1 = fibonacci2;
fibonacci2 = fibonacci;
break;
}
if (fibonacci % 2 == 1) {
n--;
}
if (n != 0) {
k++;
}
}
cout << "Elementul cautat se gaseste pe pozitia " << k << " si are valoarea " << fibonacci << endl;
return 0;
}
b) Datele de intrare sunt reprezentate de variabila n, număr natural nenul, reprezentând al câtelea termen impar din șirul lui Fibonacci se dorește a fi determinat. Valoarea sa se citește de la tastatură.
Datele de ieșire sunt reprezentate de variabila fibonacci, număr natural nenul, reprezentând al n-lea termen impar din șirul lui Fibonacci. Valoarea sa se calculează folosind formula de recurență prin care se definește șirul lui Fibonacci fibonacci(k) = 1, k = 1 sau 2, fibonacci(k) = fibonacci(k-2) + fibonacci(k-1), altfel și se afișează pe monitor.
S-au mai utilizat următoarele variabile:
- k, pasul curent de iterație, reprezentând al câtelea termen din șirul lui Fibonacci se calculează la momentul de timp respectiv (indiferent dacă acesta este par sau impar); este inițializat cu 1 și este incrementat la fiecare pas al ciclului repetitiv atâta vreme cât nu s-a obținut al n-lea termen impar din șirul lui Fibonacci;
- fibonacci1, reprezintă termenul din șirul lui Fibonacci aflat cu 2 poziții înainte de termenul curent (dacă pasul curent este k, fibonacci1 reține f(k-2), unde f este funcția Fibonacci); este inițializat cu 1 pentru k = 1;
- fibonacci2, reprezintă termenul din șirul lui Fibonacci aflat cu 1 poziție înainte de termenul curent (dacă pasul curent este k, fibonacci2 reține f(k-1), unde f este funcția Fibonacci); este inițializat cu 1 pentru k = 2.
SUBIECTUL al III-lea (30 de puncte)
1. Se observă că:
pentru i = 1, se afișează valorile 6 – j, oricare ar fi j = 1, 5
pentru i = 2
- se afișează valoarea 6 – i, pentru j = 1
- se afișează valorile 6 – j, pentru j = 2, 5
pentru i = 3
- se afișează valorile 6 – i, pentru j = 1, 2
- se afișează valorile 6 – j, pentru j = 3, 5
pentru i = 4
- se afișează valorile 6 – i, pentru j = 1, 3
- se afișează valorile 6 – j, pentru j = 4, 5
pentru i = 5
- se afișează valorile 6 – i, pentru j = 1, 4
- se afișează valoarea 6 – j, pentru j = 5
Ca o regulă generală, se afișează 6 – i pentru j < i și 6 – j altfel.
Prin urmare, condiția instrucțiunii if este i < j. Răspunsul corect este a.
2. Având în vedere că tablourile A și B sunt deja sortate (A – crescător, B – descrescător), acestea pot fi parcurse simultan (A – în sens invers, B – în sens normal) pentru construirea elementelor tabloului C.
Fie A = (a[0], a[1], a[2], a[3], a[4]) și B = (b[0], b[1], b[2], b[3], b[4]).
Rezultă că rezulatul va fi tabloul C = (c[0], c[1], c[2], c[3], c[4], c[5], c[6], c[7], c[8], c[9]), având un număr de elemente egal cu suma elementelor celor două tablouri care sunt interclasate.
a) a[4] > b[0] => c[0] = a[4] = 16
b) a[3] < b[0] => c[1] = b[0] = 15
c) a[3] = b[1] => c[2] = a[3] = 10
d) a[2] < b[1] => c[3] = b[1] = 10
e) a[2] < b[2] => c[4] = a[2] = 9
f) a[2] < b[3] => c[5] = a[3] = 8
g) a[2] > b[4] => c[6] = a[2] = 7
h) a[1] < b[4] => c[7] = b[4] = 3
i) parcurgerea vectorului b s-a terminat => c[8] = a[1] = 2
j) parcurgerea vectorului b s-a terminat => c[9] = a[0] = 1
Prin urmare se obține ca rezultat tabloul C = (16, 15, 10, 10, 9, 8, 7, 3, 2, 1), care nu este altceva decât reuniunea elementelor din tablourile A și B, sortată descrescător (construirea se face însă pe măsura parcurgerii celor două tablouri, exploatând faptul că acestea sunt deja sortate, pentru a reduce complexitatea ordonării ulterioare a rezultatului obținut).
3. Rezolvarea problemei presupune citirea celor n elemente ale vectorului, după care acesta mai este parcurs încă o dată, fie crescător (de la pozițiile mici spre pozițiile mari), fie descrescător (de la pozițiile mari spre pozițiile mici), reținându-se pe fiecare poziție a vectorului elementul anterior / următor (în funcție de sensul de parcurgere). Totuși, într-o variabilă temporară trebuie reținut ultimul element, astfel încât valoarea acestuia să fie atribuită primului element, operație care va fi realizată manual, în afara structurii repetitive.
Având în vedere că elementele vectorului pot lua valori în intervalul [0, 109], acesta trebuie declarat de tip long, astfel încât să se aloce în memorie spațiu suficient pentru stocarea unor astfel de date.
using namespace std;
#include <iostream>
int main() {
int n, k;
long *v;
cout << "n = "; cin >> n;
v = new long[n];
for (k = 0; k < n; k++) {
cout << "v[" << k << "] = ";
cin >> v[k];
}
long temp = v[n - 1];
for (k = n - 1; k > 0; k--) {
v[k] = v[k - 1];
}
v[0] = temp;
for (k = 0; k < n; k++) {
cout << v[k] << " ";
}
cout << endl;
delete[] v;
return 0;
}
4.
a) Soluția evidentă a acestei probleme constă în stocarea valorilor citite din fișier într-un vector, sortarea acestuia urmată de parcurgerea sa, perechile fiind reprezentate de valorile adiacente a căror diferență este mai mare sau egală cu 2. Totuși, cei mai buni algoritmi de sortare (heapsort, mergesort) au de regulă complexitatea O(nlogn), ceea ce face ca o astfel de abordare să nu fie eficientă.
O soluție în timp liniar presupune utilizarea unui tablou de apariții, de maxim 101 elemente, având în vedere că numerele care apar în fișier pot avea doar valori din intervalul [0, 100]. Semnificația unui element de pe o anumită poziție din acest vector este următoarea:
- 0 – numărul corespunzător poziției respective nu se regăsește în șir
- 1 – numărul corespunzător poziției respective se regăsește în șir, cel puțin o dată
Se asigură în acest mod și eficiența din punctul de vedere al memoriei folosite, întrucât se alocă doar un vector de 101 elemente, în timp ce numărul de termeni din șir poate atinge un milion.
Se parcurge ulterior vectorul de apariții, o singură dată (astfel încât complexitatea algoritmului este O(n)), reținându-se, la fiecare pas, indicele poziției la care a fost întâlnit cel mai apropiat element nenul. În situația în care se întâlnește un element nenul (corespunzător unui termen care se regăsește în șir), se verifică dacă anterior a mai fost întâlnit un alt element nenul și în caz afirmativ, se determină dacă diferența dintre poziții (deci dintre termeni) este mai mare sau egală cu 2, situație în care a fost identificată o pereche care respectă condițiile problemei, afișându-se mesajul DA și terminându-se căutarea. Trebuie să se aibă grijă ca de fiecare dată când se întâlnește un element nenul, să se actualizeze valoarea elementului precedent nenul întâlnit.
În situația în care căutarea a ajuns la ultimul element, înseamnă că nu a fost identificată nici o pereche și prin urmare se afișează mesajul NU.
b)
using namespace std;
#define MAX_SIZE 100
#include <iostream>
#include <fstream>
int main() {
ifstream file("bac.txt");
int *exists = new int[MAX_SIZE + 1], n, last_position = -1;
for (n = 0; n <= MAX_SIZE; n++) {
exists[n] = 0;
}
if (file.is_open()) {
while (file >> n) {
exists[n] = 1;
}
file.close();
for (n = 0; n <= MAX_SIZE; n++) {
if (exists[n]) {
if ((last_position != -1) && (n - last_position >= 2)) {
cout << "DA" << endl;
break;
}
last_position = n;
}
}
}
if (n == MAX_SIZE + 1) {
cout << "NU" << endl;
}
delete[] exists;
return 0;
}
