Varianta 1 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 1 din 2022 trece prin expresii, structuri, backtracking, grafuri și arbori, numere prime, recursivitate, șiruri de caractere, matrice și fișiere. Este o variantă echilibrată, ideală ca test complet.
Subiectul I (20p): 5 grile: o expresie cu / și * între numere întregi, o atribuire corectă care folosește o structură produs, o problemă de backtracking cu pachete de antrenamente sportive, numărul de componente conexe ale unui graf cu 6 noduri și completarea unui vector de „tați” după condiții despre frunze.
Subiectul al II-lea (40p): Un algoritm în pseudocod care numără factorii primi ai unui număr, luați cu puterea lor, un subprogram recursiv f în care a coboară și b urcă până se întâlnesc și o secvență cu șiruri de caractere care construiește Popescu2022 din Ana Popescu.
Subiectul al III-lea (30p): Un subprogram cu cifre (secventa, care înlocuiește fiecare secvență 22 cu 20), o problemă cu matrice despre înnisiparea parcelelor unei plaje și o problemă de eficiență care numără valorile distincte dintr-un interval, într-un șir ordonat citit din fișierul bac.txt.
/ și * au aceeași prioritate și se aplică de la stânga la dreapta, iar 22/20 este împărțire întreagă și dă 1. Expresia valorează 1*20/2, adică 10.x.denumire[5] este un singur caracter, căruia nu i se poate atribui un șir. Corectă este valoare=2*x.cantitate*x.pret;.n se împarte o singură dată, adică dacă n este prim. Alege două numere prime din [10,99], de exemplu 11 și 13.[x,y] și diferă de ultima numărată, fără să salvezi șirul într-un tablou.Indicați valoarea expresiei C/C++ alăturate.
22/20*20/2
Răspuns corect: c) 10
Operatorii / și * au aceeași prioritate și se aplică de la stânga la dreapta, iar între numere întregi / este împărțirea întreagă: 22/20 este 1, apoi 1*20 este 20, iar 20/2 este 10.
Variabilele x și valoare sunt declarate alăturat.
Indicați o instrucțiune de atribuire corectă din punctul de vedere sintactic.
struct produs
{ char denumire[50];
float cantitate, pret;
}x;
float valoare;Răspuns corect: d) valoare=2*x.cantitate*x.pret;
valoare=2*x.cantitate*x.pret; folosește două câmpuri ale variabilei x, amândouă de tip float, iar rezultatul se atribuie unei variabile float. În a) o structură nu se poate iniția printr-o listă de valori într-o atribuire; în b) produs este eticheta structurii, nu un câmp al lui x; în c) x.denumire[5] este un singur caracter, căruia nu i se poate atribui un șir.
La o sală de sport se organizează antrenamente pentru sporturi din mulțimea {tenis, fotbal, volei, handbal, baschet}, astfel încât o persoană poate opta pentru un pachet de antrenamente pentru două sau trei sporturi, dar nu poate alege fotbal și baschet în același pachet. Utilizând metoda backtracking se generează toate posibilitățile unei persoane de a opta pentru un pachet de antrenamente în cadrul sălii de sport. Două pachete sunt distincte dacă diferă prin cel puțin un sport ales. Primele cinci soluții generate sunt, în această ordine:
{tenis, fotbal}, {tenis, fotbal, volei}, {tenis, fotbal, handbal}, {tenis, volei}, {tenis, volei, handbal}.
Indicați soluția generată imediat după {fotbal, handbal}.
Răspuns corect: a) {volei, handbal}
Soluțiile se generează în ordinea sporturilor din mulțime, iar fotbalul și baschetul nu pot apărea împreună. După {fotbal, handbal} ar urma {fotbal, handbal, baschet}, dar aceasta se sare, la fel și {fotbal, baschet}; se trece deci la pachetele care încep cu volei, primul fiind {volei, handbal}.
Un graf neorientat cu 6 noduri, numerotate de la 1 la 6, are muchiile:
Indicați numărul de componente conexe ale acestuia.
Răspuns corect: b) 3
Muchiile [1,2], [1,3] și [2,3] leagă între ele nodurile 1, 2 și 3, muchia [4,6] leagă nodurile 4 și 6, iar nodul 5 rămâne izolat: sunt trei componente conexe.
Într-un arbore cu rădăcină un nod se află pe nivelul n dacă lanțul elementar care are o extremitate în nodul respectiv și cealaltă extremitate în rădăcina arborelui are lungimea n. Pe nivelul 0 se află un singur nod (rădăcina). Un arbore cu rădăcină are 12 noduri, numerotate de la 1 la 12, și este reprezentat prin vectorul de „tați” (2,4,2,0,4,4,x,6,x,x,y,y).
Indicați un set de valori pe care le pot avea x și y, știind că pe ultimul nivel există cinci noduri frunză și că un singur nod este numerotat cu o valoare egală cu numărul său de descendenți direcți („fii”) de tip „frunză”.
Răspuns corect: c) x=3 y=8
Rădăcina este nodul 4, pe nivelul 1 se află 2, 5 și 6, iar pe nivelul 2 nodurile 1, 3 (fiii lui 2) și 8 (fiul lui 6). Pentru x=3 și y=8, nodurile 7, 9 și 10 devin fii ai lui 3, iar 11 și 12 fii ai lui 8: pe nivelul 3 sunt exact cinci frunze. În plus, nodul 3 are trei fii frunză, adică tocmai numărul lui, și este singurul cu această proprietate — la x=y=3 toate cele cinci frunze ar fi fiii lui 3, iar niciun nod nu ar mai avea proprietatea cerută.
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 ce se afișează în urma executării algoritmului dacă se citește numărul 56.
citește n (număr natural) i←2; k←0 ┌cât timp n≥i execută │┌cât timp n%i=0 execută ││ k←k+1 ││ n←[n/i] │└■ │┌dacă i=2 atunci i←i+1 ││altfel i←i+2 │└■ └■ scrie k
Răspunsul din barem: 4
Algoritmul numără de câte ori se poate împărți n la divizorii lui, adică numărul factorilor primi, luați cu tot cu puterea lor. Pentru 56: se împarte de trei ori la 2 (56→28→14→7), deci k ajunge 3, apoi i crește la 3, 5 și 7; la i=7 se mai împarte o dată (7→1), deci k devine 4. Cum n a ajuns 1, bucla exterioară se oprește și se afișează 4.
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 din intervalul [10,99] care pot fi citite, astfel încât, pentru fiecare dintre acestea, în urma executării algoritmului, să se afișeze valoarea 1.
11 și 13
Se afișează 1 doar când n se împarte o singură dată, adică atunci când n este număr prim: orice alt număr din interval fie are un factor la o putere mai mare (12 = 2·2·3 dă 3), fie mai mulți factori diferiți (10 = 2·5 dă 2). Din intervalul [10,99] merge oricare număr prim: 11, 13, 17, 19, 23 și așa mai departe.
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, i = 2, k = 0;
cin >> n;
while (n >= i)
{
while (n % i == 0)
{
k = k + 1;
n = n / i;
}
if (i == 2) i = i + 1;
else i = i + 2;
}
cout << k;
return 0;
}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 a doua structură cât timp...execută cu o structură repetitivă cu test final.
citește n i←2; k←0 ┌cât timp n≥i execută │┌dacă n%i=0 atunci ││┌repetă │││ k←k+1 │││ n←[n/i] ││└până când n%i≠0 │└■ │┌dacă i=2 atunci i←i+1 ││altfel i←i+2 │└■ └■ scrie k
repetă…până când verifică abia la sfârșit, deci execută corpul cel puțin o dată. Aici asta ar fi greșit: când n nu se împarte la i, bucla originală nu se execută deloc, pe când repetă ar crește k și ar schimba n. De aceea e nevoie de garda dacă n%i=0 atunci în jurul ei. Condiția se inversează: bucla mergea cât timp n%i=0, deci se oprește când n%i≠0.
Subprogramul f este definit alăturat.
Scrieți două valori din intervalul [2000,2025] pentru variabila întreagă x, astfel încât, pentru fiecare dintre acestea, f(2022,x) să aibă valoarea 2022.
int f(int a,int b)
{ if(a<=b) return a;
return f(a-1,b+1);
}2022 și 2023
f(a,b) se oprește la primul apel în care a≤b și returnează chiar a; altfel scade a cu 1 și crește b cu 1, deci a coboară și b urcă până se întâlnesc. Ca rezultatul să fie chiar 2022, oprirea trebuie să se facă din primul apel, adică 2022≤x. Din intervalul [2000,2025] merg deci 2022, 2023, 2024 și 2025.
Variabilele s și id permit accesul la câte un șir de maximum 50 de caractere, șirul accesat prin id fiind inițial vid, iar cel accesat prin s memorând, în această ordine, separate printr-un spațiu, prenumele și numele unei persoane, fiecare fiind format numai din litere ale alfabetului englez.
Scrieți o secvență de instrucțiuni C/C++ astfel încât, în urma executării acesteia, șirul accesat prin id să memoreze numele persoanei menționate, urmat de 2022. Declarați corespunzător eventualele alte variabile utilizate.
Exemplu: dacă șirul accesat prin variabila s este Ana Popescu atunci șirul accesat prin variabila id este Popescu2022
char *p = strchr(s, ' '); strcpy(id, p + 1); strcat(id, "2022");
Șirul accesat prin s are prenumele, un spațiu și numele. strchr(s, ' ') indică spațiul, deci de la poziția următoare începe numele: p + 1. Acesta se copiază în id cu strcpy, iar peste el se adaugă 2022 cu strcat.
Subprogramul secventa are un singur parametru, n, prin care primește un număr natural (n∈[10,10^9)) în care nu există secvențe de mai mult de două cifre identice aflate pe poziții consecutive. Subprogramul înlocuiește în n fiecare secvență 22 cu câte o secvență 20 și furnizează, prin același parametru, numărul obținut. Dacă nu se înlocuiește nicio secvență, subprogramul furnizează numărul nemodificat.
Scrieți definiția completă a subprogramului.
Exemplu: dacă n=202233228, după apel n=202033208.
void secventa(int &n)
{
long long rez = 0, p = 1;
while (n > 0)
{
int c = n % 10;
n = n / 10;
if (c == 2 && n % 10 == 2)
{
// Perechea 22: cifra din dreapta devine 0, cea din stânga rămâne 2.
rez = rez + 2 * p * 10;
n = n / 10;
p = p * 100;
}
else
{
rez = rez + c * p;
p = p * 10;
}
}
n = (int)rez;
}Numărul se parcurge cifră cu cifră, de la dreapta spre stânga, iar rezultatul se construiește tot de la dreapta, cu ajutorul puterii lui 10 din p. Când cifra curentă este 2 și cea dinaintea ei este tot 2, perechea se rezolvă dintr-o dată: în rezultat intră 0 pe poziția curentă și 2 pe următoarea, iar din n se consumă amândouă cifrele. Enunțul garantează că nu există trei cifre identice alăturate, deci perechile nu se suprapun. Parametrul e transmis prin referință (int &n), fiindcă rezultatul se întoarce tot prin el.
Pentru prevenirea eroziunii la Marea Neagră, autoritățile au hotărât înnisiparea unei plaje. Plaja a fost împărțită în parcele de formă pătrată cu latura de 1 metru, dispuse ca elementele unui tablou bidimensional, reținându-se nivelul fiecărei parcele, măsurat în metri, de la nivelul mării. Înnisiparea se realizează doar pe acele parcele care au nivelul strict mai mic decât al celei mai joase dintre parcelele vecine cu ea, adăugând nisip, astfel încât cele două să aibă același nivel. Două parcele sunt vecine dacă au o latură comună.
Scrieți un program C/C++ care citește de la tastatură două numere naturale din intervalul [2,10^2], m și n, apoi elementele unui tablou bidimensional cu m linii și n coloane, numere naturale din intervalul [1,10], reprezentând nivelurile parcelelor, în ordinea dispunerii acestora pe plajă.
Programul afișează pe ecran cantitatea totală de nisip adăugată, măsurată în metri cubi.
Exemplu: pentru m=5, n=4 și tabloul alăturat, se vor înnisipa parcelele marcate, pentru a fi aduse la nivelul parcelelor vecine corespunzătoare, și se va afișa valoarea 7 (1+3+1+2).
#include <iostream>
using namespace std;
int a[102][102];
int main()
{
int m, n;
cin >> m >> n;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
cin >> a[i][j];
int total = 0;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
{
int minim = 11; // nivelurile sunt din [1,10]
if (i > 1 && a[i - 1][j] < minim) minim = a[i - 1][j];
if (i < m && a[i + 1][j] < minim) minim = a[i + 1][j];
if (j > 1 && a[i][j - 1] < minim) minim = a[i][j - 1];
if (j < n && a[i][j + 1] < minim) minim = a[i][j + 1];
if (a[i][j] < minim) total = total + minim - a[i][j];
}
cout << total;
return 0;
}Pentru fiecare parcelă se caută cel mai mic nivel dintre vecinii ei de pe latură — cel mult patru, iar marginile au mai puțini. Dacă parcela e strict mai jos decât acest minim, se ridică până la el, iar diferența intră în total. Cum fiecare parcelă are latura de un metru, diferența de nivel este chiar volumul de nisip adăugat. Tabloul se ține cu indici de la 1, ca verificarea marginilor să fie simplă.
Fișierul bac.txt conține numere naturale din intervalul [1,10^9], astfel: pe prima linie două numere, x și y (x<y), iar pe a doua linie un șir de cel mult 10^6 numere, ordonate crescător. 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 numărul de valori distincte din șirul aflat pe a doua linie a fișierului care aparțin intervalului [x,y]. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă fișierul are conținutul alăturat, pe ecran se afișează 6
2 9 1 1 1 2 2 3 5 5 5 5 6 6 7 8 10 10 12 15 21 21
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.
Timp de executare: O(n) · Memorie: O(1)
Fișierul se citește o singură dată: întâi x și y de pe prima linie, apoi numerele de pe a doua, unul câte unul, fără să fie memorate. Șirul este deja ordonat crescător, deci valorile egale vin una după alta: se numără un număr doar când se află în intervalul [x,y] și este diferit de ultimul număr numărat. Astfel fiecare valoare distinctă din interval e numărată exact o dată.
Se face o singură parcurgere, cu un număr de operații proporțional cu numărul de termeni, și se țin minte doar câteva variabile — ultimul număr numărat și contorul — oricât de lung ar fi șirul. Nu e nevoie nici de tablou, nici de o a doua trecere, iar faptul că șirul e ordonat înlătură orice căutare.
Același algoritm ca la 3.a.
Se cere să se afișeze pe ecran numărul de valori distincte din șirul aflat pe a doua linie a fișierului care aparțin intervalului [x,y]. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă fișierul are conținutul alăturat, pe ecran se afișează 6
Scrieți programul C/C++ corespunzător algoritmului proiectat.
#include <fstream>
#include <iostream>
using namespace std;
int main()
{
ifstream f("bac.txt");
int x, y, v, ant = -1, cate = 0;
f >> x >> y;
while (f >> v)
if (v >= x && v <= y)
{
if (v != ant) cate = cate + 1;
ant = v;
}
f.close();
cout << cate;
return 0;
}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