Varianta 7 de la Bacalaureatul la Informatică (Mate-Info, C/C++): conține 3 subiecte (90 de puncte) și are un timp de lucru de 3 ore. Sub fiecare exercițiu găsești răspunsul corect și rezolvarea.
Subiecte oficiale publicate de Ministerul Educației. Rezolvări realizate de subac. Actualizat la .
Varianta 7 din 2025 trece prin tipuri de date, structuri, backtracking, arbori, grafuri orientate, factori primi, recursivitate, șiruri de caractere, matrice și fișiere. Este o variantă echilibrată, bună pentru recapitularea întregii materii.
Subiectul I (20p): 5 grile: o expresie cu o împărțire reală și una întreagă, data expirării dintr-o structură medicament cu un câmp expira care este tot o structură, o problemă de backtracking cu comenzi de încălțăminte, rădăcinile pentru care un arbore are trei frunze și numărul minim de arce adăugate ca un graf orientat să aibă două componente tare conexe.
Subiectul al II-lea (40p): Un algoritm în pseudocod care află cel mai mare factor prim și produsul factorilor primi distincți ai unui număr, valorile unui subprogram recursiv și o secvență cu strstr și strcpy.
Subiectul al III-lea (30p): Un subprogram cu numere (consecutiv, care găsește f cu (f-1)·f < n ≤ f·(f+1)), o problemă cu o matrice care numără tripletele de locuri libere alăturate de pe primul și ultimul rând al unei parcări și o problemă de eficiență care extrage trei numere dintre valorile inversate citite din fișierul bac.in.
(3,2) închide circuitele 2→1→3→2 și 2→6→4→3→2, iar vârful 5 rămâne singur: un singur arc ajunge.f(3) = 3. Calculează pe rând de jos în sus: f(5) = 2, f(7) = 5 și așa mai departe, până la f(17) = 8.strstr întoarce adresa primei apariții a lui car, deci s2 devine carea și n este 5. Apoi strcpy(s1+3, s2+3) scrie ea peste restul lui s1, care devine parea.Indicați valoarea expresiei C/C++ alăturate.
15.4/2+15/2
Răspuns corect: b) 14.7
15.4 este un număr real, deci 15.4/2 dă 7.7. 15/2 este însă o împărțire între numere întregi și dă câtul, 7. Suma este 7.7 + 7 = 14.7.
15.2 ar ieși dacă și 15/2 ar fi 7.5, iar 14 sau 15 dacă primul termen ar fi rotunjit.
Variabila m, declarată alăturat, memorează, pentru un medicament, codul, procentul de compensare și data expirării (ziua, luna și anul).
Indicați o expresie C/C++ cu valoarea 1 dacă și numai dacă medicamentul expiră în anul 2025, după luna octombrie.
struct data
{ int zi,luna,an;};
struct medicament
{ int cod;
float compensare;
data expira;
}m;Răspuns corect: c) m.expira.an==2025 && m.expira.luna>10
m este variabila de tip medicament, iar data expirării este câmpul ei expira, de tip data, cu câmpurile zi, luna și an. Anul este deci m.expira.an, iar luna m.expira.luna; după octombrie înseamnă luna mai mare decât 10.
a) folosește numele tipului, data, în locul câmpului expira, iar b) și d) scriu numele în ordine greșită.
Un site de vânzări online oferă reduceri la încălțăminte pentru fiecare comandă care conține trei perechi de articole din categorii diferite din mulțimea ordonată {balerini, botine, cizme, ghete, sandale, teniși}, astfel încât o comandă să nu conțină simultan ghete și cizme, respectiv balerini și sandale. Două soluții diferă prin cel puțin o categorie. Utilizând metoda backtracking, se generează toate comenzile posibile, iar primele patru soluții generate sunt:
Indicați soluția generată imediat înainte de (cizme, sandale, teniși).
Răspuns corect: d) (botine, sandale, teniși)
Comenzile sunt submulțimi de câte trei categorii, generate în ordinea din mulțime, fără ghete împreună cu cizme și fără balerini împreună cu sandale.
(cizme, sandale, teniși) este una dintre primele comenzi care încep cu cizme, deci înaintea ei vine ultima comandă care începe cu botine: a doua și a treia categorie trebuie să fie cât mai târzii în ordine, adică sandale și teniși — (botine, sandale, teniși), care respectă ambele restricții.
Un arbore cu 6 noduri, numerotate de la 1 la 6, are muchiile:
Indicați două noduri care pot fi alese drept rădăcină, astfel încât arborele obținut, pentru fiecare dintre acestea, să aibă trei frunze.
Răspuns corect: d) 4,6
Nodurile cu un singur vecin sunt 3, 4, 5 și 6. Oricare dintre ele devine frunză dacă nu este rădăcina; nodurile 1 și 2 au mai mulți vecini, deci nu sunt frunze niciodată.
Dacă rădăcina este unul dintre nodurile 1 sau 2, toate cele patru rămân frunze. Dacă rădăcina este unul dintre 3, 4, 5, 6, frunzele sunt celelalte trei. Dintre variante, doar 4,6 are ambele noduri cu un singur vecin.
Un graf orientat cu 6 vârfuri, numerotate de la 1 la 6, are arcele:
Indicați numărul minim de arce care trebuie adăugate pentru ca graful obținut să aibă două componente tare conexe.
Răspuns corect: a) 1
Graful dat nu are circuite, deci fiecare vârf este singur în componenta lui tare conexă: șase componente.
Arcul (3,2) închide circuitele 2→1→3→2 și 2→6→4→3→2, care leagă vârfurile 1, 2, 3, 4 și 6 într-o singură componentă tare conexă, iar vârful 5 rămâne singur (din el nu pleacă niciun arc). Un singur arc ajunge, deci răspunsul este 1.
Algoritmul alăturat este reprezentat în pseudocod.
S-a notat cu a%b restul împărțirii numărului natural a la numărul natural nenul b și cu [c] partea întreagă a numărului real c.
Scrieți valorile afișate în urma executării algoritmului, dacă se citește numărul 252.
citește n (număr natural, n≥2) d←2; x←1; y←1 ┌cât timp n>1 execută │┌dacă n%d=0 atunci ││ x←d; y←y*d ││┌cât timp n%d=0 execută │││ n←[n/d] ││└■ │└■ │ d←d+1 └■ scrie x,' ',y
Răspunsul din barem: 7 42
Algoritmul caută divizorii primi ai lui n, în ordine crescătoare: la fiecare divizor d găsit, îl împarte pe n la d de câte ori se poate, reține d în x și îl înmulțește în y. La final x este cel mai mare factor prim, iar y produsul factorilor primi distincți. 252 = 2^2 · 3^2 · 7, deci x = 7 și y = 2 · 3 · 7 = 42.
Același algoritm ca la 1.a.
S-a notat cu a%b restul împărțirii numărului natural a la numărul natural nenul b și cu [c] partea întreagă a numărului real c.
Scrieți două numere distincte din intervalul [10,10^2] care pot fi citite, astfel încât, în urma executării algoritmului, pentru fiecare dintre acestea, să se afișeze două valori egale.
Exemplu: 11 și 16
x (cel mai mare factor prim) este egal cu y (produsul factorilor primi distincți) exact când n are un singur factor prim, adică este o putere a unui număr prim. Din intervalul [10,100]: orice număr prim, dar și 16, 25, 27, 32, 49, 64 sau 81.
Același algoritm ca la 1.a.
S-a notat cu a%b restul împărțirii numărului natural a la numărul natural nenul b și cu [c] partea întreagă a numărului real c.
Scrieți programul C/C++ corespunzător algoritmului dat.
#include <iostream>
using namespace std;
int main()
{
int n, d = 2, x = 1, y = 1;
cin >> n;
while (n > 1)
{
if (n % d == 0)
{
x = d;
y = y * d;
while (n % d == 0) n = n / d;
}
d = d + 1;
}
cout << x << ' ' << y;
return 0;
}Cele două structuri cât timp devin while, iar [n/d] este împărțirea întreagă din C/C++.
Același algoritm ca la 1.a.
S-a notat cu a%b restul împărțirii numărului natural a la numărul natural nenul b și cu [c] partea întreagă a numărului real c.
Scrieți în pseudocod un algoritm echivalent cu cel dat, înlocuind a doua structură cât timp...execută cu o structură repetitivă cu test final.
citește n (număr natural, n≥2) d←2; x←1; y←1 ┌cât timp n>1 execută │┌dacă n%d=0 atunci ││ x←d; y←y*d ││┌repetă │││ n←[n/d] ││└până când n%d≠0 │└■ │ d←d+1 └■ scrie x,' ',y
repetă…până când execută corpul cel puțin o dată, iar cât timp poate să nu îl execute deloc. Aici nu contează: a doua structură este în interiorul lui dacă n%d=0, deci la intrarea în ea n se împarte sigur la d, iar corpul s-ar fi executat măcar o dată. Condiția de oprire este negația celei de continuare: n%d≠0.
Subprogramul f este definit alăturat.
Scrieți valoarea f(2), respectiv valoarea f(17).
int f(int x)
{ if (x<=4) return x;
else return x-f(x-2);
}Răspunsul din barem: 2 8
Pentru x ≤ 4 funcția îl returnează chiar pe x, deci f(2) = 2 și f(3) = 3. Pentru x mai mare, f(x) = x − f(x−2), iar pentru 17 se coboară prin numerele impare: f(5) = 5 − 3 = 2, f(7) = 7 − 2 = 5, f(9) = 9 − 5 = 4, f(11) = 11 − 4 = 7, f(13) = 13 − 7 = 6, f(15) = 15 − 6 = 9, f(17) = 17 − 9 = 8.
Variabilele s1 și s2 permit accesarea câte unui șir de cel mult 50 de caractere, iar variabila n este de tip întreg.
Scrieți șirul accesat prin variabila s1, precum și valoarea lui n, în urma executării secvenței alăturate.
strcpy(s1,"parcarea"); strcpy(s2,strstr(s1,"car")); n=strlen(s2); strcpy(s1+n-2, s2+n-2);
Răspunsul din barem: parea 5
strstr(s1,"car") indică începutul lui "car" în "parcarea", deci s2 devine "carea", iar n = strlen(s2) = 5. strcpy(s1+n-2, s2+n-2) copiază în s1, de la poziția 3, șirul s2 de la poziția 3, adică "ea". s1 păstrează primele trei litere, "par", urmate de "ea": "parea".
Subprogramul consecutiv are doi parametri:
• n, prin care primește un număr natural (n∈[1,10^4]);
• f , prin care furnizează un număr natural cu proprietatea: (f-1)∙f < n ≤ f∙(f+1).
Scrieți definiția completă a subprogramului C/C++.
Exemplu: dacă n=19 atunci f=4 (3∙4 < 19 ≤ 4∙5).
void consecutiv(int n, int &f)
{
f = 1;
while (f * (f + 1) < n) f++;
}Produsele f·(f+1) cresc odată cu f: 2, 6, 12, 20, … Se caută cel mai mic f pentru care f·(f+1) ≥ n. Fiind cel mai mic, pentru f−1 produsul era mai mic decât n, adică (f−1)·f < n, deci f are exact proprietatea cerută. Valoarea se furnizează prin parametrul transmis prin referință, int &f.
Parcarea unui mall are locuri de parcare dispuse pe nr rânduri, câte np pe fiecare rând, unul lângă altul. Trei prieteni vin cu câte o mașină la mall și caută un triplet de locuri libere alăturate, plasate toate trei doar pe primul sau toate trei doar pe ultimul rând al parcării.
Scrieți un program C/C++ care citește de la tastatură două numere naturale din intervalul [3,50], nr și np, reprezentând numărul de rânduri din parcare, respectiv numărul de locuri de pe fiecare rând, apoi nr∙np valori din mulțimea {0,1}, elemente ale unui tablou bidimensional cu nr linii și np coloane, reprezentând, în ordinea dispunerii lor pe rânduri, starea locurilor de parcare (0, pentru loc liber, sau 1, pentru loc ocupat).
Programul afișează pe ecran numărul de triplete de locuri libere pe care le pot găsi prietenii.
Exemplu: pentru nr=4, np=5 și tabloul alăturat, se afișează pe ecran valoarea 3 (pe prima linie pot găsi tripletul format din al doilea, al treilea și al patrulea loc, iar pe ultima linie pot găsi tripletul format din primul, al doilea și al treilea loc sau tripletul format din al doilea, al treilea, și al patrulea loc).
#include <iostream>
using namespace std;
int main()
{
int nr, np, a[50][50], i, j, t = 0;
cin >> nr >> np;
for (i = 0; i < nr; i++)
for (j = 0; j < np; j++)
cin >> a[i][j];
for (j = 0; j + 2 < np; j++)
{
if (a[0][j] == 0 && a[0][j + 1] == 0 && a[0][j + 2] == 0) t++;
if (a[nr - 1][j] == 0 && a[nr - 1][j + 1] == 0 && a[nr - 1][j + 2] == 0) t++;
}
cout << t;
return 0;
}Un triplet de locuri alăturate începe pe o coloană j și ocupă coloanele j, j+1 și j+2, deci j merge până la np-3. Pentru fiecare astfel de j se verifică, separat, dacă cele trei locuri sunt libere pe primul rând (linia 0) și pe ultimul (linia nr-1). Tripletele se pot suprapune, ca în exemplu, unde pe ultimul rând se numără două.
La o loterie se generează aleatoriu un șir de numere naturale și pentru fiecare număr generat, se inversează ordinea cifrelor. Dintre valorile distincte obținute se extrag trei numere, în această ordine: cel mai mic, cel mai mare dintre cele rămase, apoi cel mai mic dintre cele rămase.
Fișierul text bac.in conține cel mult 10^6 numere naturale din intervalul [1001,9999], cu cifra unităților nenulă, separate prin câte un spațiu, reprezentând termenii șirului generat aleatoriu în vederea extragerii.
Scrieți un program C/C++ care afișează pe ecran cele trei numere, în ordinea extragerii acestora. Numerele afișate sunt separate prin câte un spațiu, iar dacă nu există trei astfel de numere distincte, se afișează pe ecran mesajul nu exista. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă fișierul conține numerele 1114 3212 3217 2855 7309 2131 2131 1238 7893 se afișează pe ecran, în această ordine, numerele 1312 9037 2123
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.
Timp de executare: O(n) · Memorie: O(1)
Numerele se citesc pe rând, fără să fie memorate, și pentru fiecare se calculează inversul, y, luând cifrele de la dreapta.
Cele trei numere cerute sunt, dintre valorile distincte obținute, cea mai mică, cea mai mare și a doua cea mai mică. De aceea se păstrează doar trei valori: min1 < min2, cele mai mici două valori distincte, și maxim, cea mai mare. Pentru fiecare y: dacă y < min1, vechiul min1 devine min2 și y devine min1; altfel, dacă y este strict între min1 și min2, devine min2; separat, dacă y > maxim, devine maxim. Valorile egale cu una deja reținută nu schimbă nimic.
La final există trei valori distincte exact când min2 < maxim; atunci se afișează min1, maxim, min2, altfel mesajul nu exista.
Eficiență: fiecare număr se prelucrează o singură dată, în timp constant (are patru cifre), deci algoritmul este liniar în numărul de valori din fișier; se folosesc doar câteva variabile simple, deci memoria este constantă.
La o loterie se generează aleatoriu un șir de numere naturale și pentru fiecare număr generat, se inversează ordinea cifrelor. Dintre valorile distincte obținute se extrag trei numere, în această ordine: cel mai mic, cel mai mare dintre cele rămase, apoi cel mai mic dintre cele rămase.
Fișierul text bac.in conține cel mult 10^6 numere naturale din intervalul [1001,9999], cu cifra unităților nenulă, separate prin câte un spațiu, reprezentând termenii șirului generat aleatoriu în vederea extragerii.
Scrieți un program C/C++ care afișează pe ecran cele trei numere, în ordinea extragerii acestora. Numerele afișate sunt separate prin câte un spațiu, iar dacă nu există trei astfel de numere distincte, se afișează pe ecran mesajul nu exista. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă fișierul conține numerele 1114 3212 3217 2855 7309 2131 2131 1238 7893 se afișează pe ecran, în această ordine, numerele 1312 9037 2123
Scrieți programul C/C++ corespunzător algoritmului proiectat.
#include <fstream>
#include <iostream>
using namespace std;
int main()
{
ifstream fin("bac.in");
int x, y, min1 = 10000, min2 = 10000, maxim = 0;
while (fin >> x)
{
y = 0;
while (x != 0)
{
y = y * 10 + x % 10;
x = x / 10;
}
if (y < min1)
{
min2 = min1;
min1 = y;
}
else if (y > min1 && y < min2) min2 = y;
if (y > maxim) maxim = y;
}
fin.close();
if (min2 < maxim) cout << min1 << ' ' << maxim << ' ' << min2;
else cout << "nu exista";
return 0;
}Programul face pașii de la 3.a. Numerele au patru cifre, iar cifra unităților e nenulă, deci inversul are tot patru cifre și e cel mult 9999; de aceea min1 și min2 pornesc de la 10000, o valoare pe care nicio valoare reală n-o atinge.
Vrei să vezi ce notă ai lua la examen?
Intră în modul simulare: ai cronometru de 3 ore, codul ți se compilează pe loc, iar la final primești nota conform baremului.
Începe simularea3 ore