Varianta 5 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 5 din 2026 trece prin expresii logice, recursivitate, structuri imbricate, arbori, grafuri orientate, cifre, backtracking, șiruri de caractere, numere prime, matrice și fișiere. Este o variantă echilibrată, bună pentru recapitularea întregii materii.
Subiectul I (20p): 5 grile: o expresie logică cu valoarea 1, un subprogram recursiv care numără cifrele impare minus cele pare, durata în secunde a unei părți dintr-o structură sonata, numărul de niveluri ale unui arbore dat prin vectorul de tați și numărul minim de arce adăugate ca un graf orientat să devină tare conex.
Subiectul al II-lea (40p): Un algoritm în pseudocod care numără de câte ori apare cifra k în numerele dintr-un interval, o problemă de backtracking cu cifrurile unui lacăt și o secvență care formează șirul Prof. urmat de prenumele și numele unui profesor.
Subiectul al III-lea (30p): Un subprogram cu numere prime (pagini, care verifică dacă n pagini formează o broșură și un catalog), o problemă cu o matrice care caută coloanele consecutive cu aceeași sumă și o problemă de eficiență care scrie în fișierul bac.txt, în ordine inversă, termenii unui șir până la x.
4>3>2 nu înseamnă „4 > 3 și 3 > 2”. Se evaluează de la stânga la dreapta: 4>3 dă 1, iar 1>2 dă 0.k se numără de fiecare dată când apare, deci 122 contribuie cu 2. Între 120 și 126, cifra 2 apare de 8 ori.16785.n trebuie să se împartă la 4, iar n/4 trebuie să fie prim. Pentru n=4 se obține p = 1, care nu este prim.Indicați o expresie C/C++ cu valoarea 1.
Răspuns corect: a) !(2>3 || 3>4)
2>3 și 3>4 sunt amândouă false (0), deci 2>3 || 3>4 are valoarea 0, iar negația ei are valoarea 1: varianta a).
b) și c) leagă cu && câte o condiție falsă, deci au valoarea 0. d) se evaluează de la stânga la dreapta: 4>3 are valoarea 1, iar 1>2 are valoarea 0.
Subprogramul f este definit alăturat.
Indicați valoarea lui f(56579).
int f(int n)
{ if(n==0)return 0;
if(n%2==1)return f(n/10)+1;
return f(n/10)-1;
}Răspuns corect: d) 3
Fiecare apel se ocupă de ultima cifră a lui n: adaugă 1 dacă e impară, scade 1 dacă e pară, apoi continuă cu n/10, adică fără acea cifră, până ajunge la 0.
Cifrele lui 56579 sunt 5, 6, 5, 7, 9: patru impare și una pară, deci f(56579) = 4 − 1 = 3.
În muzica clasică, o sonată este o lucrare compusă din trei părți. Variabila declarată alăturat memorează indicativul unei sonate și durata fiecăreia dintre cele trei părți ale acesteia, exprimată în minute și secunde.
Indicați o expresie a cărei valoare este egală cu durata celei de a doua părți a sonatei, exprimată în secunde.
struct sonata
{ int indicativ;
struct
{ int min,sec;
}unu,doi,trei;
}s;Răspuns corect: a) s.doi.sec+60*s.doi.min
s este variabila, iar doi este câmpul ei pentru a doua parte, la rândul lui o structură cu câmpurile min și sec. Durata în secunde este deci s.doi.sec+60*s.doi.min.
b) folosește numele tipului, sonata, în locul variabilei, iar c) și d) scriu numele în ordine inversă, ceea ce nu este o expresie C/C++ validă.
Într-un arbore cu rădăcină considerăm că un nod se află pe nivelul x dacă lanțul elementar care are o extremitate în nodul respectiv și cealaltă extremitate în rădăcina arborelui are lungimea x. Pe nivelul 0 se află un singur nod (rădăcina). Un arbore cu 8 noduri, numerotate de la 1 la 8, este reprezentat prin vectorul de tați: (3,4,0,3,4,8,2,3).
Indicați numărul de niveluri ale arborelui.
Răspuns corect: c) 4
În vectorul de tați, poziția i spune care este tatăl nodului i; rădăcina are 0, deci este nodul 3.
Pe nivelul 1 sunt fiii lui 3: nodurile 1, 4 și 8. Pe nivelul 2 sunt fiii lui 4 (nodurile 2 și 5) și fiul lui 8 (nodul 6). Pe nivelul 3 este fiul lui 2, nodul 7. Nivelurile 0, 1, 2 și 3 înseamnă patru niveluri.
Un graf orientat cu 7 vârfuri, numerotate de la 1 la 7, are arcele:
Indicați numărul minim de arce care pot fi adăugate și poziționate adecvat, astfel încât graful orientat obținut să fie tare conex.
Răspuns corect: b) 2
Graful are două componente tare conexe: vârfurile 1, 2, 3 (circuitul 1→2→3→1) și vârfurile 4, 5, 6, 7 (circuitul 4→5→6→7→4), fără niciun arc între ele.
Ca graful să devină tare conex, trebuie să existe drum în ambele sensuri între cele două componente, deci un arc de la prima la a doua și unul înapoi, de exemplu (3,4) și (4,1): două arce. Un singur arc ar da drum doar într-un sens.
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 valoarea afișată în urma executării algoritmului dacă se citesc, în această ordine, numerele 120, 126, 2.
citește m,n,k (numere naturale nenule, m≤n, 0≤k≤9) nr←0 ┌pentru i←m,n execută │ x←i │┌repetă ││┌dacă x%10=k atunci │││ nr←nr+1 ││└■ ││ x←[x/10] │└până când x=0 └■ scrie nr
Răspunsul din barem: 8
Algoritmul numără de câte ori apare cifra k în toate numerele de la m la n: pentru fiecare număr i, îi ia cifrele pe rând, de la dreapta, și le compară cu k. În numerele de la 120 la 126, cifra 2 apare o dată în 120, 121, 123, 124, 125 și 126 și de două ori în 122: 6 + 2 = 8.
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.
Dacă pentru m se citește numărul 2026, iar pentru k se citește numărul 6, scrieți două numere din intervalul [10^3,10^4] care pot fi citite pentru n, astfel încât, pentru fiecare dintre acestea, în urma executării algoritmului, să se afișeze valoarea 2.
Exemplu: 2036 și 2040
Se numără aparițiile cifrei 6 în numerele de la 2026 la n. 2026 are un 6, următorul număr care conține cifra 6 este 2036, iar după el vine 2046. Se afișează 2 exact când n este între 2036 și 2045.
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 m, n, k, nr = 0, i, x;
cin >> m >> n >> k;
for (i = m; i <= n; i++)
{
x = i;
do
{
if (x % 10 == k) nr = nr + 1;
x = x / 10;
} while (x != 0);
}
cout << nr;
return 0;
}pentru i←m,n execută devine for (i = m; i <= n; i++). repetă…până când x=0 devine do…while, cu condiția negată: se repetă cât timp x != 0. Operația [x/10] 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 adecvat structura pentru...execută cu o structură de tip cât timp...execută.
citește m,n,k (numere naturale nenule, m≤n, 0≤k≤9) nr←0 i←m ┌cât timp i≤n execută │ x←i │┌repetă ││┌dacă x%10=k atunci │││ nr←nr+1 ││└■ ││ x←[x/10] │└până când x=0 │ i←i+1 └■ scrie nr
Structura pentru își gestiona singură contorul. Cu cât timp, contorul se gestionează explicit: i primește valoarea inițială m înainte de buclă, condiția de continuare este i≤n, iar i←i+1 se face la sfârșitul corpului.
Lacătul unei biciclete are un cifru format din 5 cifre distincte, astfel încât oricare două cifre alăturate au parități diferite. Pentru că a uitat cifrul, Andrei încearcă toate soluțiile posibile, pe care le generează în ordine lexicografică, utilizând metoda backtracking. Două cifruri diferă prin cel puțin o cifră sau prin ordinea acestora, primele șase fiind, în ordinea generării:
Scrieți două soluții, una generată imediat înainte, iar cealaltă generată imediat după 16789.
Răspunsul din barem: 16785 16903
Cifrurile se generează în ordine lexicografică, cu cifre distincte și cu paritatea alternând de la o poziție la alta; 16789 are paritățile impar, par, impar, par, impar.
Înainte de el: se schimbă doar ultima cifră, cu cea mai mare cifră impară mai mică decât 9 și nefolosită. 7 este deja în cifru, deci 5: 16785.
După el: ultima cifră nu mai poate crește (9 este cea mai mare), iar a patra, 8, nici ea (nu mai există cifră pară după 8). Crește a treia cifră: după 7, următoarea impară nefolosită este 9. Pozițiile de după ea iau cele mai mici valori posibile: a patra, pară, 0; a cincea, impară și nefolosită (1 și 9 sunt deja în cifru), 3: 16903.
Variabilele s și t permit accesul la câte un șir de cel mult 50 de caractere; inițial t accesează un șir vid, iar s un șir ce memorează, în această ordine, numele și prenumele unui profesor, separate printr-un spațiu și formate din litere mari și mici ale alfabetului limbii engleze.
Scrieți o secvență de instrucțiuni C/C++ în urma executării căreia variabila t accesează șirul format, în această ordine, din titlu (Prof.), urmat de prenume și nume, separate prin câte un spațiu, ca în exemplu. Declarați eventuale alte variabile necesare.
Exemplu: dacă s accesează șirul POP Grigore, atunci t accesează șirul Prof. Grigore POP.
char *p = strchr(s, ' '); strcpy(t, "Prof. "); strcat(t, p + 1); strcat(t, " "); strncat(t, s, p - s);
p indică spațiul dintre nume și prenume. În t se scrie întâi titlul "Prof. ", apoi prenumele (tot ce urmează după spațiu, de la p+1), un spațiu și, la final, numele: strncat adaugă doar primele p-s caractere din s, adică exact numele, fără să modifice șirul s.
O editură realizează seturi turistice, formate din câte o broșură de prezentare a zonei locale și câte un catalog al producătorilor locali, astfel încât dacă o broșură are p pagini, atunci p este un număr prim, iar catalogul din același set are 3∙p pagini.
Subprogramul pagini are un parametru, n, prin care primește un număr natural (n∈[2,10^4]). Subprogramul returnează valoarea 1 dacă, folosind toate cele n pagini, se poate realiza un set turistic, sau valoarea 0 în caz contrar.
Scrieți în C/C++ definiția completă a subprogramului.
Exemplu: dacă n=44, subprogramul returnează valoarea 1 (se poate obține o broșură de 11 pagini și un catalog de 33=3∙11 pagini), iar dacă n=48 sau n=27, subprogramul returnează 0.
int pagini(int n)
{
int p, d;
if (n % 4 != 0) return 0;
p = n / 4;
if (p < 2) return 0;
for (d = 2; d * d <= p; d++)
if (p % d == 0) return 0;
return 1;
}Broșura are p pagini și catalogul 3·p, deci setul folosește p + 3·p = 4·p pagini. Se poate realiza un set din toate cele n pagini exact când n se împarte la 4, iar p = n/4 este număr prim. Primalitatea se verifică încercând divizorii de la 2 până la radicalul lui p. Cazul n=4 dă p=1, care nu este prim, deci se returnează 0.
Într-un tablou bidimensional, două coloane sunt numite stabile dacă suma valorilor de pe una dintre ele este egală cu suma valorilor de pe cealaltă, iar cele două coloane sunt consecutive în tablou.
Scrieți un program C/C++ care citește de la tastatură două numere naturale din intervalul [1,20], m și n, și m∙n numere naturale din intervalul [0,10), elemente ale unui tablou bidimensional cu m linii și n coloane, numerotate începând de la 0. Programul afișează pe ecran toate perechile de numere x și y (x<y), pentru care coloanele x și y sunt stabile în tabloul dat, sau mesajul nu exista, dacă nu există astfel de coloane.
Fiecare pereche se afișează pe câte o linie a ecranului, cu cele două valori în ordine strict crescătoare, separate prin câte un spațiu.
Exemplu: pentru m=6, n=7 și tabloul alăturat, se afișează pe ecran perechile de mai jos, nu neapărat în această ordine
0 1 1 2 5 6
| 2 | 6 | 1 | 0 | 4 | 0 | 0 |
| 0 | 3 | 5 | 2 | 3 | 1 | 0 |
| 2 | 0 | 0 | 0 | 1 | 0 | 1 |
| 6 | 0 | 5 | 0 | 6 | 0 | 1 |
| 1 | 3 | 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 2 | 0 | 0 |
#include <iostream>
using namespace std;
int main()
{
int m, n, a[20][20], s[20], i, j, gasit = 0;
cin >> m >> n;
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
cin >> a[i][j];
for (j = 0; j < n; j++)
{
s[j] = 0;
for (i = 0; i < m; i++)
s[j] = s[j] + a[i][j];
}
for (j = 0; j + 1 < n; j++)
if (s[j] == s[j + 1])
{
cout << j << ' ' << j + 1 << '\n';
gasit = 1;
}
if (gasit == 0) cout << "nu exista";
return 0;
}Se calculează întâi suma fiecărei coloane, în tabloul s. Două coloane stabile sunt consecutive, deci se compară doar s[j] cu s[j+1], pentru fiecare j, și se afișează perechea j, j+1 când sumele sunt egale. Variabila gasit ține minte dacă s-a afișat vreo pereche; dacă nu, se afișează mesajul nu exista. Enunțul acceptă perechile în orice ordine; programul le afișează de la stânga la dreapta.
Șirul 1, 2, 2, 5, 4, 11, 8, 23, 16, 47.... este definit astfel: f^0=1, iar pentru orice n, număr natural strict pozitiv, f^n=3∙f^n-1 - 1, dacă n este impar, sau f^n=2∙f^n-2, dacă n este par.
Se citește de la tastatură un număr natural x (x∈[4,10^9]), termen al șirului dat. Se cere să se scrie în fișierul bac.txt, în ordinea inversă apariției în șir, separați prin câte un spațiu, atât termenul citit, cât și toți cei care îl preced în șir pe acesta, ca în exemplu. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al spațiului de memorie utilizat.
Exemplu: dacă x=8, fișierul conține numerele 8 11 4 5 2 2 1
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.
Timp de executare: O(n) · Memorie: O(1)
Termenii de pe pozițiile pare sunt puterile lui 2 (1, 2, 4, 8, 16, …), iar cei de pe pozițiile impare au forma 3·2^k−1 (2, 5, 11, 23, 47, …). Un termen impar x provine din puterea lui 2 dinaintea lui, (x+1)/3, iar înaintea acesteia se află termenul impar anterior, (x−1)/2.
Se scrie x. Dacă x este par, adică o putere a lui 2, termenul dinaintea lui este x/2·3−1, care se scrie și devine noul x. Apoi, cât timp x≥2, se scrie (x+1)/3, x devine (x−1)/2 și, dacă mai este cel puțin 2, se scrie și el. Când x ajunge la 2 se scrie 1, iar x devine 0.
Eficiență: fiecare termen se obține din cel scris înaintea lui prin câteva operații, deci timpul este liniar în numărul de termeni scriși. Se păstrează doar valoarea curentă, fără niciun tablou, deci memoria folosită este constantă.
Șirul 1, 2, 2, 5, 4, 11, 8, 23, 16, 47.... este definit astfel: f^0=1, iar pentru orice n, număr natural strict pozitiv, f^n=3∙f^n-1 - 1, dacă n este impar, sau f^n=2∙f^n-2, dacă n este par.
Se citește de la tastatură un număr natural x (x∈[4,10^9]), termen al șirului dat. Se cere să se scrie în fișierul bac.txt, în ordinea inversă apariției în șir, separați prin câte un spațiu, atât termenul citit, cât și toți cei care îl preced în șir pe acesta, ca în exemplu. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al spațiului de memorie utilizat.
Exemplu: dacă x=8, fișierul conține numerele 8 11 4 5 2 2 1
Scrieți programul C/C++ corespunzător algoritmului proiectat.
#include <fstream>
#include <iostream>
using namespace std;
int main()
{
long long x;
cin >> x;
ofstream fout("bac.txt");
fout << x;
if (x % 2 == 0)
{
x = x / 2 * 3 - 1;
fout << ' ' << x;
}
while (x >= 2)
{
fout << ' ' << (x + 1) / 3;
x = (x - 1) / 2;
if (x >= 2) fout << ' ' << x;
}
fout.close();
return 0;
}Programul face pașii de la 3.a. Termenii se scriu pe măsură ce se obțin, deci fișierul îi conține direct în ordinea cerută, fără ca șirul să fie memorat. Valorile ajung până la 10^9, iar x/2·3 trece de limita tipului int, de aceea se folosește long long.
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