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 2024 trece prin tipuri de date, recursivitate, backtracking, structuri, grafuri orientate și arbori, factori primi, matrice, șiruri de caractere și fișiere. Este o variantă echilibrată, bună pentru recapitularea întregii materii.
Subiectul I (20p): 5 grile: o expresie cu împărțire reală, un subprogram recursiv care afișează 2 la coborâre și 4 la întoarcere, o problemă de backtracking cu patru persoane care plătesc 24 de lei, accesul la un element din tabloul puncte al unei structuri joc și numărul minim de piste cărora trebuie să le schimbi sensul ca un graf orientat să devină tare conex.
Subiectul al II-lea (40p): Un algoritm în pseudocod care adună divizorii primi distincți ai unui număr, nodurile cu un singur fiu dintr-un arbore dat prin vectorul de „tați” și o secvență care completează o matrice 5×5 cu dublul celui mai mic dintre indici.
Subiectul al III-lea (30p): Un subprogram cu cifre (Impare, care dublează fiecare cifră impară a unui număr), o problemă cu șiruri de caractere care completează cuvintele generice dintr-un șablon cu cuvinte de aceeași lungime și o problemă de eficiență care verifică dacă un șir citit din fișierul bac.in este „de tip api”.
6.3 este un număr real, deci 6.3/20 este 0.315, nu 0. Expresia valorează 24.315.x impar, cifra 4 se afișează după apelul recursiv, deci toate cifrele 4 apar la final, după 0. Rezultatul este 22220444.Indicați valoarea expresiei C/C++ alăturate.
6.3/20+24
Răspuns corect: c) 24.315
6.3 este un număr real, deci 6.3/20 dă 0.315, iar adunat cu 24 dă 24.315. 0 sau 24 ar ieși doar dacă împărțirea ar fi între numere întregi.
Subprogramul f este definit alăturat.
Indicați ce se afișează în urma apelului de mai jos.
f(2024);
void f(int x)
{ if(x>=24) if(x%2==0)
{ cout<<2; | printf("2");
f(x/2);
}
else
{ f(x/2);
cout<<4; | printf("4");
}
else cout<<0; | printf("0");
}Răspuns corect: b) 22220444
Pentru x≥24 par se afișează 2 înaintea apelului f(x/2), iar pentru x≥24 impar se afișează 4 după apel; sub 24 se afișează doar 0.
2024, 1012 și 506 sunt pare: 2, 2, 2. 253 este impar: întâi f(126), iar 4 abia la sfârșit. 126 este par: 2, apoi f(63). 63 și 31 sunt impare, deci își lasă 4-urile pentru după apeluri, iar f(15) afișează 0. La întoarcere se afișează 4 pentru 31, 4 pentru 63 și 4 pentru 253. Totul: 22220444.
Utilizând metoda backtracking se generează toate variantele prin care patru persoane pot plăti o consumație totală de 24 de lei în următoarele condiții:
• fiecare plătește o sumă nenulă, strict mai mică decât 10;
• primul plătește mai puțin decât al doilea, al doilea mai puțin decât al treilea, iar acesta mai puțin decât al patrulea.
O soluție constă în patru valori, reprezentând, în ordine, sumele plătite de fiecare dintre cele patru persoane. Primele patru soluții generate sunt, în această ordine:
Indicați soluția generată imediat după (3, 6, 7, 8).
Răspuns corect: b) (4, 5, 6, 9)
Soluțiile sunt generate în ordine lexicografică. După (3, 6, 7, 8) nu mai există nicio soluție care să înceapă cu 3: cu 3 și o valoare mai mare decât 6 pe poziția a doua, ultimele două valori, crescătoare și cel mult 9, nu mai pot completa suma de 24.
Prima valoare devine 4, iar cea mai mică a doua valoare este 5. Rămân 24 − 9 = 15 pentru ultimele două, crescătoare și cel mult 9: 6 și 9. Soluția este (4, 5, 6, 9). d) are două valori egale, deci nu respectă condiția.
În declararea de mai jos, câmpurile structurii memorează date referitoare la un joc video: categoria, numărul de niveluri de dificultate (maximum cinci) și numărul maxim de puncte care pot fi obținute la fiecare nivel.
Indicați expresia C/C++ care are valoarea 1 dacă și numai dacă numărul maxim de puncte care se pot obține pe nivelul notat cu 2 este strict mai mare decât 4.
struct joc
{ int categorie, nrNiveluri;
int puncte[5];
}g;Răspuns corect: d) g.puncte[2]>4
g este variabila, puncte este tabloul din ea, iar nivelul notat cu 2 este elementul cu indicele 2: g.puncte[2]>4. Celelalte variante scriu numele structurii, al variabilei și al câmpului în locuri greșite.
Într-un oraș sunt 5 parcuri, notate cu A, B, C, D și E, care sunt conectate prin piste pentru biciclete, pe care se circulă într-un singur sens, astfel: o pistă de la parcul A către parcul B, o pistă de la parcul B către parcul E, o pistă de la parcul C către parcul D, o pistă de la parcul D către parcul C, o pistă de la parcul E către parcul A, o pistă de la parcul E către parcul C și o pistă de la parcul E către parcul D.
Indicați numărul minim de piste pentru care trebuie schimbat sensul de circulație, astfel încât graful orientat obținut, în care parcurile reprezintă vârfurile, iar pistele reprezintă arcele, să fie tare conex.
Răspuns corect: a) 1
Parcurile A, B și E formează circuitul A→B→E→A, iar C și D circuitul C→D→C. Din E se ajunge la C și la D, dar din C sau D nu se poate ajunge înapoi.
Dacă pista E→C își schimbă sensul în C→E, din C se ajunge în E și de acolo peste tot, iar din E se ajunge în continuare la D și prin D la C. Graful devine tare conex cu o singură schimbare.
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 citește numărul 32625.
citește n (număr natural nenul) s←0; d←2 ┌cât timp d*d≤n execută │ p←0 │┌cât timp n%d=0 execută ││ n←[n/d]; p←1 │└■ │ s←s+d*p; d←d+1 └■ ┌dacă n≠1 atunci │ s←s+n └■ scrie s
Răspunsul din barem: 37
Algoritmul adună divizorii primi distincți ai lui n: fiecare d care îl divide pe n este adunat o singură dată (p devine 1), iar n se împarte la d de câte ori se poate. Ce rămâne la final, dacă nu e 1, este ultimul factor prim și se adună și el. 32625 = 3^2 · 5^3 · 29, deci suma este 3 + 5 + 29 = 37.
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,100] care pot fi citite pentru variabila n, astfel încât, pentru fiecare dintre acestea, în urma executării algoritmului, să se afișeze valoarea 2.
Exemplu: 16 32
Se afișează 2 exact când singurul divizor prim al lui n este 2, adică n este o putere a lui 2. În intervalul [10,100] acestea sunt 16, 32 și 64.
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, s = 0, d = 2, p;
cin >> n;
while (d * d <= n)
{
p = 0;
while (n % d == 0)
{
n = n / d;
p = 1;
}
s = s + d * p;
d = d + 1;
}
if (n != 1) s = s + n;
cout << s;
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 adecvat a doua structură cât timp...execută cu o structură repetitivă cu test final.
citește n (număr natural nenul) s←0; d←2 ┌cât timp d*d≤n execută │ p←0 │┌dacă n%d=0 atunci ││┌repetă │││ n←[n/d]; p←1 ││└până când n%d≠0 │└■ │ s←s+d*p; d←d+1 └■ ┌dacă n≠1 atunci │ s←s+n └■ scrie s
repetă…până când execută corpul cel puțin o dată, iar cât timp poate să nu îl execute deloc: dacă d nu îl divide pe n, bucla dată nu se execută, iar p rămâne 0. De aceea structura cu test final este pusă sub condiția n%d=0. Condiția de oprire este negația celei de continuare: n%d≠0.
Un arbore cu 10 noduri, numerotate de la 1 la 10, este reprezentat prin vectorul de „tați” (8,1,4,5,0,9,4,5,4,3). Enumerați toate nodurile arborelui care au câte un singur descendent direct („fiu”).
Răspunsul din barem: 1, 3, 8, 9
În vectorul de tați, poziția i spune tatăl nodului i, deci fiii unui nod sunt pozițiile pe care apare el ca valoare. 8 apare o dată (fiul 1), 1 o dată (fiul 2), 4 de trei ori (fiii 3, 7, 9), 5 de două ori (fiii 4 și 8), 9 o dată (fiul 6), 3 o dată (fiul 10). Nodurile cu un singur fiu sunt 1, 3, 8 și 9; ordinea în care se enumeră nu contează.
Variabilele i și j sunt de tip întreg, iar variabila a memorează un tablou bidimensional cu 5 linii și 5 coloane, numerotate începând de la 0, având inițial toate elementele egale cu 1.
Scrieți secvența de instrucțiuni C/C++ de mai jos, înlocuind punctele de suspensie cu instrucțiuni adecvate, dintre care cel mult patru de atribuire, astfel încât, în urma executării secvenței obținute, variabila a să memoreze tabloul alăturat.
for(i=0;i<5;i++)
for(j=0;j<5;j++)
..................| 0 | 0 | 0 | 0 | 0 |
| 0 | 2 | 2 | 2 | 2 |
| 0 | 2 | 4 | 4 | 4 |
| 0 | 2 | 4 | 6 | 6 |
| 0 | 2 | 4 | 6 | 8 |
for(i=0;i<5;i++)
for(j=0;j<5;j++)
if(i<j) a[i][j]=2*i;
else a[i][j]=2*j;Fiecare element este dublul celui mai mic dintre indicii lui: pe linia 0 și pe coloana 0 sunt valori 0, pe linia 1 începând cu coloana 1 sunt valori 2 și așa mai departe. Sunt două atribuiri, sub limita de patru.
Subprogramul Impare are un parametru, n, prin care primește un număr natural (n∈[1,10^4]). Subprogramul returnează numărul obținut prin duplicarea fiecărei cifre impare a lui n sau -1 dacă acesta nu are nicio cifră impară.
Scrieți definiția completă a subprogramului.
Exemplu: dacă n=3361, subprogramul returnează 3333611.
int Impare(int n)
{
int r = 0, p = 1, c, gasit = 0;
while (n > 0)
{
c = n % 10;
r = r + c * p;
p = p * 10;
if (c % 2 == 1)
{
r = r + c * p;
p = p * 10;
gasit = 1;
}
n = n / 10;
}
if (gasit == 0) return -1;
return r;
}Cifrele se iau de la dreapta și se pun într-un număr nou r, fiecare pe poziția ei (p este puterea lui 10 a poziției). O cifră impară se pune de două ori, pe două poziții consecutive. Zerourile se pun și ele, deci rămân la locul lor. Dacă nu s-a găsit nicio cifră impară, se returnează -1.
Un șablon este un text în care cuvintele sunt separate prin câte un spațiu și sunt formate fie numai din litere mici și mari ale alfabetului englez, fie numai din caractere *, în ultimul caz numindu-se cuvinte generice. Lungimea unui cuvânt este egală cu numărul de caractere care îl compun.
Un computer generează o frază pe baza unui astfel de șablon, prin înlocuirea fiecărui cuvânt generic cu unul dintre cuvintele de aceeași lungime, preluat dintr-o listă dată.
Scrieți un program C/C++ care citește de la tastatură un număr natural, n (n∈[1,100]), și o listă de n cuvinte, urmată de un șablon de tipul precizat. Fiecare cuvânt din listă este format din maximum 10 litere mici și mari ale alfabetului englez și la citire este introdus singur pe linie. Șablonul conține maximum 100 de caractere. Programul obține în memorie și apoi afișează pe ecran una dintre frazele care pot fi generate pe baza șablonului și a listei citite sau mesajul imposibil dacă nu se poate genera o astfel de frază.
Exemplu: dacă n=6, iar lista de cuvinte este rece, placuta, acasa, calduta, innorata, soare, pentru șablonul de pe primul rând din imagine se poate genera fraza de pe al doilea rând sau cea de pe al treilea rând (și altele), iar pentru șablonul de pe ultimul rând se afișează mesajul imposibil, pentru că în listă nu există cuvinte de 3 sau de 11 litere.
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
char lista[100][11], sablon[101], fraza[1101] = "", *p;
int n, i, gasit, posibil = 1;
cin >> n;
for (i = 0; i < n; i++) cin >> lista[i];
cin.get();
cin.getline(sablon, 101);
p = strtok(sablon, " ");
while (p != NULL && posibil == 1)
{
if (fraza[0] != '\0') strcat(fraza, " ");
if (p[0] == '*')
{
gasit = -1;
for (i = 0; i < n && gasit == -1; i++)
if (strlen(lista[i]) == strlen(p)) gasit = i;
if (gasit == -1) posibil = 0;
else strcat(fraza, lista[gasit]);
}
else strcat(fraza, p);
p = strtok(NULL, " ");
}
if (posibil == 1) cout << fraza;
else cout << "imposibil";
return 0;
}Cuvintele din listă se citesc fiecare într-un rând al tabloului lista, apoi cin.get() consumă sfârșitul de rând, ca șablonul să fie citit întreg. Fraza se construiește cuvânt cu cuvânt: un cuvânt obișnuit se copiază, iar un cuvânt generic (format din *) se înlocuiește cu primul cuvânt din listă care are aceeași lungime. Dacă pentru un cuvânt generic nu există niciunul, fraza nu se poate genera și se afișează imposibil. Când în listă sunt mai multe cuvinte de aceeași lungime, oricare este corect; programul îl alege pe primul.
Un șir se numește de tip api dacă numărul de apariții ale fiecărui termen este mai mic sau egal cu acel termen și are o paritate egală cu a acestuia.
Fișierul bac.in conține un șir de cel mult 10^6 numere naturale din intervalul [1,10^3], separate prin câte un spațiu. Se cere să se afișeze pe ecran mesajul DA, dacă șirul este de tip api, 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 6 27 2 6 27 6 6 14 14 2 27 se afișează pe ecran DA (termenul par 6 apare de 4 ori, 4 fiind tot număr par și 4≤6, termenii pari 2 și 14 apar de câte 2 ori, 2 fiind tot număr par și 2≤2, respectiv 2≤14, iar termenul impar 27 apare de 3 ori, 3 fiind tot număr impar și 3≤27).
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.
Timp de executare: O(n) · Memorie: O(1)
Termenii sunt între 1 și 1000, deci se poate număra câte apariții are fiecare valoare, într-un vector de apariții ap, pe măsura citirii, fără să se memoreze șirul.
După citire se parcurg valorile de la 1 la 1000. Pentru fiecare valoare i care a apărut (ap[i] ≠ 0) se verifică cele două condiții: numărul de apariții nu depășește valoarea (ap[i] ≤ i) și are aceeași paritate cu ea (ap[i]%2 = i%2). Dacă o valoare nu le respectă, șirul nu este de tip api. La final se afișează DA sau NU.
Eficiență: fiecare număr din fișier se prelucrează o singură dată, în timp constant, iar vectorul de apariții are un număr fix de elemente, deci timpul este liniar în numărul de valori citite.
Un șir se numește de tip api dacă numărul de apariții ale fiecărui termen este mai mic sau egal cu acel termen și are o paritate egală cu a acestuia.
Fișierul bac.in conține un șir de cel mult 10^6 numere naturale din intervalul [1,10^3], separate prin câte un spațiu. Se cere să se afișeze pe ecran mesajul DA, dacă șirul este de tip api, 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 6 27 2 6 27 6 6 14 14 2 27 se afișează pe ecran DA (termenul par 6 apare de 4 ori, 4 fiind tot număr par și 4≤6, termenii pari 2 și 14 apar de câte 2 ori, 2 fiind tot număr par și 2≤2, respectiv 2≤14, iar termenul impar 27 apare de 3 ori, 3 fiind tot număr impar și 3≤27).
Scrieți programul C/C++ corespunzător algoritmului proiectat.
#include <fstream>
#include <iostream>
using namespace std;
int main()
{
ifstream fin("bac.in");
int ap[1001] = {0}, x, i, ok = 1;
while (fin >> x) ap[x]++;
fin.close();
for (i = 1; i <= 1000; i++)
if (ap[i] != 0 && (ap[i] > i || ap[i] % 2 != i % 2))
ok = 0;
if (ok == 1) cout << "DA";
else cout << "NU";
return 0;
}Programul face pașii de la 3.a. Condiția ap[i] != 0 face ca valorile care nu apar deloc să nu fie verificate.
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