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.

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).

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

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.

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 (2²=4).

b) Dacă pentru variabila k se citește valoarea 5 și rezultatul așteptat este 3 (adică cea mai mare putere este 5³=125), valorile lui n pentru care poate fi obținut acest rezultat se regăsesc în intervalul [5³, 5⁴-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.

Figura 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

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

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.

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 (x_n = x_n-1 + x_n-2, x₀=0, x₁=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:

  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:

Figura 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 (x₄, …, x₆) cu proprietatea că între oricare două vârfuri x_i și x_j din secvență există o muchie și fiecare vârf x_k 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).

Figura 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(n²) î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 10⁶ * 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;
}

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.

SUBIECTUL I (30 de puncte)

---

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

 

2. Algoritmul descris în pseudocod este:

citește n (număr natural nenul)

d ← 2

cât timp d ≤ n execută

    p ← 0

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

        p ← p + 1

        n ← [n / d]

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

        scrie d, ‘ ‘

    d ← d + 1

scrie n

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

d ← 2

2 ≤ 2352

    iterația 1 a primului ciclu cât timp

       p ← 0

       2352%2=0

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

             p ← 1

             n ← 1176

       1176%2=0

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

             p ← 2

             n ← 588

       588%2=0

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

             p ← 3

             n ← 294

       294%2=0

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

             p ← 4

             n ← 147

       147%2≠0

       4%2=0 și 4≠0

          scrie 2, ‘ ‘

d ← 3

3 ≤ 147

    iterația 2 a primului ciclu cât timp

       p ← 0

       147%3=0

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

             p ← 1

             n ← 49

       49%3≠0

       1%2≠0

d ← 4

4 ≤ 49

    iterația 3 a primului ciclu cât timp

       p ← 0

       49%4≠0

       p%2=0, dar p=0

d ← 5

5 ≤ 49

    iterația 4 a primului ciclu cât timp

       p ← 0

       49%5≠0

       p%2=0, dar p=0

d ← 6

6 ≤ 49

    iterația 5 a primului ciclu cât timp

       p ← 0

       49%6≠0

       p%2=0, dar p=0

d ← 7

7 ≤ 49

    iterația 6 a primului ciclu cât timp

       p ← 0

       49%7=0

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

             p ← 1

             n ← 7

       7%7=0

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

          p ← 2

          n ← 1

       1%7≠0

       2%2=0 și 2≠0

          scrie 7, ‘ ‘

d ← 8

8 > 1

scrie 1

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

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

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

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

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

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

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

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

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

citește n (număr natural nenul)

d ← 2

dacă d ≤ n

    execută

        p ← 0

        cât timp n%d=0 execută

            p ← p + 1

            n ← [n / d]

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

            scrie d, ‘ ‘

        d ← d + 1

    cât timp d ≤ n

scrie n

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

citește n (număr natural nenul)

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

    p ← 0

    cât timp n%d=0 execută

        p ← p + 1

        n ← [n / d]

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

        scrie d, ‘ ‘

scrie n

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

using namespace std;

#include <iostream>

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

SUBIECTUL II (30 de puncte)

---

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

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

Figura 1

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

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

d⁺(1)=2

d⁺(2)=0

d⁺(3)=2

d⁺(4)=2

d⁺(5)=0

d⁺(6)=4

d⁺(7)=0

d⁺(8)=2

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

 

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

strcpy(s, “1b2d3”);

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

s[2] = ‘a’ + 2;

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

strcpy(s,s+1);

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

strcpy(s+3,s+4);

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

Răspunsul corect este d.

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

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

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

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

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

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

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

using namespace std;

#include <iostream>

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

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

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

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

Figura 2

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

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

Figura 2a
Figura 2b

 

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

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

• citirea numărului de linii/coloane al tabloului bidimensional cu verificarea restricțiilor referitoare la gama de valori din care acestea pot face parte;
• alocarea dinamică a memoriei pentru stocarea elementelor tabloului bidimensional; acest spațiu de memorie trebuie dealocat la sfârșitul programului;
• citirea și afișarea elementelor tabloului bidimensional;
• parcurgerea unei linii/coloane specifice din matrice.

using namespace std;

#define MIN 3
#define MAX 50

#include <iostream>

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

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

SUBIECTUL III (30 de puncte)

---

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

Se consideră funcția recursivă:

int f(int n) {

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

    else if (n==10) return 7;

    else return f(n-2)-1;

}

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

f(15)=f(13)-1

  f(13)=f(11)-1

    f(11)=f(9)-1

      f(9)=f(10)+3

        f(10)=7

      f(9)=7+3=10

    f(11)=10-1=9

  f(13)=9-1=8

f(15)=8-1=7

Răspunsul corect este b.

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

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

Soluția 1:

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

Soluția 2:

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

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

Soluția 3:

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

Soluția 4:

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

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

Soluția 5:

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

Soluția 6:

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

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

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

Soluția 6:

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

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

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

Este evident că trebuie respectate simultan condițiile:

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

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

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

using namespace std;

#include <iostream>

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

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

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

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

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

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

b)

using namespace std;

#include <iostream>
#include <fstream>

#define MAX 1024

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