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 2023 trece prin expresii, recursivitate, structuri imbricate, backtracking, grafuri orientate, arbori și grafuri euleriene, matrice, divizori, șiruri de caractere și fișiere. Este o variantă echilibrată, bună pentru recapitularea întregii materii.
Subiectul I (20p): 5 grile: valorile pentru care x/2+y%3 dă 23, un subprogram recursiv care transformă cifrele unui număr, declararea unei variabile m cu un câmp dm care este tot o structură, o problemă de backtracking cu pachete de câte trei ceaiuri și numărul maxim de arce ale unui graf orientat cu 8 vârfuri și trei componente tare conexe.
Subiectul al II-lea (40p): Un algoritm în pseudocod care reface un număr de cinci ori, înlocuind de fiecare dată cifrele egale cu x prin 5-x, trei muchii care fac eulerian un arbore dat prin vectorul de „tați” și o secvență care completează o matrice 5×5 după poziția față de diagonala secundară.
Subiectul al III-lea (30p): Un subprogram cu divizori (NrImp, câte numere dintr-un interval au exact trei divizori impari), o problemă cu șiruri de caractere care rescrie prescurtările din denumirea științifică a unei păsări și o problemă de eficiență cu „pașii reprezentativi” ai unui experiment, citiți din fișierul bac.txt.
/ între numere întregi dă câtul: 43/2 este 21, iar 20%3 este 2, deci x=43 și y=20 dau 23.Indicați numerele pe care le pot memora variabilele întregi x și y, astfel încât valoarea expresiei C/C++ alăturate să fie 23.
x/2+y%3
Răspuns corect: d) x=43 și y=20
Pentru x=43 și y=20: 43/2 este 21 (câtul împărțirii întregi), iar 20%3 este 2, deci expresia are valoarea 23.
a) dă 4 + 2 = 6, b) dă 10 + 0 = 10, iar c) dă 11 + 0 = 11.
Subprogramul f este definit alăturat.
Indicați valoarea lui f(2023).
int f(int n)
{ if(n==0) return 0;
if(n%10==2) return f(n/10)*10+3;
return f(n/10)*10+2;
}Răspuns corect: b) 3232
Fiecare apel se ocupă de ultima cifră a lui n: o cifră 2 devine 3, orice altă cifră devine 2, iar rezultatul pentru n/10 se pune în fața ei (înmulțit cu 10).
Cifrele lui 2023 sunt 2, 0, 2, 3, care devin 3, 2, 3, 2: f(2023) = 3232.
Expresiile alăturate au ca valori trei numere naturale reprezentând, în această ordine, următoarele informații memorate pentru o motocicletă: anul fabricației și dimensiuni specifice (garda la sol și lungimea).
Indicați o declarare corespunzătoare a variabilei m.
m.an m.dm.garda m.dm.lungime
Răspuns corect: a) struct { int an; struct{int garda, lungime;}dm; }m;
m.an arată că an este un câmp al lui m, iar m.dm.garda și m.dm.lungime arată că dm este tot un câmp al lui m, la rândul lui o structură cu câmpurile garda și lungime. Declarația a) are exact această formă.
b) și c) pun puncte în numele câmpurilor, ceea ce nu este permis, iar d) nu este o declarare validă.
Utilizând metoda backtracking, se generează toate pachetele formate din câte 3 tipuri distincte de ceai din mulțimea {matcha, mate, moringa, oolong, tulsi}. Două amestecuri sunt distincte dacă diferă prin cel puțin un tip de ceai. Primele patru soluții obținute sunt, în această ordine: (matcha, mate, moringa), (matcha, mate, oolong), (matcha, mate, tulsi) și (matcha, moringa, oolong).
Indicați succesiunea care NU se obține, prin această metodă, în ordinea dată.
Răspuns corect: d) (oolong, tulsi, mate)
Pachetele sunt submulțimi de trei tipuri de ceai, generate în ordinea din mulțime, deci fiecare soluție păstrează ordinea matcha, mate, moringa, oolong, tulsi.
(oolong, tulsi, mate) are mate după oolong și tulsi, deci nu este generată în această ordine. Celelalte trei respectă ordinea și sunt soluții.
Într-un magazin sunt 8 raioane, distribuite în trei zone importante, în fiecare zonă fiind un număr par, nenul, de raioane. În scopul fluidificării deplasării clienților se marchează unele culoare, astfel încât fiecare culoar să conecteze două raioane, iar deplasarea pe el să se facă într-un singur sens.
Se realizează o hartă, sub forma unui graf orientat, în care vârfurile reprezintă raioanele din magazin, iar arcele reprezintă culoarele marcate.
Indicați numărul maxim de culoare care se pot marca, astfel încât graful să aibă trei componente tare conexe, fiecare componentă fiind reprezentarea pe hartă a câte uneia dintre cele trei zone importante din magazin.
Răspuns corect: c) 36
8 raioane împărțite în trei zone, fiecare cu un număr par, nenul, de raioane, înseamnă zone de 2, 2 și 4 raioane.
În fiecare zonă, toate culoarele posibile, în ambele sensuri, păstrează zona tare conexă: 2·1 + 2·1 + 4·3 = 16 culoare. Între zone, culoarele pot merge doar într-un singur sens, de la o zonă la alta într-o ordine fixă (altfel două zone s-ar uni): 2·2 + 2·4 + 2·4 = 20 de culoare. În total 36.
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ă dacă se citește numărul 5174.
citește n
(număr natural)
x←5
┌repetă
│ cn←n; n←0; p←1
│┌repetă
││ c←cn%10
││┌dacă c=x atunci c←5-c
││└■
││ n←c*p+n; cn←[cn/10]; p←p*10
│└până când cn=0
│ x←x-1
└până când x=0
scrie nRăspunsul din barem: 474
Pentru x de la 5 în jos până la 1, numărul se reface cifră cu cifră, iar fiecare cifră egală cu x este înlocuită cu 5−x; cifrele 0 din față dispar la refacere. 5174: pentru x=5, 5 devine 0, deci 174; pentru x=4, 4 devine 1: 171; pentru x=3 și x=2 nu se schimbă nimic; pentru x=1, fiecare 1 devine 4: 474.
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 trei numere impare, cu cifre distincte, din intervalul [10^2,10^4) care pot fi citite astfel încât, în urma executării algoritmului, pentru fiecare dintre acestea, să se afișeze valoarea 34.
Exemplu: 521 531 5031
Cifrele se transformă pe rând: 5 devine 0, 4 devine 1 (și apoi iar 4), 3 devine 2 (și apoi iar 3), 2 devine 3, iar 1 devine 4; cifrele 0 din fața numărului dispar. Ca să rămână 34, numărul trebuie să înceapă cu 5 (care dispare, cu un eventual 0 după el), urmat de 2 sau 3 și de 1 sau 4. Numerele impare cu cifre distincte din [100,9999] de acest fel sunt 521, 531, 5021 și 5031.
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 = 5, cn, p, c;
cin >> n;
do
{
cn = n;
n = 0;
p = 1;
do
{
c = cn % 10;
if (c == x) c = 5 - c;
n = c * p + n;
cn = cn / 10;
p = p * 10;
} while (cn != 0);
x = x - 1;
} while (x != 0);
cout << n;
return 0;
}Cele două structuri repetă…până când devin do…while, cu condițiile negate: până când cn=0 devine while (cn != 0), iar până când x=0 devine while (x != 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 prima structură repetă...până când cu o structură de tip pentru...execută.
citește n (număr natural) ┌pentru x←5,1,-1 execută │ cn←n; n←0; p←1 │┌repetă ││ c←cn%10 ││┌dacă c=x atunci c←5-c ││└■ ││ n←c*p+n; cn←[cn/10]; p←p*10 │└până când cn=0 └■ scrie n
x lua pe rând valorile 5, 4, 3, 2, 1, câte o dată la fiecare trecere prin bucla exterioară, deci structura pentru îl ia de la 5 la 1, cu pasul -1. Inițializarea x←5 și actualizarea x←x-1 dispar, pentru că le face structura pentru.
Un arbore cu 7 noduri, numerotate de la 1 la 7, este reprezentat prin vectorul de „tați” (4,1,1,0,7,4,4).
Scrieți trei muchii care i se pot adăuga, astfel încât graful obținut să fie eulerian.
Exemplu: [1,5], [2,4], [3,6]
Rădăcina este 4. Muchiile arborelui sunt [1,4], [2,1], [3,1], [5,7], [6,4] și [7,4], iar gradele nodurilor sunt: 1 are 3, 2 are 1, 3 are 1, 4 are 3, 5 are 1, 6 are 1, 7 are 2. Un graf conex este eulerian când toate gradele sunt pare. Nodurile cu grad impar sunt 1, 2, 3, 4, 5 și 6; legându-le două câte două prin muchii care nu există deja, de exemplu [1,5], [2,4] și [3,6], toate gradele devin pare, iar graful rămâne conex.
Variabilele i și j sunt de tip întreg, iar variabila a memorează un tablou bidimensional cu 5 linii și 5 coloane, numerotate de la 1 la 5, având inițial toate elementele nule.
Fără a utiliza alte variabile decât cele menționate, scrieți secvența de instrucțiuni de mai jos, înlocuind punctele de suspensie astfel încât, în urma executării secvenței obținute, variabila a să memoreze tabloul alăturat.
for(i=1;i<=5;i++) for(j=1;j<=5;j++) ..................
| 4 | 3 | 2 | 1 | 0 |
| 4 | 3 | 2 | 1 | 1 |
| 4 | 3 | 2 | 2 | 2 |
| 4 | 3 | 3 | 3 | 3 |
| 4 | 4 | 4 | 4 | 4 |
for(i=1;i<=5;i++) for(j=1;j<=5;j++) if(i+j<=6) a[i][j]=5-j; else a[i][j]=i-1;
Pe linia i, până la diagonala secundară inclusiv (i+j ≤ 6), valorile sunt 4, 3, 2, … de la stânga la dreapta, adică 5−j. După diagonală, valorile rămân egale cu cea de pe diagonală, adică 5−(6−i) = i−1. Nu se folosesc alte variabile în afară de i, j și a.
Subprogramul NrImp are trei parametri:
• x și y, prin care primește câte un număr natural (2≤x<y≤10^9)
• nr, prin care furnizează numărul valorilor naturale din intervalul [x,y] cu trei divizori pozitivi impari.
Scrieți definiția completă a subprogramului.
Exemplu: dacă x=4 și y=50, după apel nr=6 (pentru valorile 9, 18, 25, 36, 49, 50).
void NrImp(int x, int y, int &nr)
{
int v, o, d, k;
nr = 0;
for (v = x; v <= y; v++)
{
o = v;
while (o % 2 == 0) o = o / 2;
k = 0;
for (d = 1; d * d <= o; d++)
if (o % d == 0)
{
k++;
if (d != o / d) k++;
}
if (k == 3) nr++;
}
}Divizorii impari ai unui număr sunt exact divizorii părții lui impare, adică ai numărului rămas după ce se împarte la 2 de câte ori se poate. Pentru fiecare v din interval se află partea impară o, se numără divizorii ei, luați în perechi d și o/d, și se numără valorile v pentru care ies exact trei.
Într-un text de cel mult 100 de caractere cuvintele sunt separate prin câte un spațiu și sunt formate din litere mari ale alfabetului englez, iar dacă sunt scrise prescurtat sunt urmate de caracterul . (punct). Textul reprezintă denumirea științifică a unei păsări și doar cuvintele din mulțimea {FAMILIA, GENUL, SPECIA}, specifice sistemului de clasificare a organismelor, sunt mereu prescurtate, prin eliminarea ultimelor lor litere.
Scrieți un program C/C++ care citește de la tastatură un text de tipul precizat și construiește în memorie, apoi afișează pe ecran denumirea științifică, în care pentru cuvintele specifice sistemului de clasificare a organismelor se păstrează doar primele trei litere, scrise cu litere mici, și urmate de punct, ca în exemplu.
Exemplu: pentru textul FAMIL. PHASIANIDAE GEN. MELEAGRIS SP. GALLOPAVO sau pentru textul FAM. PHASIANIDAE G. MELEAGRIS SPECI. GALLOPAVO se obține fam. PHASIANIDAE gen. MELEAGRIS spe. GALLOPAVO
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
char s[201], t[201] = "", *p;
cin.getline(s, 101);
p = strtok(s, " ");
while (p != NULL)
{
if (t[0] != '\0') strcat(t, " ");
if (p[strlen(p) - 1] == '.')
{
if (p[0] == 'F') strcat(t, "fam.");
else if (p[0] == 'G') strcat(t, "gen.");
else strcat(t, "spe.");
}
else strcat(t, p);
p = strtok(NULL, " ");
}
strcpy(s, t);
cout << s;
return 0;
}Doar cuvintele de clasificare sunt prescurtate, deci un cuvânt care se termină cu punct este sigur unul dintre ele. Cele trei încep cu litere diferite (F, G, S), așa că prima literă spune despre care este vorba, oricât de scurtă ar fi prescurtarea. Textul nou se construiește în t și apoi se copiază în s; s are loc pentru 200 de caractere, pentru că o prescurtare ca „G.” crește la „gen.”.
Pentru a studia un metal, s-a urmărit comportamentul său într-o succesiune de pași, la fiecare pas metalul fiind supus unei anumite temperaturi. Pașii sunt numerotați cu valori naturale consecutive, începând de la 1. Un pas se numește reprezentativ dacă la niciunul dintre pașii anteriori nu este utilizată o temperatură strict mai mare decât la acest pas. Dacă există o secvență de pași consecutivi la care se utilizează aceeași temperatură, se consideră reprezentativ doar primul pas din secvență.
Fișierul bac.txt conține cel mult 10^6 numere naturale din intervalul [0,10^4], separate prin câte un spațiu, reprezentând temperaturile la care este supus metalul, în ordinea pașilor corespunzători. Se cere să se afișeze pe ecran, separați prin câte un spațiu, pașii reprezentativi pentru datele din fișier. 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 7 4 9 10 10 10 3 9 2 10 10 8 2 30 se afișează pe ecran 1 3 4 10 14
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.
Timp de executare: O(n) · Memorie: O(1)
Temperaturile se citesc pe rând, fără să fie memorate, numărând pașii. Un pas este reprezentativ dacă temperatura lui este cel puțin cea mai mare temperatură de până atunci și nu continuă o secvență de pași consecutivi cu aceeași temperatură.
Se păstrează cea mai mare temperatură întâlnită (tr) și ultimul pas la care s-a ajuns la ea sau mai sus (ptr). La pasul curent px, cu temperatura x: dacă x > tr, pasul este reprezentativ; dacă x = tr, este reprezentativ doar dacă pasul de dinainte nu avea tot temperatura maximă (px > ptr + 1). Pasul se afișează când e reprezentativ. Apoi, dacă x ≥ tr, ptr devine px, iar dacă x > tr, tr devine x.
Eficiență: fiecare temperatură se prelucrează o singură dată, în timp constant, deci timpul este liniar în numărul de pași; se folosesc doar câteva variabile simple, deci memoria este constantă.
Pentru a studia un metal, s-a urmărit comportamentul său într-o succesiune de pași, la fiecare pas metalul fiind supus unei anumite temperaturi. Pașii sunt numerotați cu valori naturale consecutive, începând de la 1. Un pas se numește reprezentativ dacă la niciunul dintre pașii anteriori nu este utilizată o temperatură strict mai mare decât la acest pas. Dacă există o secvență de pași consecutivi la care se utilizează aceeași temperatură, se consideră reprezentativ doar primul pas din secvență.
Fișierul bac.txt conține cel mult 10^6 numere naturale din intervalul [0,10^4], separate prin câte un spațiu, reprezentând temperaturile la care este supus metalul, în ordinea pașilor corespunzători. Se cere să se afișeze pe ecran, separați prin câte un spațiu, pașii reprezentativi pentru datele din fișier. 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 7 4 9 10 10 10 3 9 2 10 10 8 2 30 se afișează pe ecran 1 3 4 10 14
Scrieți programul C/C++ corespunzător algoritmului proiectat.
#include <fstream>
#include <iostream>
using namespace std;
int main()
{
ifstream fin("bac.txt");
int x, px = 0, tr = -1, ptr = -1;
while (fin >> x)
{
px++;
if (x > tr || (x == tr && px > ptr + 1)) cout << px << ' ';
if (x >= tr) ptr = px;
if (x > tr) tr = x;
}
fin.close();
return 0;
}Programul face pașii de la 3.a. tr pornește de la -1, sub orice temperatură, deci primul pas este mereu reprezentativ.
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