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.
SUBIECTUL I (30 de puncte)
1. Expresia C/C++ are valoarea 1 (adevărat) dacă sunt îndeplinite simultan condițiile ca variabila întreagă n să fie divizibilă cu 2, fară a fi divizibilă și cu 5.
Analizăm, pe rând, fiecare dintre variantele de răspuns:
a) !((n%2==1) || (n%5==0))
Expresia este adevărată dacă nu este îndeplinită condiția ca numărul n să fie impar sau să fie divizibil cu 5. Prin negarea condiției rezultă că numărul n trebuie să fie par (divizibil cu 2) și să nu fie divizibil cu 5, adică ceea ce se cere în enunțul exercițiului. De altfel, folosind regulile operatorilor din logica matematică, există echivalența: !((n%2==1) || (n%5==0)) ⇔ (n%2!=1) && (n%5!=0)
Varianta a este corectă.
b) (n%2==0) && (n%5==0)
Expresia este adevărată dacă numărul n este în același timp divizibil și cu 2 și cu 5, ceea ce nu corespunde cu enunțul exercițiului.
Varianta b este incorectă.
c) (n%10==0) && (n%5!=0)
Expresia este adevărată dacă numărul n este divizibil cu 10 dar nu este divizibil cu 5. Această expresie este contradictorie de vreme ce un număr divizibil cu 10 este întotdeauna divizibil cu 5 (de vreme ce 10 = 2 · 5), astfel încât condiția ca acesta să nu fie divizibil și cu 5 face ca expresia să nu fie îndeplinită pentru nici un fel de număr, având valoarea 0.
Varianta c este incorectă.
d) (n%10==0) && (n%2==0)
Expresia este adevărată dacă numărul n este în același timp divizibil și cu 10 și cu 2. Se observă faptul că 10 = 2 · 5, prin urmare cea de-a doua condiție este redundantă (dacă numărul n este divizibil cu 10, este clar că este simultan divizibil și cu 2 și cu 5). Cum în această situație numărul n este divizibil cu 5, condiția din enunțul exercițiului nu este îndeplinită.
Varianta d este incorectă.
În concluzie, răspunsul corect este a.
2.
a) Se observă că algoritmul determină afișează secvențe k, k – 1, …, 1 de un număr de ori egal cu numărul de ori prin care n este mai mare decât k (n/k), urmând ca ultima secvență să cuprindă numerele k, …, k – n + (n / k ) * k + 1.
n ← 7
k ← 3
iterația 1 a ciclului cât timp … execută (7 ≥ 1)
dacă (7>3) atunci
i = 3
n ← 7 – 3 (=4)
t ← 3
iterația 1 a ciclului cât timp … execută (3 ≥ 1)
scrie 3, ‘ ‘
i ← 3 – 1 (=2)
t ← 3 – 1 (=2)
iterația 2 a ciclului cât timp … execută (2 ≥ 1)
scrie 2, ‘ ‘
i ← 2 – 1 (=1)
t ← 2 – 1 (=1)
iterația 3 a ciclului cât timp … execută (1 ≥ 1)
scrie 1, ‘ ‘
i ← 1 – 1 (=0)
t ← 1 – 1 (=0)
iterația 2 a ciclului cât timp … execută (4 ≥ 1)
dacă (4>3) atunci
i = 3
n ← 4 – 3 (=1)
t ← 3
iterația 1 a ciclului cât timp … execută (3 ≥ 1)
scrie 3, ‘ ‘
i ← 3 – 1 (=2)
t ← 3 – 1 (=2)
iterația 2 a ciclului cât timp … execută (2 ≥ 1)
scrie 2, ‘ ‘
i ← 2 – 1 (=1)
t ← 2 – 1 (=1)
iterația 3 a ciclului cât timp … execută (1 ≥ 1)
scrie 1, ‘ ‘
i ← 1 – 1 (=0)
t ← 1 – 1 (=0)
iterația 3 a ciclului cât timp … execută (1 ≥ 1)
dacă (1>3) atunci
i = 1
n ← 1 – 1 (=0)
t ← 3
iterația 1 a ciclului cât timp … execută (1 ≥ 1)
scrie 3, ‘ ‘
i ← 1 – 1 (=0)
t ← 3 – 1 (=2)
Prin urmare, în urma execuției algoritmului se va afișa 3, 2, 1, 3, 2, 1, 3.
b) Ultima valoare afișată are expresia k – n + [n / k] * k + 1, unde prin [x] se înțelege parte întreagă. Această expresie are valoarea 7 pentru k = 11, cerându-se determinarea lui n minim, respectiv maxim, n ∈ [1, 99].
Obținem ecuația: 11 – n + [n / 11] * 11 + 1 = 7, adică n – [n / 11] * 11 = 5.
Se observă că valoarea minimă se obține pentru [n / 11] = 0, adică n = 5.
Se observă că valoarea maximă se obține pentru [n / 11] = 8, adică n = 93.
Ca atare, valorile minimă, respectiv maximă ale lui n ∈ [1, 99] sunt 5, respectiv 93.
c) Structura repetitivă cât timp i ≥ 1 execută are un număr cunoscut de pași (i – care poate fi k sau n), întrucât la fiecare pas al acesteia, decrementarea variabilei contor i se face cu o singură unitate. Prin urmare, aceasta poate fi transformată cu ușurință într-o structură repetitivă de tipul pentru … execută.
citește n, k
cât timp n ≥ 1 execută
dacă n > k atunci i ← k
altfel i ← n
n ← n - i
t ← k
pentru contor = i ... 1 execută
scrie t, ' '
t ← t - 1
contor ← contor - 1
d) Implementarea algoritmului în C / C++ nu presupune nici un fel de dificultate, structura repetitivă de tip cât timp … execută având ca echivalent instrucțiunea while:
using namespace std;
#include <iostream>
int main() {
int n, k, i, t;
cout << "n="; cin >> n;
cout << "k="; cin >> k;
while (n >= 1) {
if (n > k) {
i = k;
}
else {
i = n;
}
n = n - i;
t = k;
while (i >= 1) {
cout << t << " ";
i--;
t--;
}
}
return 0;
}
SUBIECTUL al II-lea (30 de puncte)
1. Pentru o structură definită sub forma:
struct complex {
float re;
float im;
} z;
atributele pot fi accesate prin intermediul expresiilor z.re, respectiv z.im.
Pătratul modulului numărului complex reținut prin intermediul variabilei de tip structură z se obține prin intermediul expresiei z.re * z.re + z.im * z.im (suma pătratelor părții imaginare, respectiv a părții reale).
Expresiile de la variantele a-c sunt incorecte din punct de vedere sintactic, acestea nici măcar nu compilează.
Răspuns corect d.
2. Pentru ca graful să aibă un număr maxim de muchii fără a exista nici un ciclu, trebuie ca între 99 de noduri să existe o singură muchie (gradul fiecărui nod fiind astfel 2), iar între 2 noduri să nu existe nici o muchie (gradul acestora fiind 1). Prin urmare, numărul de muchii este 99.
Răspuns corect b.
3. Un arbore reprezentat prin vectorul de tați are, pe fiecare poziție k, indicele nodului părinte, respectându-se convenția că pentru nodul rădăcină, părintele are indicele 0.
Din vectorul de tați rezultă că nodul 4 este rădăcina arborelui.
Nodul 4 are drept copii nodurile 8 și 9.
Nodul 8 are drept copii nodurile 3 și 5.
Nodul 9 are drept copii nodurile 6, 7 și 10.
Nodul 3 are drept copii nodurile 1 și 2.
Restul nodurilor (1, 2, 5, 6, 7, 10) nu au copii deci, prin urmare, sunt frunze (chiar dacă se află pe niveluri diferite).
Nodurile frunză sunt 1, 2, 5, 6, 7 și 10.
4. Se observă faptul că pe fiecare linie, valorile sunt obținute prin adunarea indicelui coloanei curente la valoarea reținută pe ultima coloană a liniei precedente (care este produsul dintre indicele liniei și indicele coloanei). Ca atare, formula de calcul pentru valoarea de pe poziția i, j a matricei a (cu 1 ≤ i, j ≤ 5) este (i – 1) * 5 + j unde (i – 1) * 5 este valoarea de pe ultima coloană a liniei precedente iar j este valoarea coloanei curente.
using namespace std;
#include <iostream>
#define SIZE 6
int main() {
int **a, i, j;
a = new int*[SIZE];
for (i = 0; i < SIZE; i++) {
a[i] = new int[SIZE];
}
for (i = 1; i <= 5; i++) {
for (j = 1; j <= 5; j++) {
a[i][j] = (i - 1) * 5 + j;
cout << a[i][j] << " ";
}
cout << endl;
}
for (i = 0; i < SIZE; i++) {
delete a[i];
}
delete a;
return 0;
}
5. Rezolvarea problemei presupune parcurgerea șirului, caracter cu caracter, marcându-se momentul în care s-a întâlnit o vocală diferită de i, respectiv o consoană. Se afișează mesajul DA în situația în care s-a întâlnit cel puțin o consoană și nu s-a întâlnit nici o vocală diferită de i, în caz contrar afișându-se mesajul NU.
using namespace std;
#define MAXSIZE 100
#include <iostream>
#include <string>
int main() {
char *s;
int k, consonant_found = 0, vowel_found = 0;
s = new char[MAXSIZE];
cout << "s="; cin >> s;
for (k = 0; k < strlen(s); k++) {
switch (s[k]) {
case 'a':
case 'e':
case 'o':
case 'u':
vowel_found = 1;
case 'i':
break;
default:
consonant_found = 1;
break;
}
}
if (consonant_found && !vowel_found) {
cout << "DA" << endl;
}
else {
cout << "NU" << endl;
}
delete s;
return 0;
}
SUBIECTUL al III-lea (30 de puncte)
1. Prin intermediul metodei backtracking, se construiește soluția într-o stivă de trei elemente, pe fiecare nivel al stivei reținându-se câte un parfum din mulțimea inițială. La fiecare pas, se alege elementul de pe o poziție a stivei, alegându-se un element din mulțime având indicele imediat superior celui de pe poziția precedentă. O soluție este obținută în momentul în care sunt completate toate elementele stivei. La revenire, se alege pe nivelul inferior un element având indicele imediat următor din mulțime față de cel din soluția anterioară, procesul continuând până când nu se mai pot obține soluții, situație în care revenirea se face reconstruind soluția coborând pe stivă cu încă o poziție și reluând același mecanism până ce se epuizează toate soluțiile.
Astfel, soluțiile obținute vor fi:
1) (ambră, cedru, iris)
2) (ambră, cedru, mosc)
3) (ambră, cedru, santal)
4) (ambră, iris, mosc)
==================
5) (ambră, iris, santal)
6) (ambră, mosc, santal)
7) (cedru, iris, mosc)
8) (cedru, iris, santal)
9) (cedru, mosc, santal)
10) (iris, mosc, santal)
În secvența propusă apar soluțiile (ambră, mosc, santal), (cedru, mosc, santal), (cedru, iris, mosc), (cedru, iris, santal). Se observă faptul că soluția (cedru, mosc, santal) apare pe o poziție incorectă, întrucât nici soluția precedentă și nici soluția ulterioară nu corespund ordinii generării soluției, iar prin eliminarea sa din secvență se obțin trei dintre soluții, în ordinea în care au fost generate (pozițiile 6-8).
Răspuns corect b.
2. Se observă faptul că subprogramul F se va apela recursiv, primind ca parametrii numărul pentru care se dorește afișarea divizorilor proprii și divizorul propriu-zis. Divizorul propriu-zis este incrementat cu fiecare apel recursiv al subprogramului F. Momentul în care recursivitatea este părăsită este cel în care divizorul propriu-zis atinge o valoare egală cu jumătatea numărului (valoare peste care nu se mai pot găsi alți divizori). Divizorii proprii sunt afișați începând cu acest moment, în situația în care este respectată condiția n%d==0, deci în ordine descrescătoare, pe măsură ce se revine din recursivitate.
Ca atare, un apel corect al subprogramului F va fi F(2015, 2), astfel încât valoarea 1 nu va fi inclusă printre divizorii numărului 2015 (având în vedere faptul că este îndeplinită condiția 2015%1==0). De asemenea, având în vedere faptul că primul divizor propriu al numărului 2015 este 5, căutarea poate începe cu această valoare, astfel încât numărul de apeluri recursive să fie mai mic și impul de execuție proporțional. Așadar și apelul F(2015, 5) va avea același rezultat (ca de altfel și F(2015, 3), respectiv F(2015, 4)), doar că acesta este de preferat din punct de vedere al eficienței.
3. Soluția constă în parcurgerea cifră cu cifră a numărului și inspectarea acesteia pentru a se verifica dacă este un număr prim sau nu. Parcurgerea cifră cu cifră se realizează prin împărțiri succesive la 10 (restul împărțirii la 10 dă cifra curentă, pornind de la ordinul unităților spre ordine mai mari, câtul împărțirii la 10 realizează trecerea la pasul următor al algoritmului). În momentul în care a fost identificat o cifră ca număr prim, se incrementează un contor în care este reținur rezultatul. Pentru a se stabili dacă un număr este prim sau nu, este definit un subprogram separat, care parcurge toți potențialii divizori (între 2 și radicalul numărului) și în cazul în care se obține un rest nenul la împărțirea dintre numărul respectiv și divizor se trage concluzia că numărul nu este prim. Cazurile n = 0 și n = 1 sunt tratate individual.
using namespace std;
#include <iostream>
#include <math.h>
int prim(int n) {
if (n == 0 || n == 1) {
return 0;
}
for (int k = 2; k <= sqrt(n); k++) {
if (n % k == 0) {
return 0;
}
}
return 1;
}
int NrPrime(long n) {
int cifre_prime = 0;
while (n > 0) {
if (prim(n % 10)) {
cifre_prime++;
}
n = n / 10;
}
return cifre_prime;
}
int main() {
long n;
cout << "n="; cin >> n;
cout << "Numarul " << n << " contine " << NrPrime(n) << " cifre prime" << endl;
return 0;
}
4.
a) Se observă faptul că fiecare termen impar din prima jumătate a șirului se înmulțește cu toți termenii pari din ultima jumătate a șirului, prin urmare, termenul impar poate fi dat factor comun și înmulțit cu suma termenilor pari. În continuare, se dă factor comun suma termenilor pari din ultima jumătate a șirului, aceasta fiind înmulțită cu suma termenilor impari din prima jumătate a șirului. Un raționament similar se urmează și în cazul celeilalte sume, vizând tipurile complementare de termeni.
Se notează:
- sum_first_odd: suma termenilor impari din prima jumătate a șirului;
- sum_first_even: suma termenilor pari din prima jumătate a șirului;
- sum_last_odd: suma termenilor impari din ultima jumătate a șirului;
- sum_last_even: suma termenilor pari din ultima jumătate a șirului.
Astfel, suma cerută va fi sum_first_odd * sum_last_even + sum_first_even * sum_last_odd.
Sumele astfel definite pot fi determinate pe măsură ce termenii sunt citiți din fișier, astfel încât complexitatea algoritmului este liniară – (O(n)), iar pentru reținerea sumelor respective sunt alocate patru variabile de tip întreg, astfel încât se respectă și constrângerea cu privire la eficiența din perspectiva spațiului de stocare.
b)
using namespace std;
#include <iostream>
#include <fstream>
int parity(int n) {
return n % 2;
}
int main() {
ifstream file("bac.txt");
int n, crt_pos = 0, temp, sum_first_odd = 0, sum_first_even = 0, sum_last_odd = 0, sum_last_even = 0;
if (file.is_open()) {
file >> n;
while (file >> temp) {
if (crt_pos++ < n) {
if (parity(temp)) {
sum_first_odd += temp;
}
else {
sum_first_even += temp;
}
}
else {
if (parity(temp)) {
sum_last_odd += temp;
}
else {
sum_last_even += temp;
}
}
}
cout << "Suma este " << (sum_first_odd * sum_last_even + sum_first_even * sum_last_odd) << endl;
file.close();
}
return 0;
}
