Rezolvare Bacalaureat Informatica 2019 C++ sesiunea august

Data: august 2019
Profil: Matematica-Informatica
Limbaj: C++

Tutoriale Recomandate:

Subiectul I.

1. O expresie C/C++ care are valoarea 0 este:

a. ’m’ < ’n’
b. ’m’ == ’M’
c. ’M’==’m’+’N’-’n’
d. ’N’==’M’+1

In aceasta problema se converteste fiecare caracter cu codul lui echivalent in tabelul ascii. Convertim fiecare caracter iar subpunctele devin:

a. 109 < 110
b. 109 == 77 -> raspunsul corect
c. 77 == 109 + 78 – 110
d. 78 == 77 + 1

2. Subprogramul f este definit alăturat. Indicaţi ce se afişează în urma apelului de mai jos.
f(75,30);

void f(int i, int j)
{
    cout << i << " ";
    if( i != j )
    {
        if( i < j )
        { 
            i = i + j; 
            j = i - j; 
            i = i - j; 
        }
        f( i - j, j);
    }
}

Facem tabelul si urmarim cum se schimba pe rand valorile

Asadar raspunsul final este c. 75 45 15 15

3. Utilizând metoda backtracking, se generează toate torturile formate din trei straturi de tipuri distincte de cremă din mulţimea {caramel, ciocolată, frișcă, nuci, vanilie}. Ultimul strat este de frișcă sau de vanilie, iar aceste tipuri de cremă nu pot apărea pe primele două straturi. Două torturi cu straturi din aceleași tipuri de cremă sunt diferite dacă acestea sunt dispuse în altă ordine. Primele patru soluții generate sunt, în această ordine: (caramel, ciocolată, frișcă), (caramel, ciocolată, vanilie), (caramel, nuci, frișcă), (caramel, nuci, vanilie). A cincea soluție este:

Codificam variantele de raspuns:

1 – caramel
2 – ciocolata
3 – frisca
4 – nuci
5 – vanilie
De asemenea, 3 si 5 sunt ultimele cifre ce sunt acceptate pe ultima pozitie. Iar 3 si 5 nu au voie sa se regaseasca pe prima sau a doua pozitie.

Asadar varianta de raspuns este a. (ciocolată, caramel, frișcă)

4. Numărul de noduri ale unui arbore cu 4 muchii este:

Numaram nodurile si obtinem raspunsul d. 5

5. Valorile care pot reprezenta gradele nodurilor unui graf neorientat, cu 6 noduri, sunt:

Realizam cate o figura pentru fiecare subpunct. Observam faptul ca doar pentru subpunctul b putem forma un graf ce respecta cerinta.

Subiectul II.

1. S-a notat cu a%b restul împărţirii numărului natural a la numărul natural nenul b şi cu [c] partea întreagă a numărului real c.

citeşte n (număr natural)
m<- 0; x <-1
cât timp x ≤ 9 execută
--- cp <-n
--- cât timp cp ≠ 0 execută
------ dacă cp % 10 = x atunci
--------- m <-m * 10 + x
------ cp<- [ cp / 10 ]
--- x <-x+1
scrie m

a) Scrieţi valoarea afişată dacă se citește numărul 27102.

Facem tabelul corespunzator acestui algoritm si obtinem raspunsul 1227.

b) Scrieţi trei numere distincte din intervalul [10,9999] care pot fi citite, astfel încât în urma executării algoritmului, pentru fiecare dintre acestea, valoarea afişată să fie 11.

Facem urmatoarea observatie: acest algoritm afiseaza cifrele ce se regasesc in numar, in ordine crescatoare a lor. De exemplu daca am fi citit pentru numarul n: 1234, 4321, 4213 sau 1423 atunci la final s-ar fi afisat 1234.

Mai observat faptul ca x incepe de la 1, cifra 0 fiind ignorata. Asadar pentru a obtine 11 la final, noi putem citii numerele 11, 101 sau 1001 .

c) Scrieţi programul C/C++ corespunzător algoritmului dat.

#include    <iostream>

using namespace std;

int main()
{
    int m, x, cp;
    unsigned int n;
    cin >> n;
    m = 0;
    x = 1;
    while( x <= 9 )
    {
        cp = n;
        while( cp != 0 )
        {
            if(cp % 10 == x)
                m = m * 10 + x;
            cp = cp / 10;
        }
        x = x + 1;
    }
    cout << m;
}

d) Scrieţi în pseudocod un algoritm, echivalent cu cel dat, înlocuind prima structură cât timp…execută cu o structură de tip pentru…execută.

citeşte n (număr natural)
m<- 0;
pentru x <- 1, 9 execută
--- cp <-n
--- cât timp cp ≠ 0 execută
------ dacă cp % 10 = x atunci
--------- m <-m * 10 + x
------ cp<- [ cp / 10 ]
scrie m

2. Fiind date două șiruri de caractere a şi b, îl numim pe a sufix al lui b dacă a este egal cu b sau dacă b se poate obţine din a prin alipirea la stânga a unor noi caractere. Variabilele a şi b pot memora câte un șir cu cel mult 20 de caractere. Scrieţi o secvenţă de instrucţiuni în urma executării căreia variabila a să memoreze un sufix al lui b format din trei caractere, sau șirul nedeterminat, dacă nu există un astfel de sufix.
Exemplu: dacă b memorează şirul centaur, atunci a memorează şirul aur, iar dacă b memorează şirul au, atunci a memorează şirul nedeterminat.

Pentru a rezolva aceasta problema vom apela la un truc clasic atunci cand vine vorba de lucrul cu sirurile de caractere.

Sa presupunem ca noi avem memorat in variabila s cuvantul “tutorial“. Ce se intampla atunci cand vom afisa s+1 sau s+2 ?

Pentru cout << s + 1; vom obtine “utorial“.
Pentru cout << s + 2; vom obtine “torial“.

Asadar, noi trebuie sa atribuim lui b ultimele 3 litere ale lui a.

int lungime = strlen(b) - 3;
if(lungime < 0)
    strcpy(a, "nedeterminat");
else
    strcpy(a, b+lungime);
cout << a;

3. În declarările alăturate, variabila p memorează coordonatele unui punct în sistemul de coordonate xOy, iar variabila c memorează datele caracteristice ale unui cerc: lungimea razei și coordonatele centrului său. Scrieți o expresie care are valoarea 1 dacă şi numai dacă punctul corespunzător variabilei p coincide cu centrul cercului corespunzător variabilei c.

struct punct
{ 
    int x,y;
}p;

struct cerc
{
    struct punct centru;
    float raza;
}c;

(p.x == c.centru.x && p.y == c.centru.y)

Subiectul III.

1. Subprogramul MaxImp are doi parametri, a și b, prin care primeşte câte un număr natural
(2≤a<b≤400). Subprogramul returnează cel mai mare număr natural din intervalul [a,b] pentru care produsul divizorilor săi impari pozitivi este strict mai mare decât el însuși sau 0, dacă nu există niciun astfel de număr. Scrieţi definiţia completă a subprogramului.
Exemplu: dacă a=14 și b=19, atunci subprogramul returnează 18 (1 · 3 · 9 = 27 > 18).

int MaxImp(int a, int b)
{
    for(int i = b; i >= a; i--)
    {
        int produs = 1;
        for(int div = 2; div <= i / 2; div++)
        {
            if(i % div == 0 && div % 2 == 1)
                produs = produs * div;
        }
        if(produs > i)
            return produs;
    }
    return 0;
}

2. Numim pătrat de dimensiune m al unui tablou bidimensional tabloul obținut din acesta păstrând doar elementele aflate pe primele m linii şi pe primele m coloane ale sale. Scrieţi un program C/C++ care citeşte de la tastatură un număr natural, n (n∈[2,20]), apoi elementele unui tablou bidimensional cu n linii şi n coloane, numere naturale din intervalul [0,10⁴]. Programul determină un pătrat de dimensiune maximă al tabloului citit, cu toate elementele egale, și afișează pe ecran valoarea acestei dimensiuni.
Exemplu: pentru n=5 și tabloul alăturat, se afişează pe ecran 3.

#include    <iostream>

using namespace std;

int main()
{
    int n;
    unsigned int matrice[20][20];

    cin >> n;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
            cin >> matrice[i][j];
    }

    unsigned int el = matrice[0][0];

    int stop = 0;
    for(int m = 2; m <= n; m++)
    {
        for(int i = 0; i < m; i++)
            if(matrice[i][m - 1] != el)
                stop = m - 1;

        for(int j = 0; j < m; j++)
            if(matrice[m - 1][j] != el)
                stop = m - 1;

        if(stop != 0)
            break;
    }
    cout << stop;
    return 0;
}

3. Fişierul bac.txt conţine un şir de cel puțin două și cel mult 10⁶ numere naturale din intervalul [0,10³], separate prin câte un spaţiu. Șirul are cel puțin un termen par și cel puțin un termen impar. Se cere să se afișeze pe ecran termenii șirului, separați prin câte un spaţiu, astfel încât toți cei impari să apară înaintea tuturor celor pari, şi atât subșirul format din cei impari, cât şi subșirul format din cei pari, să fie în ordine crescătoare, ca în exemplu. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fişierul conţine numerele 12 2 3 1 2 5 se afişează pe ecran: 1 3 5 2 2 12
a) Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.
b) Scrieți programul C/C++ corespunzător algoritmului proiectat.

a) Vom rezolva aceasta problema folosind vectorii de aparitie (sau vectorii de frecventa). Declaram separat doi vectori de aparitie: unul pentru numerele impare si unul pentru numerele pare.

Pe masura ce citim numerele, incrementam pozitia lor corespunzatoare paritatii numarului. In acelasi timp memoram cel mai mare nr impar si cel mai mare nr par citit. La final parcurgem vectorii de aparitii pana la maximul lor corespunzator si afisam numerele in ordine crescatoare.

Acest algoritm este eficient din punct de vedere al spatiului, deoarece nu trebuie sa memoram 100,000 numere. De asemenea, nu mai este nevoie de nici o sortare ulterioara, deoarece folosind vectorii de aparitie, avem garantat faptul ca numerele vor aparea in ordine crescatoare. Complexitatea acestui algoritm este liniara in O(n) – unde n este numarul total de numere din fisier.

#include    <iostream>
#include    <fstream>

using namespace std;

ifstream fin("bac.txt");

int impare[1001];
int pare[1001];

int main()
{
    int n;
    int maxImp = -1, maxPar = -1;
    while(fin >> n)
    {
        if(n % 2 == 0)
        {
            if(n > maxPar)
                maxPar = n;
            pare[n]++;
        }
        else
        {
            if(n > maxImp)
                maxImp = n;
            impare[n]++;
        }
    }

    for(int i = 1; i <= maxImp; i++)
    {
        for(int ap = 1; ap <= impare[i]; ap++)
            cout << i << " ";
    }
    
    for(int i = 0; i <= maxPar; i++)
    {
        for(int ap = 1; ap <= pare[i]; ap++)
            cout << i << " ";
    }
    return 0;
}

Comentarii

Rezolvare Bacalaureat Informatica 2019 C++ sesiunea august

Subiectul I.

Subiectul II.

Subiectul III.

TPN Rewind – Rezumatul a 7 ANI de activitate

Vectori de frecventa / aparitii – Tablouri unidimensionale

S-ar putea sa iti placa