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