Rezolvare Bacalaureat Informatica 2020 C++ iulie

Data: iulie 2020
Profil: Matematica-Informatica
Limbaj: C++

Tutoriale Recomandate:

Subiectul I.

1. Indicati valoarea expresiei C/C++ alaturate: 3 + 5.0 / 2 + 2

Trebuie sa avem foarte mare grija la tipul variabilelor din aceasta expresie. De obicei aveam operatii doar cu numere intregi, dar de data aceasta apare si un numar cu virgula – 5.0.

O proprietate importanta in C++ este faptul ca atunci cand avem expresii cu mai multe tipuri de variabile – toate variabilele “se vor convertii” intr-o variabila comuna, pentru a calcula rezultatul folosind un singur tip de numar.

Asadar, raspunsul este d) 7.5

2. Variabila v memomreaza un tablou unidimensional cu 4 elemente, numerotate incepand de la 0. Subprogramul f este definit alaturat. Indicati setul de elemente pe care le poate avea tabloul memorat in v, in ordinea in care apar in acesta, astfel incat, in urma apelului de mai jos, sa se afiseze pe ecran 2020. f(0, v);

void f(int i, int v[4])
{
    if(i >= 3)
        v[i] = v[i] + 1;
    else
        f(i + 1, v);
    cout << v[i];
}

Executam subprogramul pentru subpunctul a, pentru a vedea cum functioneaza aceasta functie recursiva.

f(0, v) -> f(1, v) cout
f(1, v) -> f(2, v) cout
f(2, v) -> f(3, v) cout
f(3, v) -> v[3]++ cout

Deci daca am avea setul de valori {-1, 1, 0, 2} vom obtine pe ecran 301-1 , cu alte cuvinte, se mareste ultimul numar cu o unitate si se afiseaza elementele de la dreapta la stanga. Asadar, pentru b) 0,2,0,1 vom obtine 2020.

3. Utilizand metoda backtracking se genereaza toate variantele prin care patru persoane pot plati o consumatie totala de 200 de lei in urmatoarele conditii:

fiecare plateste o suma nenula, divizibila cu 10
primul plateste mai mult decat al doilea, al doilea mai mult decat al treilea, iar acesta mai mult decat al patrulea.

O solutie consta in patru valori, reprezentand, in ordine sumele platite de fiecare dintre cele patru persoane. Primele patru solutii generate sunt, in aceasta ordine: (70, 60, 40, 30), (70, 60, 50, 20), (80, 50, 40, 30), (80, 60, 40, 20). Indicati cea de a sasea solutie, in ordinea generarii acestora.

Asadar, raspunsul corect este c) 80, 70, 30, 20

4. Un arbore cu 10 noduri, numerotate de la 1 la 10, este reprezentat prin vectorul de “tati” (7, 5, 6, 5, 7, 0, 6, 3, 3, 8). Indicati numarul de noduri “frunza” ale acestui arbore.

Desenam arborele si observam ca avem 5 frunze: 10, 9, 1, 2 si 4. Asadar raspunsul este c) 5 frunze.

O alta metoda de a rezolva aceasta problema este sa va uitati cu atentie la vectorul de tati si sa identificati ce numere nu apar in el. Iar frunzele din arbore nu se regasesc in vectorul de tati pentru ca frunzele nu au “mostenitori” prin definitie, asadar nu au cum sa fie “tati”.

5. Un graf neorientat cu 5 noduri este reprezentat prin matricea de adiacenta alaturata. Indicati numarul grafurilor partiale conexe ale acestuia care sunt diferite de graful dat.

Pentru a obtine un graf conex, avand 5 noduri trebuie sa folosim minim 4 muchii. In problema noastra desenul are 5 muchii in total. Asadar putem elimina maxim o muchie. Acum ne gandim ce muchii putem elimina.

Daca eliminam (pe rand) muchiile subliniate cu rosu, putem obtine un graf conex. Asadar raspunsul este a) 4 grafuri partiale.

Subiectul II.

1. Algoritmul alăturat este reprezentat în pseudocod. 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 a (număr natural)
c <- 0
repetă
--- b <- a; x <- 0
--- repetă
------ dacă b % 10 = c atunci
--------- x <- 1
------ b <- [b/10]
--- până când b = 0 sau x = 1
--- scrie x, ’ ’
--- c <- c + 2
până când c > 9

a. Scrieți valorile afișate dacă se citește numărul 240107.

Facem tabelul pentru acest algoritm si obtinem raspunsul: 1 1 1 0 0.

b. Scrieți cel mai mic și cel mai mare număr din intervalul [10⁵,10⁶), cu cifre distincte, care pot fi citite astfel încât, pentru fiecare dintre acestea, în urma executării algoritmului, toate valorile afișate să fie nenule.

Analizam mai intai ce face algoritmul acesta. Parcurge pe rand toate cifrele pare (0, 2, 4, 6 si 8) si verifica fiecare cifra din a pe rand daca este egala cu cifra curenta. Daca numarul a contine acea cifra para atunci se va afisa 1, in caz contrar, se va afisa 0.

Trebuie sa luam cel mai mic si cel mai mare numar de 6 cifre (100,000 -> 999,999) care are toate cifrele pare. Asadar obtinem raspunsul 102468 si 986420.

c. Scrieți programul C/C++ corespunzător algoritmului dat.

#include    <iostream>

using namespace std;

int main()
{
    unsigned int a, c, b, x;
    cin >> a;
    c = 0;
    do
    {
        b = a;
        x = 0;
        do
        {
            if(b % 10 == c)
                x = 1;
            b = b / 10;
        }while(b != 0 && x != 1);
        cout << x << " ";
        c = c + 2;
    }while(c <= 9);
    return 0;
}

d. Scrieți în pseudocod un algoritm echivalent cu cel dat, înlocuind adecvat a doua structură repetă…până când cu o structură repetitivă de alt tip.

citește a (număr natural)
c <- 0
repetă
--- b <- a; x <- 0
--- cat timp b != 0 si x != 1
------ dacă b % 10 = c atunci
--------- x <- 1
------ b <- [b/10]
--- scrie x, ’ ’
--- c <- c + 2
până când c > 9

2. Variabila c memorează, pentru un calculator, capacitatea memoriei (interne și externe), măsurată în GB, și o literă, corespunzătoare tipului monitorului acestuia. Știind că expresiile C/C++ de mai jos au ca valori litera corespunzătoare tipul monitorului și două numere naturale din intervalul [1,10⁶], reprezentând capacitatea memoriei interne, respectiv capacitatea memoriei externe a calculatorului, scrieți definiția unei structuri cu eticheta calculator, care permite memorarea datelor despre un calculator, și declarați corespunzător variabila c.

c.monitor c.memorie.interna c.memorie.externa

struct calculator
{
    char monitor;
    struct 
    {
        unsigned int interna;
        unsigned int externa;
    }memorie;
}c;

3. Variabilele i și j sunt de tip întreg, iar variabila a memorează un tablou bidimensional cu 9 linii și 9 coloane, numerotate de la 0 la 8, având inițial toate elementele egale cu simbolul egal (=).
Scrieți secvența de mai jos, înlocuind punctele de suspensie, astfel încât, în urma executării secvenței obținute, variabila a să memoreze tabloul alăturat.

for(i = 0; i < 9; i++)
    for(j = 0; j < 9; j++)
        ..................

Aceasta este o problema clasica atunci cand lucram cu tablourile bidimensionale (sau matricile). Trebuie sa determinam zona din “sud“-ul matricei. Daca luam toate elementele ce se afla sub diagonala principala si sub diagonala secundara obtinem zona din sud.

Asadar raspunsul este:

for(i = 0; i < 9; i++)
    for (j = 0; j < 9; j++)
        if (i > j && i + j > 8)
            a[i][j] = '<';
        else
            a[i][j] = '>';

Subiectul III.

1. Subprogramul suma are doi parametri, a și b, prin care primește câte un număr natural din intervalul [1,10⁴]. Subprogramul returnează suma divizorilor naturali comuni lui a și b.
Scrieți definiția completă a subprogramului.
Exemplu: dacă a=20 și b=12, atunci subprogramul returnează valoarea 7 (1+2+4=7).

unsigned int suma(unsigned int a, unsigned int b)
{
    unsigned int s = 0, i;
    for(i = 1; i <= a; i++)
    {
        if(a % i == 0 && b % i == 0)
            s = s + i;
    }
    return s;
}

Pentru a rezolva aceasta problema trebuie sa parcurgem divizorii comuni ai lui a si ai lui b. Asadar parcurgem cu un indice – i – toate numerele de la 1 pana la a (sau pana la b) si verificam daca i este divizor al parametrilor. Daca este, il adaugam la suma noastra si o returnam la final.

O alta metoda de rezolvare ar fi fost parcurgerea indicilor de la 1 pana la max(a, b) / 2. Dar aceasta problema nu cere optimizare, asa ca ar trebuii sa fie punctata.

2. Numim rotire spre stânga a unui cuvânt format din cel puțin trei litere operația prin care prima sa literă se mută la final, iar toate celelalte litere se mută cu o poziție spre stânga.
Exemplu: în urma rotirii spre stânga a cuvântului ilumina se obține cuvântul luminai.
Un text are cel mult 100 de caractere, iar cuvintele sale sunt formate din litere mici ale alfabetului englez și sunt separate prin câte un spațiu. Scrieți un program C/C++ care citește de la tastatură un text de tipul menționat mai sus și îl transformă în memorie prin rotirea spre stânga a fiecărui cuvânt al său format din cel puțin trei litere, ca în exemplu. Programul afișează pe ecran textul obținut sau mesajul nu exista, dacă în text nu există niciun cuvânt de cel puțin trei litere.
Exemplu: pentru textul un palc mic de scolarite ilumina sala se afișează pe ecran un alcp icm de colarites luminai alas

Pentru a rezolva aceasta problema trebuie sa vedem cum facem sa rotim caracterele spre stanga. Asadar aplicam urmatoarea idee:

Salvam primul caracter intr-o variabila auxiliara
Mutam fiecare caracter pe casuta din stanga ei
Inlocuim ultimul caracter din cuvant cu variabila auxiliara

Pentru a implementa aceasta idee avem doua metode de rezolvare:

Tratand sirul de caractere ca pe un “vector de numere“

#include    <iostream>
#include    <cstring>

using namespace std;

int main()
{
    char text[101], rezultat[101] = "";
    int contor = 0;
    cin.getline(text, 101);

    char *cuvant = strtok(text, " ");
    while(cuvant)
    {
        char cuvantAux[101], primaLit;
        strcpy(cuvantAux, cuvant);
        if(strlen(cuvant) >= 3)
        {
            primaLit = cuvantAux[0];
            for(int i = 0; i < strlen(cuvant); i++)
                cuvantAux[i] = cuvantAux[i + 1];
            cuvantAux[strlen(cuvant) - 1] = primaLit;

            contor++;
        }
        strcat(rezultat, cuvantAux);
        strcat(rezultat, " ");
        cuvant = strtok(NULL, " ");
    }
    if(contor != 0)
        cout << rezultat;
    else
        cout << "nu exista";
    
    return 0;
}

Folosind functia predefinita strcpy():

if(strlen(cuvant) >= 3)
{
    primaLit = cuvantAux[0];
    strcpy(cuvantAux, cuvantAux+1);
    cuvantAux[strlen(cuvant) - 1] = primaLit;

    contor++;
}

3. Un șir finit se numește palindromic dacă parcurgându-l termen cu termen, de la stânga la dreapta sau de la dreapta la stânga se obține același șir de valori.
Exemplu: șirul 12, 13, 16, 13, 12 este palindromic.
Fișierul bac.in conține un șir de cel mult 10⁶ numere naturale din intervalul [1,10³], separate prin câte un spațiu. Se cere să se afișeze pe ecran mesajul DA, dacă numerele din șir pot fi rearanjate, astfel încât să formeze un șir palindromic, sau mesajul NU în caz contrar. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul conține numerele 100 30 100 30 500 30 30 se afișează pe ecran DA
a. Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.
b. Scrieți programul C/C++ corespunzător algoritmului proiectat.

a. Pentru a rezolva aceasta problema vom apela la un vector de frecventa (sau aparitii). Pe masura ce citim numere din fisier, incrementam pozitia corespuznatoare din vectorul de aparitii. Dupa ce am citit toate numerele, parcurgem vectorul de aparitii si verificam daca in acesta se afla mai mult de o valoare impara.

In cazul in care se afla, afisam mesajul “NU” deoarece nu putem aseza numerele sa indeplineasca conditia de a fi palindromic. In caz contrar afisam mesajul “DA” deoarece putem sa asezam fiecare numar par de-oparte si de-alta a numarului impar gasit (daca acesta exista).

Algoritmul are o complexitate liniara in timp O(n) unde n reprezinta valoarea maxima din sir. De asemenea acest algoritm are o complexitate constanta O(1) in memorie, deoarece indiferent de numarul valorilor din sir, noi utilizam aceleasi numar de bytes.

#include    <iostream>
#include    <fstream>

using namespace std;

ifstream fin("bac.in");

int AP[1000];
int main()
{
    unsigned int x, nrMax = 0;
    while(fin >> x)
    {
        AP[x]++;
        if(x > nrMax)
            nrMax = x;
    }
    int contorImp = 0;
    for(int i = 1; i <= nrMax; i++)
    {
        if(AP[i] % 2 == 1)
            contorImp++;
    }
    if(contorImp > 1)
        cout << "NU";
    else
        cout << "DA";
    return 0;
}

Comentarii

Rezolvare Bacalaureat Informatica 2020 C++ iulie

Subiectul I.

Subiectul II.

Subiectul III.

Vectori de cuvinte in C++ | Siruri de caractere

Problema #1424 – Smartphone – Rezolvari PBInfo

S-ar putea sa iti placa