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 2024 trece prin expresii logice, recursivitate, backtracking, structuri imbricate, grafuri orientate și neorientate, șiruri de caractere, cifre, matrice și fișiere. Este o variantă echilibrată, bună pentru exersat atenția la detalii.
Subiectul I (20p): 5 grile: o expresie echivalentă cu !(x>25 || y<6), un subprogram recursiv care modifică parametrul înainte de afișare, o problemă de backtracking cu numere de mașină, accesul la anul dintr-o structură telefon cu un câmp achizitionare care este tot o structură și lungimea maximă a unui drum elementar într-un graf orientat cu 5 vârfuri.
Subiectul al II-lea (40p): Un algoritm în pseudocod care afișează partea impară a fiecărui număr par de la 1 la n, listele de adiacență ale unui graf parțial conex și fără cicluri și o secvență care verifică dacă printre 10 cuvinte citite există unul de două litere, cu o vocală și o consoană.
Subiectul al III-lea (30p): Un subprogram cu cifre (fulg, care verifică o aglomerare de nouă cristale de patru tipuri), o problemă cu o matrice în care fiecare element este cea mai mică valoare obținută prin alipirea numerelor liniei și coloanei și o problemă de eficiență cu cea mai mare cifră din numerele fișierului numere.in.
!(x>25 || y<6) devine x<=25 && y>=6.x*5/2 se calculează între numere întregi: 9 devine 22, iar 22 devine 55. Afișarea vine după apel, deci ordinea este 545522.38 38. Dacă un singur număr conține cifra maximă, se afișează nu exista.Variabilele x și y sunt de tip real.
Indicați o expresie C/C++ echivalentă cu cea alăturată.
!(x>25 || y<6)
Răspuns corect: a) x<=25 && y>=6
Negația unei disjuncții este conjuncția negațiilor: !(x>25 || y<6) este !(x>25) && !(y<6), adică x<=25 && y>=6.
b) și d) folosesc || în loc de &&, iar c) nu neagă a doua condiție.
Subprogramul f este definit alăturat.
Indicați ce se afișează în urma apelului de mai jos.
f(9);
void f(int x)
{ if(x%5!=0)
{ x=x*5/2; f(x);}
else x=x-1;
cout<<x; | printf("%d",x);
}Răspuns corect: b) 545522
f(9): 9 nu se divide cu 5, deci x devine 9*5/2 = 22 și se apelează f(22); afișarea lui x vine după apel. f(22): x devine 22*5/2 = 55 și se apelează f(55). f(55): 55 se divide cu 5, deci x devine 54 și se afișează 54.
Revenind din apeluri, f(22) afișează 55, iar f(9) afișează 22. Pe ecran apare 545522.
Utilizând metoda backtracking, se generează, respectând ordinea enumerării elementelor din mulțimile precizate mai jos, toate numerele de mașină care cuprind câte trei elemente constitutive, separate prin cratimă:
• indicativul județului, din mulțimea {B, BR, HD, MM, SV, TL};
• un număr, format din două cifre din mulțimea {2, 4, 6, 8}, în ordine strict crescătoare;
• trei litere mari distincte din mulțimea {A, B, C}, cea din mijloc fiind A.
Primele șapte numere generate sunt, în această ordine:
Indicați două soluții, prima generată imediat înainte de soluția SV-68-CAB, iar a doua generată imediat după soluția SV-68-CAB.
Răspuns corect: d) SV-68-BAC, TL-24-BAC
Numerele se generează ca un contor cu trei poziții — indicativul, numărul, literele — fiecare în ordinea din mulțimea lui. Cu litere distincte din {A, B, C} și A la mijloc, există doar două variante, BAC și CAB, iar cel mai mare număr este 68.
Înainte de SV-68-CAB se schimbă doar literele: SV-68-BAC. După el, numărul și literele sunt deja la ultima variantă, deci se trece la indicativul următor, TL, cu primul număr și primele litere: TL-24-BAC.
Variabila t, declarată alăturat, memorează, pentru un telefon, următoarele date: tipul sistemului de operare (litera A pentru Android și litera W pentru Windows), prețul produsului, precum și data achiziționării (ziua, luna și anul).
Indicați o expresie C/C++ prin care se accesează anul achiziționării telefonului.
struct data
{ int zi,luna,an;
};
struct telefon
{ char sistem;
float pret;
struct data achizitionare;
} t;Răspuns corect: d) t.achizitionare.an
t este variabila, achizitionare este câmpul ei de tip data, iar anul este câmpul an al acestui câmp: t.achizitionare.an.
a) și c) folosesc numele tipului, telefon, în locul variabilei, iar b) folosește numele tipului data în locul câmpului achizitionare.
Oricare dintre cele 5 vârfuri ale unui graf orientat are proprietatea că suma dintre gradul său extern și gradul său intern este 4.
Indicați lungimea maximă a unui drum elementar în acest graf.
Răspuns corect: c) 4
Un drum elementar trece prin vârfuri distincte, deci într-un graf cu 5 vârfuri are cel mult 4 arce: 8 sau 10 ar cere vârfuri repetate.
Lungimea 4 se poate atinge. De exemplu, cu arcele (1,2), (2,3), (3,4), (4,5), (1,3), (1,4), (1,5), (2,4), (2,5) și (3,5), fiecare vârf are suma gradelor extern și intern egală cu 4, iar drumul 1, 2, 3, 4, 5 are lungimea 4.
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ă dacă se citește numărul 10.
citește n (număr natural, n≥2) i←1 ┌cât timp i≤n execută │ m←i │┌cât timp m%2=0 execută ││ m←[m/2] │└■ │┌dacă m≠i atunci ││ scrie m,' ' │└■ │ i←i+1 └■
Răspunsul din barem: 1 1 3 1 5
Pentru fiecare i de la 1 la n, m pornește de la i și se împarte la 2 cât timp este par; rămâne partea impară a lui i. Dacă m diferă de i (adică i era par), m se afișează. Pentru n=10 se afișează numerele pentru i = 2, 4, 6, 8, 10: 1, 1, 3, 1, 5.
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ă valori distincte care pot fi citite astfel încât, în urma executării algoritmului, pentru fiecare dintre acestea, numărul de valori egale cu 1 afișate să fie 4.
Exemplu: 16 31
Valoarea 1 se afișează exact pentru puterile lui 2 (în afară de 1, pentru care m = i): 2, 4, 8, 16, 32, … Ca să apară de patru ori, printre numerele de la 1 la n trebuie să fie 2, 4, 8 și 16, dar nu și 32, deci n poate fi orice număr din intervalul [16,31].
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 = 1, m;
cin >> n;
while (i <= n)
{
m = i;
while (m % 2 == 0) m = m / 2;
if (m != i) cout << m << ' ';
i = i + 1;
}
return 0;
}Cele două structuri cât timp devin while, iar [m/2] 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 prima structură repetitivă cât timp...execută cu o structură de tip pentru...execută.
citește n (număr natural, n≥2) ┌pentru i←1,n execută │ m←i │┌cât timp m%2=0 execută ││ m←[m/2] │└■ │┌dacă m≠i atunci ││ scrie m,' ' │└■ └■
Structura pentru își gestionează singură contorul: valoarea inițială i←1 și valoarea finală n se scriu în antet, iar i←i+1 dispare din corp, pentru că se face automat la fiecare pas.
Un graf neorientat cu 6 noduri, numerotate de la 1 la 6, are muchiile:
Scrieți listele de adiacență ale unui graf parțial al său care să fie conex și fără cicluri.
Exemplu: 1: 2 2: 1, 3, 4, 5 3: 2 4: 2, 6 5: 2 6: 4
Un graf parțial păstrează toate nodurile și o parte dintre muchii. Ca să fie conex și fără cicluri (un arbore cu 6 noduri), trebuie să rămână exact 5 muchii, fără niciun ciclu. Graful dat are ciclurile 2-4-5 și 4-5-6; eliminând muchiile [4,5] și [5,6], rămân [1,2], [2,3], [2,4], [2,5] și [4,6], care leagă toate nodurile fără cicluri. Sunt și alte variante corecte, de exemplu eliminând [2,5] și [4,6].
Variabilele c și i sunt de tip întreg, iar variabila s permite memorarea unui șir de cel mult 20 de caractere. Se citesc de la tastatură 10 cuvinte, formate din litere mici ale alfabetului englez și separate prin Enter.
Scrieți secvența de mai jos, înlocuind punctele de suspensie astfel încât, în urma executării secvenței obținute, variabila c să memoreze valoarea 1 dacă există printre cuvintele citite cel puțin unul format din două litere și care să conțină o vocală și o consoană, sau valoarea 0 altfel. Se consideră vocale literele a, e, i, o, u.
Exemplu: dacă se citesc cuvintele daca, au, plecat, el, nu, primeste, si, inghetata, de, fragi, variabila c are valoarea 1.
c=.....;
for(i=1;i<=10;i++) { cin>>s; | scanf("%s",s);
............
}c=0;
for(i=1;i<=10;i++) { cin>>s;
if(strlen(s)==2 && (strchr("aeiou",s[0])!=NULL) != (strchr("aeiou",s[1])!=NULL)) c=1;
}c pornește de la 0 și devine 1 când se găsește un cuvânt potrivit. Un cuvânt de două litere conține o vocală și o consoană exact când una dintre litere e vocală și cealaltă nu: strchr("aeiou", litera) spune dacă litera e vocală, iar cele două rezultate trebuie să difere.
La un laborator sunt studiate aglomerările de fulgi de nea formate din câte nouă cristale de patru tipuri diferite date (notate cu 1, 2, 3 sau 4), astfel încât din fiecare tip să existe cel puțin câte un cristal. O astfel de aglomerare de fulgi a fost reprezentată printr-un număr natural, în care fiecare cifră reprezintă tipul unui cristal. Subprogramul fulg are un parametru, n, prin care primește un număr natural (n∈[0,10^9)). Subprogramul returnează valoarea 1, dacă prin n este reprezentată o aglomerare de fulgi de nea dintre cele studiate, sau 0 în caz contrar.
Scrieți în C/C++ definiția completă a subprogramului.
Exemplu: dacă n=112243413 subprogramul returnează 1, iar dacă n=12314 sau n=112253513 sau n=112243457 sau n=111122223, subprogramul returnează 0.
int fulg(int n)
{
int c, nr = 0, f[10] = {0};
while (n > 0)
{
c = n % 10;
if (c < 1 || c > 4) return 0;
f[c]++;
nr++;
n = n / 10;
}
if (nr == 9 && f[1] > 0 && f[2] > 0 && f[3] > 0 && f[4] > 0) return 1;
return 0;
}Cifrele se iau pe rând de la dreapta. O cifră în afara tipurilor 1–4 înseamnă imediat 0. Pentru celelalte se numără câte cifre are numărul (nr) și de câte ori apare fiecare tip (în tabloul f). Aglomerarea este una dintre cele studiate când are exact 9 cristale și fiecare dintre cele patru tipuri apare cel puțin o dată.
Fiind date două numere naturale a și b, numim valoare generată de a și b un număr obținut din a prin alipirea la stânga sau la dreapta sa a cifrelor lui b, în ordinea în care apar în acesta.
Exemplu: dacă a=123 și b=45, se pot obține două numere generate de acestea: 12345 și 45123.
Scrieți un program C/C++ care citește de la tastatură două numere naturale din intervalul [2,50], m și n, și construiește în memorie un tablou bidimensional cu m linii, numerotate de la 1 la m, și n coloane, numerotate de la 1 la n, în care fiecare element este egal cu cea mai mică valoare generată de numerele de ordine ale liniei, respectiv coloanei pe care se află.
Programul afișează pe ecran tabloul obținut, fiecare linie a tabloului pe câte o linie a ecranului, elementele fiecărei linii fiind separate prin câte un spațiu.
Exemplu: pentru m=5 și n=4 se obține tabloul alăturat.
| 11 | 12 | 13 | 14 |
| 12 | 22 | 23 | 24 |
| 13 | 23 | 33 | 34 |
| 14 | 24 | 34 | 44 |
| 15 | 25 | 35 | 45 |
#include <iostream>
using namespace std;
int main()
{
int m, n, a[51][51], i, j, x, y;
cin >> m >> n;
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
{
if (j < 10) x = i * 10 + j;
else x = i * 100 + j;
if (i < 10) y = j * 10 + i;
else y = j * 100 + i;
if (x < y) a[i][j] = x;
else a[i][j] = y;
}
for (i = 1; i <= m; i++)
{
for (j = 1; j <= n; j++)
cout << a[i][j] << ' ';
cout << '\n';
}
return 0;
}Alipirea cifrelor lui b la dreapta lui a înseamnă a înmulțit cu 10 (dacă b are o cifră) sau cu 100 (dacă are două cifre), plus b; numerele liniilor și coloanelor sunt cel mult 50. Pentru fiecare element se calculează cele două valori generate, x (coloana la dreapta liniei) și y (linia la dreapta coloanei), și se păstrează cea mai mică.
Fișierul numere.in conține un șir de cel mult 10^6 numere naturale din intervalul [0,99]. Numerele din fișier sunt separate prin câte un spațiu.
Se cere să se determine primul și ultimul număr din șir care conțin cea mai mare cifră ce apare în scrierea numerelor din fișier. Numerele determinate se afișează pe ecran, în ordinea apariției lor în șir, separate printr-un spațiu. Dacă nu există două astfel de numere pe poziții distincte, se afișează pe ecran mesajul nu exista. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al spațiului de memorie utilizat.
Exemplu: dacă fișierul conține numerele 34 5 38 30 87 70 11 8 82 25 se afișează pe ecran 38 82, dacă fișierul conține numerele 34 5 38 30 87 70 11 8 38 25 se afișează pe ecran 38 38, iar dacă fișierul conține numerele 34 5 38 30 se afișează pe ecran nu exista.
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.
Timp de executare: O(n) · Memorie: O(1)
Numerele se citesc pe rând, fără să fie memorate. Pentru fiecare număr x (cel mult două cifre) se află cea mai mare cifră a lui, cm, ca maximul dintre x%10 și [x/10].
Se păstrează cifra maximă întâlnită până atunci (cifMax), primul număr care o conține (p) și ultimul (u, pornit de la -1). Dacă cm > cifMax, s-a găsit o cifră mai mare: cifMax, p și u se reiau (p = x, u = -1). Dacă cm = cifMax, numărul conține și el cifra maximă și devine ultimul găsit (u = x). Un număr care conține cea mai mare cifră din fișier nu poate avea o cifră și mai mare, deci verificarea cifrei lui maxime este suficientă. La final, dacă u = -1 se afișează nu exista, altfel p și u.
Eficiență: fiecare număr se prelucrează o singură dată, în timp constant, deci algoritmul este liniar în numărul de valori; se folosesc doar câteva variabile simple, deci memoria este constantă.
Fișierul numere.in conține un șir de cel mult 10^6 numere naturale din intervalul [0,99]. Numerele din fișier sunt separate prin câte un spațiu.
Se cere să se determine primul și ultimul număr din șir care conțin cea mai mare cifră ce apare în scrierea numerelor din fișier. Numerele determinate se afișează pe ecran, în ordinea apariției lor în șir, separate printr-un spațiu. Dacă nu există două astfel de numere pe poziții distincte, se afișează pe ecran mesajul nu exista. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al spațiului de memorie utilizat.
Exemplu: dacă fișierul conține numerele 34 5 38 30 87 70 11 8 82 25 se afișează pe ecran 38 82, dacă fișierul conține numerele 34 5 38 30 87 70 11 8 38 25 se afișează pe ecran 38 38, iar dacă fișierul conține numerele 34 5 38 30 se afișează pe ecran nu exista.
Scrieți programul C/C++ corespunzător algoritmului proiectat.
#include <fstream>
#include <iostream>
using namespace std;
int main()
{
ifstream fin("numere.in");
int x, cm, cifMax = -1, p = -1, u = -1;
while (fin >> x)
{
cm = x % 10;
if (x / 10 > cm) cm = x / 10;
if (cm > cifMax)
{
cifMax = cm;
p = x;
u = -1;
}
else if (cm == cifMax) u = x;
}
fin.close();
if (u == -1) cout << "nu exista";
else cout << p << ' ' << u;
return 0;
}Programul face pașii de la 3.a. cifMax pornește de la -1, astfel încât primul număr citit (chiar și 0) stabilește prima cifră maximă.
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