subac

Bac informatică 2024 Model, rezolvată

Lucrarea „2024 Model” 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.

Rezolv-o cu timpul de la examen3 ore
IIIIII

Enunțurile sunt cele oficiale, publicate de Ministerul Educației pe subiecte.edu.ro. Răspunsurile și explicațiile sunt scrise de subac.

Subiectul I20 de puncte

  1. Exercițiul 14p

    Variabila x este de tip întreg și poate memora un număr natural din intervalul [0,109).

    Indicați valoarea maximă pe care o poate avea expresia C/C++ alăturată.

    x%2024
    • a)20.24
    • b)295
    • c)2023
    • d)494071
    Arată răspunsul și explicația

    Răspuns corect: c) 2023

    Restul împărțirii la 2024 poate fi orice valoare de la 0 la 2023, iar 2023 se obține, de exemplu, pentru x = 2023. Un rest nu poate depăși împărțitorul minus 1, deci 494071 nu este posibil, iar 20.24 nu este un număr întreg.

  2. Exercițiul 24p

    Subprogramele f1, f2 și f3 sunt definite mai jos.

    Pentru n=24, se obține aceeași valoare la apelul subprogramelor:

    int f1(int n)
{ return n*(n+1)/2; }
int f2(int n)
{ if(n!=0) return n+f2(n-1);
  return 0;
}

int f3(int n)
{ if(n==0) return 0;
  if(n%2==1) return n+f3(n-1);
  return n*n/4+2*f3(n/2);
}
    • a)f1 și f2
    • b)f1 și f3
    • c)f2 și f3
    • d)f1, f2 și f3
    Arată răspunsul și explicația

    Răspuns corect: d) f1, f2 și f3

    f1 calculează suma 1+2+…+n cu formula, iar f2 aceeași sumă prin adunări repetate: pentru n=24, amândouă dau 300.

    f3 descompune altfel aceeași sumă: pentru n impar adaugă n la suma până la n−1, iar pentru n par folosește 1+…+n = n²/4 + 2·(1+…+n/2). f3(3) = 3 + f3(2) = 3 + 3 = 6, f3(6) = 9 + 2·6 = 21, f3(12) = 36 + 2·21 = 78, f3(24) = 144 + 2·78 = 300. Toate trei dau 300.

  3. Exercițiul 34p

    Utilizând metoda backtracking, se generează toate modalitățile de a realiza preparate la cuptor, folosind într-o tavă patru ingrediente distincte din mulțimea {broccoli, cașcaval, conopidă, ou, pătrunjel, smântână}. Fiecare preparat respectă următoarele condiții:

    • NU sunt folosite conopidă și broccoli în același preparat, iar dacă în acesta există una dintre cele două legume, ea este plasată prima în tavă;

    • dacă se folosește pătrunjel într-un preparat, el este plasat ultimul în tavă;

    • dacă se folosește smântână și cașcaval în același preparat, smântâna este plasată în tavă înainte de cașcaval.

    Două preparate sunt distincte dacă diferă prin cel puțin un ingredient sau prin ordinea plasării acestora în tavă. Primele cinci preparate generate sunt, în această ordine:

    1. (broccoli, cașcaval, ou, pătrunjel)
    2. (broccoli, ou, cașcaval, pătrunjel)
    3. (broccoli, ou, smântână, cașcaval)
    4. (broccoli, ou, smântână, pătrunjel)
    5. (broccoli, smântână, cașcaval, ou)

    Indicați al șaptelea preparat generat.

    • a)(broccoli, smântână, ou, cașcaval)
    • b)(conopidă, cașcaval, ou, pătrunjel)
    • c)(ou, smântână, cașcaval, pătrunjel)
    • d)(smântână, cașcaval, ou, pătrunjel)
    Arată răspunsul și explicația

    Răspuns corect: a) (broccoli, smântână, ou, cașcaval)

    Preparatele se generează în ordinea din mulțime: broccoli, cașcaval, conopidă, ou, pătrunjel, smântână. După al cincilea, (broccoli, smântână, cașcaval, ou), pe ultima poziție se încearcă ingredientul următor după ou: pătrunjelul, care poate fi ultimul — al șaselea preparat este (broccoli, smântână, cașcaval, pătrunjel).

    Pe ultima poziție nu mai urmează nimic potrivit (smântâna e deja folosită), așa că pe a treia poziție, după cașcaval, se trece la următorul ingredient permis, oul (conopida nu poate sta cu broccoli), iar pe ultima poziție primul potrivit este cașcavalul, așezat după smântână: (broccoli, smântână, ou, cașcaval).

  4. Exercițiul 44p

    Un arbore cu 10 noduri, numerotate de la 1 la 10, este reprezentat prin vectorul de „tați” (7,4,6,7,4,7,0,9,6,5).

    Indicați numărul de noduri „frunză” ale acestui arbore.

    • a)6
    • b)5
    • c)4
    • d)2
    Arată răspunsul și explicația

    Răspuns corect: b) 5

    Frunzele sunt nodurile care nu sunt tatăl niciunui alt nod, adică nu apar ca valori în vector. Valorile folosite sunt 7, 4, 6, 9 și 5 (0 marchează rădăcina), deci nodurile 1, 2, 3, 8 și 10 nu au fii: 5 frunze.

  5. Exercițiul 54p

    Într-un oraș sunt 5 piețe, iar una dintre acestea este conectată direct cu fiecare dintre celelalte patru prin câte o bandă de transport bidirecțională.

    Indicați numărul minim de benzi de transport bidirecționale care trebuie adăugate, astfel încât graful neorientat obținut, în care nodurile reprezintă piețele, iar muchiile reprezintă benzile de transport, să fie eulerian.

    • a)0
    • b)2
    • c)4
    • d)6
    Arată răspunsul și explicația

    Răspuns corect: b) 2

    Graful este o stea: piața centrală are gradul 4, iar celelalte patru gradul 1. Un graf conex este eulerian când toate nodurile au grad par.

    Cele patru noduri de grad impar se pot lega două câte două prin două benzi noi: fiecare ajunge la gradul 2, centrul rămâne cu 4, iar graful rămâne conex. O singură bandă ar face pare doar două grade, deci minimul este 2.

Subiectul al II-lea40 de puncte

  1. Exercițiul 1.a6p

    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 citesc, în această ordine, numerele 4, 721, 20020, 1321, 211.

    citește n (număr natural nenul)
 m←0; i←n
┌cât timp i≥1 execută
│ citește x (număr natural)
│┌cât timp x%10 ≤ [x/10]%10 execută
││ x←[x/10]
│└■
│ m←m+x; i←i-1
└■
┌dacă m≠n atunci scrie m
│altfel scrie "egal"
└■
    Arată răspunsul și explicația

    Răspunsul din barem: 2024

    2024

Pentru fiecare număr x citit, cât timp ultima cifră este cel mult cât penultima, ultima cifră se taie. Rămâne prefixul care se termină cu prima cifră (de la dreapta) mai mare decât cea din stânga ei. Valorile rămase se adună în m, iar dacă m este egal cu n se afișează egal.
721 → 72 → 7; 20020 → 2002; 1321 → 132 → 13; 211 → 21 → 2. Suma este 7 + 2002 + 13 + 2 = 2024, diferită de 4, deci se afișează 2024.

  2. Exercițiul 1.b6p

    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.

    Dacă primul număr citit este 2, scrieți un set de numere distincte din intervalul [10,104] care pot fi citite în continuare astfel încât, în urma executării algoritmului, să se afișeze mesajul egal.

    citește n (număr natural nenul)
 m←0; i←n
┌cât timp i≥1 execută
│ citește x (număr natural)
│┌cât timp x%10 ≤ [x/10]%10 execută
││ x←[x/10]
│└■
│ m←m+x; i←i-1
└■
┌dacă m≠n atunci scrie m
│altfel scrie "egal"
└■
    Arată răspunsul și explicația
    Exemplu: 10 11

Pentru n=2 se afișează egal când suma celor două valori rămase este 2, deci fiecare număr trebuie să se reducă la 1. Asta se întâmplă pentru numerele formate din cifre 1 urmate doar de cifre 0: 10, 11, 100, 110, 111, 1000, 1100, 1110, 1111 și 10000.

  3. Exercițiul 1.c10p

    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 nenul)
 m←0; i←n
┌cât timp i≥1 execută
│ citește x (număr natural)
│┌cât timp x%10 ≤ [x/10]%10 execută
││ x←[x/10]
│└■
│ m←m+x; i←i-1
└■
┌dacă m≠n atunci scrie m
│altfel scrie "egal"
└■
    Arată răspunsul și explicația
    #include <iostream>
using namespace std;

int main()
{
    int n, m = 0, i, x;
    cin >> n;
    i = n;
    while (i >= 1)
    {
        cin >> x;
        while (x % 10 <= x / 10 % 10) x = x / 10;
        m = m + x;
        i = i - 1;
    }
    if (m != n) cout << m;
    else cout << "egal";
    return 0;
}

Cele două structuri cât timp devin while, [x/10] este împărțirea întreagă, iar [x/10]%10 este penultima cifră a lui x.

  4. Exercițiul 1.d6p

    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ă cu o structură de tip pentru...execută.

    citește n (număr natural nenul)
 m←0; i←n
┌cât timp i≥1 execută
│ citește x (număr natural)
│┌cât timp x%10 ≤ [x/10]%10 execută
││ x←[x/10]
│└■
│ m←m+x; i←i-1
└■
┌dacă m≠n atunci scrie m
│altfel scrie "egal"
└■
    Arată răspunsul și explicația
    citește n (număr natural nenul)
m←0
┌pentru i←n,1,-1 execută
│ citește x (număr natural)
│┌cât timp x%10 ≤ [x/10]%10 execută
││ x←[x/10]
│└■
│ m←m+x
└■
┌dacă m≠n atunci scrie m
│altfel scrie "egal"
└■

Contorul i pornea de la n și scădea cu 1 cât timp i≥1, deci structura pentru îl ia de la n la 1, cu pasul -1. Inițializarea i←n și actualizarea i←i-1 dispar, pentru că le face structura pentru.

  5. Exercițiul 26p

    Variabila t memorează simultan, pentru un telefon, următoarele date: producătorul (o literă mare a alfabetului englez), frecvența procesorului (număr natural) și dimensiunea, dată prin trei valori, reprezentând lățimea, grosimea și lungimea, în această ordine, în milimetri (numere reale).

    Știind că expresiile C/C++ de mai jos au ca valori producătorul și lățimea telefonului, respectiv frecvența procesorului acestuia, scrieți definiția unei structuri cu eticheta telefon, care permite memorarea datelor despre un telefon, și declarați corespunzător variabila t.

    t.producator   t.dimensiune[0]    t.frecventa
    Arată răspunsul și explicația
    struct telefon
{   char producator;
    int frecventa;
    float dimensiune[3];
} t;

Expresiile arată câmpurile necesare: t.producator este o literă (char), t.frecventa un număr natural, iar t.dimensiune[0] arată că dimensiunea este un tablou, cu cele trei valori reale (lățimea, grosimea și lungimea).

  6. Exercițiul 36p

    Variabila i este de tip întreg, iar variabila a memorează un tablou bidimensional cu 4 linii și 24 de coloane, numerotate începând cu 0, cu elemente numere întregi.

    Fără a utiliza alte variabile decât cele menționate, scrieți o secvență de instrucțiuni în urma executării căreia să se afișeze pe ecran, separate prin câte un spațiu, indicii coloanelor cu proprietatea că atât primul, cât și ultimul lor element, au valoarea 2024.

    Arată răspunsul și explicația
    for (i = 0; i < 24; i++)
    if (a[0][i] == 2024 && a[3][i] == 2024)
        cout << i << ' ';

Primul element al coloanei i este pe prima linie, a[0][i], iar ultimul pe ultima linie, a[3][i]. Singura variabilă de care e nevoie în plus față de tablou este i, care parcurge coloanele.

Subiectul al III-lea30 de puncte

  1. Exercițiul 110p

    Subprogramul produs are doi parametri, a și b, prin care primește câte un număr natural din intervalul [1,103]. Subprogramul returnează produsul divizorilor naturali comuni lui a și b.

    Scrieți definiția completă a subprogramului.

    Exemplu: dacă a=20 și b=12, atunci subprogramul returnează valoarea 8 (1∙2∙4=8).

    Arată răspunsul și explicația
    int produs(int a, int b)
{
    int d, p = 1;
    for (d = 2; d <= a && d <= b; d++)
        if (a % d == 0 && b % d == 0)
            p = p * d;
    return p;
}

Un divizor comun al lui a și b este cel mult cât cel mai mic dintre ele. Se încearcă toate valorile d de la 2 până acolo (1 nu schimbă produsul) și se înmulțesc cele care îi divid pe amândoi.

  2. Exercițiul 210p

    Un text are cel mult 100 de caractere, iar cuvintele sale sunt formate numai din litere mici ale alfabetului englez, sunt distincte și sunt separate prin câte un spațiu.

    Scrieți un program C/C++ care citește de la tastatură un număr natural n (n∈[1,102]), apoi un text de tipul precizat mai sus, și afișează pe ecran cuvinte ale acestuia, pe două linii separate, astfel încât prima linie să conțină mulțimea cuvintelor care au mai puțin de n litere, iar a doua linie să conțină mulțimea cuvintelor care au mai mult de n litere. Cuvintele de pe fiecare linie sunt afișate într-o ordine oarecare, iar dacă una dintre cele două mulțimi este vidă, se afișează pe ecran doar mesajul nu exista.

    Exemplu: pentru n=3 și textul era o apa rece si cu gust bun se poate afișa pe ecran textul alăturat.

    o si cu
rece gust
    Arată răspunsul și explicația
    #include <iostream>
#include <cstring>
using namespace std;

int main()
{
    char s[101], mici[101] = "", mari[101] = "", *p;
    int n;
    cin >> n;
    cin.get();
    cin.getline(s, 101);
    p = strtok(s, " ");
    while (p != NULL)
    {
        if ((int)strlen(p) < n)
        {
            strcat(mici, p);
            strcat(mici, " ");
        }
        else if ((int)strlen(p) > n)
        {
            strcat(mari, p);
            strcat(mari, " ");
        }
        p = strtok(NULL, " ");
    }
    if (mici[0] == '\0' || mari[0] == '\0') cout << "nu exista";
    else cout << mici << '\n' << mari;
    return 0;
}

După citirea lui n, cin.get() consumă sfârșitul de rând, ca textul să fie citit întreg pe rândul următor. Cuvintele se separă cu strtok și se adaugă, după lungime, la șirul celor scurte sau al celor lungi; cele cu exact n litere nu apar nicăieri. Dacă unul dintre șiruri a rămas gol, se afișează doar nu exista.
Enunțul acceptă cuvintele în orice ordine pe fiecare linie; programul le păstrează în ordinea din text.

  3. Exercițiul 3.a2p

    La un concurs se acordă premiile I, al II-lea și al III-lea. Fiecare premiant este recompensat cu câte o carte, care are un preț egal pentru toți cei cu același premiu. Prețurile cărților alese pentru premiile I, al II-lea și al III-lea sunt stabilite astfel încât să fie în ordine strict descrescătoare, iar pentru fiecare premiu să se ia în considerare cel mai mare preț pentru care există suficiente cărți propuse, în condițiile precizate.

    Fișierul bac.txt conține pe prima linie trei numere naturale din intervalul [1,20], n1, n2 și n3, reprezentând numărul concurenților care primesc premiile I, al II-lea, respectiv al III-lea, iar pe a doua linie un șir de cel mult 106 numere naturale din intervalul [10,103], separate prin câte un spațiu, fiecare număr reprezentând prețul unei cărți propuse pentru premiere.

    Se cere să se afișeze pe ecran, separate prin câte un spațiu, în ordine strict descrescătoare, prețurile cărților alese, corespunzătoare celor trei premii, iar dacă nu există trei astfel de prețuri, se afișează mesajul nu exista. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.

    Exemplu: dacă fișierul conține valorile de mai jos, se afișează pe ecran, în această ordine, numerele 100 52 20.

    3 2 4
500 100 25 100 200 100 20 10 200 100 75 52 52 15 52 20 20 10 30 20 15 100

    Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.

    Arată răspunsul și explicația
    Prețurile sunt între 10 și 1000, deci se poate număra câte cărți există la fiecare preț, într-un vector de apariții ap, fără să se memoreze șirul.

După citire, prețurile se parcurg de la cel mai mare la cel mai mic. Primul preț la care există cel puțin n1 cărți devine prețul premiului I (x). De acolo în jos, primul preț cu cel puțin n2 cărți devine prețul premiului al II-lea (y), iar apoi primul cu cel puțin n3 cărți, prețul premiului al III-lea (z). Fiecare preț se folosește pentru un singur premiu, deci cele trei ies strict descrescătoare. Dacă z nu a fost găsit până la final, se afișează nu exista.

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 (cel mult 1000), deci timpul este liniar în numărul de valori citite.

  4. Exercițiul 3.b8p

    La un concurs se acordă premiile I, al II-lea și al III-lea. Fiecare premiant este recompensat cu câte o carte, care are un preț egal pentru toți cei cu același premiu. Prețurile cărților alese pentru premiile I, al II-lea și al III-lea sunt stabilite astfel încât să fie în ordine strict descrescătoare, iar pentru fiecare premiu să se ia în considerare cel mai mare preț pentru care există suficiente cărți propuse, în condițiile precizate.

    Fișierul bac.txt conține pe prima linie trei numere naturale din intervalul [1,20], n1, n2 și n3, reprezentând numărul concurenților care primesc premiile I, al II-lea, respectiv al III-lea, iar pe a doua linie un șir de cel mult 106 numere naturale din intervalul [10,103], separate prin câte un spațiu, fiecare număr reprezentând prețul unei cărți propuse pentru premiere.

    Se cere să se afișeze pe ecran, separate prin câte un spațiu, în ordine strict descrescătoare, prețurile cărților alese, corespunzătoare celor trei premii, iar dacă nu există trei astfel de prețuri, se afișează mesajul nu exista. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.

    Exemplu: dacă fișierul conține valorile de mai jos, se afișează pe ecran, în această ordine, numerele 100 52 20.

    3 2 4
500 100 25 100 200 100 20 10 200 100 75 52 52 15 52 20 20 10 30 20 15 100

    Scrieți programul C/C++ corespunzător algoritmului proiectat.

    Arată răspunsul și explicația
    #include <fstream>
#include <iostream>
using namespace std;

int main()
{
    ifstream fin("bac.txt");
    int ap[1001] = {0}, n1, n2, n3, v, p, x = 0, y = 0, z = 0;
    fin >> n1 >> n2 >> n3;
    while (fin >> v) ap[v]++;
    fin.close();
    for (p = 1000; p >= 10 && z == 0; p--)
        if (x == 0)
        {
            if (ap[p] >= n1) x = p;
        }
        else if (y == 0)
        {
            if (ap[p] >= n2) y = p;
        }
        else if (ap[p] >= n3) z = p;
    if (z == 0) cout << "nu exista";
    else cout << x << ' ' << y << ' ' << z;
    return 0;
}

Programul face pașii de la 3.a. Structura dacă…altfel dacă asigură că un preț este folosit pentru un singur premiu, iar bucla se oprește imediat ce s-au găsit toate trei.

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