Lucrarea „2024 Varianta 4” 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.
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
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.
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 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.
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 └■
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].
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 programul C/C++ corespunzător algoritmului dat.
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 └■
#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++.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 î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) 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 └■
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,109)). 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 106 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.
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 106 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 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