Varianta 4 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 4 din 2022 trece prin expresii, recursivitate, backtracking, șiruri de caractere, arbori și grafuri, structuri, pătrate perfecte, matrice și fișiere. Este o variantă echilibrată, bună pentru exersat atenția la condițiile din enunț.
Subiectul I (20p): 5 grile: expresia cu valoarea 2022, un subprogram recursiv care taie cifre dintr-un număr, o problemă de backtracking cu mașini Dacia expuse câte trei, o secvență cu strchr și strcpy aplicată unei adrese de email și numărul maxim de „frați” ai unui nod într-un arbore cu 7 noduri.
Subiectul al II-lea (40p): Un algoritm în pseudocod care afișează numerele prime formate din câte două cifre alăturate ale lui n, un subgraf complet cu număr maxim de noduri și o secvență care calculează încasările din bilete pentru 15 săli memorate într-un tablou de structuri sala.
Subiectul al III-lea (30p): Un subprogram (patrate) care caută x și y cu x²·y²=n, o problemă cu matrice în care se elimină elementele de pe diagonala principală și o problemă de eficiență cu „secvențe progresive” dintr-un șir crescător citit din fișierul bac.txt.
1011*1+1 dă 1012. Doar 1011*(1+1) valorează 2022.s[strlen(s)-3] este punctul din info@rocnee.eu, nu litera e. După ce îl înlocuiești cu '\0', șirul devine info@rocnee, iar în d se copiază rocnee.n pierde o singură cifră, deci perechile se suprapun: 18, 51, 75, 37, 23. Se afișează doar cele care nu se împart la 2, 3, 5 sau 7: 37 23.x²·y²=n rezultă că n trebuie să fie pătrat perfect. Condiția x<y cere valori diferite: pentru n=16, singura variantă ar fi x=y=2, deci se furnizează 0 și 0.Indicați expresia C/C++ cu valoarea 2022.
Răspuns corect: d) 1011*(1+1)
1011*(1+1) este 1011*2, adică 2022. În a) și b) se obține 505, fiindcă 4044/8 este împărțire întreagă (4044/4/2 se face tot de la stânga la dreapta, 1011/2), iar în c) înmulțirea are prioritate față de adunare, deci rezultatul este 1012.
Subprogramul f este definit alăturat.
Indicați valoarea parametrului x pentru care f(x,3) are valoarea 2022.
int f(int n,int p)
{ if(n==0) return 0;
else if(p==0) return n*10+2;
else return f(n/10,p-1);
}Răspuns corect: c) 202345
Subprogramul taie ultima cifră a lui n la fiecare apel, până când p ajunge 0; abia atunci întoarce n*10+2. Pentru f(x,3) se taie trei cifre, deci rezultatul este (x/1000)*10+2. Din (x/1000)*10+2=2022 rezultă x/1000=202, adică x începe cu 202 și are șase cifre — dintre variante, doar 202345.
Utilizând metoda backtracking, se generează toate posibilitățile de a expune câte trei mașini produse în România, din gama Dacia, din mulțimea {Dokker (negru), Duster (negru), Lodgy (gri), Logan (alb), Sandero (roșu)}, astfel încât să nu fie expuse simultan două mașini de aceeași culoare, Sandero să NU apară pe prima poziție, iar Logan să NU fie înainte de Dokker sau Duster. Două soluții sunt distincte dacă au cel puțin o mașină diferită sau dacă ordinea mașinilor este diferită. Primele cinci soluții generate sunt, în această ordine:
Indicați penultima soluție, în ordinea generării acestora.
Răspuns corect: a) Logan, Lodgy, Sandero
Ultimele soluții sunt cele care încep cu mașina cea mai din dreapta în mulțime, dar Sandero nu poate sta pe prima poziție, deci ele încep cu Logan. Cum Logan nu are voie înaintea lui Dokker sau Duster, după el pot veni doar Lodgy și Sandero: ultimele două soluții sunt (Logan, Lodgy, Sandero) și (Logan, Sandero, Lodgy). Penultima este deci (Logan, Lodgy, Sandero).
Variabilele s și d permit memorarea câte unui șir cu maximum 50 de caractere.
Indicați șirul memorat prin intermediul variabilei d în urma executării secvenței alăturate.
strcpy(s,"info@rocnee.eu"); s[strlen(s)-3]='\0'; strcpy(d,strchr(s,'@')+1);
Răspuns corect: c) rocnee
Șirul info@rocnee.eu are 14 caractere, iar s[strlen(s)-3] este caracterul de pe poziția 11, adică punctul; înlocuit cu terminatorul de șir, s devine info@rocnee. strchr(s,'@') indică @, deci de la caracterul următor începe rocnee, care se copiază în d.
Într-un arbore cu 7 noduri, numerotate de la 1 la 7, nodul 1 este rădăcină și pentru orice nod numerotat cu i (i∈[1,7]), dacă se notează cu F(i) numărul de descendenți direcți („fii”) ai săi, atunci F(i)=0, dacă i este „frunză”, altfel F(i)=i+1.
Indicați numărul maxim de „frați” ai nodului 7.
Răspuns corect: b) 3
Rădăcina 1 nu e frunză, deci are 2 fii. Rămân patru noduri, care trebuie să fie fiii unui singur nod i, cu i+1 fii: din 1+2+(i+1)=7 rezultă i=3, deci nodul 3 are patru fii, printre care și 7. Nodul 7 are astfel trei frați. Mai mulți nu se pot: un părinte cu cinci fii ar cere 1+2+5=8 noduri.
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 1237518.
citește n (număr natural) ┌repetă │ x←n%100 │┌dacă x>1 atunci ││ p←(x%2)*(x%3)*(x%5)*(x%7) ││┌dacă p≠0 atunci │││ scrie x,' ' ││└■ │└■ │ n←[n/10] └până când n<10
Răspunsul din barem: 37 23
La fiecare pas se iau ultimele două cifre ale lui n și se scriu doar dacă nu se împart la 2, 3, 5 sau 7 — adică, pentru un număr de două cifre, doar dacă sunt număr prim. Pentru 1237518: 18 se împarte la 2, 51 la 3, 75 la 5, 37 nu se împarte la niciunul, deci se scrie; apoi 23, tot prim, se scrie și el; la 12 se iese, pentru că 12 se împarte la 2, iar n a ajuns sub 10.
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 [100,999] care pot fi citite, astfel încât, pentru fiecare dintre acestea, în urma executării algoritmului, să se afișeze două numere.
113 și 137
Dintr-un număr de trei cifre se iau, pe rând, ultimele două cifre și primele două. Se scrie un număr doar dacă nu se împarte la 2, 3, 5 sau 7, adică doar dacă e prim. Ca să se afișeze două numere, trebuie ca atât numărul format din ultimele două cifre, cât și cel format din primele două să fie prime: la 113 sunt 13 și 11, la 137 sunt 37 și 13. Merg la fel 173, 197, 311, 313 și celelalte de aceeași formă.
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, x, p;
cin >> n;
do
{
x = n % 100;
if (x > 1)
{
p = (x % 2) * (x % 3) * (x % 5) * (x % 7);
if (p != 0) cout << x << ' ';
}
n = n / 10;
} while (n >= 10);
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 structura repetă...până când cu o structură repetitivă cu test inițial.
citește n (număr natural) ┌cât timp n≥10 execută │ x←n%100 │┌dacă x>1 atunci ││ p←(x%2)*(x%3)*(x%5)*(x%7) ││┌dacă p≠0 atunci │││ scrie x,' ' ││└■ │└■ │ n←[n/10] └■
repetă…până când verifică la sfârșit și se oprește când condiția devine adevărată, iar cât timp verifică la început și merge înainte cât timp condiția e adevărată: condiția n<10 devine deci n≥10. Cele două algoritme afișează același lucru pentru orice n: pentru un n de o singură cifră, cel original execută corpul o dată, iar cel nou deloc, dar nici cel original nu scrie nimic, pentru că x este 0 sau 1 ori se împarte la 2, 3, 5 sau 7.
Un graf neorientat cu 6 noduri, numerotate de la 1 la 6, are muchiile:
Scrieți mulțimea muchiilor unui subgraf al acestui graf, care să fie complet și să aibă un număr maxim de noduri.
Răspunsul din barem: [1,2], [1,3], [1,5], [2,3], [2,5], [3,5]
Un subgraf complet are muchie între oricare două noduri ale lui. Nodurile 1, 2, 3 și 5 sunt legate două câte două — muchiile [1,2], [1,3], [1,5], [2,3], [2,5] și [3,5] există toate în graf. Mai mult nu se poate: nodul 4 nu e legat de 3 și de 5, iar nodul 6 e legat doar de 4 și de 5.
Pentru o sală de spectacole se memorează următoarele informații specifice: numărul de locuri disponibile și prețul biletului pentru un loc. Variabilele i și s sunt întregi, iar variabila t memorează informațiile specifice pentru fiecare dintre cele 15 săli de spectacole dintr-un oraș.
Scrieți o secvență de instrucțiuni în urma executării căreia variabila s să memoreze suma totală obținută în urma vânzării biletelor pentru un festival de teatru care s-ar desfășura simultan în toate sălile, iar acestea ar fi ocupate complet.
struct sala
{ int nrLocuri;
int pret;
} t[15];s = 0;
for (i = 0; i < 15; i++)
s = s + t[i].nrLocuri * t[i].pret;Suma totală din vânzarea tuturor biletelor este, pentru fiecare sală, numărul de locuri înmulțit cu prețul unui bilet. Se parcurg cele 15 săli din tabloul t și se adună produsele într-o variabilă pornită de la 0.
Subprogramul patrate are trei parametri:
• n, prin care primește un număr natural (n∈[2,10^9]);
• x și y, prin care furnizează câte un număr natural cu proprietatea că x^2∙y^2=n și 2≤x<y sau valoarea 0, prin fiecare dintre aceștia, dacă nu există două astfel de numere. Dacă sunt mai multe astfel de valori, se furnizează cele corespunzătoare unei valori minime a lui x.
Scrieți definiția completă a subprogramului.
Exemplu: pentru n=400, după apel, x=2 și y=10, iar pentru n=16 sau n=24, după apel, x=0 și y=0.
void patrate(int n, int &x, int &y)
{
int s = 0;
while ((s + 1) * (s + 1) <= n) s = s + 1; // s = [√n]
x = 0;
y = 0;
if (s * s != n) return; // n nu e pătrat perfect
for (int d = 2; d * d < s; d++) // d < s/d, adică x < y
if (s % d == 0)
{
x = d;
y = s / d;
return;
}
}Din x²·y²=n rezultă (x·y)²=n, deci n trebuie să fie pătrat perfect, iar x·y este chiar [√n]. Se caută apoi cel mai mic divizor x≥2 al lui s=x·y pentru care x<y, adică x·x<s; perechea se întoarce la prima potrivire, iar căutarea din doi în sus garantează că x este minim. Dacă n nu e pătrat perfect sau dacă niciun divizor nu îndeplinește condiția — ca la 16, unde ar ieși 4·4 — amândoi parametrii rămân 0.
Suprafața unei scene a fost împărțită în zone dispuse ca elementele unui tablou bidimensional cu număr egal de linii și coloane. Fiecare instrument are alocată o zonă și este identificat printr-un număr natural. Dirijorul hotărăște eliminarea tuturor instrumentelor plasate pe diagonala principală a tabloului și rearanjarea celor păstrate, prin deplasarea unora dintre acestea cu câte o poziție spre stânga, astfel încât să nu existe zone intermediare libere, ca în exemplu.
Scrieți un program C/C++ care citește de la tastatură numere naturale din intervalul [2,10^2], și anume n și elementele unui tablou bidimensional cu n linii și n coloane, reprezentând numerele de identificare ale instrumentelor, în ordinea plasării lor inițiale pe scenă. Programul modifică apoi tabloul în memorie corespunzător hotărârii dirijorului și afișează pe ecran tabloul obținut, fiecare linie a tabloului pe câte o linie a ecranului, elementele de pe aceeași linie fiind separate prin câte un spațiu.
Exemplu: pentru n=4 și tabloul
#include <iostream>
using namespace std;
int a[102][102];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> a[i][j];
// Fiecare linie își pierde elementul de pe diagonală, iar cele din dreapta
// lui se mută cu o poziție la stânga.
for (int i = 0; i < n; i++)
for (int j = i; j < n - 1; j++)
a[i][j] = a[i][j + 1];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n - 1; j++)
cout << a[i][j] << ' ';
cout << '\n';
}
return 0;
}Pe linia i, elementul de șters este chiar a[i][i]. Toate elementele din dreapta lui se mută cu o poziție la stânga, deci linia rămâne cu n-1 elemente; cele din stânga diagonalei nu se mișcă. La afișare se scriu primele n-1 elemente ale fiecărei linii.
Numim secvență progresivă a unui șir crescător de numere naturale un subșir al acestuia, format din termeni aflați pe poziții consecutive în șirul dat, cu proprietatea că fiecare termen apare în subșir de un număr de ori egal cu valoarea sa. Lungimea secvenței este egală cu numărul de termeni ai acesteia.
Fișierul bac.txt conține un șir crescător de cel mult 10^6 numere naturale din intervalul [1,10^6], astfel încât orice termen al șirului apare de un număr de ori cel mult egal cu valoarea sa. Numerele sunt separate prin câte un spațiu.
Se cere să se afișeze pe ecran lungimea maximă a unei secvențe progresive din șirul aflat în fișier. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă fișierul conține numerele 1 2 2 3 4 4 4 4 6 6 6 6 6 6 7 7 7 8 8 8 8 8 8 8 8 atunci pe ecran se afișează valoarea 10.
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.
Timp de executare: O(n) · Memorie: O(1)
Șirul din fișier este crescător, deci valorile egale stau una lângă alta. Se citește fișierul o singură dată, fără a-l memora, numărând câte apariții are valoarea curentă. Când se trece la o valoare nouă, grupul tocmai încheiat se verifică: dacă numărul de apariții este chiar valoarea lui, grupul e „bun" și lungimea lui se adaugă la secvența în curs; dacă nu, secvența se rupe și se pornește de la zero. Lungimea maximă întâlnită este răspunsul.
O secvență progresivă e formată numai din grupuri întregi și alăturate — un grup luat pe jumătate ar avea valoarea repetată de mai puține ori decât ea însăși — de aceea e de ajuns să fie verificate grupurile, în ordinea în care apar.
Se face o singură parcurgere, cu un număr de operații proporțional cu numărul de termeni, și se rețin doar câteva variabile: valoarea curentă, de câte ori a apărut, lungimea secvenței în curs și maximul. Memoria folosită nu crește cu lungimea șirului.
Numim secvență progresivă a unui șir crescător de numere naturale un subșir al acestuia, format din termeni aflați pe poziții consecutive în șirul dat, cu proprietatea că fiecare termen apare în subșir de un număr de ori egal cu valoarea sa. Lungimea secvenței este egală cu numărul de termeni ai acesteia.
Fișierul bac.txt conține un șir crescător de cel mult 10^6 numere naturale din intervalul [1,10^6], astfel încât orice termen al șirului apare de un număr de ori cel mult egal cu valoarea sa. Numerele sunt separate prin câte un spațiu.
Se cere să se afișeze pe ecran lungimea maximă a unei secvențe progresive din șirul aflat în fișier. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă fișierul conține numerele 1 2 2 3 4 4 4 4 6 6 6 6 6 6 7 7 7 8 8 8 8 8 8 8 8 atunci pe ecran se afișează valoarea 10.
Scrieți programul C/C++ corespunzător algoritmului proiectat.
#include <fstream>
#include <iostream>
using namespace std;
int main()
{
ifstream f("bac.txt");
int v, ant = 0, cate = 0, curent = 0, maxim = 0;
while (f >> v)
{
if (v == ant) cate = cate + 1;
else
{
if (ant != 0)
{
if (cate == ant)
{
curent = curent + cate;
if (curent > maxim) maxim = curent;
}
else curent = 0;
}
ant = v;
cate = 1;
}
}
// Ultimul grup din fișier nu are după el o valoare nouă care să îl închidă.
if (ant != 0)
{
if (cate == ant)
{
curent = curent + cate;
if (curent > maxim) maxim = curent;
}
}
f.close();
cout << maxim;
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