Tag: subiecte

Rezolvarea subiectelor de informatică de la examenul de bacalaureat național, sesiunea august 2015 (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 al II-lea (30 de puncte)


1. Expresia C/C++ are valoarea 1 (adevărat) dacă variabila întreagă x aparține reuniunii de intervale (-∞, -3) ∪ (-1, 1) ∪ (3, +∞).

Analizăm, pe rând, fiecare dintre variantele de răspuns:

a) abs(x) > 3 && x == 0

|x| = x, x ∈ [0, +∞) și |x| = -x, x ∈ (-∞, 0)

Relația abs(x) > 3 devine astfel:

x > 3, x ∈ [0, +∞) și -x > 3, x ∈ (-∞, 0)

sau încă

x > 3, x ∈ [0, +∞) și x < -3, x ∈ (-∞, 0)

Condiția inițială devine:

x ∈ (-∞, -3) ∪ {0} ∪ (3, +∞), ceea ce contravine condiției din enunț.

Varianta a este incorectă.

b) abs(x) < 1 || abs(x) > 3

|x| = x, x ∈ [0, +∞) și |x| = -x, x ∈ (-∞, 0)

Relația abs(x) < 1 devine astfel:

x < 1, x ∈ [0, +∞) și -x < 1, x ∈ (-∞, 0)

sau încă

x < 1, x ∈ [0, +∞) și x > -1, x ∈ (-∞, 0)

Condiția inițială devine:

x ∈ (-∞, -3) ∪ (-1, 1) ∪ (3, +∞), ceea ce corespunde condiției din enunț.

Varianta b este corectă.

c) abs(x-3) < 1

|x-3| = x-3, x ∈ [3, +∞) și |x-3| = 3-x, x ∈ (-∞, 3)

Relația abs(x-3) < 1 devine astfel:

x-3 < 1, x ∈ [3, +∞) și 3-x < 1, x ∈ (-∞, 3)

sau încă

x < 4, x ∈ [3, +∞) și x > 2, x ∈ (-∞, 3)

Condiția inițială devine:

x ∈ (2, 4), ceea ce contravine condiției din enunț.

Varianta c este incorectă.

d) abs(x-1) > 3

|x-1| = x-1, x ∈ [1, +∞) și |x-1| = 1-x, x ∈ (-∞, 1)

Relația abs(x-1) > 3 devine astfel:

x-1 > 3, x ∈ [1, +∞) și 1-x > 3, x ∈ (-∞, 1)

sau încă

x > 4, x ∈ [1, +∞) și x < -2, x ∈ (-∞, 1)

Condiția inițială devine:

x ∈ (-∞, -2) ∪ (4, +∞), ceea ce contravine condiției din enunț.

Varianta d este incorectă.

Ca atare, răspunsul corect este b.

2. Potrivit secvenței de cod:

while (x >= y)
        x = x - y;
z = x;

 din variabila x se scade valoarea y atâta vreme cât x >= y, cu alte cuvinte x = x – [x/y] * y. Se observă faptul că valoarea rămasă în x este egală cu restul împărțirii lui x la y (x%y).

Ca atare, răspunsul corect este c.

3. Având declarate variabilele:

float re, im;

 care reprezintă partea reală, respectiv partea imaginară a unui număr complex z, pătratul modulului acestuia (∑ = |z|2 = re2 + im2) se poate calcula astfel:

float s = 0.0;
s = re * re + im * im;

 Dacă variabilele sunt declarate având tipul double, se poate face uz de funcția pow din biblioteca math.h:

double re, im;
double s = 0.0;
s = pow (re, 2) + pow (im, 2);

 4.

a) Algoritmul descris în pseudocod analizează fiecare cifră în parte a numărului n și, în măsura în care aceasta este un număr prim, este adăugată la suma cerută de enunțul exercițiului. Parcurgerea cifră cu cifră a numărului de analizat se face prin împărțiri succesive la 10 până ce numărul devine nul, cifra din pasul curent al algoritmului (care este analizată pentru a se verifica dacă este sau nu număr prim) fiind reprezentată de restul împărțirii la 10. Pentru fiecare cifră, se decide dacă aceasta este număr prim sau nu în urma parcurgerii tuturor valorilor cuprinse între 2 și rădăcina sa pătrată (interval în care se pot găsi potențialii divizori), verificându-se restul împărțirii cifrei la fiecare dintre aceste valori. În situația în care o singură valoare divide cifra, se poate concluziona că aceasta nu reprezintă un număr prim. În cazul în care nici una dintre valori nu divide cifra, se poate concluziona că aceasta reprezintă un număr prim. Cazurile în care cifra are valoarea 0 sau 1 sunt tratate în mod separat.

citește n
suma ← 0
cât timp n > 0 execută
    cifra_curentă ← n % 10
    prim ← 1
    dacă cifra_curentă = 0 sau cifra_curentă = 1 atunci prim ← 0
        altfel
        pentru divizor = 2, √cifra_curentă execută
             dacă cifra_curentă % divizor = 0 atunci prim ← 0
    dacă prim = 1 atunci suma ← suma + cifra_curentă
    n ← n / 10
tipărește suma

b) Datele de intrare sunt reprezentate de variabila n, de tip întreg, reprezentând numărul pentru care se calculează suma cifrelor prime. Aceasta se citește de la tastatură înainte ca algoritmul să fie executat.

Datele de ieșire sunt reprezentate de variabila suma, de tip întreg, reprezentând suma cifrelor prime a numărului n. Aceasta se afișează pe ecran în urma execuției algoritmului.

Alte variabile folosite în cadrul algoritmului sunt:

  • cifra_curentă reprezintă o cifră a numărului n (obținută ca rest al împărțirii numărului n la 10) analizată în pasul curent al algoritmului, pentru a se determina dacă este număr prim sau nu, în urma acesteia luându-se decizia de a se adăuga la sumă sau nu;
  • prim este o variabilă având ca valori posibile 1 (adevărat) sau 0 (fals) în funcție de proprietatea cifrei analizate în pasul curent a algoritmului de a fi sau nu număr prim;
  • divizor este o variabilă, luând valori cuprinse între 2 și rădăcina pătrată a cifrei curente, reprezentând potențialii divizori ai cifrei curente; în măsura în care unul dintre aceștia verifică proprietatea de a divide cifra curentă (restul împărțirii cifrei curente la el este nul), se poate conchide faptul că numărul analizat nu este prim; altfel, dacă nici un număr din intervalul menționat nu verifică proprietatea de a divide cifra curentă, se poate conchide faptul că numărul analizat este prim.

 

SUBIECTUL al III-lea (30 de puncte)


1. Se observă faptul că pe fiecare poziție 1 ≤ i, j ≤ 5 se găsește o valoare egală cu indicele coloanei la care se adaugă valoarea maximă de pe linia precedentă (aceasta din urmă fiind determinată prin înmulțirea indicelui liniei cu numărul de elemente de pe o linie, adică 5).

Ca atare, valoarea afișată pe poziția i, j este (i – 1) * 5 + j.

Varianta corectă este a.

2. Se caută, prin metoda căutării binare, valoarea x = 5 în tabloul unidimensional ordonat (1, 3, 5, 7, 12, 21, 49).

Se pornește căutarea de la mijlocul vectorului (poziția 4), adică cu valoarea 7. Pentru că x = 5 < 7, se continuă căutarea în jumătatea stângă a vectorului, adică între pozițiile (1, 3).

Se continuă căutarea cu mijlocul părții stângi a vectorului (poziția 2), adică cu valoarea 3. Pentru că x = 5 > 3, se continuă căutarea în jumătatea dreaptă a părții stângi a vectorului, adică între pozițiile (3, 3).

Se continuă căutarea cu mijlocul jumătății drepte a părții stângi a vectorului care conține un singur element, adică cu valoarea 5. Pentru că x = 5 == 5, se termină procesul de căutare.

În concluzie, valorile cu care se face comparația sunt 7, 3 și 5.

3. Rezolvarea problemei presupune parcurgerea, element cu element, a vectorului, și marcarea momentului în care a fost întâlnit un element par, respectiv a unui element impar diferit de 2015. Se afișează rezultatul DA în situația în care a fost întâlnit cel puțin un element par și nici un element impar diferit de 2015, în caz contrar afișându-se rezultatul NU.

#include <iostream>

using namespace std;

int main() {
    int n, odd_encountered = 0, even_encountered = 0;
    long *v;
    cout << "n="; cin >> n;
    v = new long [n];
    for (int k = 0; k < n; k++) {
        cout << "v[" << k << "]=";
        cin >> v[k];
    }
    for (int k = 0; k < n; k++) {
        if (v[k] % 2 == 0) {
            even_encountered = 1;
        } else if (v[k] != 2015) {
            odd_encountered = 1;
        }
    }
    if (even_encountered && !odd_encountered) {
        cout << "DA";
    } else {
        cout << "NU";
    }
    delete v;
    return 0;
}

4.

a) Fie x1, x2, …, xi numerele impare aflate printre primii n termeni ai șirului aflați în fișier și y1, y2, …, yp numerele pare aflate printre ultimii n termeni ai șirului.

Problema cere calcularea sumei:

∑ = x1 * y1 + x1 * y2 + … + x1 * yp + x2 * y1 + x2 * y2 + … + x2 * yp + … + xi * y1 + xi * y2 + … + xi * yp = x1 * (y1 + y2 + … + yp) + x2 * (y1 + y2 + … + yp) + … + xi * (y1 + y2 + … + yp) = (x1 + x2 + … + xi) * (y1 + y2 + … + yp)

Prin urmare, este suficient să se calculeze suma elementelor impare aflate printre primii n termeni ai șirului, respectiv suma elementelor pare aflate printre ultimii n termeni ai șirului, realizându-se ulterior produsul acestora pentru a se obține rezultatul solicitat de enunțul problemei.

Se notează:

  • sum_first_odd: suma tuturor numerelor impare aflate între primii n termeni ai șirului;
  • sum_last_even: suma tuturor numerelor pare aflate între ultimii n termeni ai șirului.

Rezultatul problemei va fi, în această situație sum_first_odd * sum_last_even.

În acest fel, complexitatea în timp a algoritmului este liniară O(n), șirul de numere fiind parcurs o singură dată, asigurându-se în același timp și eficiența din punctul de vedere al memoriei folosite întrucât sunt alocate doar două variabile de tip întreg.

b)

#include <iostream>
#include <fstream>

using namespace std;

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

int main() {
    ifstream file("bac.txt");
    int n, crt_pos = 0, temp, sum_first_odd = 0, sum_last_even = 0;
    if (file.is_open()) {
        file >> n;
        while (file >> temp) {
            if (crt_pos++ < n) {
                if (parity(temp)) {
                    sum_first_odd += temp;
                }
            } else {
                if (!parity(temp)) {
                    sum_last_even += temp;
                }
            }
        }
        cout << "Suma este " << (sum_first_odd * sum_last_even) << endl;
        file.close();
    }
    return 0;
}

 

Rezolvarea subiectelor de informatică de la examenul de bacalaureat național, sesiunea august 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. Expresia C/C++ are valoarea 1 (adevărat) dacă sunt îndeplinite simultan condițiile ca variabila întreagă n să fie divizibilă cu 2, fară a fi divizibilă și cu 5.

Analizăm, pe rând, fiecare dintre variantele de răspuns:

a) !((n%2==1) || (n%5==0))

Expresia este adevărată dacă nu este îndeplinită condiția ca numărul n să fie impar sau să fie divizibil cu 5. Prin negarea condiției rezultă că numărul n trebuie să fie par (divizibil cu 2) și să nu fie divizibil cu 5, adică ceea ce se cere în enunțul exercițiului. De altfel, folosind regulile operatorilor din logica matematică, există echivalența: !((n%2==1) || (n%5==0)) ⇔ (n%2!=1) && (n%5!=0)

Varianta a este corectă.

b) (n%2==0) && (n%5==0)

Expresia este adevărată dacă numărul n este în același timp divizibil și cu 2 și cu 5, ceea ce nu corespunde cu enunțul exercițiului.

Varianta b este incorectă.

c) (n%10==0) && (n%5!=0)

Expresia este adevărată dacă numărul n este divizibil cu 10 dar nu este divizibil cu 5. Această expresie este contradictorie de vreme ce un număr divizibil cu 10 este întotdeauna divizibil cu 5 (de vreme ce 10 = 2 · 5), astfel încât condiția ca acesta să nu fie divizibil și cu 5 face ca expresia să nu fie îndeplinită pentru nici un fel de număr, având valoarea 0.

Varianta c este incorectă.

d) (n%10==0) && (n%2==0)

Expresia este adevărată dacă numărul n este în același timp divizibil și cu 10 și cu 2. Se observă faptul că 10 = 2 · 5, prin urmare cea de-a doua condiție este redundantă (dacă numărul n este divizibil cu 10, este clar că este simultan divizibil și cu 2 și cu 5). Cum în această situație numărul n este divizibil cu 5, condiția din enunțul exercițiului nu este îndeplinită.

Varianta d este incorectă.

În concluzie, răspunsul corect este a.

2.

a) Se observă că algoritmul determină afișează secvențe k, k – 1, …, 1 de un număr de ori egal cu numărul de ori prin care n este mai mare decât k (n/k), urmând ca ultima secvență să cuprindă numerele k, …, k – n + (n / k ) * k + 1.

n ← 7

k ← 3

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

        dacă (7>3) atunci

                i = 3

         n ← 7 – 3 (=4)

         t ← 3

         iterația 1 a ciclului cât timp … execută (3 ≥ 1)

                  scrie 3, ‘ ‘

                  i ← 3 – 1 (=2)

                  t ← 3 – 1 (=2)

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

                  scrie 2, ‘ ‘

                  i ← 2 – 1 (=1)

                  t ← 2 – 1 (=1)

         iterația 3 a ciclului cât timp … execută (1 ≥ 1)

                  scrie 1, ‘ ‘

                  i ← 1 – 1 (=0)

                  t ← 1 – 1 (=0)

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

        dacă (4>3) atunci

                i = 3

         n ← 4 – 3 (=1)

         t ← 3

         iterația 1 a ciclului cât timp … execută (3 ≥ 1)

                  scrie 3, ‘ ‘

                  i ← 3 – 1 (=2)

                  t ← 3 – 1 (=2)

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

                  scrie 2, ‘ ‘

                  i ← 2 – 1 (=1)

                  t ← 2 – 1 (=1)

         iterația 3 a ciclului cât timp … execută (1 ≥ 1)

                  scrie 1, ‘ ‘

                  i ← 1 – 1 (=0)

                  t ← 1 – 1 (=0)

iterația 3 a ciclului cât timp … execută (1 ≥ 1)

        dacă (1>3) atunci

                i = 1

         n ← 1 – 1 (=0)

         t ← 3

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

                  scrie 3, ‘ ‘

                  i ← 1 – 1 (=0)

                  t ← 3 – 1 (=2)

Prin urmare, în urma execuției algoritmului se va afișa 3, 2, 1, 3, 2, 1, 3.

b) Ultima valoare afișată are expresia k – n + [n / k] * k + 1, unde prin [x] se înțelege parte întreagă. Această expresie are valoarea 7 pentru k = 11, cerându-se determinarea lui n minim, respectiv maxim, n ∈ [1, 99].

Obținem ecuația: 11 – n + [n / 11] * 11 + 1 = 7, adică n – [n / 11] * 11 = 5.

Se observă că valoarea minimă se obține pentru [n / 11] = 0, adică n = 5.

Se observă că valoarea maximă se obține pentru [n / 11] = 8, adică n = 93.

Ca atare, valorile minimă, respectiv maximă ale lui n ∈ [1, 99] sunt 5, respectiv 93.

c) Structura repetitivă cât timp i ≥ 1 execută are un număr cunoscut de pași (i – care poate fi k sau n), întrucât la fiecare pas al acesteia, decrementarea 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
cât timp n ≥ 1 execută
    dacă n > k atunci i ← k
        altfel i ← n
    n ← n - i
    t ← k
    pentru contor = i ... 1 execută
        scrie t, ' '
        t ← t - 1
        contor ← contor - 1

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, i, t;
    cout << "n="; cin >> n;
    cout << "k="; cin >> k;
    while (n >= 1) {
        if (n > k) {
            i = k;
        }
        else {
            i = n;
        }
        n = n - i;
        t = k;
        while (i >= 1) {
            cout << t << " ";
            i--;
            t--;
        }
    }
    return 0;
}

 

SUBIECTUL al II-lea (30 de puncte)


1. Pentru o structură definită sub forma:

struct complex {
    float re;
    float im;
} z;

atributele pot fi accesate prin intermediul expresiilor z.re, respectiv z.im.

Pătratul modulului numărului complex reținut prin intermediul variabilei de tip structură z se obține prin intermediul expresiei z.re * z.re + z.im * z.im (suma pătratelor părții imaginare, respectiv a părții reale).

Expresiile de la variantele a-c sunt incorecte din punct de vedere sintactic, acestea nici măcar nu compilează.

Răspuns corect d.

2. Pentru ca graful să aibă un număr maxim de muchii fără a exista nici un ciclu, trebuie ca între 99 de noduri să existe o singură muchie (gradul fiecărui nod fiind astfel 2), iar între 2 noduri să nu existe nici o muchie (gradul acestora fiind 1). Prin urmare, numărul de muchii este 99.

Răspuns corect b.

3. Un arbore reprezentat prin vectorul de tați are, pe fiecare poziție k, indicele nodului părinte, respectându-se convenția că pentru nodul rădăcină, părintele are indicele 0.

Din vectorul de tați rezultă că nodul 4 este rădăcina arborelui.

Nodul 4 are drept copii nodurile 8 și 9.

Nodul 8 are drept copii nodurile 3 și 5.

Nodul 9 are drept copii nodurile 6, 7 și 10.

Nodul 3 are drept copii nodurile 1 și 2.

Restul nodurilor (1, 2, 5, 6, 7, 10) nu au copii deci, prin urmare, sunt frunze (chiar dacă se află pe niveluri diferite).

bac2015_MI2_exII3Nodurile frunză sunt 1, 2, 5, 6, 7 și 10.

 

4. Se observă faptul că pe fiecare linie, valorile sunt obținute prin adunarea indicelui coloanei curente la valoarea reținută pe ultima coloană a liniei precedente (care este produsul dintre indicele liniei și indicele coloanei). Ca atare, formula de calcul pentru valoarea de pe poziția i, j a matricei a (cu 1 ≤ i, j ≤ 5) este (i – 1) * 5 + j unde (i – 1) * 5 este valoarea de pe ultima coloană a liniei precedente iar j este valoarea coloanei curente.

using namespace std;

#include <iostream>

#define SIZE 6

int main() {
    int **a, i, j;
    a = new int*[SIZE];
    for (i = 0; i < SIZE; i++) {
        a[i] = new int[SIZE];
    }
    for (i = 1; i <= 5; i++) {
        for (j = 1; j <= 5; j++) {
            a[i][j] = (i - 1) * 5 + j;
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    for (i = 0; i < SIZE; i++) {
        delete a[i];
    }
    delete a;
    return 0;
}

 

5. Rezolvarea problemei presupune parcurgerea șirului, caracter cu caracter, marcându-se momentul în care s-a întâlnit o vocală diferită de i, respectiv o consoană. Se afișează mesajul DA în situația în care s-a întâlnit cel puțin o consoană și nu s-a întâlnit nici o vocală diferită de i, în caz contrar afișându-se mesajul NU.

using namespace std;

#define MAXSIZE 100

#include <iostream>
#include <string>

int main() {
    char *s;
    int k, consonant_found = 0, vowel_found = 0;
    s = new char[MAXSIZE];
    cout << "s="; cin >> s;
    for (k = 0; k < strlen(s); k++) {
        switch (s[k]) {
            case 'a':
            case 'e':
            case 'o':
            case 'u':
                vowel_found = 1;
            case 'i':
                break;
            default:
                consonant_found = 1;
                break;
        }
    }
    if (consonant_found && !vowel_found) {
        cout << "DA" << endl;
    }
    else {
        cout << "NU" << endl;
    }
    delete s;
    return 0;
}

 

SUBIECTUL al III-lea (30 de puncte)


1. Prin intermediul metodei backtracking, se construiește soluția într-o stivă de trei elemente, pe fiecare nivel al stivei reținându-se câte un parfum din mulțimea inițială. La fiecare pas, se alege elementul de pe o poziție a stivei, alegându-se un element din mulțime având indicele imediat superior celui de pe poziția precedentă. O soluție este obținută în momentul în care sunt completate toate elementele stivei. La revenire, se alege pe nivelul inferior un element având indicele imediat următor din mulțime față de cel din soluția anterioară, procesul continuând până când nu se mai pot obține soluții, situație în care revenirea se face reconstruind soluția coborând pe stivă cu încă o poziție și reluând același mecanism până ce se epuizează toate soluțiile.

Astfel, soluțiile obținute vor fi:

1) (ambră, cedru, iris)

2) (ambră, cedru, mosc)

3) (ambră, cedru, santal)

4) (ambră, iris, mosc)

==================

5) (ambră, iris, santal)

6) (ambră, mosc, santal)

7) (cedru, iris, mosc)

8) (cedru, iris, santal)

9) (cedru, mosc, santal)

10) (iris, mosc, santal)

În secvența propusă apar soluțiile (ambră, mosc, santal), (cedru, mosc, santal), (cedru, iris, mosc), (cedru, iris, santal). Se observă faptul că soluția (cedru, mosc, santal) apare pe o poziție incorectă, întrucât nici soluția precedentă și nici soluția ulterioară nu corespund ordinii generării soluției, iar prin eliminarea sa din secvență se obțin trei dintre soluții, în ordinea în care au fost generate (pozițiile 6-8).

Răspuns corect b.

2. Se observă faptul că subprogramul F se va apela recursiv, primind ca parametrii numărul pentru care se dorește afișarea divizorilor proprii și divizorul propriu-zis. Divizorul propriu-zis este incrementat cu fiecare apel recursiv al subprogramului F. Momentul în care recursivitatea este părăsită este cel în care divizorul propriu-zis atinge o valoare egală cu jumătatea numărului (valoare peste care nu se mai pot găsi alți divizori). Divizorii proprii sunt afișați începând cu acest moment, în situația în care este respectată condiția n%d==0, deci în ordine descrescătoare, pe măsură ce se revine din recursivitate.

Ca atare, un apel corect al subprogramului F va fi F(2015, 2), astfel încât valoarea 1 nu va fi inclusă printre divizorii numărului 2015 (având în vedere faptul că este îndeplinită condiția 2015%1==0). De asemenea, având în vedere faptul că primul divizor propriu al numărului 2015 este 5, căutarea poate începe cu această valoare, astfel încât numărul de apeluri recursive să fie mai mic și impul de execuție proporțional. Așadar și apelul F(2015, 5) va avea același rezultat (ca de altfel și F(2015, 3), respectiv F(2015, 4)), doar că acesta este de preferat din punct de vedere al eficienței.

3. Soluția constă în parcurgerea cifră cu cifră a numărului și inspectarea acesteia pentru a se verifica dacă este un număr prim sau nu. Parcurgerea cifră cu cifră se realizează prin împărțiri succesive la 10 (restul împărțirii la 10 dă cifra curentă, pornind de la ordinul unităților spre ordine mai mari, câtul împărțirii la 10 realizează trecerea la pasul următor al algoritmului). În momentul în care a fost identificat o cifră ca număr prim, se incrementează un contor în care este reținur rezultatul. Pentru a se stabili dacă un număr este prim sau nu, este definit un subprogram separat, care parcurge toți potențialii divizori (între 2 și radicalul numărului) și în cazul în care se obține un rest nenul la împărțirea dintre numărul respectiv și divizor se trage concluzia că numărul nu este prim. Cazurile n = 0 și n = 1 sunt tratate individual.

using namespace std;
#include <iostream>
#include <math.h>

int prim(int n) {
    if (n == 0 || n == 1) {
        return 0;
    }
    for (int k = 2; k <= sqrt(n); k++) {
        if (n % k == 0) {
            return 0;
        }
    }
    return 1;
}

int NrPrime(long n) {
    int cifre_prime = 0;
    while (n > 0) {
        if (prim(n % 10)) {
            cifre_prime++;
        }
        n = n / 10;
    }
    return cifre_prime;
}

int main() {
    long n;
    cout << "n="; cin >> n;
    cout << "Numarul " << n << " contine " << NrPrime(n) << " cifre prime" << endl;
    return 0;
}

 

4.

a) Se observă faptul că fiecare termen impar din prima jumătate a șirului se înmulțește cu toți termenii pari din ultima jumătate a șirului, prin urmare, termenul impar poate fi dat factor comun și înmulțit cu suma termenilor pari. În continuare, se dă factor comun suma termenilor pari din ultima jumătate a șirului, aceasta fiind înmulțită cu suma termenilor impari din prima jumătate a șirului. Un raționament similar se urmează și în cazul celeilalte sume, vizând tipurile complementare de termeni.

Se notează:

  • sum_first_odd: suma termenilor impari din prima jumătate a șirului;
  • sum_first_even: suma termenilor pari din prima jumătate a șirului;
  • sum_last_odd: suma termenilor impari din ultima jumătate a șirului;
  • sum_last_even: suma termenilor pari din ultima jumătate a șirului.

Astfel, suma cerută va fi sum_first_odd * sum_last_even + sum_first_even * sum_last_odd.

Sumele astfel definite pot fi determinate pe măsură ce termenii sunt citiți din fișier, astfel încât complexitatea algoritmului este liniară – (O(n)), iar pentru reținerea sumelor respective sunt alocate patru variabile de tip întreg, astfel încât se respectă și constrângerea cu privire la eficiența din perspectiva spațiului de stocare.

b)

using namespace std;
#include <iostream>
#include <fstream>

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

int main() {
    ifstream file("bac.txt");
    int n, crt_pos = 0, temp, sum_first_odd = 0, sum_first_even = 0, sum_last_odd = 0, sum_last_even = 0;
    if (file.is_open()) {
        file >> n;
        while (file >> temp) {
            if (crt_pos++ < n) {
                if (parity(temp)) {
                    sum_first_odd += temp;
                }
                else {
                    sum_first_even += temp;
                }
            }
            else {
                if (parity(temp)) {
                    sum_last_odd += temp;
                }
                else {
                    sum_last_even += temp;
                }
            }
        }
        cout << "Suma este " << (sum_first_odd * sum_last_even + sum_first_even * sum_last_odd) << endl;
        file.close();
    }
    return 0;
}

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

Nici în acest an rata de promovabilitate înregistrată la examenul de bacalaureat în sesiunea de toamnă nu a fost foarte crescută (25,67%), fiind comparabilă cu cea din anii precedenți (23,80%). Cei mai mulți dintre cei reușiți aparțin promoției curente (74,80%), prevalente fiind mediile din intervalul 6-6,49. Este important și procentul celor care au absentat (aproximativ 20%) precum și numărul mare de contestații înregistrate, la fiecare probă în parte, în raport cu rezultatele înregistrate în urma acestora. Toate aceste cifre pledează, așa cum susțineam și anul trecut, pentru desființarea unei sesiuni suplimentare a examenului de bacalaureat. Sunt relativ puține facultățile care organizează sesiune de admitere în luna septembrie și probabil că și interesul “absolvenților” pentru admiterea la facultate este mai redus. Perioada dintre cele două sesiuni este de numai o lună și jumătate și este greu de crezut că un elev poate asimila, într-un răstimp atât de scurt, informațiile pe care ar fi trebuit să și le însușească pe parcursul a patru ani de liceu. Este adevărat că o astfel de măsură ar putea descuraja eventualele încercări ulterioare ale celor respinși, însă un număr mai scăzut de persoane cu diplomă de bacalaureat nu este în mod necesar un dezastru, ci doar o reflecție mai fidelă (decât în prezent) al nivelului cultural din țară.

Subiectele (și baremele aferente) pentru proba de matematică din sesiunea august 2015 a examenului de bacalaureat pot fi descărcate de pe site-ul Ministerului Educației Naționale dedicat subiectelor la examenele naționale:

Din punct de vedere al dificultății, subiectele din sesiunea de toamnă au fost asemănătoare cu cele din sesiunea de vară, obținerea unei note de 7-8 putând fi realizată doar cu aplicarea câtorva formule, fără a presupune ingeniozitatea folosirii unor artificii de calcul. Astfel de cerințe făceau diferența doar între o medie de 9 și una de 10, care oricum nu a fost obținută de nimeni. Unele dintre exerciții ar fi putut fi rezolvate chiar și de absolvenții de gimnaziu (grafice de funcții de gradul întâi, rezolvarea unor triunghiuri dreptunghice particulare).

S-a încercat și în acest an o distribuire echilibrată a subiectelor: subiectul I conține 4 exerciții de algebră din materia claselor a IX-a și a X-a precum și 2 exerciții de geometrie și trigonometrie, subiectul al II-lea este format din 2 exerciții de algebră din materia claselor a X-a (polinoame) și a XI-a (determinanți) iar subiectul al III-lea vizează cunoștințele de analiză matematică din clasa a XI-a (grafice de funcții și limite de funcții) și din clasa a XII-a (calculul integralelor). A devenit aproape un “obicei” evitarea elementelor de combinatorică, sistemelor de ecuații liniare, legilor de compoziție, șirurilor de funcții și a aplicării unor teoreme (Darboux, Rolle, spre exemplu). Acestea ar putea fi integrate printre celelalte subiecte, asigurând astfel o verificare mai completă a cunoștințelor și sporind corespunzător gradul de dificultate al exercițiilor, în special pentru profilurile cu mai multe ore de matematică pe săptămână.

Subiectele de algebră și elemente de analiză matematică de la examenul de admitere la facultate, Universitatea “Politehnica” București, sesiunea iulie 2015

În acest an, senatul Universității “Politehnica” București a luat decizia îndrăzneață ca pentru obținerea statutului de student în cadrul oricărei facultăți din cadrul său să se susțină examen de admitere, format din două probe distincte, desfășurate pe parcursul a trei ore. La o astfel de opțiune se poate să fi contribuit și eșecul din vara precedentă când numărul candidaților înscriși a fost foarte mare, locurile au fost ocupate încă din sesiunea din iulie la cele mai multe dintre facultăți, însă mulți dintre cei admiși nu au reușit să promoveze examenele din prima sesiune, din cauza pregătirii anterioare deficitare.

O astfel de hotărâre dovedește – așa cum am afirmat și mai sus – destul de mult curaj, în condițiile în care conducerea Academiei de Studii Economice București a stabilit ca admiterea în anul I al ciclului de licență să se facă practic pe baza mediei de la examenul de bacalaureat, de vreme ce toți candidații au primit calificativul ADMIS în urma evaluării eseului motivațional (pentru a cărui alcătuire puteau fi găsite suficient de multe solicitări – remunerate – pe diverse forumuri si alte site-uri). Din punct de vedere pecuniar, alegerea a fost una încununată de succes (taxa de înscriere nefiind chiar modică – 100 RON pentru 2 opțiuni, pentru fiecare opțiune suplimentară fiind necesar să se achite încă 25 RON), însă adevăratul cost va fi plătit odată cu sesiunea de examene din iarnă de înseși cadrele didactice ale facultăților care, în fața unor studenți slab pregătiți, se vor confrunta cu următoarea dilemă: vor scădea nivelul cerințelor până la un nivel vecin cu prostituția academică pentru ca numărul restanțierilor să fie unul acceptabil sau vor menține aceleași criterii de exigență ca în trecut, riscând să declanșeze un fenomen de abandon în masă?

(Re)introducerea examenului de admitere obligatoriu a scăzut destul de mult interesul absolvenților de liceu pentru facultățile tehnice (comparativ cu anul precedent), putându-se vorbi de concurență la doar 6 din cele 15 instuții de învățământ superior din cadrul Politehnicii (Automatică și Calculatoare, Electronică, Telecomunicații și Tehnologia Informației, Transporturi, Inginerie Aerospațială, Inginerie Medicală, Antreprenoriat, Ingineria și Managementul Afacerilor). Cu toate acestea, în urma redistribuirii candidaților pe baza opțiunilor, cam toată lumea a reușit să prindă un loc pe undeva și puține sunt facultățile pentru care locurile bugetate să fi rămas descoperite.

Noutatea – de mult așteptată – în privința examenului de admitere de la Universitatea “Politehnica” București a constat în faptul că subiectele la examene au fost diferențiate în funcție de facultăți:

  • o variantă A, cu subiecte banale, care să verifice faptul că materia pentru examenul de admitere a fost parcursă cât de cât – pentru facultățile la care nivelul de concurență a fost scăzut, subunitar;
  • o variantă B, cu câteva subiecte de departajare (în special pentru note peste 8,50-9) pentru facultățile la care numărul de candidați pe loc permitea acest lucru.

Subiectele de algebră și elemente de analiză matematică au fost, și în acest an, extrem de facile, dovadă fiind numărul mare de candidați care au reușit să obțină nota 10 (numai la Facultatea de Automatică și Calculatoare, specializarea Calculatoare și Tehnologia Informației 289 de candidați din cei 320 admiși au avut o astfel de performanță).

În cazul variantei A, subiectele au fost preponderent de algebră (15 subiecte din cele 18, dintre care 4 puteau fi rezolvate și de absolvenții de gimanziu – ecuații și inecuații de gradul I cu o necunoscută, sisteme de ecuații cu 2 necunoscute, radicali de gradul întâi). De asemenea, s-a insistat mai mult pe materia claselor a IX-a și a X-a (aproximativ 70% din subiecte). Prin urmare, examenul a fost mai degrabă unul formal, menit să descurajeze doar pe cei care și-ar fi depus dosarul doar ca să își asigure un loc la facultate (sau în cămin), fără să aibă vreo intenție de a urma cursurile facultății respective.

În ceea ce privește varianta B, mi-au atras atenția trei subiecte:

  • o limită, rezolvabilă aplicând regula lui l’Hôspital, pentru care inițial trebuia să se rezolve o integrală definită, folosind formula „prin părți”; exercițiul nu era foarte dificil, nu presupunea un grad de ingeniozitate prea ridicat, însă era necesar un nivel sporit de atenție la calcule; în plus, erau combinate noțiuni de analiză matematică din două zone diferite: calculul integral și rezolvarea limitelor de funcții;
  • o ecuație de gradul întâi în care necunoscuta făcea parte dintr-o expresie cu 3 module imbricate; de asemenea, și aici era necesară foarte multă răbdare în a „diseca” toate cazurile posibile și foarte multă atenție în a identifica intervalele pe care se studiază soluția ecuației; nici variantele de răspuns nu erau menite să ajute foarte mult candidatul întrucât soluțiile ecuației nu erau „oferite pe tavă” (astfel încât identificarea răspunsului corect să se rezume la o simplă identificare), fiind necesar să se determine numărul acestora;
  • un polinom de grad n cu parametru care se cerea a fi identificat pe baza unei condiții de divizibilitate cu un alt polinom ale cărui rădăcini erau numere complexe; soluția pe care am găsit-o eu implica scrierea numărului complex sub formă trigonometrică și aplicarea formulei lui Moivre pentru ridicarea la puterea n, urmată de egalarea cu 0 a valorii polinomului în punctele care anulau și polinomul cu care acesta trebuia să se dividă – din acest moment, identificarea parametrului se făcea foarte ușor, mai ales că se regăsea printre variantele de răspuns, însă nu știu în ce măsură o astfel de rezolvare se încadrează în tematica examenului de admitere.

Au lipsit, ca în fiecare an, binomul lui Newton, șirurile de numere, legile de compoziție, care nu se pretează probabil tipului de examen de tip grilă.

Rezolvările complete ale subiectelor de algebră și elemente de analiză matematică pentru examenul de admitere la facultate în cadrul Universității “Politehnica” București pot fi descărcate de mai jos:

rezolvari_upb2015A

rezolvari_upb2015B

Pentru anii următori, provocarea ar fi ca gradul de dificultate al subiectelor să fie mai sporit, astfel încât departajarea candidaților să fie cât mai corectă, iar ponderea examenului de bacalaureat să conteze din ce în ce mai puțin pentru ocuparea unui loc, mai ales la facultățile unde concurența este mare.

Rezolvarea subiectelor de informatică de la examenul de bacalaureat național, sesiunea iulie 2015 (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 al II-lea (30 de puncte)


1. Vom analiza, pe rând, fiecare dintre expresiile propuse spre evaluare:

a) x = sqrt(x);

Această expresie este corectă din punct de vedere sintactic, întrucât variabilei reale x (x > 0), inițializată anterior, i se asociază o valoare egală cu rădăcina sa pătrată.

b) x = sqrt(sqrt(16));

Această expresie este corectă din punct de vedere sintactic, întrucât în urma evaluării expresiei, variabila reală x va fi inițializată cu valoarea 2.0 (sqrt(16) = 4.0, sqrt(4.0) = 2.0), pierzându-se astfel valoarea stocată anterior;

c) cin >> sqrt(4); sau scanf(“%f”, &sqrt(4));

Această expresie este incorectă din punct de vedere sintactic, întrucât expresia sqrt(4) este o constantă (evaluată la valoarea 2.0), astfel încât nu poate fi citită, de la tastatură, o altă valoare care să fie atribuită ulterior acesteia. Atribuirea de valori de la tastatură este posibilă numai pentru variabile, aceasta constituind o modalitate pentru inițializarea sa.

d) cout << sqrt(4)+1; sau printf(“%f”, sqrt(4)+1);

Această expresie este corectă din punct de vedere sintactic, întrucât, în urma execuției acesteia, pe monitor se va afișa valoarea 3.0 (expresia sqrt(4) este evaluată ca fiind 2.0, ulterior această valoare fiind incrementată).

Răspunsul corect este c.

2. Pentru determinarea celui mai mare divizor comun, se folosește de regulă algoritmul lui Euclid, care este disponibil în două variante (prin scăderi și împărțiri succesive), implementarea putând fi atât iterativă, cât și recursivă.

În exemplele din problemă, sunt prezentate variantele iterative, prin scăderi și împărțiri succesive:

a) prin scăderi succesive:

if (x == 0) {
    x = y;
}
while (y != 0) {
    if (x > y) {
        x = x - y;
    } else {
        y = y - x;
    }
}

b) prin împărțiri succesive:

while (y != 0) {
    aux = y;
    y = x % y;
    x = aux;
}

Se observă că secvența S1 este echivalentă cu algoritmul de la punctul a).

Se observă că secvența S2 NU este echivalentă cu algoritmul de la punctul b), întrucât valoarea reținută de variabila x se pierde, odată ce se stochează în ea restul împărțirii lui x la y, stocarea lui y în variabila temporară z neavând nici un sens, de vreme ce aceasta nu mai este utilizată ulterior. De asemenea, y primește valoarea lui x, astfel că ciclul repetitiv se va termina după cel mult 2 iterații.

Prin urmare, răspunsul corect este a.

3. În urma majorării cu 50%, cartea va avea următorul preț:

preț = preț + preț * 50% = preț + preț * 0,5 = preț * (1 + 0,5) = preț * 1,5 = preț * 3 /2

Așadar, instrucțiunile C/C++ prin care valoarea unei variabile reale p (declarată ca float p; sau double p; și inițializată corespunzător) pot fi:

a) p = p * 1.5;

b) p = p * 3/2;

4.

a) Întrucât se cere algoritmul de rezolvare în pseudocod, este mai facil ca soluția pentru această problemă să fie iterativă și să nu se folosească de alte funcții ajutătoare (pentru determinarea unui element din șirul lui Fibonacci sau pentru verificarea parității unui număr).

Astfel, într-un ciclu repetitiv, se vor calcula termenii șirului lui Fibonacci, începând cu f(1). Dacă un termen din șir este impar, atunci se scade din valoarea lui n o unitate, semn că un număr dintre cele care îndeplinesc condiția solicitată a fost găsit, căutarea terminându-se în momentul în care n ajunge 0. Calcularea unui termen din șirul lui Fibonacci (dacă pasul curent din iterație este k, se va calcula fibonacci(k)) se face reținând în permanență cele 2 valori anterioare: fibonacci(k-1) și fibonacci(k-2) astfel încât să se poată aplica formula de recurență cunoscută: fibonacci(k) = fibonacci(k-1) + fibonacci(k-2).

intreg n, k = 1, fibonacci1, fibonacci2, fibonnaci
citeste n
cat timp n > 0 executa
    daca k = 1 atunci
        fibonacci1 = 1
        fibonacci = 1
    altfel daca k = 2 atunci
        fibonacci2 = 1
        fibonacci = 1
    altfel
        fibonacci = fibonacci1 + fibonacci2
        fibonacci1 = fibonacci2
        fibonacci2 = fibonaaci
    sfarsit daca
    daca fibonacci % 2 != 0 atunci
        n = n - 1
    sfarsit daca
    k = k + 1;
sfarsit cat timp
afiseaza fibonacci

Implementarea în C/C++ a algoritmului în pseudocod prezentat anterior este:

using namespace std;

#include <iostream>

int main() {
    int n, k = 1, fibonacci1 = 0, fibonacci2 = 0, fibonacci;
    cout << "n = "; cin >> n;
    while (n > 0) {
        switch (k) {
            case 1:
                fibonacci1 = 1;
                fibonacci = 1;
                break;
            case 2:
                fibonacci2 = 1;
                fibonacci = 1;
                break;
            default:
                fibonacci = fibonacci1 + fibonacci2;
                fibonacci1 = fibonacci2;
                fibonacci2 = fibonacci;
                break;
        }
        if (fibonacci % 2 == 1) {
            n--;
        }
        if (n != 0) {
            k++;
        }
    }
    cout << "Elementul cautat se gaseste pe pozitia " << k << " si are valoarea " << fibonacci << endl;
    return 0;
}

b) Datele de intrare sunt reprezentate de variabila n, număr natural nenul, reprezentând al câtelea termen impar din șirul lui Fibonacci se dorește a fi determinat. Valoarea sa se citește de la tastatură.

Datele de ieșire sunt reprezentate de variabila fibonacci, număr natural nenul, reprezentând al n-lea termen impar din șirul lui Fibonacci. Valoarea sa se calculează folosind formula de recurență prin care se definește șirul lui Fibonacci fibonacci(k) = 1, k = 1 sau 2, fibonacci(k) = fibonacci(k-2) + fibonacci(k-1), altfel și se afișează pe monitor.

S-au mai utilizat următoarele variabile:

  • k, pasul curent de iterație, reprezentând al câtelea termen din șirul lui Fibonacci se calculează la momentul de timp respectiv (indiferent dacă acesta este par sau impar); este inițializat cu 1 și este incrementat la fiecare pas al ciclului repetitiv atâta vreme cât nu s-a obținut al n-lea termen impar din șirul lui Fibonacci;
  • fibonacci1, reprezintă termenul din șirul lui Fibonacci aflat cu 2 poziții înainte de termenul curent (dacă pasul curent este k, fibonacci1 reține f(k-2), unde f este funcția Fibonacci); este inițializat cu 1 pentru k = 1;
  • fibonacci2, reprezintă termenul din șirul lui Fibonacci aflat cu 1 poziție înainte de termenul curent (dacă pasul curent este k, fibonacci2 reține f(k-1), unde f este funcția Fibonacci); este inițializat cu 1 pentru k = 2.

 

SUBIECTUL al III-lea (30 de puncte)


1. Se observă că:

pentru i = 1, se afișează valorile 6 – j, oricare ar fi j = 1, 5

pentru i = 2

  • se afișează valoarea 6 – i, pentru j = 1
  • se afișează valorile 6 – j, pentru j = 2, 5

pentru i = 3

  • se afișează valorile 6 – i, pentru j = 1, 2
  • se afișează valorile 6 – j, pentru j = 3, 5

pentru i = 4

  • se afișează valorile 6 – i, pentru j = 1, 3
  • se afișează valorile 6 – j, pentru j = 4, 5

pentru i = 5

  • se afișează valorile 6 – i, pentru j = 1, 4
  • se afișează valoarea 6 – j, pentru j = 5

Ca o regulă generală, se afișează 6 – i pentru j < i și 6 – j altfel.

Prin urmare, condiția instrucțiunii if este i < j. Răspunsul corect este a.

2. Având în vedere că tablourile A și B sunt deja sortate (A – crescător, B – descrescător), acestea pot fi parcurse simultan (A – în sens invers, B – în sens normal) pentru construirea elementelor tabloului C.

Fie A = (a[0], a[1], a[2], a[3], a[4]) și B = (b[0], b[1], b[2], b[3], b[4]).

Rezultă că rezulatul va fi tabloul C = (c[0], c[1], c[2], c[3], c[4], c[5], c[6], c[7], c[8], c[9]), având un număr de elemente egal cu suma elementelor celor două tablouri care sunt interclasate.

a) a[4] > b[0] => c[0] = a[4] = 16

b) a[3] < b[0] => c[1] = b[0] = 15

c) a[3] = b[1] => c[2] = a[3] = 10

d) a[2] < b[1] => c[3] = b[1] = 10

e) a[2] < b[2] => c[4] = a[2] = 9

f) a[2] < b[3] => c[5] = a[3] = 8

g) a[2] > b[4] => c[6] = a[2] = 7

h) a[1] < b[4] => c[7] = b[4] = 3

i) parcurgerea vectorului b s-a terminat => c[8] = a[1] = 2

j) parcurgerea vectorului b s-a terminat => c[9] = a[0] = 1

Prin urmare se obține ca rezultat tabloul C = (16, 15, 10, 10, 9, 8, 7, 3, 2, 1), care nu este altceva decât reuniunea elementelor din tablourile A și B, sortată descrescător (construirea se face însă pe măsura parcurgerii celor două tablouri, exploatând faptul că acestea sunt deja sortate, pentru a reduce complexitatea ordonării ulterioare a rezultatului obținut).

3. Rezolvarea problemei presupune citirea celor n elemente ale vectorului, după care acesta mai este parcurs încă o dată, fie crescător (de la pozițiile mici spre pozițiile mari), fie descrescător (de la pozițiile mari spre pozițiile mici), reținându-se pe fiecare poziție a vectorului elementul anterior / următor (în funcție de sensul de parcurgere). Totuși, într-o variabilă temporară trebuie reținut ultimul element, astfel încât valoarea acestuia să fie atribuită primului element, operație care va fi realizată manual, în afara structurii repetitive.

Având în vedere că elementele vectorului pot lua valori în intervalul [0, 109], acesta trebuie declarat de tip long, astfel încât să se aloce în memorie spațiu suficient pentru stocarea unor astfel de date.

using namespace std;

#include <iostream>

int main() {
    int n, k;
    long *v;
    cout << "n = "; cin >> n;
    v = new long[n];
    for (k = 0; k < n; k++) {
        cout << "v[" << k << "] = ";
        cin >> v[k];
    }
    long temp = v[n - 1];
    for (k = n - 1; k > 0; k--) {
        v[k] = v[k - 1];
    }
    v[0] = temp;
    for (k = 0; k < n; k++) {
        cout << v[k] << " ";
    }
    cout << endl;
    delete[] v;
    return 0;
}

4.

a) Soluția evidentă a acestei probleme constă în 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, de maxim 101 elemente, având în vedere că numerele care apar în fișier pot avea doar valori din intervalul [0, 100]. Semnificația unui element  de pe o anumită poziție din acest vector este următoarea:

  • 0 – numărul corespunzător poziției respective nu se regăsește în șir
  • 1 – numărul corespunzător poziției respective 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, afișându-se mesajul DA și terminându-se căutarea. 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.

În situația în care căutarea a ajuns la ultimul element, înseamnă că nu a fost identificată nici o pereche și prin urmare se afișează mesajul NU.

b)

using namespace std;

#define MAX_SIZE 100

#include <iostream>
#include <fstream>

int main() {
    ifstream file("bac.txt");
    int *exists = new int[MAX_SIZE + 1], n, last_position = -1;
    for (n = 0; n <= MAX_SIZE; n++) {
        exists[n] = 0;
    }
    if (file.is_open()) {
        while (file >> n) {
            exists[n] = 1;
        }
        file.close();
        for (n = 0; n <= MAX_SIZE; n++) {
            if (exists[n]) {
                if ((last_position != -1) && (n - last_position >= 2)) {
                    cout << "DA" << endl;
                    break;
                }
                last_position = n;
            }
        }
    }
    if (n == MAX_SIZE + 1) {
        cout << "NU" << endl;
    }
    delete[] exists;
    return 0;
}

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

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