Day: July 5, 2015

Rezolvarea subiectelor de informatică de la examenul de bacalaureat național, sesiunea iulie 2015 (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. Variabila întreagă x are (minim) forma abcd, cu a ≠ b ≠ c ≠ d, unde a este cifra miilor, b este cifra sutelor, c este cifra zecilor și d este cifra unităților.

Se cere să se determine expresia care returnează cifra b.

În acest sens, trebuie să se elimine cifrele c și d, lucru care se poate realiza prin împărțirea numărului la 100, apoi cifra b se obține ca rest al împărțirii la 10 a numărului rămas. Astfel, expresia va avea valoarea (x/100)%10, iar răspunsul corect este d.

Vom analiza și rezultatul celorlalte expresii propuse ca variante de răspuns.

a) x/100 = ab

b) x%100 = cd

c) (x/10)%10 = c

d) (x/100)%10 = b

2.

a) Așa cum se poate observa, algoritmul determină cea mai mare putere a lui k mai mică sau egală cu n.

n ← 7

k ← 2

pm ← 0

i ← 1

iterația 1 a ciclului cât timp … execută (1 ≤ 7)

x ← 1

p ← 0

ciclul cât timp … execută nu se execută în acest caz (1 % 2 ≠ 0)

condiția instrucțiunii dacă (0 > 0) nu este îndeplinită

i ← 2

iterația 2 a ciclului cât timp … execută (2 ≤ 7)

x ← 2

p ← 0

iterația 1 a ciclului cât timp … execută (2 % 2 = 0)

x ← [2 / 2] = 1

p ← 1

încheierea ciclului cât timp … execută (1 % 2 ≠ 0)

dacă (1 > 0) atunci

pm ← 1

i ← 3

iterația 3 a ciclului cât timp … execută (3 ≤ 7)

x ← 3

p ← 0

ciclul cât timp … execută nu se execută în acest caz (3 % 2 ≠ 0)

condiția instrucțiunii dacă (0 > 1) nu este îndeplinită

i ← 4

iterația 4 a ciclului cât timp … execută (4 ≤ 7)

x ← 4

p ← 0

iterația 1 a ciclului cât timp … execută (4 % 2 = 0)

x ← [4 / 2] = 2

p ← 1

iterația 2 a ciclului cât timp … execută (4 % 2 = 0)

x ← [2 / 2] = 1

p ← 2

încheierea ciclului cât timp … execută (1 % 2 ≠ 0)

dacă (2 > 1) atunci

pm ← 2

i ← 5

iterația 5 a ciclului cât timp … execută (5 ≤ 7)

x ← 5

p ← 0

ciclul cât timp … execută nu se execută în acest caz (5 % 2 ≠ 0)

condiția instrucțiunii dacă (0 > 2) nu este îndeplinită

i ← 6

iterația 6 a ciclului cât timp … execută (6 ≤ 7)

x ← 6

p ← 0

iterația 1 a ciclului cât timp … execută (6 % 2 = 0)

x ← [6 / 2] = 3

p ← 1

încheierea ciclului cât timp … execută (3 % 2 ≠ 0)

condiția instrucțiunii dacă (1 > 2) nu este îndeplinită

i ← 7

iterația 7 a ciclului cât timp … execută (7 ≤ 7)

x ← 7

p ← 0

ciclul cât timp … execută nu se execută în acest caz (7 % 2 ≠ 0)

condiția instrucțiunii dacă (0 > 2) nu este îndeplinită

i ← 8

încheierea ciclului cât timp … execută (8 > 7)

scrie 2

Cea mai mare putere a lui 2 mai mică sau egală cu 7 este 4 (22=4).

b) Dacă pentru variabila k se citește valoarea 5 și rezultatul așteptat este 3 (adică cea mai mare putere este 53=125), valorile lui n pentru care poate fi obținut acest rezultat se regăsesc în intervalul [53, 54-1], adică [125, 624]. Prin urmare, cea mai mică valoare pentru n este 125, iar cea mai mare valoare pentru n este 624, garantând obținerea rezultatului dorit.

c) Structura repetitivă cât timp i ≤ n execută are un număr cunoscut de pași (n), întrucât la fiecare pas al acesteia, incrementarea variabilei contor i se face cu o singură unitate. Prin urmare, aceasta poate fi transformată cu ușurință într-o structură repetitivă de tipul pentru … execută.

citește n, k
pm ← 0
i ← 1
pentru i = 1, n execută
    x ← i
    p ← 0
    cât timp x % k = 0 execută
        x ← [x / k]
        p ← p + 1
    dacă p > pm atunci
        pm ← p
    i ← i + 1
scrie pm

 d) Implementarea algoritmului în C / C++ nu presupune nici un fel de dificultate, structura repetitivă de tip cât timp … execută având ca echivalent instrucțiunea while:

using namespace std;

#include <iostream>

int main() {
    int n, k, pm = 0, i = 1, x, p;
    cout << "n = "; cin >> n;
    cout << "k = "; cin >> k;
    while (i <= n) {
        x = i;
        p = 0;
        while (x % k == 0) {
            x /= k; 			
            p++;
        }
        if (p > pm) {
            pm = p;
        }
        i++;
    }
    cout << "pm = " << pm << endl;
    return 0;
}

SUBIECTUL al II-lea (30 de puncte)


1. În situația în care prețul cărții trebuie majorat cu 50%, înseamnă că noua sa valoare (raportată la valoarea veche) trebuie multiplicată cu 1.5, adică cu 3/2 (înmulțirea cu o variabilă de tip float asigură faptul că se va realiza operația cu numere reale, nu cu numere întregi).

Accesul la câmpul unei structuri se face prin operatorul . în cazul în care este vorba despre variabile obișnuite și prin operatorul -> în cazul în care se lucrează cu referințe / adrese de memorie (pointeri).

Prin urmare, valoarea preț a variabilei c (de tip carte) va fi disponibilă prin expresia c.pret.

Răspunsul corect este a.

2. Nodul 1 este rădăcină și are drept copii nodurile 2 și 3.

Nodul 2 are drept copii nodurile 4, 5, 6, 7, 8.

Nodul 3 are drept copii nodurile 9, 10, 11, 12, 13, 14, 15.

Nodul 4 are drept copii nodurile 16, 17, 18, 19, 20, 21, 22, 23, 24.

Nodul 5 are drept copii nodurile 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35.

Nodul 6 are drept copii nodurile 36, 37.

bac2015_MI1_exII2Figura 1

Ca atare, numărul de noduri frunză se obține ca diferență dintre numărul total de noduri (37) din care se scade numărul de noduri care au copii (6), adică 31. Răspunsul corect este b.

Altfel, se putea observa că cel mai mare pătrat perfect din intervalul [1, 37] este 36 și parte întreagă din rădăcina lui pătrată este 6. Astfel, doar 6 dintre noduri au copii, în timp ce toate celelalte sunt frunze.

3.Din figura de mai jos se poate observa faptul că există trei cicluri în graf:

  • 3, 4, 6
  • 3, 5, 6
  • 3, 4, 6, 5

bac2015_MI1_exII3Figura 2

Prin urmare, nodurile care nu aparțin nici unui ciclu din graf sunt 1, 2, 7, 8.

4. Problema cere ca pentru un șir dat b, să se determine un șir a format din prima jumătate a acestuia. Astfel, rezolvarea presupune parcurgerea primei jumătăți a șirului respectiv, copierea caracter cu caracter și adăugarea terminatorului de șir ‘\0’ la sfârșit.

using namespace std;

#define MAX_LENGTH 20

#include <iostream>
#include <string>

int main() {
    char *a, *b;
    int index;
    a = new char[MAX_LENGTH];
    b = new char[MAX_LENGTH];
    cout << "b = "; cin >> b;
    for (index = 0; index < (int)strlen(b) / 2; index++) {
        a[index] = b[index];
    }
    a[index] = '\0';
    cout << "a = " << a << endl;
    delete a;
    delete b;
    return 0;
}

 5. Problema presupune citirea elementelor de pe linia 0 a tabloului bidimensional și, concomitent, construirea următoarelor linii, de la 1 la n – 1. Astfel, pentru fiecare linie j (j = 1, n – 1), poziția la care va fi reținut elementul care pe linia 0 se află pe coloana i (i = 0, n – 1), va fi decalat exact cu j, iar în situația în care valoarea respectivă depășește n, se realizează transferul său începând cu 0, comportament ce poate fi obținut folosind restul împărțirii sumei i + j la n.

using namespace std;

#include <iostream>

int main() {
    int n, **m, i, j;
    cout << "n = "; cin >> n;
    m = new int* [n];
    for (i = 0; i < n; i++) {
        m[i] = new int[n];
    }
    for (i = 0; i < n; i++) {
        cout << "m[0][" << i << "] = "; cin >> m[0][i];
        for (j = 1; j < n; j++) {
            m[j][(i + j) % n] = m[0][i];
        }
    }
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            cout << m[i][j] << " ";
        }
        cout << endl;
    }
    for (i = 0; i < n; i++) {
        delete m[i];
    }
    delete m;
    return 0;
}

SUBIECTUL al III-lea (30 de puncte)


1. Prin intermediul metodei backtracking, se construiește numărul într-o stivă de trei elemente, pe fiecare nivel al stivei reținându-se câte o cifră a sa. La fiecare pas, se incrementează elementul din vârful stivei, verificându-se dacă suma cifrelor este egală cu 5, caz în care se obține o soluție. În cazul în care elementul din vârful stivei depășește valoarea 9, se revine la cifra de pe nivelul anterior, incrementându-se aceasta și punând pe nivelul următor valoarea 0. Acest comportament se repetă pentru fiecare nivel al stivei la care, în urma operației de incrementare, se depășește valoarea 9.

Inițial, stiva are valorile 1000. Se incrementează cifra unităților cu 1, verificându-se la fiecare număr format dacă suma cifrelor este egală cu 6. Când aceasta ajunge la 9, se incrementează cifra zecilor, cifra unităților fiind reinițializată cu 0. Același comportament este urmărit de fiecare dată când o cifră de pe un nivel ajunge la valoarea 9, incrementându-se cifra de pe nivelul anterior și reinițializându-se toate cifrele de pe nivelurile următoare cu 0.

Primul număr care îndeplinește condiția este 1005.

Al doilea număr care îndeplinește condiția este 1014.

Al treilea număr care îndeplinește condiția este 1023.

Prin urmare, răspunsul corect este b.

2. Subprogramul F este o funcție recursivă care afișează caracterul curent, atâta vreme cât acesta este cel puțin ‘a’ (valoarea 97), invocând metoda pentru caracterul anterior.

Astfel, în condiția în care funcția F se apelează pentru caracterul ‘d’, se vor afișa caracterele ‘d’, ‘c’, ‘b’ și ‘a’ în această ordine (‘dcba’).

F(‘d’) ⇒ afișează ‘d’, apelează F(‘c’)

    F(‘c’) ⇒ afișează ‘c’, apelează F(‘b’)

        F(‘b’) ⇒ afișează ‘b’, apelează F(‘a’)

          F(‘a’) ⇒ afișează ‘a’, apelează F(‘`’)

             F(‘`’) ⇒ se termină fără să afișeze nimic (nu se îndeplinește condiția impusă în instrucțiunea if)

           revenire în F(‘a’)

       revenire în F(‘b’)

    revenire în F(‘c’)

revenire în F(‘d’)

3. Se definesc următoarele funcții ajutătoare:

  • funcția fibonacci(n) calculează al n-lea termen din șirul lui Fibonacci;
  • funcția odd(n) verifică dacă numărul n este impar sau nu, întorcând 1 dacă numărul este impar și 0 altfel (practic, se întoarce restul împărțirii lui n la 2).

Folosind aceste funcții, se implementează subprogramul fibo, care determină câte un număr din șirul lui Fibonacci, verificând dacă acesta este impar sau nu. În momentul în care este identificat un astfel de număr, se incrementează un contor (reprezentând al câtelea număr impar din șirul lui Fibonacci este), astfel încât în momentul în care se ajunge la n, se întoarce valoarea respectivă ca rezultat al funcției.

using namespace std;

#include <iostream>

int fibonacci(int n) {
    if (n == 1) return 1;
    if (n == 2) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int odd(int n) {
    return (n % 2);
}

int fibo(int n) {
    int current_index = 1, current_position = 0;
    while (1) {
        int current_number = fibonacci(current_index++);
        if (odd(current_number)) {
            current_position++;
            if (current_position == n) {
                return current_number;
            }
        }
    }
}

int main() {
    int n;
    cout << "n = "; cin >> n;
    cout << "Al n-lea numar impar din sirul lui Fibonacci este " << fibo(n) << endl;
    return 0;
}

4.

a) Soluția evidentă a acestei probleme este stocarea valorilor citite din fișier într-un vector, sortarea acestuia urmată de parcurgerea sa, perechile fiind reprezentate de valorile adiacente a căror diferență este mai mare sau egală cu 2. Totuși, cei mai buni algoritmi de sortare (heapsort, mergesort) au de regulă complexitatea O(nlogn), ceea ce face ca o astfel de abordare să nu fie eficientă.

O soluție în timp liniar presupune utilizarea unui tablou de apariții, având în vedere că numerele care apar în fișier pot avea doar valori din intervalul [0, 100]. Semnificația unui element din acest vector este următoarea:

  • 0 – numărul respectiv nu se regăsește în șir
  • 1 – numărul respectiv se regăsește în șir, cel puțin o dată

Se asigură în acest mod și eficiența din punctul de vedere al memoriei folosite, întrucât se alocă doar un vector de 101 elemente, în timp ce numărul de termeni din șir poate atinge un milion.

Se parcurge ulterior vectorul de apariții, o singură dată (astfel încât complexitatea algoritmului este O(n)), reținându-se, la fiecare pas, indicele poziției la care a fost întâlnit cel mai apropiat element nenul. În situația în care se întâlnește un element nenul (corespunzător unui termen care se regăsește în șir), se verifică dacă anterior a mai fost întâlnit un alt element nenul și în caz afirmativ, se determină dacă diferența dintre poziții (deci dintre termeni) este mai mare sau egală cu 2, situație în care a fost identificată o pereche care respectă condițiile problemei. Trebuie să se aibă grijă ca de fiecare dată când se întâlnește un element nenul, să se actualizeze valoarea elementului precedent nenul întâlnit.

De asemenea, trebuie să se contorizeze și numărul de perechi identificate, astfel încât, în situația în care acesta este nul, să se poată afișa mesajul nu există.

b)

using namespace std;

#define MAX_VALUE 100

#include <iostream>
#include <fstream>

int main() {
    int k, *occurencies, number_of_pairs = 0, x = -1, y = -1;
    ifstream f("bac.txt");
    occurencies = new int[MAX_VALUE + 1];
    for (k = 0; k <= MAX_VALUE; k++) {
        occurencies[k] = 0;
    }
    if (f.is_open()) {
        while (f >> k) {
            occurencies[k] = 1;
        }
        f.close();
        for (k = 0; k <= MAX_VALUE; k++) {
            if (occurencies[k]) {
                if (x != -1) {
                    if (y != -1) {
                        x = y;
                    }
                    y = k;
                    if (y - x >= 2) {
                        number_of_pairs++;
                        cout << x << " " << y << endl;
                    }
                } else {
                    x = k;
                }
            }
        }
    }
    if (!number_of_pairs) {
        cout << "nu exista" << endl;
    }
    delete occurencies;
    return 0;
}