Rezolvarea subiectelor de informatică de la examenul de bacalaureat național, sesiunea august 2014 (2)

Filiera teoretică, profilul real, specializarea științe ale naturii

 

Enunțul subiectelor precum și baremul de corectare pot fi descărcate de pe site-ul Ministerului Educației Naționale.

Pe contul de GitHub poate fi consultat codul sursă corespunzător subiectelor care solicită elaborarea de programe C/C++.

SUBIECTUL I (30 de puncte)


Acest subiect este identic cu cel de la specializarea matematică-informatică.

SUBIECTUL II (30 de puncte)


1. Pentru ca expresia sqrt(x/10+x%10)==4 să aibă valoarea 1 (adică valoarea de adevăr adevărat), este necesar ca expresia de sub radical să aibă valoarea 16, adică x/10+x%10=16. Se cere valoarea maximă a lui x, acesta fiind un număr întreg cu 2 cifre.

Pentru x ≥ 90, x/10 = 9, aceasta fiind valoarea maximă pe care o poate avea această expresie. Prin urmare x%10 = 16 – x/10 = 16 – 9 = 7. Singura valoare care întrunește simultan condițiile x ≥ 90 și x%10=7 este x=97.

Într-adevăr, 97/10+97%10=9+7=16 și aceasta este valoarea maximă a unui întreg format din 2 cifre care să respecte condiția dată.

Răspuns corect: d.

2. Pentru a determina formula de calcul a sumei numerelor dintr-un interval [k, n], k<n, numere naturale, se recurge la formula de calcul a unor numere în progresie aritmetică, cu termenul inițial a1=1 și rația r = 1:

1 + 2 + … + n = n(n + 1) / 2

1 + 2 + … + (k-1) = k(k – 1) / 2

de unde Sn,k = k + … + n = 1 + 2 + … + n – (1 + 2 + … + (k-1)) = n(n + 1) / 2 – k(k – 1) / 2 = (n2 + n – k2 + k) / 2 = (n2 – k2 + n + k) / 2 = ((n + k)(n – k) + (n + k)) / 2 = (n + k)(n – k + 1) / 2

Ultima cifră a sumei se determină ca rest al împărțirii la 10: Sn,k % 10 = ((n + k)(n – k + 1) / 2) % 10.

a) Se observă că secvența S1 folosește o formulă de calcul prescurtat pentru ultima cifră a sumei, având aceeași expresie ca cea determinată mai sus și prin urmare, corectă.

b) În secvența S2 sunt adunate, în cadrul unui ciclu repetitiv for, toate numerele cuprinse între k și n, reținându-se în fiecare pas al iterației doar ultima cifră,  această metodă de calcul fiind de asemenea corectă.

c) În secvența S3 se adaugă, tot în cadrul unui ciclu repetitiv for, un număr din intervalul [k + 1, n] la ultima cifră a sumei calculată până la pasul respectiv al iterației. O astfel de abordare prezintă două erori:

c.1) omite numărul k, iterația realizându-se de la k+1;

c.2) nu determină întotdeauna ultima cifră a sumei, pentru valori ale lui n > 9 obținându-se de fapt rezultatul adunării ultimului număr al intervalului (n) cu ultima cifră a sumei numerelor din intervalul [k + 1, n – 1].

Prin urmare, numai secvențele S1 și S2 furnizează rezultatul dorit.

Răspuns corect: a.

Exercițiul reprezintă o capcană pentru candidații insuficient pregătiți la matematică, pe care formula din secvența S1 îi poate induce în eroare, cu atât mai mult cu cât există ca variantă de răspuns care dă drept corectă doar secvența de cod S2.

3. Problema presupune citirea unei variabile de tip char și prelucrarea ei (incrementare / decrementare) într-o instrucțiune switch care testează dacă caracterul aparține mulțimii {‘a’, ‘e’, ‘i’} sau nu.

using namespace std;

#include <iostream>

int main() {
    char c;
    cout << "c="; cin >> c;
    switch (c) {
        case 'a':
        case 'e':
        case 'i':
            c++;
            break;
        default:
            c--;
    }
    cout << c << endl;
    return 0;
}

4. Acest subiect este identic cu cerința 3, subiectul III de la specializarea matematică-informatică, cu excepția faptului că nu se solicită scrierea programului C/C++ corespunzător, ci descrierea algoritmului în pseudocod, fără utilizarea de subprograme.

a) Se generează toate combinațiile posibile pentru x ∈ [0, n], respectiv y ∈ [x + 1, n] (astfel încât să se respecte restricția x < y), urmând să se verifice dacă există un z întreg, y < z, calculat după formula z = (n – x * y) / y.

Valorile pentru x și y vor fi generate prin cicluri repetitive de tip pentru, cu pasul de incrementare 1, testându-se pentru fiecare pereche (x, y) astfel generată dacă respectă condiția impusă:

repetă

    citește n

până când n≥2

pentru x = 0, n; pas 1

    pentru y = x + 1, n; pas 1

        z = (n – x * y) / y

        dacă (n – x * y) % y == 0 și y < z atunci

            tipărește “(“,x,”,”,y,”,”,z,”)”

b) Data de intrare este reprezentată de numărul natural n. Datele de ieșire sunt reprezentate de soluțiile ecuației (x, y, z).

Variabilele x și y sunt generate în cadrul unui ciclu repetitiv cu număr cunoscut de pași de tip pentru (cu pasul de incrementare 1), luând valori în intervalele [0, n], respectiv [x + 1, n], calculându-se valoarea lui z în funcție de acestea. Dacă valoarea astfel determinată satisface restricțiile impuse de problemă (z întreg și y < z), atunci se afișează soluția găsită.

SUBIECTUL III (30 de puncte)


1. Verificăm, succesiv, care sunt valorile testate pentru fiecare dintre variantele de răspuns:

a) (16, 17, 21, 29, 49, 80, 95) – vector cu 7 elemente

Se caută elementul pe poziția 4; acesta este 29, dar 21 < 29 și se continuă căutarea în partea stângă a vectorului (16, 17, 21).

Se caută elementul pe poziția 2; acesta este 17, dar 21 > 17 și se continuă căutarea în partea dreaptă a vectorului (21).

Se caută elementul pe poziția 3; acesta este 21, elementul a fost găsit.

Elementele cu care s-a realizat compararea au fost (29, 17, 21) – nu corespund cu valoarea indicată în enunț.

b) (4, 16, 21, 49, 56, 70, 85) – vector cu 7 elemente

Se caută elementul pe poziția 4; acesta este 49, dar 21 < 49 și se continuă căutarea în partea stângă a vectorului (4, 16, 21).

Se caută elementul pe poziția 2; acesta este 16, dar 21 > 16 și se continuă căutarea în partea dreaptă a vectorului (21).

Se caută elementul pe poziția 3; acesta este 21, elementul a fost găsit.

Elementele cu care s-a realizat compararea au fost (49, 16, 21) – corespund cu valoarea indicată în enunț.

c) (7, 9, 10, 16, 21, 45, 49) – vector cu 7 elemente

Se caută elementul pe poziția 4; acesta este 16, dar 21 > 16 și se continuă căutarea în partea dreaptă a vectorului (21, 45, 49).

Se caută elementul pe poziția 6; acesta este 45, dar 21 < 45 și se continuă căutarea în partea stângă a vectorului (21).

Se caută elementul pe poziția 5; acesta este 21, elementul a fost găsit.

Elementele cu care s-a realizat compararea au fost (16, 45, 21) – nu corespund cu valoarea indicată în enunț.

d) (16, 20, 21, 49, 50, 56, 59) – vector cu 7 elemente

Se caută elementul pe poziția 4; acesta este 49, dar 21 < 49 și se continuă căutarea în partea stângă a vectorului (16, 20, 21).

Se caută elementul pe poziția 2; acesta este 20, dar 21 > 20 și se continuă căutarea în partea dreaptă a vectorului (21).

Se caută elementul pe poziția 3; acesta este 21, elementul a fost găsit.

Elementele cu care s-a realizat compararea au fost (49, 20, 21) – nu corespund cu valoarea indicată în enunț.

Răspuns corect: b.

3. În rezolvarea problemei se presupune inițial că toate numerele citite sunt strict mai mici decât 2014 (ok=1), valoarea acesteia modificându-se la 0 în structura repetitivă cu număr cunoscut de pași de tip for în cazul în care s-a citit un număr în variabila x care nu respectă o astfel de condiție.

using namespace std;

#include <iostream>

int main() {
    int ok = 1, i, x;
    for (i = 1; i <= 10; i++) {
        cin >> x;
        if (x >= 2014) ok = 0;
    }
    cout << ok << endl;
    return 0;
}

Secvența poate fi optimizată în sensul opririi procesului de citire în condițiile în care s-a citit deja un număr mai mare sau egal cu 2014, citirea următoarelor numere nemodificând în nici un fel rezultatul:

for (i = 1; i <= 10 && ok; i++) {
    // ...
}

3. Acest subiect reprezintă o variantă simplificată a cerinței 5, subiectul II de la specializarea matematică-informatică, solicitându-se generarea numerelor pare nedivizibile cu 5 într-un vector în loc de o matrice.

Generarea numerelor pare nedivizibile cu 5 nu comportă probleme: se pornește de la valoarea 2 și se realizează incrementarea cu 2 atâta vreme cât valoarea obținută nu este divizibilă cu 5, altfel se trece mai departe. Valorile sunt completate în ordine, în vector, de la poziția cea mai mică spre poziția cea mai mare.

using namespace std;

#include <iostream>

int main() {
    int n, *vector, k, numar_curent = 2;
    do {
        cout << "n=";
        cin >> n;
    } while (n < 2 || n > 50);
    vector = new int [n];
    for (k = 0; k < n; k++) {
        while (numar_curent % 5 == 0)
            numar_curent += 2;
        vector[k] = numar_curent;
        numar_curent += 2;
    }
    for (k = 0; k < n; k++)
        cout << vector[k] << " ";
    cout << endl;
    delete[] vector;
    return 0;
}

4. Acest subiect reprezintă o variantă simplificată a celui omolog de la specializarea matematică-informatică, cerându-se doar determinarea numărului aflat pe o anumită poziție după identificarea valorilor distincte și sortarea acestora în ordine crescătoare.

a) O soluție eficientă trebuie să țină cont de formatul datelor din fișier, și anume puteri ale lui 10 mai mici sau egale cu 9. În acest sens, se poate construi un vector care să rețină, pentru fiecare putere în parte, dacă numărul corespunzător acesteia apare sau nu în fișier. Suma valorilor acestui vector reprezintă, astfel, numărul de valori distincte. Ulterior, numărul aflat pe poziția cerută este puterea pentru care suma aparițiilor (0 sau 1) de până la el este mai mică sau egală cu poziția respectivă.

Astfel, complexitatea algoritmului propus este O(1) – întrucât se parcurge un vector cu 10 elemente. În situația în care datele din fișier ar fi fost stocate ca atare într-un vector, și s-ar fi aplicat un algoritm de sortare clasic (quick-sort, de exemplu), eliminându-se valorile duplicate, complexitatea ar fi fost în medie O(nlogn) sau O(n2) în cazul cel mai defavorabil. De remarcat faptul că eficiența se manifestă nu doar în privința timpului de execuție, ci și a memoriei folosite întrucât se folosește un vector de întregi de 10 elemente (10*2octeți = 20 octeți); dacă s-ar fi reținut toate numerele din fișier, s-ar fi putut utiliza până la 106 * 4 octeți (variabile de tip long) ≅ 4 MB de memorie.

b)

using namespace std;

#define MAX 10

#include <iostream>
#include <fstream>

int numar_putere(long n) {
    int rezultat = 0;
    while (n != 1)
        if (n % 10 == 0) {
        rezultat++;
        n /= 10;
        }
        else
            return -1;
    return rezultat;
}

long putere_numar(int putere) {
    int rezultat = 1;
    while (putere) {
        rezultat *= 10;
        putere--;
    }
    return rezultat;
}

int main() {
    long n, numar_curent;
    int index, total = 0, *aparitii = new int[MAX];
    for (index = 0; index < MAX; index++)
        aparitii[index] = 0;
    // deschidere fisier
    ifstream fisier("bac.txt");
    if (fisier.is_open()) {
        fisier >> n;
        while (fisier >> numar_curent) {
            // determinare putere p a numarului de forma 10^p citit din fisier
            index = numar_putere(numar_curent);
            if (index != -1) { // numarul citit din fisier are forma corecta
                if (!aparitii[index])
                    // numarul de pe pozitia index nu a mai fost descoperit pana acum
                    // incrementare total de valori distincte
                    total++;
                // macare a numarului de pe pozitia index ca distinct
                aparitii[index] = 1;
            }
        }
        // inchidere fisier
        fisier.close();
    }
    if (total < n)
        cout << "Nu exista" << endl;
    else {
        index = 0;
        total = 0; // total valori distincte pana la indexul curent
        while (total < n) // nu s-a ajuns la pozitia cautata
            // incrementare total valori distincte, daca este cazul
            total += aparitii[index++];
        cout << putere_numar(--index) << endl;
    }
    delete[] aparitii;
    return 0;
}

Leave a Reply

Your email address will not be published.