Simularea 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 .
Simularea din 2025 trece prin expresii cu numere reale, recursivitate, tablouri bidimensionale, arbori, grafuri neorientate, backtracking, structuri imbricate, subprograme cu parametri de ieșire, șiruri de caractere și fișiere.
Subiectul I (20p): 5 grile: o expresie cu numere reale, un subprogram recursiv care construiește 2025, un element de pe diagonala secundară a unui tablou 2025×2025, nodul cu cei mai mulți fii dintr-un vector de „tați” și numărul de muchii al unui graf cu 5 componente fără cicluri.
Subiectul al II-lea (40p): Un algoritm în pseudocod care interschimbă două numere și afișează valori și simbolul * într-o structură pentru, grupe de accesorii de înot de 200 de lei generate cu backtracking și o structură specialist cu o structură în interior.
Subiectul al III-lea (30p): Un subprogram cu cifre (harsad, care găsește cel mai mare număr divizibil cu suma cifrelor sale), o problemă cu șiruri de caractere care caută cuvintele cu același număr de vocale ca ultimul și o problemă de eficiență cu etichetele unor bijuterii citite din bijuterii.in.
n este parametru de ieșire, deci se transmite prin referință: int &n.Indicați valoarea expresiei C/C++ alăturate.
20.25/2.5*100
Răspuns corect: c) 810
20.25 este un număr real, deci toate operațiile se fac cu numere reale, de la stânga la dreapta: 20.25/2.5 dă 8.1, iar 8.1*100 dă 810.
Subprogramul f este definit alăturat.
Indicați apelul în urma căruia se obține valoarea 2025.
int f(int x)
{ if(x>500) return 5;
else return 5*f(x*10+5)+x;
}Răspuns corect: d) f(0)
Pentru x≤500, f(x) adaugă cifra 5 la coada lui x și se apelează pentru numărul obținut, până trece de 500, unde întoarce 5.
f(0) = 5·f(5) + 0; f(5) = 5·f(55) + 5; f(55) = 5·f(555) + 55, iar f(555) = 5. Înapoi: f(55) = 25 + 55 = 80, f(5) = 400 + 5 = 405, f(0) = 2025.
Variabila m memorează elementele unui tablou bidimensional cu 2025 de linii și 2025 de coloane, numerotate de la 0 la 2024.
Indicați expresia C/C++ prin care poate fi accesat un element aflat pe diagonala secundară a tabloului.
Răspuns corect: a) m[1999][25]
Pe diagonala secundară suma indicilor este numărul de linii minus 1, adică 2024. 1999 + 25 = 2024, deci m[1999][25] este pe ea. m[25][52] are suma 77, iar scrierea cu : nu există în C/C++.
Un arbore cu 11 noduri, numerotate de la 1 la 11, este reprezentat prin vectorul de „tați” (4,3,7,6,7,8,6,0,7,7,7).
Indicați numărul maxim de descendenți direcți („fii”) ai unui nod.
Răspuns corect: b) 5
Fiii unui nod sunt pozițiile pe care apare el în vectorul de tați. 7 apare pe pozițiile 3, 5, 9, 10 și 11, deci are 5 fii; 6 și celelalte noduri apar de cel mult două ori.
Un graf neorientat are 25 de noduri și 5 componente conexe, fiecare dintre acestea fiind fără cicluri.
Indicați numărul de muchii ale grafului.
Răspuns corect: a) 20
Fiecare componentă fără cicluri este un arbore, iar un arbore cu k noduri are k-1 muchii. Adunat pe toate cele 5 componente: 25 - 5 = 20 de muchii.
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.
Scrieți ce se afișează în urma executării algoritmului dacă se citesc, în această ordine, numerele 20 și 25.
citește m,n (numere naturale) ┌dacă m<n atunci │ n←n+m │ m←n-m │ n←n-m └■ k←m ┌pentru i←m,n,-1 execută │ scrie k,' ' │┌dacă i%2=0 atunci ││ k←k-1 ││ scrie '*' │└■ │ k←k-1 └■
Răspunsul din barem: 25 24 *22 21 *19 18 *
Dacă m<n, cele trei atribuiri interschimbă valorile lui m și n, deci m devine 25, iar n devine 20. k pornește de la 25, iar i coboară de la 25 la 20.
La fiecare pas se afișează k urmat de un spațiu, iar k scade cu 1. Când i este par, k mai scade o dată și se afișează *. Așa că după 25 și 24 (i=25, i=24) urmează *, iar k sare peste 23: urmează 22 și 21, apoi *, 19 și 18, apoi *.
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.
Dacă pentru m se citește numărul 5, scrieți două numere din intervalul [1,50] care pot fi citite pentru n astfel încât, în urma executării algoritmului, pentru fiecare dintre acestea, ultima valoare numerică afișată să fie 2.
Exemplu: 3 10
Cu n<5, k pornește de la 5 și i coboară de la 5 la n; k scade cu 1 la fiecare pas și încă o dată când i este par. Pentru n=3: se afișează 5, apoi 4 și 2, deci ultima valoare este 2. Cu n>5, m și n se interschimbă: k pornește de la n, iar i coboară de la n la 5. Ultima valoare numerică este 2 doar pentru n=10 și n=11. Numerele bune sunt deci 3, 10 și 11.
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.
Scrieți programul C/C++ corespunzător algoritmului dat.
#include <iostream>
using namespace std;
int main()
{
int m, n, k, i;
cin >> m >> n;
if (m < n)
{
n = n + m;
m = n - m;
n = n - m;
}
k = m;
for (i = m; i >= n; i--)
{
cout << k << ' ';
if (i % 2 == 0)
{
k = k - 1;
cout << '*';
}
k = k - 1;
}
return 0;
}pentru i←m,n,-1 execută devine for (i = m; i >= n; i--), cu pasul -1. Interschimbarea prin adunări și scăderi se scrie la fel; merge și cu o variabilă auxiliară.
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.
Scrieți în pseudocod un algoritm echivalent cu cel dat, înlocuind structura pentru...execută cu o structură repetitivă de tip cât timp...execută.
citește m,n (numere naturale) ┌dacă m<n atunci │ n←n+m │ m←n-m │ n←n-m └■ k←m i←m ┌cât timp i≥n execută │ scrie k,' ' │┌dacă i%2=0 atunci ││ k←k-1 ││ scrie '*' │└■ │ k←k-1 │ i←i-1 └■
Cu cât timp, contorul se gestionează explicit: i primește valoarea inițială m înainte de buclă, se continuă cât timp i≥n (pasul este -1, deci se coboară spre n), iar i←i-1 se face la sfârșitul corpului.
Utilizând metoda backtracking se generează toate grupele de accesorii pentru înot din mulțimea ordonată astfel: {cască, clipsuri pentru nas, costum de înot, dopuri pentru urechi, înotătoare, ochelari, pantofi acvatici, placă}. Accesoriile au prețurile următoare, exprimate în lei: cască - 20, clipsuri pentru nas - 10, costum de înot - 50, dopuri pentru urechi - 20, înotătoare - 150, ochelari - 50, pantofi acvatici - 100, placă - 150. Într-o grupă accesoriile sunt distincte și costă, în total, 200 de lei. Două soluții diferă prin cel puțin un accesoriu. Primele trei soluții generate sunt, în această ordine:
Scrieți a patra și a cincea soluție obținute, în ordinea generării acestora.
Răspunsul din barem: (cască, clipsuri pentru nas, dopuri pentru urechi, placă) (costum de înot, înotătoare)
Grupele se generează ca submulțimi, cu accesoriile în ordinea din mulțime, iar suma prețurilor trebuie să fie 200. După (cască, clipsuri, dopuri, ochelari, pantofi) se caută altă continuare pentru (cască, clipsuri, dopuri), care costă 50 de lei: mai rămân 150, iar după ochelari singurul accesoriu de 150 este placa. Cu cască și clipsuri nu mai există alte grupe, așa că se trece mai departe. Cu cască la început nu se mai ajunge la 200 fără clipsuri, deci următoarea soluție începe cu costumul de înot: 50 + 150 cu înotătoarele.
Variabila s memorează date ale fiecăruia dintre cei 30 de specialiști IT ai unei companii: date personale (codul numeric personal – CNP și anul nașterii) și anul angajării.
Știind că expresiile C/C++ de mai jos reprezintă codul numeric personal (un șir de 13 caractere/cifre), anul nașterii, respectiv anul angajării (numere naturale din intervalul [1970,2025]) celui de al șaselea angajat, scrieți definiția unei structuri, cu eticheta specialist, înregistrare care să permită memorarea datelor unui specialist IT, și declarați corespunzător variabila s.
s[5].personal.CNP s[5].personal.anNastere s[5].anAngajare
struct specialist
{ struct
{ char CNP[14];
int anNastere;
} personal;
int anAngajare;
} s[30];Expresiile din enunț spun exact ce câmpuri trebuie să existe: s[5].personal.CNP și s[5].personal.anNastere arată că personal este la rândul lui o structură, cu CNP-ul (13 caractere, deci un tablou de 14, cu loc pentru terminator) și anul nașterii. anAngajare este un câmp simplu al lui specialist. s este un tablou de 30 de structuri, iar al șaselea angajat este s[5], fiindcă indicii încep de la 0. Structura din interior poate fi definită și separat, înaintea lui specialist.
Un număr „care aduce bucurie” - harsad (sau număr Niven), este un număr întreg divizibil cu suma cifrelor sale.
Subprogramul harsad are doi parametri:
• k, prin care primește un număr natural (k∈[1,10^6]);
• n, prin care furnizează cel mai mare număr natural harsad mai mic sau egal cu k.
Scrieți definiția completă a subprogramului.
Exemplu: pentru k=2027, după apel, n=2025 (2+0+2+5=9, iar 2025 este divizibil cu 9).
void harsad(int k, int &n)
{
int x, s, gasit = 0;
n = k;
while (gasit == 0)
{
s = 0;
x = n;
while (x > 0)
{
s = s + x % 10;
x = x / 10;
}
if (n % s == 0) gasit = 1;
else n = n - 1;
}
}n pornește de la k și scade cu 1 până când este divizibil cu suma cifrelor lui. Bucla se oprește sigur, fiindcă orice număr de o cifră este harsad. n este parametru de ieșire, deci se transmite prin referință (int &n), ca valoarea găsită să ajungă înapoi la apelant.
Două cuvinte se numesc asemenea dacă sunt distincte și au același număr de vocale. Se consideră vocale literele:
Scrieți un program C/C++ care citește de la tastatură un număr natural n (n∈[1,10^2]), apoi n cuvinte, separate prin Enter. Fiecare cuvânt este format din cel mult 20 de caractere, numai litere mici ale alfabetului englez. Programul afișează pe ecran, separate prin câte un spațiu, toate cuvintele asemenea cu ultimul cuvânt citit, sau mesajul nu exista dacă nu există astfel de cuvinte.
Exemplu: dacă se citesc datele 9, mereu, primavara, infloresc, ghioceii, lalelele, si, brandusele, de, primavara, se afișează pe ecran, nu neapărat în această ordine, cuvintele:
lalelele brandusele
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
char c[100][21];
int n, i, j, v[100], gasit = 0;
cin >> n;
for (i = 0; i < n; i++)
{
cin >> c[i];
v[i] = 0;
for (j = 0; c[i][j] != '\0'; j++)
if (strchr("aeiou", c[i][j]) != NULL) v[i]++;
}
for (i = 0; i < n - 1; i++)
if (v[i] == v[n - 1] && strcmp(c[i], c[n - 1]) != 0)
{
cout << c[i] << ' ';
gasit = 1;
}
if (gasit == 0) cout << "nu exista";
return 0;
}Cuvintele se citesc într-un tablou, iar pentru fiecare se numără vocalele (strchr caută litera în șirul "aeiou"). Apoi se compară fiecare cuvânt de dinaintea ultimului cu acesta: se afișează dacă are același număr de vocale și este diferit de el (strcmp). Dacă nu s-a afișat nimic, se scrie nu exista.
Pentru o paradă a modei sunt pregătite seturi de bijuterii, un set fiind format din cercei și pandantiv, cu câte cel puțin două pietre prețioase și semiprețioase. Sunt utilizate nouă tipuri de pietre, numerotate de la 1 la 9, iar orice bijuterie are o etichetă, număr natural în care fiecare cifră corespunde unei pietre din montură, în ordinea descrescătoare a importanței în cadrul modelului. Un set este potrivit dacă cele mai importante două pietre ale fiecărei bijuterii din set sunt de același tip, chiar dacă nu în aceeași ordine a importanței.
Fișierul bijuterii.in conține numere naturale din intervalul [10,999]: pe prima linie două numere nc și np, reprezentând numărul de cercei, respectiv de pandantive disponibile, pe a doua linie un șir de nc numere, reprezentând etichetele cerceilor, iar pe a treia linie un șir de np numere, reprezentând etichetele pandantivelor. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu. Se cere să se afișeze pe ecran mesajul DA, dacă se poate forma cel puțin un set potrivit de bijuterii, sau mesajul NU, în caz contrar. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul conține numerele
10 11
497 125 521 497 513 258 491 55 551 16
21 259 943 77 945 57 52 552 16 17 71
se afișează pe ecran mesajul DA (două dintre cele 14 seturi potrivite se pot forma din cerceii cu eticheta 258 și fiecare dintre pandantivele cu etichetele 259, respectiv 52, pentru toate aceste bijuterii pietrele de tipurile 2 și 5 fiind cele mai importante).
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.
Timp de executare: O(n) · Memorie: O(1)
Contează doar primele două cifre ale fiecărei etichete, adică un număr de două cifre: eticheta însăși, dacă are două cifre, sau eticheta fără ultima cifră, dacă are trei.
La citirea cerceilor se marchează într-un vector de apariții ac, cu indici de la 10 la 99, numărul format din primele două cifre ale fiecăruia. Apoi, pentru fiecare pandantiv, se iau primele două cifre p1 și p2 și se verifică dacă este marcat p1p2 sau p2p1 (aceleași pietre, în altă ordine). Dacă unul dintre ele este marcat, se afișează DA, altfel NU.
Eficiență: fiecare etichetă se prelucrează o singură dată, în timp constant, deci timpul este liniar în numărul de bijuterii, iar vectorul de apariții are dimensiune fixă.
Pentru o paradă a modei sunt pregătite seturi de bijuterii, un set fiind format din cercei și pandantiv, cu câte cel puțin două pietre prețioase și semiprețioase. Sunt utilizate nouă tipuri de pietre, numerotate de la 1 la 9, iar orice bijuterie are o etichetă, număr natural în care fiecare cifră corespunde unei pietre din montură, în ordinea descrescătoare a importanței în cadrul modelului. Un set este potrivit dacă cele mai importante două pietre ale fiecărei bijuterii din set sunt de același tip, chiar dacă nu în aceeași ordine a importanței.
Fișierul bijuterii.in conține numere naturale din intervalul [10,999]: pe prima linie două numere nc și np, reprezentând numărul de cercei, respectiv de pandantive disponibile, pe a doua linie un șir de nc numere, reprezentând etichetele cerceilor, iar pe a treia linie un șir de np numere, reprezentând etichetele pandantivelor. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu. Se cere să se afișeze pe ecran mesajul DA, dacă se poate forma cel puțin un set potrivit de bijuterii, sau mesajul NU, în caz contrar. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul conține numerele
10 11
497 125 521 497 513 258 491 55 551 16
21 259 943 77 945 57 52 552 16 17 71
se afișează pe ecran mesajul DA (două dintre cele 14 seturi potrivite se pot forma din cerceii cu eticheta 258 și fiecare dintre pandantivele cu etichetele 259, respectiv 52, pentru toate aceste bijuterii pietrele de tipurile 2 și 5 fiind cele mai importante).
Scrieți programul C/C++ corespunzător algoritmului proiectat.
#include <fstream>
#include <iostream>
using namespace std;
int main()
{
ifstream fin("bijuterii.in");
int nc, np, x, i, ac[100] = {0}, ok = 0;
fin >> nc >> np;
for (i = 0; i < nc; i++)
{
fin >> x;
if (x > 99) x = x / 10;
ac[x] = 1;
}
for (i = 0; i < np; i++)
{
fin >> x;
if (x > 99) x = x / 10;
if (ac[x] == 1 || ac[x % 10 * 10 + x / 10] == 1) ok = 1;
}
fin.close();
if (ok == 1) cout << "DA";
else cout << "NU";
return 0;
}Programul face pașii de la 3.a. O etichetă de trei cifre se împarte la 10 ca să rămână primele două. Pentru un pandantiv, x % 10 * 10 + x / 10 este numărul cu cele două cifre inversate.
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