Tag: bacalaureat 2014

Subiectele de matematică la examenul de bacalaureat național, sesiunea august 2014

Cu toate că și subiectele din sesiunea august 2014 ale probei de matematică (E.c) de la examenul de bacalaureat național, au avut un grad de dificultate ușor spre mediu (nici un exercițiu din cele propuse nu punea vreo dificultate, fiind vorba de probleme clasice, ce solicitau cel mult atenție la calcule), rata de promovabilitate a fost de numai 23,78%, dintre care cele mai multe medii (86,78%) au fost cuprinse între 6 – 6,99 [1]. În lipsa unor statistici mai detaliate, putem suspecta că matematica a fost una dintre disciplinele “responsabile” de un astfel de rezultat, ținând cont de faptul că din cei 92,67% candidați care au susținut examen la materia obligatorie a profilului, marea majoritate (87,90%) au trebuit să treacă de furcile caudine ale acestei probe [2].

Comparativ cu subiectele de la sesiunea iulie 2014, problemele propuse spre rezolvare la specializarea matematică-informatică au fost mult mai facile, implicând doar pe alocuri calcule ceva mai laborioase.

La, subiectul I (care ar trebui să acopere materia claselor IX-X), două dintre exerciții (punctele 2 și 4) puteau fi rezolvate chiar de un absolvent de gimnaziu și nu înțeleg motivul pentru a fi propuse la un astfel de nivel (altul decât de a înlesni promovarea). Problemele de geometrie au fost de asemenea banale și implicau egalarea unor termeni asemenea, respectiv aplicarea unei formule (teorema cosinusului) – pentru cei cu un spirit de observație deficitar.

Subiectele de algebră (II) s-au limitat la clasele X-XI și au evitat, și de această dată, elementele de combinatorică, binomul lui Newton, sistemele de ecuații, partea de inele și grupuri, care par a deveni “cenușăresele” matematicii de liceu, cel puțin din perspectiva profesorilor care alcătuiesc subiectele de examen.

Subiectele de analiză matematică (III) mi s-au părut mai echilibrate, cu toate că nu presupuneau nici un efort de ingeniozitate, fiind în mare parte exerciții de “manual”. De regulă, acestea făceau diferența între 8,50 și 10 însă probabil că pentru profilul de candidați de la această sesiune nu a fost cazul.

Probabil că persoanele din cadrul Centrului Național de Evaluare și Examinare sunt destul de plictisite, pentru că se observă deja o rutină în modul de elaborare al subiectelor. Poate că acestea ar trebui rotite în fiecare an, astfel încât să existe și elemente de noutate, care să provoace candidații să gândească,

rezolvari_bac2014(2)

Având în vedere că în toamnă susțin bacalaureatul mai ales cei respinși la sesiunea din vară sau absolvenții promoțiilor anterioare, procentul de reușiți (în creștere față de anul trecut cu 2,28%) nu mi se pare îngrijorător, ci mai degrabă proporțional cu interesul arătat față de acest examen. Prezența la orele de meditații organizate în licee pentru pregătirea bacalaureatului pe perioada verii a lăsat de dorit. Tocmai de aceea cred că astfel de rezultate ar trebui să reprezinte o pledoarie pentru desființarea acestei runde de examen. În acest fel, elevii vor fi și mai motivați să se pregătească pentru singurul examen organizat într-un an. Altfel, nu se justifică efortul, este doar o risipă de fonduri și resurse umane irosite…

PS. Subiectele (și baremele aferente) pentru probele de matematică și de istorie de la sesiunea iulie 2014 a examenului de bacalaureat pot fi descărcate de pe site-ul Ministerului Educației Naționale dedicat subiectelor la examenele naționale.

[1] REZULTATE BAC 2014: Ponderea candidaţilor care au luat bacalaureatul în toamnă a urcat la 23,78%, după contestaţii

[2] BACALAUREATUL DE TOAMNĂ: Probele scrise încep luni, peste 39.000 de candidaţi susţin examenul la limba română

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;
}

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

Filiera teoretică, profilul real, specializările matematică-informatică, matematică-informatică intensiv informatică.

Filiera vocațională, profilul militar, specializarea matematică-informatică.

 

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)


1. Dacă variabila x este de tip întreg, operatorul % calculează restul împărțirii întregi dintre cei doi operanzi, iar la împărțirea cu 7 restul maxim care se poate obține este 6.

Precizarea faptului că variabila x poate memora un număr natural cu cel mult două cifre nu are nici un fel de relevanță pentru enunțul problemei. Aceasta ar fi putut să îl pună pe candidat în dificultate în condițiile în care acesta ar fi considerat că valoarea maximă a expresiei x%7 se obține pentru valoarea maximă a lui x (în acest caz 99), însă variantele de răspuns în aceste condiții ar fi trebuit să fie altele.

Răspunsul corect este a.

2. a) Este lesne de observat faptul că programul citește numere naturale în variabla x până la întâlnirea lui 0, verificând pentru fiecare în parte dacă face parte din șirul lui Fibonacci (xn = xn-1 + xn-2, x0=0, x1=1) și determinând numărul de ocurențe ale acestora.

n ← 0

1) x ← 10

a ← 0, b ← 1

iterația 1 a ciclului repetă … până când

    c ← 1

    a ← 1

    b ← 1

iterația 2 a ciclului repetă … până când

    c ← 2

    a ← 1

    b ← 2

iterația 3 a ciclului repetă … până când

    c ← 3

    a ← 2

    b ← 3

iterația 4 a ciclului repetă … până când

    c ← 5

    a ← 3

    b ← 5

iterația 5 a ciclului repetă … până când

    c ← 8

    a ← 5

    b ← 8

iterația 6 a ciclului repetă … până când

    c ← 13

    a ← 8

    b ← 13

încheierea ciclului repetă … până când (13 ≥ 10)

c ≠ x (13 ≠ 10) ⇒ n rămâne 0

2) x ← 8, se repetă primele 5 iterații ale ciclului repetă … până când de mai sus, c ← 8 și c = x, iar n devine 1

3) x ← 11, se repetă primele 6 iterații ale ciclului repetă … până când de mai sus, c ← 13 și c ≠ x, iar n rămâne 1

4) x ← 1, se repetă prima iterație a ciclului repetă … până când de mai sus, c ← 1 și c = x, iar n devine 2

5) x ← 21, se repetă primele 7 iterații a ciclului repetă … până când de mai sus, c ← 21 și c = x, iar n devine 3

6) x ← 0, se repetă prima iterație a ciclului repetă … până când de mai sus, c ← 1 și c ≠ x, iar n rămâne 3

Se afișează 3.

b) Trebuie identificate acele patru numere din intervalul [0, 9] care nu fac parte din șirul lui Fibonacci, astfel încât contorul care numără ocurențele numerelor cu această proprietate să rămână 0.

Numerele din șirul lui Fibonacci din intervalul [0, 9] sunt: 0, 1, 2, 3, 5, 8. Prin urmare, ar trebui citite 4, 6, 7, 9. De asemenea, poate fi citit și 0 întrucât valoarea minimă a lui c (pentru care se verifică apartenența la șirul lui Fibonacci) este 1.

c) Algoritmul se transformă foarte facil prin citirea lui x de două ori:

– inițial, în afara ciclului cât timp x≠0

– la fiecare iterație (la final) a ciclului cât timp x≠0 – când se citește o valoare nulă în variabila x nu mai este necesar să se execute instrucțiunile din cadrul ciclului pentru că acestea nu produc o modificare a rezultatului final (valoarea reținută în variabila n)

n ← 0

citește x (număr natural)

cât timp x≠0

    a ← 0

    b ← 1

    repetă

        c ← a + b

        a ← b

        b ← c

    până când c ≥ x

    dacă x=c atunci

        n ← n + 1

    citește x

scrie n

d) Pentru implementarea algoritmului C/C++ corespunzător, trebuie transformate condițiile ciclului repetitiv cu test final repetă … până când prin negarea lor logică, astfel încât să fie adecvate instrucțiunii do … while:

  • c≥x devine c<x;
  • x=0 devine x≠0.
using namespace std;

#include <iostream>

int main() {
    int n = 0, x, a, b, c;
    do {
        cin >> x;
        a = 0; b = 1;
        do {
            c = a + b;
            a = b;
            b = c;
        } while (c < x);
        if (x == c) n++;
    } while (x != 0);
    cout << n << endl;
    return 0;
}

SUBIECTUL II (30 de puncte)


1. În Figura 1 sunt reprezentați arborii reprezentați prin vectorul de tați din variantele de răspuns, observându-se că structura de la varianta de răspuns b) nu este un arbore, ci un graf:

 BAC2014MI2_II1 Figura 1

Răspuns corect b.

2. Numărul de muchii ale unui graf neorientat complet cu n noduri este n(n-1)/2.

În cazul de față, numărul de muchii al unui graf neorientat complet cu 9 noduri este 9*8/2 = 36 muchii.

Se va elimina un număr maxim de muchii în cazul în care graful neorientat complet se împarte în două componente conexe (la rândul lor grafuri neorientate complete) cât mai echilibrate.

În cazul de față, o componentă conexă va avea 5 noduri, deci 5*4/2 = 10 muchii, iar cealaltă 4 noduri, deci 4*3/2 = 6 muchii, în total 16 muchii. Se observă astfel că s-au eliminat 36 – 16 = 20 muchii, număr maxim de muchii ce pot fi eliminate cu păstrarea conexității și completitudinii componentelor obținute.

În Figura 2 sunt reprezentate atât graful inițial cât și cele două componente conexe ale grafului obținut prin eliminarea unui număr maxim de muchii:

BAC2014MI2_II2aBAC2014MI2_II2bFigura 2

Răspuns corect c.

3. Un drum elementar în graf între vârful 4 și vârful 6 este o secvență de vârfuri (x4, …, x6) cu proprietatea că între oricare două vârfuri xi și xj din secvență există o muchie și fiecare vârf xk este conținut o singură dată.

În Figura 3 este reprezentat graful precum și drumul elementar între vârful 4 și vârful 6: (4, 5, 2, 6).

BAC2014MI2_II3Figura 3

 4. strlen(s)=11, deci se afișează valoarea 11

i=0, s[0]=’B’, nu se gaseste in sirul “EAIOU”, si nu se realizeaza nici o modificare

i=1, s[1]=’A’, se gaseste in sirul “EAIOU”, la adresa s+2 se copiază șirul ALAUREAT ⇒ șirul s va conține BAALAUREAT (strlen(s)=10)

i=2, s[2]=’A’, se gaseste in sirul “EAIOU”, la adresa s+3 se copiază șirul AUREAT ⇒ șirul s va conține BAAAUREAT (strlen(s)=9)

i=3, s[3]=’A’, se gaseste in sirul “EAIOU”, la adresa s+4 se copiază șirul REAT ⇒ șirul s va conține BAAAREAT (strlen(s)=8)

i=4, s[4]=’R’, nu se gaseste in sirul “EAIOU”, nu se realizează nici o modificare

i=5, s[5]=’E’, se gaseste in sirul “EAIOU”, la adresa s+6 se copiază șirul T ⇒ șirul s va conține BAAARET (strlen(s)=7)

i=6, s[6]=’T’, nu se gaseste in sirul “EAIOU”, nu se realizează nici o modificare

se afișează BAAARET

Răspunsul corect este:

11BAAARET

5. Se generează toate numerele pare începând cu 2 (prin adunare cu 2), trecându-se la următorul număr par în cazul în care acesta este divizibil cu 5. Aceste valori sunt completate în matrice, în ordine, parcurgându-se liniile de la stânga la dreapta și coloanele de sus în jos.

Pentru afișarea cu format în C++ s-a utilizat biblioteca iomanip.

using namespace std;

#define SPACING 2

#include <iostream>
#include <iomanip>

int main() {
    int m, n, **matrice, i, j, k, numar_curent=2;
    do {
        cout << "m=";
        cin >> m;
    } while (m < 2 || m > 20);
    do {
        cout << "n=";
        cin >> n;
    } while (n < 2 || n > 20);
    matrice = new int*[m];
    for (k = 0; k < m; k++)
        matrice[k] = new int[n];
    for (i = 0; i < m; i++)
        for (j = 0; j < n; j++) {
            while (numar_curent % 5 == 0)
                numar_curent += 2;
            matrice[i][j] = numar_curent;
            numar_curent += 2;
        }
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++)
            cout << setw(SPACING) << matrice[i][j] << " ";
        cout << endl;
    }
    for (k = 0; k < m; k++)
        delete[] matrice[k];
    delete[] matrice;
    return 0;
}

SUBIECTUL III (30 de puncte)


1. O variantă mai facilă de abordare a acestui subiect este de a vedea care sunt soluțiile generate prin metoda backtracking imediat după fiecare dintre variantele de răspuns propuse, verificând care dintre acestea corespund soluției din enunț.

a) (rock, jazz, house, latino, pop) – se observă că nu este soluție întrucât genul latino nu precede genul house;

b) (rock, jazz, latino, house, pop)

Următoarea soluție se obține inversând ordinea ultimelor două genuri de muzică din vârful stivei: (rock, jazz, latino, pop, house), care nu coincide însă cu soluția din enunț.

c) (pop, latino, rock, house, jazz)

Următoarea soluție se obține reconstruind valorile aflate pe ultimele trei niveluri din vârful stivei.

Pe poziția 3, următoarea valoare (în ordinea celor din mulțimea inițială, care nu au fost încercate încă) este house (imediat următoare după rock – din soluția anterioară).

Pe pozițiile 4 și 5 se trec valorile rămase, în ordinea în care apar în mulțimea inițială: jazz, rock.

Următoarea soluție este așadar (pop, latino, house, jazz, rock), care coincide cu soluția din enunț.

d) (pop, rock, latino, house, jazz)

Următoarea soluție se obține reconstruind valorile aflate pe ultimele patru niveluri din vârful stivei.

Pe poziția 2, următoarea valoare (în ordinea celor din mulțimea inițială, care nu au fost încercate încă) este latino (imediat următoare după rock – din soluția anterioară).

Pe pozițiile 3, 4 și 5 se trec valorile rămase, în ordinea în care apar în mulțimea inițială: jazz, rock, house.

Următoarea soluție este așadar (pop, latino, jazz, rock, house), care nu coincide însă cu soluția din enunț.

Răspuns corect c.

2. Este evident că funcția f calculează cel mai mare divizor comun dintre numerele a și b folosind algoritmul lui Euclid (implementarea recursivă), varianta împărțirii succesive lui a la b.

Prin urmare, problema cere determinarea unui număr x ∈ [1, 50] astfel încât cmmdc(30, x)=5.

Astfel, valori posibile ale lui x sunt: 5, 25, 35.

3. Se genereză perechi de numere (x, y) cu x ∈ [0, n] și y ∈ [x+1, n] (pentru a se asigura relația de precedență x<y), după care se verifică dacă există un z (y<z) care să verifice relația x*y+y*z=n.

Cu alte cuvinte, z = (n – x * y) / y, trebuie să fie număr întreg (restul împărțirii lui n – x * y la y trebuie să fie 0) și trebuie să fie mai mare decât y.

using namespace std;

#include <iostream>

void triplete(int n) {
    int x, y, z;
    for (x = 0; x <= n; x++)
        for (y = x + 1; y <= n; y++) 
            if ((n - x * y) % y == 0 && (n - x * y) / y > y)
                cout << "(" << x << "," << y << "," << (n - x * y) / y << ")" << endl;
}

int main() {
    int n;
    do {
        cout << "n=";
        cin >> n;
    } while (n < 2 || n>10000);
    triplete(n);
    return 0;
}

4. 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, numărul de ocurențe. Ulterior, numărul aflat pe poziția cerută este puterea pentru care suma ocurențelor 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), 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) Algoritmul nu pune probleme de implementare.

S-au definit două funcții ajutătoare:

  • numar_putere – determină ce putere a lui 10 este un numar n dat ca parametru sau -1 dacă numărul nu este putere a lui 10;
  • putere_numar – determină numărul obținut prin ridicarea lui 10 la puterea dată ca parametru.

După citirea numerelor din fișier și construirea vectorului de ocurențe, se caută poziția la care suma ocurențelor de până la ea depășește indexul citit pentru a se determina numărul din șirul ordonat căutat.

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, *ocurente = new int[MAX];
    for (index = 0; index < MAX; index++)
        ocurente[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
                // incrementare numar de ocurente a numarului citit din fisier
                ocurente[numar_putere(numar_curent)]++;
                // total de numere citite din fisier
                total++;
            }
        }
        // inchidere fisier
        fisier.close();
    }
    if (total < n)
        cout << "Nu exista" << endl;
    else {
        index = 0;
        total = 0; // total de numere pana la indexul curent
        while (total < n) // nu s-a ajuns la pozitia cautata
            // adaugare numar de ocurente de pe pozitia curenta
            total += ocurente[index++]; 
        cout << putere_numar(--index) << endl;
    }
    delete[] ocurente;
    return 0;
}

Rezolvarea subiectelor de informatică de la examenul de bacalaureat național, sesiunea iulie 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. Subiectul urmărește să verifice cunoașterea funcțiilor predefinite din limbajul C/C++ (abs) precum și abilități cu privire la rezolvarea unor probleme.

Pentru x ∈ [45, 55], valorile pe care le poate lua expresia x/10 sunt 4 (pentru x ∈ [45, 49]) sau 5 (pentru x ∈ [50, 55]) iar ale expresiei x%10 pot fi cuprinse între 0 (pentru x=50) și 9 (pentru x=49). Așadar, diferența maximă dintre cele două expresii (în modul) poate fi 5, aceasta obținându-se atât pentru x=49 (abs(4-9)=5) cât și pentru x=50(abs(5-0)=0).

Răspunsul corect este b.

 

2. Prin acest exercițiu se dorește să se verifice capacitatea de înțelegere a unui algoritm precum și posibilitatea de completare a acestuia.

În enunț se precizează faptul că m>n, cu alte cuvinte m-n>0. De asemenea, se observă că pe fiecare iterație a instrucțiunii repetitive cu test final x este incrementat cu 1, y este decrementat cu 1, astfel încât diferența x-y va fi incrementată cu 2. Pentru a se satisface condiția de terminare a ciclului repetitiv (x<y ⇔ x-y<0), trebuie să se realizeze un număr de iterații egal cu:

a) (m-n)/2, dacă n-m este par, astfel încât diferența inițială (negativă) n-m (valoarea lui x-y) să fie anulată (la sfârșitul ciclului repetitiv cu test final x=y)

În aceste condiții r=m-n (după înmulțirea cu 2) numai dacă r reflectă numărul de iterații ale ciclului repetitiv cu test final, adică r = r + 1

b) (m-n)/2 + 1, dacă n-m este impar, astfel încât diferența inițială (negativă) n-m (valoarea lui x-y) să fie devină pozitivă (la sfârșitul ciclului repetitiv cu test final x = y + 1)

În aceste condiții r=m-n(+1) (după înmulțirea cu 2 și decrementarea în urma testului de egalitate dintre x și y – din rezultat ar fi trebuit să se scadă 2 și nu 1) numai dacă r reflectă numărul de iterații ale ciclului repetitiv cu test final, adică r = r + 1

Răspunsul corect este c.

 

3. Acest subiect reprezintă o variantă a celui omolog de la specializarea matematică-informatică, propunându-și să verifice capacitatea unui elev de a elabora un algoritm relativ simplu. Nu este testată capacitatea elevului de a lucra cu structuri de date.

Și pentru această problemă trebuie tratate cele trei cazuri:

a) minutul de start este mai mic decât minutul de stop (momentul de start este anterior momentului de stop) ⇒ rezultat acceptat;

b) minutul de start este egal cu minutul de stop:

    1. secunda de start este mai mică decât secunda de stop (momentul de start este anterior momentului de stop) ⇒ rezultat acceptat;

    2. secunda de start este egală sau mai mare decât secunda de stop (momentul de start coincide cu momentul de stop sau este ulterior momentului de stop) ⇒ rezultat respins.

c) minutul de start este mai mare cu minutul de stop (momentul de start este ulterior momentului de stop) ⇒ rezultat respins.

using namespace std;

#include <iostream>

int main() {
    int minut_start, secunda_start, minut_stop, secunda_stop;
    cout<<“start”<<endl;
    cout<<“minut:”; cin>>minut_start;
    cout<<“secunda:”; cin>>secunda_start;
    cout<<“stop”<<endl;
    cout<<“minut:”; cin>>minut_stop;
    cout<<“secunda:”; cin>>secunda_stop;
    if (minut_start<minut_stop)
        cout<<“acceptat”<<endl;
    else if (minut_start==minut_stop) {
        if (secunda_start<secunda_stop)
            cout<<“acceptat”<<endl;
        else
            cout<<“respins”<<endl;
    } else if (minut_start>minut_stop)
        cout<<“respins”<<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) Este evident că trebuie respectate simultan condițiile:

  • n! ∈ [a, b]
  • (n-1)! ∉ [a, b]
  • (n+1)! ∉ [a, b]
  • b-a maxim

de unde rezultă automat faptul că a = (n-1)! + 1 și b=(n+1)! – 1.

Algoritmul în pseudocod este următorul:

citește n

factorial ← 1

pentru contor = 2, n-1

    factorial ← factorial * contor

a ← factorial + 1

b ← factorial * n * (n + 1) – 1

afișează a, b

b) Datele de intrare sunt n, care trebuie să respecte condiția de a face parte din intervalul [2, 10].

Datele de ieșire sunt a și b, reprezentând limita inferioară, respectiv limita superioară a intervalului factorial.

A fost utilizată o variabilă contor, pentru a indica iterația curentă în ciclul repetitiv cu număr cunoscut de pași și variabila factorial, în care se calculează valoarea (n-1)!, utilizată ulterior pentru determinarea limitei inferioare, respectiv a limitei superioare a intervalului factorial.

Având formulele pentru limita inferioară, respectiv limita superioară determinate mai sus, algoritmul nu trebuie decât să calculeze (n-1)! (printr-un algoritm iterativ, folosind un ciclu repetitiv cu număr cunoscut de pași – factorial = 1 * 2 * … * (n-1)) și pe baza sa a (n+1)! care sunt ulterior incrementate, respectiv decrementate pentru a se obține valorile dorite.

 

SUBIECTUL III (30 de puncte)


1. Interclasarea a doi vectori presupune introducerea elementelor unui vector neordonat între elementele unui vector ordonat (de obicei crescător), astfel încât după această operație să se mențină proprietatea de ordine între elementele vectorului rezultat (xi < xj, ∀i<j).

În cazul de față se cunosc A = (4, 11, 14, 18, 21) și A ∪ B = (3, 4, 8, 11, 14, 14, 17, 18, 21, 46). Pentru determinarea vectorului B, trebuie realizată operația de diferență dintre A ∪ B și A.

Procedând astfel, se obține că B = (A ∪ B) \ A = (3, 4, 8, 11, 14, 14, 17, 18, 21, 46) \ (4, 11, 14, 18, 21) = (3, 8, 14, 17, 46). Acestea sunt valorile pe care vectorul B trebuie să le conțină, nu neapărat în această ordine, întrucât sortarea se realizează în cadrul operației de interclasare, fiecare element din B fiind plasat în A ∪ B pe poziția corespunzătoare, astfel încât să se mențină proprietatea de ordine.

Dintre toate variantele de răspuns, se observă că doar varianta b conține toate elementele vectorului B și numai pe cele aparținându-i acestuia.

 

2. Exercițiul reprezintă o problemă clasică de căutare a unei valori într-o mulțime neordonată.

În secvența dată se citesc 10 valori de la tastatură și se cere ca variabila ok să rețină rezultatul căutării (0 dacă valoarea nu face parte din mulțime, 1 dacă aceasta este identificată printre elementele mulțimii).

Prin urmare, valoarea ok va fi inițializată cu 0 (inițial, valoarea nu a fost găsită), urmând ca în ciclul repetitiv cu număr cunoscut de pași să se modifice valoarea acesteia (în 1) în condițiile în care, în urma unui instrucțiuni de tip decizional, elementul citit este identificat ca fiind cel căutat.

ok = 0; // elementul nu a fost gasit printre valorile citite

for(i = 1; i <= 10; i++) {

    cin>>x;

    if (x == 2014)

        ok = 1; // elementul a fost gasit printre valorile citite

}

 

3. Subiectul vizează verificarea modului de lucru cu tablouri (citire, scriere, indexare, modificare a valorilor conform unei condiții). De asemenea, deși baremul nu o precizează explicit, ar trebui urmărit modul de alocare / dealocare (dinamică) a memoriei pentru tablou, respectiv verificarea restricțiilor precizate în enunț pentru datele de intrare (n și x cuprinse între anumite valori, elementele vectorului de maxim 4 cifre, minim un element par în vector).

Prin urmare, algoritmul:

  • va citi variabila n, urmărind respectarea restricțiilor specificate în enunț;
  • va aloca tabloul dinamic (pentru fix atâtea elemente câte urmează să fie citite);
  • va citi fiecare element al tabloului, într-o secvență repetitivă cu număr cunoscut de pași, verificând, pentru fiecare în parte, dacă a fost respectat criteriul de validare
  1. pentru fiecare element al tabloului în parte, să aibă maxim 4 cifre (să fie mai mic decât 10000);
  2. doar la ultimul element, să fie existat anterior cel puțin un element par (restul împărțirii la 2 să fie 0) – întânirea unui astfel de element se face pentru fiecare element al tabloului care respectă criteriul de validare;
  • va citi variabila x, urmărind respectarea restricțiilor specificate în enunț;
  • va parcurge tabloul, scăzând valoarea x din elementul curent în cazul în care acesta este par;
  • va scrie fiecare element al tabloului, acesta fiind separat de celelalte printr-un spațiu;
  • va dealoca spațiul de memorie rezervat pentru tablou.

using namespace std;

#include <iostream>

int main() {
    int n, *vector, x, contor, par = 0;
    do {
        cout<<“n=”;
        cin>>n;
    } while (n <= 2 || n >= 50);
    vector = new int[n];
    for (contor=0; contor < n; contor++) {
        int conditie = 0;
        do {
            cout<<“vector[“<<(contor+1)<<“]=”;
            cin>>vector[contor];
            if (vector[contor] < 10000) {
                if (vector[contor] % 2 == 0)
                    par = 1;
                if (contor == (n – 1)) {
                    if (par)
                        conditie = 1;
                }
                else
                    conditie = 1;
            }
        } while (!conditie);
    }
    do {
        cout<<“x=”;
        cin>>x;
    } while (x <= 0 || x >= 10);
    for (contor = 0; contor < n; contor++)
        if (vector[contor] %2 == 0)
            vector[contor] -= x;
    for (contor = 0; contor < n; contor++)
        cout<<vector[contor]<<” “;
    cout<<endl;
    delete vector;
    return 0;
}

 

4. Acest subiect reprezintă o variantă simplificată a  celui omolog de la specializarea matematică-informatică, solicitându-se identificarea cifrelor cu apariție maximă, nu a subnumerelor (de 2 cifre).

a) Se determină toate cifrele unui număr (ca rest al împărțirii la 10 al acestuia), eliminându-se succesiv ultima cifră (prin împărțirea sa la 10) până când acesta devine nul (nu mai conține cifre). Valorile cifrelor și numărul de apariții al fiecărui subnumăr va fi contorizat în cadrul a doi vectori, unul care reține valorile (cifre), iar celălalt care stochează numărul de apariții (ocurente). De fiecare dată se verifică, prin căutare, dacă cifra respectivă există anterior. (S-ar fi putut inițializa un vector cu 10 elemente corespunzătoare fiecărei cifre de la 0 la 9, eliminându-se altfel vectorul care reține cifrele propriu-zise precum și căutarea care se realizează de fiecare dată pentru a se verifica dacă cifra respectivă există sau nu). Se determină maximul numărului de ocurențe și valoarea (valorile) corespunzătoare acestui maxim se afișează.

Complexitatea algoritmului propus este O(n) întrucât vectorul este parcurs de 2 ori, odată pentru determinarea cifrelor și odată pentru determinarea maximului numărului de ocurențe (stocarea valorilor cifrelor în vector presupune și ea o parcurgere pentru căutare, însă și aceasta se realizează tot în timp liniar și poate fi eliminată prin varianta amintită).

b)

Soluția 1:

using namespace std;

#include <iostream>
#include <fstream>

#define MAX 10 // pot fi maxim 10 cifre, insa nu este obligatoriu ca toate sa se regaseasca in fisier

int main() {
    long numar;
    // vectori ce contin
    // – valorile cifrelor aferente numerelor din fisier
    // – numarul de aparitii pentru fiecare cifra
    int *cifre, *ocurente, dimensiune = 0;
    // alocare memorie
    cifre = new int[MAX];
    ocurente = new int[MAX];
    // deschidere fisier
    ifstream fisier(“bac.txt”);
    if (fisier.is_open()) {
        // citire numar din fisier
        while (fisier>>numar) {
            while (numar != 0) {
                // determinare cifra
                int cifra = numar % 10, gasit = 0;
                // cautare cifra in vector
                for (int contor = 0; contor < dimensiune && !gasit; contor++)
                    // cifra a fost gasita in vector, se incrementeaza numarul de ocurente
                    if (cifre[contor] == cifra) {
                        ocurente[contor]++;
                        gasit = 1;
                    }
                // cifra nu a fost gasit in vector, se stocheaza (numarul de ocurente este 1)
                if (!gasit) {
                    cifre[dimensiune] = cifra;
                    ocurente[dimensiune] = 1;
                    dimensiune++;
                }
                numar /= 10;
            }
        }
        // inchidere fisier
        fisier.close();
    }
    // determinare numar maxim de ocurente
    int maxim = 1;
    for (int contor = 0; contor < dimensiune; contor++)
        if (ocurente[contor] >= maxim)
            maxim = ocurente[contor];
    // afisarea subnumerelor care apar de cele mai multe ori
    for (int contor = 0; contor < dimensiune; contor++)
        if (ocurente[contor] == maxim)
            cout<<cifre[contor]<<” “;
    cout<<endl;
    // dealocare memorie
    delete cifre;
    delete ocurente;
    cin>>maxim;
    return 0;
}

Soluția 2:

using namespace std;

#include <iostream>
#include <fstream>

#define MAX 10 // pot fi maxim 10 cifre, insa nu este obligatoriu ca toate sa se regaseasca in fisier

int main() {
    long numar;
    // vector ce contine numarul de aparitii pentru fiecare cifra
    // ocurente[i] – numarul de aparitii pentru cifra i, i=0..9
    int *ocurente, dimensiune = 0;
    // alocare memorie
    ocurente = new int[MAX];
    for (int contor = 0; contor < MAX; contor++)
        ocurente[contor] = 0;
    // deschidere fisier
    ifstream fisier(“bac.txt”);
    if (fisier.is_open()) {
        // citire numar din fisier
        while (fisier>>numar) {
            while (numar != 0) {
                // determinare cifra
                int cifra = numar % 10;
                // incrementarea numarului de ocurente pentru cifra curenta
                ocurente[cifra]++;
                numar /= 10;
            }
        }
        // inchidere fisier
        fisier.close();
    }
    // determinare numar maxim de ocurente
    int maxim = 1;
    for (int contor = 0; contor < MAX; contor++)
        if (ocurente[contor] >= maxim)
            maxim = ocurente[contor];
    // afisarea subnumerelor care apar de cele mai multe ori
    for (int contor = 0; contor < MAX; contor++)
        if (ocurente[contor] == maxim)
            cout<<contor<<” “;
    cout<<endl;
    // dealocare memorie
    delete ocurente;
    return 0;
}

Subiectele de matematică la examenul de bacalaureat național, sesiunea iulie 2014

Subiectele de la proba de matematică (E.c) de la examenul de bacalaureat național, sesiunea iulie 2014, au avut un grad de dificultate sub medie, fapt demonstrat și de numărul mare de medii de 10 (nu mai puțin de 108 la nivelul întregii țări!!!) înregistrate anul acesta. Nu mai puțin adevărat este faptul că există și un îngrijorător procent de candidați respinși (puțin peste 40%), care nu ar fi avut nici un motiv să nu obțină o notă de promovare în condițiile în care subiectele formulate nu ar fi trebuit să pună nici un fel de probleme. Este păcat că site-ul Ministerului Educației Naționale pe care sunt publicate rezultatele la examenul de bacalaureat nu oferă instrumente mai avansate pentru realizarea de statistici pentru fiecare disciplină în parte, spre exemplu.

Matematica este, de câțiva ani, disciplina obligatorie pentru elevii care au absolvit profilul real, corespondenta istoriei pentru elevii care au urmat cursurile aferente profilului uman. Ar merita menționat faptul că în timp ce la istorie, competențele specifice și conținuturile evaluate fac parte exclusiv din programa analitică a clasei a XII-a, la matematică sunt verificate cunoștințele din toți cei patru ani de liceu. În plus, matematica nu se poate deprinde doar pe parcursul unui an școlar (sau mai puțin), presupune acumulare continuă (datorită interdependenței dintre algebră, analiză matematică, geometrie și trigonometrie) și exercițiu susținut, pentru formarea experienței de lucru. Din acest punct de vedere, absolvenții profilului real sunt evident dezavantajați și nu înțeleg de ce Ministerul Educației Naționale perpetuează această stare de lucruri.

Revenind strict la subiectele propuse spre rezolvare în acest an, ele puteau fi rezolvate în mai puțin de o oră din cele 3 și pe cel mult patru pagini. Nu a existat nici măcar un subiect care să testeze ingeniozitatea elevului, care să îl forțeze să fie original, să propună o metodă de rezolvare inovativă. S-au preferat exerciții clasice, la care elevii erau solicitați să aplice o formulă sau cel mult o metodă de lucru cât se poate de convențională.

Nu cunosc conținutul celorlalte variante, însă este îngrijorător faptul că lipsesc din cunoștințele evaluate elementele de combinatorică, limitele de șiruri, reprezentarea grafică a unei funcții (prilej cu care se putea verifica abilitatea de a aplica teorema lui Lagrange, Rolle, Fermat), inelele și grupurile (subiect ce putea fi combinat lejer cu unul dintre exercițiile legate de polinoame / sisteme de ecuații), aplicațiile primitivelor pentru calculul de arii. Sigur că în formatul curent al probei de matematică nu pot fi propuse exerciții care să acopere întreaga programă analitică, însă cunoștințele esențiale trebuie incluse și, așa cum am arătat mai sus, anumite elemente pot fi combinate astfel încât un subiect să implice mai multe competențe specifice / conținuturi simultan.

rezolvari_bac2014

Foarte probabil, au existat numeroase motive care au concurat la elaborarea unor astfel de subiecte: faptul că ne aflăm într-un an electoral, iar absolvenții de liceu tocmai au împlinit vârsta necesară pentru a putea vota, numărul mare de locuri în învățământul universtar (de stat sau particular) la care accesul este condiționat de promovarea examenului de bacalaureat, acestea trebuind ocupate pentru a asigura locul de muncă al cadrelor didactice ce își desfășoară activitatea în respectivele instituții de învățământ (și de ce nu, prosperitatea facultății / universității respective), “spălarea” imaginii pe care învâțământul românesc îl are în fața opiniei publice prin niște rezultate care nu reflectă realitatea… O complicitate tacită din care singurii care au de pierdut sunt elevii, chiar dacă pe moment nu conștientizează acest lucru.

Una peste alta, este îngrijorător faptul că scăderea exigențelor la un examen care se dorește să fie al maturității nu este deloc proporțională cu creșterea promovabilității, care, de ceva vreme, se încăpățânează să stagneze uneva între 50-60%.

PS. Subiectele (și baremele aferente) pentru probele de matematică și de istorie de la sesiunea iulie 2014 a examenului de bacalaureat pot fi descărcate de pe site-ul Ministerului Educației Naționale dedicat subiectelor la examenele naționale.

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

Filiera teoretică, profilul real, specializările: matematică-informatică, matematică-informatică intensiv informatică

Filiera vocațională, profilul militar, specializarea matematică-informatică

 

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)


1. Subiectul își propune să verifice cunoașterea ordinii precedenței operatorilor în C/C++ precum și rezultatul operațiilor cu întregi. Operatorii * și / au aceeași precedență, deci evaluarea expresiei se face de la stânga la dreapta:
42/10*29/10=4*29/10=116/10=11
Răspunsul corect este c.

 

2. Algoritmul descris în pseudocod este:

citește n (număr natural nenul)

d ← 2

cât timp d ≤ n execută

    p ← 0

    cât timp n%d=0 execută (pentru dezambiguizare, mai corect ar fi fost n%d==0)

        p ← p + 1

        n ← [n / d]

    dacă p%2=0 și p≠0 atunci

        scrie d, ‘ ‘

    d ← d + 1

scrie n

a) În cazul în care se citește n = 2352, execuția algoritmului este următoarea:

d ← 2

2 ≤ 2352

    iterația 1 a primului ciclu cât timp

       p ← 0

       2352%2=0

          iterația 1 a celui de-al doilea ciclu cât timp

             p ← 1

             n ← 1176

       1176%2=0

          iterația 2 a celui de-al doilea ciclu cât timp

             p ← 2

             n ← 588

       588%2=0

          iterația 3 a celui de-al doilea ciclu cât timp

             p ← 3

             n ← 294

       294%2=0

          iterația 4 a celui de-al doilea ciclu cât timp

             p ← 4

             n ← 147

       147%2≠0

       4%2=0 și 4≠0

          scrie 2, ‘ ‘

d ← 3

3 ≤ 147

    iterația 2 a primului ciclu cât timp

       p ← 0

       147%3=0

          iterația 1 a celui de-al doilea ciclu cât timp

             p ← 1

             n ← 49

       49%3≠0

       1%2≠0

d ← 4

4 ≤ 49

    iterația 3 a primului ciclu cât timp

       p ← 0

       49%4≠0

       p%2=0, dar p=0

d ← 5

5 ≤ 49

    iterația 4 a primului ciclu cât timp

       p ← 0

       49%5≠0

       p%2=0, dar p=0

d ← 6

6 ≤ 49

    iterația 5 a primului ciclu cât timp

       p ← 0

       49%6≠0

       p%2=0, dar p=0

d ← 7

7 ≤ 49

    iterația 6 a primului ciclu cât timp

       p ← 0

       49%7=0

          iterația 1 a celui de-al doilea ciclu cât timp

             p ← 1

             n ← 7

       7%7=0

          iterația 2 a celui de-al doilea ciclu cât timp

          p ← 2

          n ← 1

       1%7≠0

       2%2=0 și 2≠0

          scrie 7, ‘ ‘

d ← 8

8 > 1

scrie 1

Așadar, în urma execuției algoritmului se va afișa 2 7 1.

Se observă că algoritmul determină divizorii numărului n nenul, citit de la tastatură, afișându-i doar pe aceea care apar la puteri pare în descompunerea în factori primi.

Algoritmul nu este unul eficient întrucât verifică divizorii secvențial, fără a ține cont de faptul că unii dintre aceștia, nefiind primi, au mai fost testați în iterațiile anterioare ale structurii repetitive cât timp (de exemplu 4=22, 6=2*3).

b) Pentru a se afișa valoarea 5, înseamnă că numărul respectiv trebuie să fie o putere pară a lui 5, iar 5 trebuie să fie singurul său divizor sau 5 trebuie să fie singurul său divizor aflat la o putere pară.

Dacă puterea pară este p = 2, numărul va fi un multiplu de 52=25, ceea ce satisface condiția ca numărul  să aibă maxim două cifre.

Dacă puterea pară este p = 4 sau mai mare, numărul va fi un multiplu de 54=625 sau mai mult, ceea ce nu mai satisface condiția ca numărul  să aibă maxim două cifre.

Așadar, numerele cerute pot fi 25*1=25, 25*2=50, 25*3=75, alte valori nemairespectând condiția ca numărul să fie format din maxim două cifre.

c) Alte structuri repetitive cunoscute sunt execută … cât timp (structură repetitivă cu test final) respectiv pentru (structură repetitivă cu număr cunoscut de pași).

Soluția 1 (structură repetitivă cu test final) – verificarea inițială se face printr-o instrucțiune de tip dacă

citește n (număr natural nenul)

d ← 2

dacă d ≤ n

    execută

        p ← 0

        cât timp n%d=0 execută

            p ← p + 1

            n ← [n / d]

        dacă p%2=0 și p≠0 atunci

            scrie d, ‘ ‘

        d ← d + 1

    cât timp d ≤ n

scrie n

Soluția 2 (structură repetitivă cu număr cunoscut de pași) – are avantajul că este mai comprimată, conținând în sine inițializarea inițială, condiția de trecere la iterația următoare precum și pasul de incrementare.

citește n (număr natural nenul)

pentru d ← 2, d ≤ n, d ← d + 1 execută

    p ← 0

    cât timp n%d=0 execută

        p ← p + 1

        n ← [n / d]

    dacă p%2=0 și p≠0 atunci

        scrie d, ‘ ‘

scrie n

d) Implementarea algoritmului dat în C/C++ nu pune probleme majore:

using namespace std;

#include <iostream>

int main() {
    int n, d=2;
    cout<<"n="; cin>>n;
    while (d<=n) {
        int p=0;
        while (n%d==0) {
            p++;
            n/=d;
        }
        if (p%2==0 && p) cout<<d<<" ";
        d++;
    }
    cout<<n;
    return 0;
}

SUBIECTUL II (30 de puncte)


1. Exercițiul urmărește să verifice cunoașterea noțiunilor aferente unui graf orientat (grad extern al unui nod) precum și reprezentarea sa dându-se numărul de arce.

Graful descris prin noduri și arce are forma ca în figura 1:

Info2014MIsubIIex1Figura 1

Gradul extern al unui nod x, d+(x) reprezintă numărul arcelor care ies din nodul x.

În cazul de față, se observă că:

d+(1)=2

d+(2)=0

d+(3)=2

d+(4)=2

d+(5)=0

d+(6)=4

d+(7)=0

d+(8)=2

Vârfurile care au gradul extern nul sunt 2, 5, 7, iar numărul lor este 3. Răspunsul corect este c.

 

2. Exercițiul urmărește să verifice cunoașterea funcțiilor predefinite în C/C++ pentru lucrul cu șiruri de caractere.

strcpy(s, “1b2d3”);

Funcția strcpy are rolul de a copia un șir sursă (cel de-al doilea parametru) într-un șir destinație (primul parametru). Variabila s va reține prin urmare “1b2d3”.

s[2] = ‘a’ + 2;

Valoarea expresiei ‘a’ + 2 este ‘c’. Ținându-se cont că în C/C++ indexarea într-un tablou (și deci și într-un șir de caractere) se face pornind de la poziția 0, caracterul ‘c’ va fi stocat pe pozița a treia a șirului de caractere. Variabila s va reține acum “1bcd3″.

strcpy(s,s+1);

 Variabila s este un pointer, deci prin incrementare se obține șirul de caractere aflat de la poziția 1 până la sfârșit, adică bcd3. Acesta se copiază în variabila s, care va reține acum “bcd3“.

strcpy(s+3,s+4);

La poziția s+4 se află caracterul terminator de șir, adică ‘\0’, care va suprascrie ultimul caracter al șirului stocat de variabila s, aflat pe poziția s+3. Variabila s va conține acum “bcd“.

Răspunsul corect este d.

3. Exercițiul urmărește să verifice corectitudinea lucrului cu structuri de date definite de utilizator.

În elaborarea algoritmului trebuie să se trateze cele trei cazuri:

a) minutul de start este mai mic decât minutul de stop (momentul de start este anterior momentului de stop) ⇒ rezultat acceptat;

b) minutul de start este egal cu minutul de stop:

    1. secunda de start este mai mică decât secunda de stop (momentul de start este anterior momentului de stop) ⇒ rezultat acceptat;

    2. secunda de start este egală sau mai mare decât secunda de stop (momentul de start coincide cu momentul de stop sau este ulterior momentului de stop) ⇒ rezultat respins.

c) minutul de start este mai mare cu minutul de stop (momentul de start este ulterior momentului de stop) ⇒ rezultat respins.

using namespace std;

#include <iostream>

struct timp {
      int minut;
      int secunda;
} start, stop;

int main() {
     cout<<“start”<<endl;
      cout<<“minut:”; cin>>start.minut;
      cout<<“secunda:”; cin>>start.secunda;
      cout<<“stop”<<endl;
      cout<<“minut:”; cin>>stop.minut;
      cout<<“secunda:”; cin>>stop.secunda;
      if (start.minut<stop.minut)
      cout<<“acceptat”<<endl;
      else if (start.minut==stop.minut) {
            if (start.secunda<stop.secunda)
                  cout<<“acceptat”<<endl;
            else
                  cout<<“respins”<<endl;
      } else if (start.minut>stop.minut)
            cout<<“respins”<<endl;
      return 0;
}

4. Exercițiul urmărește să verifice cunoașterea noțiunilor aferente unui arbore oarecare drept caz particular al unui graf neorientat (rădăcină, frunză, lanț elementar).

Arborele descris prin muchiile sale are forma ca în figura 2:

Info2014MIsubIIex3Figura 2

Se observă că înălțimea maximă a arborelui este 5, aceasta obținându-se pe lanțurile elementare: 7 → 3 → 2 → 5 → 8 → 9 sau, invers 9 → 8 → 5 → 2 → 3 → 7. Prin urmare, rădăcinile pot fi 7 sau 9.

Reprezentările celor 2 arbori pot fi vizualizate în figurile 2a și 2b:

Info2014MIsubIIex3aFigura 2a
Info2014MIsubIIex3bFigura 2b

 

5. Exercițiul urmărește să verifice lucrul cu tablouri bidimensionale (manipularea indecșilor pentru accesarea elementelor de pe linii/coloane).

“Problemele” ridicate de rezolvarea acestei probleme sunt următoarele:

  • citirea numărului de linii/coloane al tabloului bidimensional cu verificarea restricțiilor referitoare la gama de valori din care acestea pot face parte;
  • alocarea dinamică a memoriei pentru stocarea elementelor tabloului bidimensional; acest spațiu de memorie trebuie dealocat la sfârșitul programului;
  • citirea și afișarea elementelor tabloului bidimensional;
  • parcurgerea unei linii/coloane specifice din matrice.
Nu este permisă crearea unui alt tablou bidimensional cu m-1 linii / n-1 coloane și copierea elementelor necesare din tabloul bidimensional inițial. Enunțul specifică foarte clar faptul că tabloul trebuie modificat în memorie.

using namespace std;

#define MIN 3
#define MAX 50

#include <iostream>

int main() {
    int m, n;
    // citirea numarului de linii si de coloane al tabloului bidimensional
    // cu verificarea restrictiilor
    do {
        cout<<“m=”;
        cin>>m;
    } while (m<MIN || m>MAX);
    do {
        cout<<“n=”;
        cin>>n;
    } while (n<MIN || n>MAX);
    // alocare memorie tablou bidimensional
    int** matrice = new int*[m];
    for (int k=0; k<m; k++)
        matrice[k]=new int[n];
    // citirea tabloului bidimensional
    for (int i=0; i<m; i++)
        for (int j=0; j<n; j++) {
            cout<<“matrice[“<<(i+1)<<“][“<<(j+1)<<“]=”;
            cin>>matrice[i][j];
        }
    // eliminare ultima coloana
    for (int k=0;k<m;k++) {
        matrice[k][n-2]=matrice[k][n-1];
        matrice[k][n-1]=0;
    }
    // eliminare ultima linie
    for (int k=0;k<n;k++) {
        matrice[m-2][k]=matrice[m-1][k];
        matrice[m-1][k]=0;
    }
    // afisarea tabloului bidimensional
    for (int i=0; i<m-1; i++) {
        for (int j=0; j<n-1; j++)
            cout<<matrice[i][j]<<” “;
        cout<<endl;
    }
    // dealocare memorie tablou bidimensional
    for (int k=0;k<m;k++)
        delete matrice[k];
    delete matrice;
    return 0;
}

Ștergerea unei valori (de pe linia/coloana rămase libere) a fost simulată prin suprascrierea valorii respective cu 0. Afișarea matricii rămase nu mai parcurge această linie/coloană alocată în memorie.

SUBIECTUL III (30 de puncte)


1. Exercițiul verifică cunoștințele legate de funcțiile recursive.

Se consideră funcția recursivă:

int f(int n) {

    if (n<10) return f(n+1)+3;

    else if (n==10) return 7;

    else return f(n-2)-1;

}

și se cere rezultatul evaluării f(15).

f(15)=f(13)-1

  f(13)=f(11)-1

    f(11)=f(9)-1

      f(9)=f(10)+3

        f(10)=7

      f(9)=7+3=10

    f(11)=10-1=9

  f(13)=9-1=8

f(15)=8-1=7

Răspunsul corect este b.

2. Exercițiul verifică înțelegerea principiului metodei de programare backtracking pentru generarea tuturor soluțiilor care îndeplinesc o anumită condiție.

Pentru generarea șiragurilor de câte 4 mărgele, se aleg – pentru fiecare poziție (de la 1 la 4) – culori din mulțimea {rosu, galben, roz, albastru, violet}, în ordine – astfel încât să se respecte condițiile ca mărgelele din șirag să fie distincte și în șirag să nu se găsească culorile roșu și galben pe poziții alăturate.

Soluția 1:

  • poziția 1: roșu (prima culoare din mulțime)
  • poziția 2: roșu (nu respectă condiția de distinct), galben (nu respectă condiția de alăturare), roz
  • poziția 3: roșu (nu respectă condiția de distinct), galben
  • poziția 4: roșu (nu respectă condiția de distinct), galben (nu respectă condiția de distinct), roz (nu respectă condiția de distinct), albastru

Soluția 2:

  • poziția 1: roșu (prima culoare din mulțime)
  • poziția 2: roșu (nu respectă condiția de distinct), galben (nu respectă condiția de alăturare), roz
  • poziția 3: roșu (nu respectă condiția de distinct), galben
  • poziția 4: roșu (nu respectă condiția de distinct), galben (nu respectă condiția de distinct), roz (nu respectă condiția de distinct), albastru (aceeași soluție ca 1), violet

În acest moment s-au epuizat toate soluțiile care au roșu pe poziția 1, roz pe poziția 2 și galben pe poziția 3. Următoarele soluții au în vedere găsirea altei culori pe poziția 3 în afară de galben.

Soluția 3:

  • poziția 1: roșu (prima culoare din mulțime)
  • poziția 2: roșu (nu respectă condiția de distinct), galben (nu respectă condiția de alăturare), roz
  • poziția 3: roșu (nu respectă condiția de distinct), galben (toate soluțiile cu galben pe această poziție au fost epuizate), roz (nu respectă condiția de distinct), albastru
  • poziția 4: roșu (nu respectă condiția de distinct), galben

Soluția 4:

  • poziția 1: roșu (prima culoare din mulțime)
  • poziția 2: roșu (nu respectă condiția de distinct), galben (nu respectă condiția de alăturare), roz
  • poziția 3: roșu (nu respectă condiția de distinct), galben (toate soluțiile cu galben pe această poziție au fost epuizate), roz (nu respectă condiția de distinct), albastru
  • poziția 4: roșu (nu respectă condiția de distinct), galben (aceeași soluție ca 3), roz (nu respectă condiția de distinct), albastru (nu respectă condiția de distinc), violet

În acest moment s-au epuizat toate soluțiile care au roșu pe poziția 1, roz pe poziția 2 și albastru pe poziția 3. Următoarele soluții au în vedere găsirea altei culori pe poziția 3 în afară de galben și albastru.

Soluția 5:

  • poziția 1: roșu (prima culoare din mulțime)
  • poziția 2: roșu (nu respectă condiția de distinct), galben (nu respectă condiția de alăturare), roz
  • poziția 3: roșu (nu respectă condiția de distinct), galben (toate soluțiile cu galben pe această poziție au fost epuizate), roz (nu respectă condiția de distinct), albastru (toate soluțiile cu albastru pe această poziție au fost epuizate), violet
  • poziția 4: roșu (nu respectă condiția de distinct), galben

Soluția 6:

  • poziția 1: roșu (prima culoare din mulțime)
  • poziția 2: roșu (nu respectă condiția de distinct), galben (nu respectă condiția de alăturare), roz
  • poziția 3: roșu (nu respectă condiția de distinct), galben (toate soluțiile cu galben pe această poziție au fost epuizate), roz (nu respectă condiția de distinct), albastru (toate soluțiile cu albastru pe această poziție au fost epuizate), violet
  • poziția 4: roșu (nu respectă condiția de distinct), galben (aceeași soluție ca 5), roz (nu respectă condiția de distinct), albastru

Așadar, următoarea soluție generată este {roșu, roz, violet, albastru}.

În acest moment s-au epuizat toate soluțiile care au roșu pe poziția 1, roz pe poziția 2. Următoarele soluții au în vedere găsirea altei culori pe poziția 2 în afară de roz.

Soluția 6:

  • poziția 1: roșu (prima culoare din mulțime)
  • poziția 2: roșu (nu respectă condiția de distinct), galben (nu respectă condiția de alăturare), roz (toate soluțiile cu roz pe această poziție au fost epuizate), albastru
  • poziția 3: roșu (nu respectă condiția de distinct), galben
  • poziția 4: roșu (nu respectă condiția de distinct), galben (nu respectă condiția de distinct), roz

Așadar, următoarea soluție generată este {roșu, albastru, galben, roz}.

3. Exercițiul își propune să verifice lucrul cu subprograme și transmiterea de parametrii prin valoare, scrierea modularizată a programelor precum și elaborarea de algoritmi eficienți.

Este evident că trebuie respectate simultan condițiile:

  • n! ∈ [a, b]
  • (n-1)! ∉ [a, b]
  • (n+1)! ∉ [a, b]
  • b-a maxim

de unde rezultă automat faptul că a = (n-1)! + 1 și b=(n+1)! – 1.

Se poate defini o funcție care calculează factorialul unui număr pentru a determina (n-1)! și (n+1)! sau, pentru eficiență, funcția poate fi apelată o singură dată, pentru (n-1)!, (n+1)! determinându-se apoi, pe baza acestei valori, prin înmulțirea cu n*(n+1).

Atenție! Parametrii a și b sunt transmiși subprogramului interval prin referință, valorile determinate în cadrul subprogramului fiind furnizate prin intermediul acestora.

using namespace std;

#include <iostream>

int factorial(int n) {
    int rezultat = 1;
    for (int k=2; k<=n; k++)
        rezultat*=k;
    return rezultat;
}

void interval(int n, int* a, int* b) {
    int baza = factorial(n-1);
    *a = baza + 1;
    *b = baza * n * (n+1) – 1;
}

int main() {
    int n;
    do {
        cout<<“n=”;
        cin>>n;
    } while (n<2 || n>10);
    int a, b;
    interval(n, &a, &b);
    cout<<“a=”<<a<<” b=”<<b<<endl;
    return 0;
}

4. Exercițiul vizează verificarea aptitudinilor de lucru cu fișiere în C/C++ precum și elaborarea unui algoritm eficient, în timp polinomial, cu argumentarea alegerii unei astfel de soluții.

a) Se determină toate subnumerele unui număr ca rest al împărțirii la 100 al numărului respectiv (întrucât un subnumăr poate conține exact 2 cifre), eliminându-se succesiv ultima cifră (prin împărțirea sa la 10) până când nu mai există subnumere. Valorile subnumerelor și numărul de apariții al fiecărui subnumăr va fi contorizat în cadrul a doi vectori, unul care reține valorile (subnumere), iar celălalt care stochează numărul de apariții (ocurente). De fiecare dată se verifică, prin căutare, dacă subnumărul respectiv există anterior. Se determină maximul numărului de ocurențe și valoarea (valorile) corespunzătoare acestui maxim se afișează.

Complexitatea algoritmului propus este O(n) întrucât vectorul este parcurs de 2 ori, odată pentru determinarea subnumerelor și odată pentru determinarea maximului numărului de ocurențe (stocarea valorilor subnumerelor în vector presupune și ea o parcurgere pentru căutare – astfel încât să nu se rețină duplicate -, însă și aceasta se realizează tot în timp liniar).

b)

using namespace std;

#include <iostream>
#include <fstream>

#define MAX 1024

int main() {
    long numar;
    // vectori ce contin
    // – valorile subnumerelor aferente numerelor din fisier
    // – numarul de aparitii pentru fiecare subnumar
    int *subnumere, *ocurente, dimensiune = 0;
    // alocare memorie
    subnumere = new int[MAX];
    ocurente = new int[MAX];
    // deschidere fisier
    ifstream fisier(“bac.txt”);
    if (fisier.is_open()) {
        // citire numar din fisier
        while (fisier>>numar) {
            while (numar%100 > 10) {
                // determinare subnumar
                int subnumar = numar % 100, gasit = 0;
                // cautare subnumar in vector
                for (int k=0; k<dimensiune && !gasit; k++)
                    // subnumarul a fost gasit in vector, se incrementeaza numarul de ocurente
                    if (subnumere[k] == subnumar) {
                        ocurente[k]++;
                        gasit = 1;
                    }
                // subnumarul nu a fost gasit in vector, se stocheaza (numarul de ocurente este 1)
                if (!gasit) {
                    subnumere[dimensiune] = subnumar;
                    ocurente[dimensiune] = 1;
                    dimensiune++;
                }
                numar /= 10;
            }
        }
        // inchidere fisier
        fisier.close();
    }
    // determinare numar maxim de ocurente
    int maxim = 1;
    for (int k=0; k<dimensiune; k++)
        if (ocurente[k]>=maxim)
            maxim = ocurente[k];
    // afisarea subnumerelor care apar de cele mai multe ori
    for (int k=0; k<dimensiune; k++)
        if (ocurente[k]==maxim)
            cout<<subnumere[k]<<” “;
    cout<<endl;
    // dealocare memorie
    delete subnumere;
    delete ocurente;
    return 0;
}