Tag: bacalaureat 2015

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

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