Rezolvare subiecte bac informatica 2018 C++ simulare

Data: simulare 2018
Profil: Matematica-Informatica
Limbaj: C++

Subiectul I.

1. Valoarea expresiei C/C++ 2018/3/22 este:

Calculam expresia: 2018/3 = 672. Pe urma 672 / 22 este 30. Asadar raspunsul este a.

2. Algoritmul alăturat este reprezentat în pseudocod.

citeste n
x <- 1
cat timp x <= [n/3] executa
--- y <- x + 1
--- cat timp y <= [n/3] executa
------ z <- n - x - y
------ daca z % 2 = x % 2 atunci
--------- scrie x, y, z, "*"
------ y <- y + 1
--- x <- x + 1
scrie "#"

a. Scrieţi ce se afișează dacă se citește numărul 9.

n = 9

x = 1
y = 2
z = 6

x = 1
y = 3
z = 5

scrie 135*

x = 2
y = 3
z = 4

scrie 234*

x = 3

scrie #

Asadar raspunsul este 135*234*#.

b. Scrieți cel mai mic număr natural care poate fi citit astfel încât, în urma executării algoritmului, să se afișeze o singură dată simbolul *.

Cu cat numarul n este mai mare, cu atat numarul de simboluri * va fi mare. Ne vom baza pe aceasta observatie, astfel incat sa cautam un numar “n” cat mai mic. Astfel incat la final sa se afiseze doar o singura data simbolul *.

Daca alegem n sa fie 0, 1, 2 atunci prima conditie nu va fi executata, deoarece [n/3] va fi 0. Iar x incepe de la 1, deci nu va intra deloc in structura repetitiva.

Daca alegem n 3, 4, 5 atunci prima conditie va fi executata o singura data, deoarece [n/3] va fi 1. In schimb y va fi 2, iar algoritmul nu va intra in a doua structura repetitiva.

Alegand n = 6, putem observa ca simbolul * va fi afisat doar o singura data.

De asemenea n = 8 ar fi urmatorul numar pentru care simbolul * va fi afisat doar o data, insa noua ni se cere cel mai mic numar.

c. Scrieţi în pseudocod un algoritm echivalent cu cel dat, înlocuind adecvat prima structură cât timp…execută cu o structură repetitivă de tip pentru…execută.

citeste n
pentru x <- 1, [n/3] executa
--- y <- x + 1
--- cat timp y <= [n/3] executa
------ z <- n - x - y
------ daca z % 2 = x % 2 atunci
--------- scrie x, y, z, "*"
------ y <- y + 1
scrie "#"

d. Scrieţi programul C/C++ corespunzător algoritmului dat.

#include    <iostream>

using namespace std;

int main()
{
    int x, y, z;
    unsigned int n; // numar natural

    cin >> n;
    x = 1;
    while(x <= n / 3)
    {
        y = x + 1;
        while(y <= n / 3)
        {
            z = n - x - y;
            if(z % 2 == x % 2)
                cout << x << y << z << "*";
            y = y + 1;
        }
        x = x + 1;
    }
    cout << "#";
    return 0;
}

Subiectul II.

1. Indicați matricea de adiacență a unui graf orientat cu 4 vârfuri, numerotate de la 1 la 4, căruia îi poate aparține drumul 1,3,4,3,2.

Avem 4 variante, asa ca vom reprezenta fiecare matrice ca un graf, dupa care vom analiza fiecare graf.

Subiectul 2 – Problema 1 – varianta a

Aceasta solutie este incorecta deoarece: Nu avem un drum de la (1, 3)

Subiectul 2 – Problema 1 – varianta b

Aceasta solutie este incorecta deoarece: Nu avem un drum de la (4, 3)

Subiectul 2 – Problema 1 – varianta c

Aceasta solutie este incorecta deoarece: Nu avem un drumde la (4, 3)

Subiectul 2 – Problema 1 – varianta d

Aceasta este solutia corecta.

2. Într-un arbore fiecare nod are cel mult 3 fii. Dacă 10 dintre nodurile sale au gradul egal cu 1, atunci numărul maxim de noduri cu gradul egal cu 4 este:

Aceasta problema pot spune ca mi-a creat cateva batai de cap, deoarece trebuie distinse doua defintii foarte importante: fiu si grad.

Fiul unui nod = Succesorii directi ai unui nod se numesc fiii sai, el fiind nodul tata, iar succesorii sai directi sunt frati intre ei.

Gradul unui nod = Numarul fiilor unui nod se numeste gradul acelui nod, iar gradul maxim al nodurilor unui arbore se numeste gradul arborelui. Un nod de grad 0 (fara fii) se numeste terminal (frunza), restul fiind noduri interne (avand cel putin un fiu).

Asadar, avand aceste definitii fixate, vom incerca sa desenam graful. Vom incepe plin a plasa 10 noduri, astfel incat acestea sa aibe maxim 3 fii.

EDIT: Rezolvarea se afla mai jos. Gradul unui nod si fiul unui nod in unele carti de specialitate au aceeasi definitie iar in altele, au definitii diferite.

Rezolvare Subiectul 2 – Problema 2

In solutia propusa de Mihăiță-Cătălin Bănică, avem 10 noduri cu gradul 1 si 4 noduri cu gradul 4.

3. Pentru o stație meteo se memorează, în variabila m, următoarele informații: luna și anul în care au fost făcute măsurători, precum și temperaturile medii înregistrate în 15 dintre zilele lunii respective. Știind că expresiile C/C++ de mai jos au ca valori luna (un număr natural din intervalul [1,12]) și anul în care au fost măsurate temperaturi (număr natural), respectiv prima temperatură medie înregistrată (un număr real), scrieți definiția unei structuri cu eticheta meteo, care permite memorarea informațiilor precizate, și declarați corespunzător variabila m.

m.luna
m.an
m.temperatura[0]

Deoarece avem un tip de date ce memoreaza mai multe caracteristici simultan, ne dam seama ca este vorba despre un struct.

struct meteo
{
    unsigned int luna;
    unsigned int an;
    int temperatura[15];
}m;

4. 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 nule.
Scrieţi secvenţa de instrucţiuni 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++)

Enunt Subiectul 2 – Problema 4

Prima observatie pe care o putem face este faptul ca matricea noastra este patratica, asadar ne putem folosii de diagonalele ei. Din cate putem vedea, diagonala secundara este ocupata cu cifre de 8. Pornim de la aceasta observatie si construim diagonala secundara, insa atunci cand o construim, mai adaugam si vecinul din dreapta si din stanga.

for(int i = 0; i < 9; i++)
    for(int j = 0; j < 9; j++)
        if(i + j == 8 || i + j == 7 || i + j == 9)
            matrice[i][j] = 8;
        else
            matrice[i][j] = 1;

5. O pereche de cuvinte, unul cu număr par de litere, iar celălalt cu număr impar de litere, se numește descentrată dacă se poate obține cuvântul cu număr par de litere din celălalt, prin duplicarea caracterului din mijlocul acestuia.
Exemplu: perechile crezi și creezi, respectiv a și aa sunt descentrate.
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 precizat mai sus şi afișează pe ecran mesajul DA, dacă acesta conține cel puțin o pereche descentrată, sau mesajul NU în caz contrar.
Exemplu: dacă textul citit este: crezi ca poti sa creezi ceva original
se afișează pe ecran mesajul DA.

#include    <iostream>
#include    <cstring>
#include    <vector>

using namespace std;

int cuvinte_total;
char cuvinte[100][100]; // Creeam un vector de cuvinte

int main()
{
    //Citirea textului
    char text[100];
    cin.get(text, 100);

    //Impartirea textului in cuvinte
    char *p = strtok(text, " ");
    while(p != NULL)
    {
        strcpy(cuvinte[cuvinte_total], p); // Memoram cuvantul in vector
        cuvinte_total++;
        p = strtok(NULL, " ");
    }

    bool flag = false;
    for(int i = 0; i < cuvinte_total; i++) // Parcurgem fiecare cuvant in parte
    {
        if(strlen(cuvinte[i]) % 2) // verificam daca are un numar impar de cifre
        {
            char cuvant_descentrat[100];
            strcpy(cuvant_descentrat, cuvinte[i]);
            int mijloc = strlen(cuvant_descentrat) / 2;

            strcpy(cuvant_descentrat + mijloc + 1, cuvant_descentrat + mijloc); // Dublam litera din mijloc

            for(int j = i + 1; j < cuvinte_total; j++)
            {
                if(strcmp(cuvinte[j], cuvant_descentrat) == 0)
                {
                    cout << "DA";
                    flag = true;
                }
            }
        }
        if(flag == true)
            break;
    }
    if(flag == false)
        cout << "NU";
    return 0;
}

Subiectul III.

1. Subprogramul f este definit alaturat. Valoarea f(2203, 2018) este:

int f(int x, int y)
{
    if(x * y == 0) 
        return 0;
    if(x % 2 == y % 2) 
        return 1 + 10 * f(x/10, y/10);
    return 10 * f(x/10, y/10);
}

Executam algoritmul recursiv si vom obtine:

x = 2203
y = 2018
return 10 * f(220, 201)

x = 220
y = 201
return 10 * f(22, 20)

x = 22
y = 20
return 1 + 10 * f(2, 2)

x = 2
y = 2
return 1 + 10 * f(0, 0)

x = 0
y = 0
return 0;

Executam calulele si vom obtine:

f(2203, 2018) = 10 * f(220, 201)
f(220, 201) = 10 * f(22, 20)
f(22, 20) = 1 + 10 * f(2, 2)
f(2, 2) = 1 + 10 * f(0, 0)
f(0, 0) = 0
f(2, 2) = 1
f(22, 20) = 11
f(220, 201) = 110
f(2203, 2018) = 1100

2. Utilizând metoda backtracking, se generează toate posibilitățile de a forma șiraguri de câte 4 mărgele de culori distincte din mulţimea {roșu, albastru, roz, portocaliu, verde}, astfel încât în fiecare șirag nu pot fi pe poziții alăturate mărgele roșii și albastre. Două șiraguri sunt distincte dacă au cel puțin o mărgea de culoare diferită sau dacă ordinea culorilor mărgelelor este diferită.
Primele cinci soluţii generate sunt, în această ordine, (roșu, roz, albastru, portocaliu), (roșu, roz, albastru, verde), (roșu, roz, portocaliu, albastru), (roșu, roz, portocaliu, verde), (roșu, roz, verde, albastru). Scrieţi cea de a şasea şi cea de a şaptea soluţie, în ordinea generării acestora.

Codificam culorile in urmatoarea ordine:

1 – rosu
2 – albastru
3 – roz
4 – portocaliu
5 – verde

Si vom rescrie in ordine primele 5 solutii: 1 3 2 4 | 1 3 2 5 | 1 3 4 2 | 1 3 4 5 |1 3 5 2

Urmatoarele doua solutii sunt: 1 3 5 4 si 1 4 2 3. Adica (roşu,roz,verde,portocaliu) si (roşu,portocaliu,albastru,roz)

3. Se consideră subprogramul radical, cu trei parametri:

– n, prin care primeşte un număr natural (n ∈ [1,10⁹]);
– x și y, prin care furnizează două numere naturale cu proprietatea că √n poate fi scris sub forma x ∙ √y, unde x are o valoare maximă.

Scrieţi definiţia completă a subprogramului.
Exemplu: pentru numărul n=15000, în urma apelului, x=50 şi y=6, iar pentru numărul n=9, în urma apelului, x=3 şi y=1.

Aceasta problema face parte din problemele clasice ce le rezolvam in clasa 9 atunci cand prelucram divizorii unui numar. Haideti sa luam numarul 15000 si sa il scriem sub forma factorilor primi.

15000 = 2³ * 3¹ * 5⁴.

Tot ce trebuie noi sa facem este sa calculam √15000. Iar pentru asta ne vom folosii de urmatoarea observatie. Dupa ce descompunem numarul in factori primi, ne uitam la exponenti.

Daca exponentul este par, extragem direct numarul si il punem in x.
Daca exponentul este impar, il adaugam mai intai in y, dupa care punem ce a ramas in x.

void radical(int n, int &x, int &y)
{
    x = 1;
    y = 1;

    int divizor = 2;
    while(n > 1)
    {
        int exponent = 0;
        while(n % divizor == 0)
        {
            exponent ++;
            n = n / divizor;
        }

        if(exponent)
        {
            if(exponent % 2 == 0)
                x = x * pow(divizor, exponent / 2);
            else
            {
                y = y * divizor;
                exponent--;
                if(exponent)
                    x = x * pow(divizor, exponent / 2);
            }
        }
        divizor ++;
    }
}

4. Se consideră un șir ai cărui termeni sunt numere naturale nenule, de o singură cifră. Numim număr asociat al acestui șir un număr natural format cu termenii șirului, în ordinea în care aceștia apar în șir.
Exemplu: numărul asociat șirului 1, 2, 5, 3, 2 este 12532.
Fişierul text bac.txt conţine numere naturale din intervalul [1, 9]: pe prima linie două numere, x și y, iar pe a doua linie un șir de cel puţin trei şi cel mult 10⁵ termeni. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.
Se cere inserarea valorilor x și y în șirul aflat pe a doua linie fișierului, astfel încât numărul asociat șirului obținut să fie minim. Termenii șirului obținut se afișează pe ecran, separați prin câte un spațiu.
Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.
Exemplu: dacă fişierul bac.txt conţine numerele
9 6
1 7 5
atunci, pentru că numerele asociate șirurilor care se pot obține sunt 96175, 69175, 61975, 61795, 61759, 91675, 19675, 16975, 16795, 16759, 91765, 19765, 17965, 17695, 17659, 91756, 19756, 17956, 17596, 17569, pe ecran se afişează șirul: 16759
a) Descrieţi în limbaj natural algoritmul proiectat, justificând eficienţa acestuia.
b) Scrieţi programul C/C++ corespunzător algoritmului descris.

a) Aceasta problema poate fi rezolvata foarte usor fara a apela la backtracking pentru a genera toate solutiile posibile. Primul pas pe care il facem este sa ne asiguram ca x <= y. Daca conditia nu este indeplinita, schimbam x si y intre ele.

Mai apoi trebuie sa avem grija cum plasam x si y astfel incat sa obtinem cel mai mic numar posibil. Pentru a obtine cel mai mic numar posibil trebuie sa il punem pe x inaintea primului termen mai mare ca el (de aceea 6 a fost pus inaintea lui 7, in exemplul nostru).

Dupa aceea il plasam pe y dupa aceeasi regula: inaintea primei cifre mai mare ca el (in cazul nostru 9 este cea mai mare cifra, si a fost plasat la coada).

Algoritmul este eficient d.p.d.v. al timpului deoarece are complexitatea in timp O(n). De asemenea nu utilizam structuri de date aditionale, mentinand astfel complexitatea in spatiu, constanta O(1).

#include    <iostream>
#include    <fstream>

using namespace std;

ifstream fin("bac.txt");

bool xLiber = true;
bool yLiber = true;
int main()
{
    int x, y;
    fin >> x >> y;
    if(x > y)
        swap(x, y);

    int n;
    while(fin >> n)
    {
        if(n > x && xLiber)
        {
            if(n > y && yLiber)
            {
                cout << x << y << n;
                xLiber = false;
                yLiber = false;
            }
            else
            {
                cout << x << n;
                xLiber = false;
            }
        }
        else if(n > y && !xLiber && yLiber)
        {
            cout << y << n;
            yLiber = false;
        }
        else
            cout << n;
    }
    if(yLiber)
        cout << y;

    return 0;
}

Comentarii

2018 bac simulare

Rezolvare subiecte bac informatica 2018 C++ simulare

Subiectul I.

Subiectul II.

Subiectul III.

Date generale despre Permisul ECDL

Algoritmul Bellman-Ford în C++ (infoarena)

S-ar putea sa iti placa