Lucrarea „2025 Varianta 1” de la Bacalaureatul la informatică, specializarea Mate-Info, limbajul C/C++: 3 subiecte, 90 de puncte și 3 ore de lucru la examen. Sub fiecare exercițiu ai răspunsul și explicația, închise până le deschizi, ca să încerci întâi singur.
Enunțurile sunt cele oficiale, publicate de Ministerul Educației pe subiecte.edu.ro. Răspunsurile și explicațiile sunt scrise de subac.
Indicați expresia C/C++ cu aceeași valoare ca a expresiei alăturate.
2025%2019+6
Răspuns corect: d) 2025%2021+8
2025%2019 este restul împărțirii lui 2025 la 2019, adică 6, deci expresia dată valorează 6 + 6 = 12.
Variantele: a) 2025/2020+5 = 1 + 5 = 6; b) 2025/2021+8 = 1 + 8 = 9; c) 2025%2020+5 = 5 + 5 = 10; d) 2025%2021+8 = 4 + 8 = 12. Doar d) are aceeași valoare.
Subprogramul f este definit alăturat.
Indicați ce se afișează în urma apelului de mai jos.
f(3);
void f(int n)
{ int i;
for(i=1;i<=n;i++)if(i%2==0){ cout<<i; | printf("%d",i);
f(i-1);
}
else { f(i-1);
cout<<i; | printf("%d",i);
}
}Răspuns corect: a) 1211213
f(0) nu afișează nimic. Pentru fiecare i de la 1 la n: dacă i e par, se afișează i și apoi se apelează f(i-1); dacă e impar, întâi se apelează f(i-1) și abia apoi se afișează i.
f(1) afișează 1. f(2) afișează 1 (pentru i=1), apoi 2 și f(1), adică 121. f(3) afișează 1 (i=1), apoi 2 urmat de f(1), adică 21 (i=2), apoi f(2), adică 121, urmat de 3 (i=3). Totul: 1 21 1213, adică 1211213.
Indicați o declarare a unui tablou bidimensional m, care poate memora maximum 100 de numere reale.
Răspuns corect: b) float m[4][25];
Un tablou bidimensional se declară cu câte o pereche de paranteze drepte pentru fiecare dimensiune, iar numerele reale se memorează în tipul float. float m[4][25]; are 4·25 = 100 de elemente.
a) scrie dimensiunile cu virgulă, ceea ce nu este valid în C/C++; c) nu este o declarare validă; d) declară un tablou unidimensional de numere întregi.
Utilizând metoda backtracking, s-au generat toate codurile posibile pentru deblocarea unor telefoane, coduri de câte 6 cifre distincte, din mulțimea cifrelor, ordonată crescător. Fiecare cod are primele trei cifre impare și ultimele trei cifre pare. Primele patru coduri sunt:
Indicați penultimul cod generat.
Răspuns corect: c) 975862
Codurile se generează în ordine crescătoare, deci ultimul este cel mai mare: primele trei cifre, impare, cât mai mari, 9, 7, 5, iar ultimele trei, pare, 8, 6, 4 — 975864.
Chiar înaintea lui, se schimbă doar ultima cifră, cu cea mai mare cifră pară mai mică decât 4 și nefolosită: 2. Penultimul cod este 975862.
Un graf orientat fără circuite are 10 vârfuri.
Indicați numărul maxim de arce ale grafului.
Răspuns corect: b) 45
Într-un graf orientat fără circuite vârfurile se pot așeza în ordine, astfel încât fiecare arc să meargă de la un vârf la unul aflat după el. Între două vârfuri poate exista deci cel mult un arc, într-un singur sens, iar cu toate perechile folosite se obțin 10·9/2 = 45 de arce.
90 ar însemna arce în ambele sensuri între oricare două vârfuri, deci circuite.
Algoritmul alăturat este reprezentat în pseudocod.
Scrieți ce se afișează în urma executării algoritmului dacă se citesc, în această ordine, numerele 7 și 17.
citește m,n (numere naturale nenule, m≤n) nr←0;i←m ┌repetă │ x←1 │┌cât timp x*x<i execută ││ x←x+1 │└■ │┌dacă x*x=i atunci nr←i ││altfel i←i+1 │└■ └până când i>n sau nr≠0 scrie nr
Răspunsul din barem: 9
9 Pentru fiecare i, începând de la m, bucla cât timp găsește cel mai mic x cu x*x ≥ i. Dacă x*x este chiar i, i este pătrat perfect și se reține în nr; altfel se trece la i+1. Algoritmul afișează deci primul pătrat perfect din intervalul [m,n] sau 0, dacă nu există. Pentru 7 și 17, primul pătrat perfect de la 7 încolo este 9.
Algoritmul alăturat este reprezentat în pseudocod.
Dacă pentru variabila n se citește valoarea 25, scrieți două numere distincte care pot fi citite pentru variabila m, astfel încât, în urma executării algoritmului, pentru fiecare dintre acestea, să se afișeze valoarea 25.
citește m,n (numere naturale nenule, m≤n) nr←0;i←m ┌repetă │ x←1 │┌cât timp x*x<i execută ││ x←x+1 │└■ │┌dacă x*x=i atunci nr←i ││altfel i←i+1 │└■ └până când i>n sau nr≠0 scrie nr
Exemplu: 17 și 25 Se afișează primul pătrat perfect de la m până la 25. Ca acesta să fie chiar 25, între m și 24 nu trebuie să existe niciun pătrat perfect; cel dinaintea lui 25 este 16, deci m poate fi orice număr din intervalul [17,25].
Algoritmul alăturat este reprezentat în pseudocod.
Scrieți programul C/C++ corespunzător algoritmului dat.
citește m,n (numere naturale nenule, m≤n) nr←0;i←m ┌repetă │ x←1 │┌cât timp x*x<i execută ││ x←x+1 │└■ │┌dacă x*x=i atunci nr←i ││altfel i←i+1 │└■ └până când i>n sau nr≠0 scrie nr
#include <iostream>
using namespace std;
int main()
{
int m, n, nr = 0, i, x;
cin >> m >> n;
i = m;
do
{
x = 1;
while (x * x < i) x = x + 1;
if (x * x == i) nr = i;
else i = i + 1;
} while (i <= n && nr == 0);
cout << nr;
return 0;
}
repetă…până când i>n sau nr≠0 devine do…while cu condiția de continuare, negata celei de oprire: i <= n && nr == 0 (negata lui „sau” este „și” între condițiile negate).Algoritmul alăturat este reprezentat în pseudocod.
Scrieți în pseudocod un algoritm echivalent cu cel dat, înlocuind structura cât timp...execută cu o structură repetitivă cu test final.
citește m,n (numere naturale nenule, m≤n) nr←0;i←m ┌repetă │ x←1 │┌cât timp x*x<i execută ││ x←x+1 │└■ │┌dacă x*x=i atunci nr←i ││altfel i←i+1 │└■ └până când i>n sau nr≠0 scrie nr
citește m,n (numere naturale nenule, m≤n) nr←0; i←m ┌repetă │ x←1 │┌dacă x*x<i atunci ││┌repetă │││ x←x+1 ││└până când x*x≥i │└■ │┌dacă x*x=i atunci nr←i ││altfel i←i+1 │└■ └până când i>n sau nr≠0 scrie nr repetă…până când execută corpul cel puțin o dată, iar cât timp poate să nu îl execute deloc: pentru i=1, x←1 are deja x*x ≥ i și x nu trebuie să crească. De aceea structura cu test final este pusă sub condiția x*x<i. Condiția de oprire este negata celei de continuare: x*x≥i.
Un graf neorientat cu 6 noduri, numerotate de la 1 la 6, este reprezentat prin listele de adiacență alăturate.
Scrieți mulțimea nodurilor și mulțimea muchiilor unui subgraf al acestuia, fără noduri izolate, care să fie graf eulerian.
1: 2, 3, 4, 6 2: 1, 3, 5 3: 1, 2, 5 4: 1, 5, 6 5: 2, 3, 4, 6 6: 1, 4, 5
Exemplu: nodurile {1, 2, 3} și muchiile {[1,2], [1,3], [2,3]}
Din listele de adiacență, muchiile grafului sunt [1,2], [1,3], [1,4], [1,6], [2,3], [2,5], [3,5], [4,5], [4,6] și [5,6]. Un subgraf păstrează un grup de noduri și toate muchiile dintre ele. Ca să fie eulerian, trebuie să fie conex și să aibă toate gradele pare.
Nodurile 1, 2 și 3 sunt legate două câte două: subgraful lor este un ciclu cu trei muchii, fiecare nod are gradul 2 și niciun nod nu e izolat. Merge la fel, de exemplu, și subgraful cu nodurile 1, 4 și 6.Variabila p memorează simultan, pentru un tip de prăjitură, codul (un număr natural de două cifre), prețul (număr real) și un set de trei numere naturale din intervalul [1,102], reprezentând informații specifice, în această ordine: tipul glazurii, tipul cremei principale și numărul de blaturi.
Știind că expresiile C/C++ de mai jos au ca valori codul, prețul, respectiv tipul glazurii pentru o prăjitură, scrieți definiția unei structuri cu eticheta prajitura, care permite memorarea datelor despre o prăjitură, și declarați corespunzător variabila p.
p.cod p.pret p.informatii[0]
struct prajitura
{ int cod;
float pret;
int informatii[3];
} p;
Expresiile din enunț spun exact ce câmpuri trebuie să existe: p.cod este un întreg, p.pret un număr real, iar p.informatii[0] arată că informatii este un tablou, cu cele trei numere naturale (glazura, crema și numărul de blaturi).Numărul natural an este ascendent al numărului natural n, dacă oricare dintre cifrele lui an este mai mare sau egală cu cifra unităților lui n.
Exemplu: oricare dintre numerele 7, 9, 98 sau 7998 este ascendent al lui 827, dar numărul 857 nu este ascendent al lui 827.
Subprogramul ascendent are trei parametri:
• n, prin care primește un număr natural (n∈[0,103));
• x și y, prin care primește câte un număr natural din intervalul [0,103) (x<y).
Subprogramul returnează suma ascendenților lui n din intervalul [x,y], sau valoarea 0, dacă nu există niciun astfel de ascendent.
Scrieți definiția completă a subprogramului C/C++.
Exemplu: dacă n=827, x=9, y=800, subprogramul returnează 7893 (9+77+78+79+87+88+89+ 97+98+99+777+778+779+787+788+789+797+798+799=7893).
int ascendent(int n, int x, int y)
{
int u = n % 10, s = 0, k, t, ok;
for (k = x; k <= y; k++)
{
t = k;
ok = 1;
do
{
if (t % 10 < u) ok = 0;
t = t / 10;
} while (t != 0);
if (ok == 1) s = s + k;
}
return s;
}
u este cifra unităților lui n. Pentru fiecare k din intervalul [x,y] se verifică toate cifrele lui k: dacă una este mai mică decât u, k nu este ascendent. Ascendenții se adună în s, care rămâne 0 dacă nu există niciunul.
Structura do…while verifică și numărul 0, care are o singură cifră, 0.Un cuvânt semioglindit se obține dintr-un cuvânt cu 2·k (k∈[1,102]) litere, prin interschimbarea în acesta a secvenței formate din primele k litere cu secvența formată din ultimele k litere.
Exemplu: din cuvântul platim se obține cuvântul semioglindit timpla.
Într-un text de cel mult 200 de caractere, cuvintele sunt formate din litere mici ale alfabetului englez și sunt separate prin câte un spațiu.
Scrieți un program C/C++ care citește de la tastatură un text de tipul precizat, pe care îl transformă în memorie, prin înlocuirea fiecărui cuvânt cu număr par de litere, cu cel semioglindit obținut din acesta, ca în exemplu. Programul afișează pe ecran textul obținut, sau mesajul nu exista, dacă toate cuvintele au număr impar de litere.
Exemplu: pentru textul am facut fotografii unei flori mari se afișează pe ecran textul ma facut rafiifotog eiun flori rima
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
char s[201], c;
int i = 0, j, k, p, gasit = 0;
cin.getline(s, 201);
while (s[i] != '\0')
{
j = i;
while (s[j] != ' ' && s[j] != '\0') j++;
if ((j - i) % 2 == 0)
{
gasit = 1;
k = (j - i) / 2;
for (p = 0; p < k; p++)
{
c = s[i + p];
s[i + p] = s[i + k + p];
s[i + k + p] = c;
}
}
i = j;
if (s[i] == ' ') i++;
}
if (gasit == 1) cout << s;
else cout << "nu exista";
return 0;
}
Textul se parcurge cuvânt cu cuvânt: i este începutul cuvântului, j poziția de după el, deci cuvântul are j-i litere. Pentru un cuvânt cu număr par de litere, 2·k, se interschimbă litera de pe poziția i+p cu cea de pe poziția i+k+p, pentru p de la 0 la k-1: prima jumătate ajunge în locul celei de-a doua și invers, direct în șirul citit.
Variabila gasit ține minte dacă s-a transformat vreun cuvânt; dacă toate au număr impar de litere, se afișează nu exista.Un tânăr pasionat de călătorii are o listă cu muzee virtuale și, pentru fiecare, câte un singur interval orar, în care acesta poate fi vizitat online, gratuit. Tânărul dispune zilnic de același interval orar pentru vizite; un muzeu este convenabil dacă poate fi vizitat online gratuit în timpul disponibil și dacă pentru vizită îi poate aloca cel puțin o oră. Muzeele din listă sunt numerotate cu valori naturale consecutive, începând cu 1, și cel puțin unul este convenabil.
Fișierul text bac.in conține cel mult 105 linii, iar pe fiecare linie câte o pereche de numere, reprezentând limitele câte unui interval orar: pe prima linie intervalul orar de care tânărul dispune zilnic, iar pe fiecare dintre următoarele linii, intervalul orar de vizitare gratuită pentru câte un muzeu, în ordinea din listă. Limitele intervalelor sunt ore fixe, numere naturale din intervalul [8,22], iar cele aflate pe aceeași linie a fișierului sunt în ordine strict crescătoare și sunt separate printr-un spațiu.
Se cere să se afișeze pe ecran, separate printr-un spațiu, două valori, reprezentând numărul de muzee convenabile, respectiv numărul de ordine al ultimului astfel de muzeu din lista tânărului.
Utilizați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă fișierul conține valorile alăturate, atunci pe ecran se afișează numerele 3 4.
| 16 | 19 |
| 15 | 18 |
| 17 | 21 |
| 19 | 21 |
| 18 | 20 |
| 12 | 13 |
(pot fi vizitate trei muzee cu numerele de ordine 1, 2 și 4, în intervalele 16-18, 17-19, respectiv 18-19).
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.
Datele se prelucrează pe măsura citirii, fără să fie memorate. Se citește întâi intervalul disponibil al tânărului, [h1,h2]. Apoi, pentru fiecare muzeu, se numără al câtelea este și se citește intervalul lui, [a,b]. Timpul în care muzeul poate fi vizitat este intersecția celor două intervale: de la v1 = max(h1,a) până la v2 = min(h2,b). Muzeul este convenabil dacă intersecția are cel puțin o oră, adică v1 < v2 (orele sunt fixe). Atunci se crește numărul de muzee convenabile și se reține numărul de ordine al muzeului curent ca ultimul convenabil. La final se afișează cele două valori. Eficiență: fiecare interval se citește și se prelucrează o singură dată, în timp constant, deci algoritmul este liniar în numărul de linii din fișier. Se folosesc doar câteva variabile simple, fără tablou, deci memoria folosită este constantă.
Un tânăr pasionat de călătorii are o listă cu muzee virtuale și, pentru fiecare, câte un singur interval orar, în care acesta poate fi vizitat online, gratuit. Tânărul dispune zilnic de același interval orar pentru vizite; un muzeu este convenabil dacă poate fi vizitat online gratuit în timpul disponibil și dacă pentru vizită îi poate aloca cel puțin o oră. Muzeele din listă sunt numerotate cu valori naturale consecutive, începând cu 1, și cel puțin unul este convenabil.
Fișierul text bac.in conține cel mult 105 linii, iar pe fiecare linie câte o pereche de numere, reprezentând limitele câte unui interval orar: pe prima linie intervalul orar de care tânărul dispune zilnic, iar pe fiecare dintre următoarele linii, intervalul orar de vizitare gratuită pentru câte un muzeu, în ordinea din listă. Limitele intervalelor sunt ore fixe, numere naturale din intervalul [8,22], iar cele aflate pe aceeași linie a fișierului sunt în ordine strict crescătoare și sunt separate printr-un spațiu.
Se cere să se afișeze pe ecran, separate printr-un spațiu, două valori, reprezentând numărul de muzee convenabile, respectiv numărul de ordine al ultimului astfel de muzeu din lista tânărului.
Utilizați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă fișierul conține valorile alăturate, atunci pe ecran se afișează numerele 3 4.
| 16 | 19 |
| 15 | 18 |
| 17 | 21 |
| 19 | 21 |
| 18 | 20 |
| 12 | 13 |
(pot fi vizitate trei muzee cu numerele de ordine 1, 2 și 4, în intervalele 16-18, 17-19, respectiv 18-19).
Scrieți programul C/C++ corespunzător algoritmului proiectat.
#include <fstream>
#include <iostream>
using namespace std;
int main()
{
ifstream fin("bac.in");
int h1, h2, a, b, v1, v2, nr = 0, crt = 0, ultim = 0;
fin >> h1 >> h2;
while (fin >> a >> b)
{
crt++;
if (a > h1) v1 = a;
else v1 = h1;
if (b < h2) v2 = b;
else v2 = h2;
if (v1 < v2)
{
nr++;
ultim = crt;
}
}
fin.close();
cout << nr << ' ' << ultim;
return 0;
}
Programul face pașii de la 3.a. Intersecția se calculează fără funcții din biblioteci: v1 este cel mai mare dintre începuturi, v2 cel mai mic dintre sfârșituri. Enunțul garantează cel puțin un muzeu convenabil, deci ultim primește sigur o valoare.Vrei să vezi cât ai lua?
În test ai cronometrul de la examen, codul tău se compilează pe loc, iar la final primești nota.
Rezolv-o cu timpul de la examen