Rezolvare subiecte bac informatica 2018 C++ sesiunea iulie

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

Subiectul I.

1. Variabilele x și y sunt de tip întreg și memorează câte un număr natural nenul. O expresie echivalentă cu cea alăturată poate fi: !(x%y!=0 || y<2)

Deoarece avem o expresie negata, trebuie sa inversam toate interogarile pe care le stim, astfel incat, expresia alaturata devine (x % y == 0 && y >= 2).
Nota: negarea lui „<” este „>=”

Asadar, analizam variantele de raspuns, iar cea corecta este: c. (x/y)*y == x && y>=2

2. 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 [a] partea întreagă a numărului real a.

citeste n (numar intreg nenul)
dacă n < 0 atunci
--- n <- -n
s <- 0
repeta
--- x <- n % 10
--- pentru i <- 1, x executa
------ s <- s + x
--- n <- [n / 10]
pana când n=0
scrie s

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

Acest algoritm descompune numarul citit in cifre: 2, 0, 1 si 8. Dupa care ridica fiecare cifra din numar la patrat si o aduna intr-o variabila „s”. Astfel incat, dupa ce executam tot algoritmul, numarul nostru s = 4 + 0 + 1 + 64. Deci s = 69.

b. Scrieţi patru numere distincte din intervalul [10,103] care pot fi citite astfel încât, în urma executării algoritmului, pentru fiecare dintre acestea, să se afișeze valoarea 100.

Numarul 100 este suma dintre 36 si 64, asadar trebuie sa ne jucam cu cifrele 6 si 8, obtinand urmatoarele variante: 68, 86, 608 si 806.

c. Scrieţi în pseudocod un algoritm echivalent cu cel dat, înlocuind adecvat structura pentru…execută cu o atribuire.

citeste n (numar intreg nenul)
dacă n < 0 atunci
--- n <- -n
s <- 0
repeta
--- x <- n % 10
--- s <- s + (x * x)
--- n <- [n / 10]
pana când n=0
scrie s

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

#include    <iostream>

using namespace std;

int main()
{
    int n, s;
    cin >> n;

    if(n < 0)
        n = n * -1;
    s = 0;

    do {
        int x = n % 10;
        for(int i = 1; i <= x; i++)
            s = s + x;
        n = n / 10;
    } while(n == 0);

    cout << s;
    return 0;
}

Subiectul II.

1. În declararea alăturată, variabila m memorează, pentru fiecare dintre cele 20 de medicamente dintr-o farmacie, prețul, precum și date despre substanța activă specifică: doza și codul acesteia. O expresie a cărei valoare reprezintă codul substanţei active specifice din primul medicament este:

struct medicament 
{
    float pret;
    struct 
    {
        int cod, doza;
    }substanta;
}m[20];

Avem o lista cu 20 de medicamente, lista numerotata de la 0 la 19 in variabila „m”. Asadar, pentru a accesa codul substantei din primul medicament trebuie sa scriem: b. m[0].substanta.cod

2. Intr-un graf orientat cel puțin două vârfuri au gradul intern 2, cel puțin un vârf are gradul intern 3 și cel puțin un vârf are gradul extern 3. Numărul minim de vârfuri ale grafului este:

Rezolvare Subiectul 2 Problema 2

Construim graful nostru respectand cerintele problemei. Deoarece poti sa faci un drum din nodul 2 in nodul 2, exista doua variante de raspuns: 3 si 4 noduri.

3. Un arbore are 9 noduri, numerotate de la 1 la 9, şi muchiile [1,2], [1,6], [1,8], [1,9], [2,3], [2,7], [4,5], [5,7]. Scrieți trei noduri care ar putea fi alese drept rădăcină astfel încât nodul 2 să aibă un număr minim de descendenți.

Rezolvare Subiectul 2 – Problema 3

Desenam arborele descris in enunt. Observam mai apoi ca daca inlocuim nodul 1, cu oricare din nodurile 6, 8 sau 9, graful nostru va ramane la fel, iar nodul 2 va avea un numar minim de descendenti.

4. Variabilele i şi j sunt de tip întreg, iar variabila a memorează un tablou bidimensional cu 9 linii şi 9 coloane, numerotate de la 0 la 8, având iniţial toate elementele egale cu -1.
Fără a utiliza alte variabile, scrieţi secvenţa de instrucţiuni de mai jos, înlocuind punctele de suspensie astfel încât, în urma executării secvenţei obţinute, variabila a să memoreze tabloul alaturat.

for(i = 0; i < 9; i++)
    for(j = 0; j < 9; j++)
Enunt Subiectul 2 – Problema 4

Observam faptul ca diagonalele sunt completate cu 0, asa ca vom pornii de la aceasta observatie. Mai apoi, putem observa ca elementul curent este egal cu suma indicilor (i + j) elementului respectiv. De exemplu, in casuta [0, 7] (primul rand, penultimul element) este 7.

if(i == j || i + j == 8)
    a[i][j] = 0;
else
    a[i][j] = (i + j) % 8;

5. Fiind dat un cuvânt s, format numai din litere, și un cod c, de aceeași lungime cu s, format numai din cifre, numim codificare a lui s pe baza codului c operația de construire a unui nou șir, în care inițial se copiază prima literă din s, apoi, parcurgând de la stânga la dreapta restul șirului s, se adaugă litera curentă la începutul noului șir, dacă cifra corespunzătoare de pe aceeași poziție în c este pară, sau la finalul noului șir, în caz contrar.
Exemplu: dacă șirul s este etalon, iar codul este 025843 se obține cuvântul oltean (inițial șirul conține litera e, apoi se adaugă, în ordinea parcurgerii lui s, literele t, l și o la început, iar restul literelor la final).
Scrieţi un program C/C++ care citeşte de la tastatură două cuvinte, notate cu s și c, fiecare având cel mult 102 caractere, s fiind format doar din litere mici ale alfabetului englez, iar c fiind format doar din cifre. După primul cuvânt se tastează Enter. Programul construiește în memorie și afișează pe ecran cuvântul obținut prin codificarea lui s pe baza lui c, dacă cele două cuvinte au aceeași lungime, sau mesajul cod incorect, în caz contrar.
Exemplu: dacă se citesc cuvintele alăturate, se afişează pe ecran cuvântul oltean

Din punctul meu de vedere, aceasta problema a fost cea mai dificila sesiunea asta. Ideea pentru rezolvarea problemei este sa incepem totul de la coada. Construim mai intai cuvantul format din cifrele impare (parcurgem de-asemenea sirul cu cifre invers).

Dupa ce am construit sirul urmarind cifrele impare, vom pune prima litera in mijloc, si vom parcurge din nou sirul cu cifre, dar de data aceasta in ordine normala. Atunci cand intalnim o cifra para, plasam litera corespunzatoare in cuvantul nostru final.

La final rasturnam cuvantul obtinut si il afisam pe ecran.

#include    <iostream>
#include    <cstring>

using namespace std;

int main()
{
    char s[105], c[105];
    cin >> s >> c;

    int lungime_totala = 0;
    char cuvant_initial[105];
    char cuvant_final[105];

    for(int i = strlen(c) - 1; i >= 0; i--)
    {
        int cifra_curenta = c[i] - 48;
        if(cifra_curenta % 2 == 1)
        {
            cuvant_initial[lungime_totala] = s[i];
            lungime_totala++;
        }
    }

    cuvant_initial[lungime_totala] = s[0];
    lungime_totala++;

    for(int i = 1; i < strlen(c); i++)
    {
        int cifra_curenta = c[i] - 48;
        if(cifra_curenta % 2 == 0)
        {
            cuvant_initial[lungime_totala] = s[i];
            lungime_totala++;
        }
    }

    for(int i = 0; i < lungime_totala; i++)
        cuvant_final[i] = cuvant_initial[lungime_totala - 1 - i];

    cout << cuvant_final;
    return 0;
}

Subiectul III.

1. O companie organizează cursuri de programare în limbaje din mulțimea {PHP, Java, Python, C#, SQL}, astfel încât o persoană poate opta pentru un curs în care se studiază un număr par de limbaje, dar nu poate alege Java și Python în același curs. Utilizând metoda backtracking se generează toate posibilitățile unei persoane de a opta pentru un curs în cadrul ofertei companiei. Două cursuri sunt distincte dacă diferă prin cel puțin un limbaj sau prin ordinea în care se studiază limbajele. Primele cinci soluții generate sunt, în această ordine: (PHP, Java), (PHP, Java, C#, SQL), (PHP, Java, SQL, C#), (PHP, Python), (PHP, Python, C#, SQL).
Soluția generată imediat după (Java, PHP, SQL, C#) este:

a. Java, C#

2. Subprogramul f este definit alăturat. Scrieți trei valori naturale pe care le poate avea variabila întreagă x astfel încât, în urma apelului de mai jos, pentru fiecare dintre acestea, să NU se afișeze niciun caracter * f(‘e’,x);

void f(char ch, int x)
{
    cout << ch;
    if(x == 0)
        cout << '*';
    else
        if(ch == 'a')
            cout << x;
        else
            f(ch-1, x-1);
}

De fiecare data cand se va executa functia f se va verifica daca x este egal cu 0. Ne propunem sa nu atingem niciodata cu x valoarea 0, astfel incat putem lua orice valoare mai mare ca 5 (deoarece recursivitatea se va oprii in momentul in care ch va lua valoarea lui ‘a’).

3. Subprogramul resturi are patru parametri, n, x, y și r, prin care primeşte câte un număr natural din intervalul [1,109], r<x<y<n. Subprogramul returnează numărul de valori naturale din intervalul [1,n] pentru care atât restul împărțirii la x, cât și restul împărțirii la y, sunt egale cu r.
Scrieţi definiţia completă a subprogramului.
Exemplu: pentru n=200, x=5, y=14 și r=2, subprogramul returnează numărul 3 (pentru numerele 2, 72 și 142 atât restul împărțirii la 5, cât și restul împărțirii la 14, este 2).

int resturi(unsigned int n, unsigned int x, unsigned int y, unsigned int r)
{
    int contor = 0;
    for(int i = 1; i <= n; i++)
    {
        if((i % x == r) && (i % y == r))
            contor++;
    }
    return contor;
}

4. Numim secvență neuniformă a unui șir de numere naturale un subșir al acestuia, format din termeni aflați pe poziții consecutive în șirul dat, cu proprietatea că oricare trei termeni aflați pe poziții consecutive sunt diferiți. Lungimea secvenței este egală cu numărul de termeni ai acesteia.
Fișierul bac.txt conține un șir de cel mult 106 numere naturale din intervalul [0,9]. Numerele sunt separate prin câte un spațiu, iar în șir există cel puțin trei termeni diferiți pe poziții consecutive.
Se cere să se afișeze pe ecran lungimea maximă a unei secvențe neuniforme a șirului aflat în fișier. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă fişierul bac.txt conţine numerele 7 7 1 3 7 7 5 3 3 3 7 8 9 atunci pe ecran se afișează valoarea 4

#include    <iostream>
#include    <fstream>

using namespace std;

ifstream fin("bac.txt");

int main()
{
    unsigned int n;
    int precedent = -1;
    int precedent2 = -1;
    int contor = 1;
    int contor_max = 0;
    while(fin >> n)
    {
        if(precedent != n && precedent2 != n){
            contor++;
            if(contor > contor_max)
                contor_max = contor;
        }
        else
            contor = 1;
        //cout << n << " ";
        precedent2 = precedent;
        precedent = n;
    }
    cout << contor_max;
    return 0;
}

 

Comments (0)
Add Comment