Data: iunie 2021
Profil: Matematica-Informatica
Limbaj: C++
Tutoriale Recomandate:
- Cum iei cat mai multe puncte la Bacalaureatul de Informatica
- Functii si parametrii in C++
- Despre recursivitate in informatica
- Siruri de caractere in C++
- Citirea si scrierea din fisiere text in limbajul C++
- Tipul struct in C++ | Teorie si probleme rezolvate
- Descompunerea in factori primi a unui numar in C++
Subiectul I.
1. Indicați o expresie C/C++ care are valoarea 1 daca si numai daca valorile variabilelor intregi x si y sunt numere pare.
a. x % 2 == 0 && (y + 1) % 2 != 0
b. (x + y) / 2 == 0
c. (x + y) % 2 = 0 && (x – y) % 2 == 0
d. x % 2 == y % 2
Luam pe rand fiecare varianta si le discutam pentru a vedea care dintre acestea este corecta. Pentru a putea verifica cat mai usor expresiile, vom presupune pentru fiecare varianta, trei cazuri:
- numar par si numar impar
- numar par si numar par
- numar impar si numar impar
a. Varianta corecta. Deoarece (x % 2 == 0) inseamna ca x este par iar (y + 1) % != 0 se poate traduce in (y + 1) % 2 = 1 sau y % 2 == 0 -> adica si y este par.
b. Daca x = 4 si y = 6, atunci (x + y) / 2 nu va fi 0
c. Daca x = 3 si y = 7, atunci expresia va fi adevarata, chiar daca ambele numere sunt impare.
d. Daca x = 3 si y = 7, atunci expresia va fi adevarata, chiar daca ambele numere sunt impare.
2. Subprogramul f este definit alaturat, indicati valorile pe care le pot avea parametrii n si c, astfel incat, in urma apelului, f(n, c) sa aiba valoarea 2021.
a. n = 2021 si c = 0
b. n = 200211 si c = 2
c. n = 312032 si c = 3
d. n = 720721 si c = 7
int f(int n, int c)
{
if(n == 0)
return 0;
else
if(n % 10 == c)
return f(n / 10, c);
else
return n % 10 + 10 * f(n / 10, c);
}
Calculam fiecare varianta de raspuns si obtinem:
- varianta a: 221
f(2021, 0) -> 1 + 10 * f(202, 0) -> 221
f(202, 0) -> 2 + 10 * (20, 0) -> 22
f(20, 0) -> f(2, 0) -> 2
f(2, 0) -> 2 + 10 * f(0, 0) -> 2
f(0, 0) -> 0 - varianta b: 11
f(200211, 2) -> 1 + 10 * f(20021, 2) -> 11
f(20021, 2) -> 1 + 10 * f(2002, 2) -> 1
f(2002, 2) -> f(200, 2) -> 0
f(200, 2) -> 0 + 10 * f(20, 2) -> 0
f(20, 2) -> f(2, 2) -> 0
f(2, 2) -> f(0, 2) -> 0
f(0, 2) -> 0 - varianta c: 1202
f(312032, 3) –> 2 + 10 * f(31203, 3) -> 1202
f(31203, 3) -> f(3120, 3) -> 120
f(3120, 3) -> 0 + 10 * f(312, 3) -> 120
f(312, 3) -> 2 + 10 * f(31, 3) -> 12
f(31, 3) -> 1 + 10 * f(3, 3) -> 1
f(3, 3) -> f(0, 3) -> 0
f(0, 3) -> 0 - varianta d: 2021
f(720721, 7) -> 1 + 10 * f(72072, 7) -> 2021
f(72072, 7) -> 2 + 10 * f(7207, 7) -> 202
f(7207, 7) -> f(720, 7) -> 20
f(720, 7) -> 0 + 10 * f(72, 7) -> 20
f(72, 7) -> 2 + 10 * f(7, 7) -> 2
f(7, 7) -> f(0, 7) -> 0
f(0 ,7) -> 0
3. Variabila m memoreaza elementele unui tablou bidimensional cu 100 de linii si 100 coloane, numerotate de la 0 la 99. Indicati expresia C/C++ prin care poate fi accesat un element aflat pe diagonala secundara a tabloului.
a. m[42/42]
b. m[42|42]
c. m[42]:[57]
d. m[42][57]
4. Un graf neorientat are 6 noduri, numerotate de la 1 la 6, si muchiile [1, 2], [1, 3], [2, 3], [3, 4], [3, 5], [4, 5], [5, 6]. Indicati un ciclu elementar al acestui graf.
a. 1, 2, 3
b. 1, 2, 3, 1
c. 1, 2, 3, 4, 5, 3, 1
d. 1, 2, 3, 4, 5, 6, 1
Desenam graful descris in enunt si il analizam
Teoria Grafurilor – Lant. Ciclu. Arbore – Daca intr-un ciclu, toate varfurile cu exceptia primului si a ultimului sunt distincte doua cate doua, atunci ciclul se numeste elementar.
- Varianta a nu contine nodul de start, deci nu este ciclu.
- Varianta b este varianta corecta.
- Varianta c nu convine deoarece nodul 3 se repeta
- Varianta d nu convine deoarece nodurile insirate nu reprezinta un ciclu (nu exista muchia 6 <-> 1)
5. Intr-un arbore cu radacina un nod se afla pe nivelul x daca lantul elementar care are o extremitate in nodul respectiv si cealalta extremitate in radacina arborelui are lungimea x. Pe nivelul 0 se afla un singur nod (radacina).
Intr-un arbore cu radacina toate nodurile de pe acelasi nivel au un numar egal de “fii” si nu exista doua niveluri diferite cu acelasi numar de noduri. Indicati numarul minim de noduri de pe nivelul 3.
a. 12
b. 9
c. 8
d. 5
Deoarece problema ne precizeaza pe ascuns faptul ca arborele este unul binar (fiecare nod are doi fii), varianta corecta este c. 8
Subiectul II.
1. S-a notat cu a <-> b operatia de interschimbare a valorilor variabilelor a si b.
citeste x, y (numere naturale nenule) daca x > y atunci --- x <-> y nr <- 1 pentru i <- y, x, -1 executa --- scrie 1 --- daca nr >= x atunci ------ scrie 2 --- nr <- nr * 3 --- scrie 1
a) Scrieți ce se afiseaza in urma executarii algoritmului daca se citesc in aceasta ordine, numerele 8 si 5.
Facem tabelul pentru acest pseudocod si obtinem: 1111121121
b) Dacă pentru variabila x se citește valoarea 10, scrieți doua numere care pot fi citite pentru variabila y, astfel incat, in urma executarii algoritmului, pentru fiecare dintre acestea, cifra 2 sa fie afisata de trei ori.
Observam faptul ca nr preia puteri ale lui 3. Asadar pentru fiecare iteratie a lui i, in functie de valoarea lui nr se va afisa cate un “2”. Trebuie sa urmarim ca diferenta dintre x si y sa fie in jur de 4 (pentru a afisa de trei ori). Varianta corecta de raspuns este: 15 si 6
c) Scrieţi programul C/C++ corespunzător algoritmului dat, fara a utiliza eventuale subprograme predefinite pentru interschimbare.
#include <iostream>
using namespace std;
int main()
{
unsigned int x, y;
if (x > y)
{
int aux = x;
x = y;
y = aux;
}
unsigned int nr = 1;
for(int i = y; i >= x; i--)
{
cout << 1;
if(nr >= x)
cout << 2;
nr = nr * 3;
cout << 1;
}
return 0;
}
d) Scrieți în pseudocod un algoritm echivalent cu cel dat, înlocuind structura pentru…executa cu o structură repetitivă cu test inițial.
citeste x, y (numere naturale nenule) daca x > y atunci --- x <-> y nr <- 1 cat timp y >= x executa --- scrie 1 --- daca nr >= x atunci ------ scrie 2 --- nr <- nr * 3 --- scrie 1 --- y = y - 1
2. Utilizând metoda backtracking se generează toate grupurile de cel putin doua pasari cantatoare din multimea {cinteza, ciocarlie, mierla, privighetoare, scatiu}, astfel incat mierla si privighetoarea sa nu fie in acelasi grup. Doua grupuri difera prin cel putin o pasare. Primele patru solutii generate sunt, in aceasta ordine: (cinteza, ciocarlie), (cinteza, ciocarlie, mierla), (cinteza, ciocarlie, mierla, scatiu), (cinteza, ciocarlie, privighetoare).
Scrieti urmatoarele doua solutii generate imediat dupa (ciocarlie, privighetoare, scatiu).
Codificam fiecare varianta de raspuns cu un numar pentru a usura munca si vom avea:
- 1 – cinteza
- 2 – ciocarlie
- 3 – mierla
- 4 – privighetoare
- 5 – scatiu
Prin urmare variantele de raspuns devin: (1, 2) (1, 2, 3) (1, 2, 3, 5) (1, 2, 4)
Trebuie sa vedem ce variante urmeaza dupa (2, 4, 5). Prima varianta valida este (2, 4, 5, 1) dar aceasta varianta a fost deja folosita atunci cand am generat (1, 2, 4, 5). Drept urmare, singurele variante nefolosite sunt (2, 5) si (3, 5) adica (ciocarlie, scatiu) si (mierla, scatiu)
3. In declararea alaturata, variabilele f si fs, memoreaza in campurile a si b numaratorul, respectiv numitorul cate unei fractii. Fara a utiliza alte variabile, scrieti o secventa de instructiuni care sa memoreze in variabila fs fractia obtinuta prin scaderea din fractia 2020/2021 a fractiei memorate in variabila f.
struct fractie
{
int a, b;
} f, fs;
fs.a = (2020 * f.b) - (f.a * 2021) fs.b = 2021 * f.b
Subiectul III.
1.Subprogramul divPrim are doi parametri:
– n, prin care primește un număr natural (n ∈ [2, 109])
– s, prin care furnizează suma divizorilor primi ai lui n care apar la o putere impară în descompunerea în factori primi a acestuia.
Scrieți definiția completă a subprogramului.
Exemplu: dacă n = 360, dupa apel s = 7 (360 = 23 * 32 * 51, deci s = 2 + 5).
Pentru a rezolva aceasta problema, ne vom folosii de descompunerea in factori primi a unui numar in C++ si vom aduna pe rand toti divizorii care au un exponent impar.
void divPrim(unsigned int n, unsigned int &s)
{
unsigned int divizor = 2;
while (n > 1)
{
if(n % divizor == 0)
{
unsigned int putere = 0;
while(n % divizor == 0)
{
putere = putere + 1;
n = n / divizor;
}
if(putere % 2 == 1)
s = s + divizor;
}
divizor++;
}
}
2. Scrieți un program C/C++ care citește de la tastatură două numere naturale n și k, apoi n cuvinte, separate prin Enter. Fiecare cuvant este format din cel mult 10 caractere, numai litere mici ale alfabetului englez, iar numerele citite sunt din intervalul [1, 20].
Programul afiseaza pe ecran, pe linii separate, primele k cuvinte dintre cele citite pentru care ultima litera este o vocala, sau doar mesajul nu exista daca nu exista k astfel de cuvinte. Se considera vocale literele a, e, i, o, u.
Exemplu: daca se citesc datele alaturate:
5 2
norii
cumulus
pluteau
pe
cer
Se afieaza pe ecran:
norii
pluteau
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
unsigned int n, k;
cin >> n >> k;
for(int i = 1; i <= n; i++)
{
char cuvant[15];
cin >> cuvant;
unsigned int lungimeCuv = strlen(cuvant);
if(cuvant[lungimeCuv - 1] == 'a' || cuvant[lungimeCuv - 1] == 'e' || cuvant[lungimeCuv - 1] == 'i' || cuvant[lungimeCuv - 1] == 'o' || cuvant[lungimeCuv - 1] == 'u')
{
if(k != 0)
{
k = k - 1;
cout << cuvant << "\n";
}
}
}
return 0;
}
3.Numarul natural a se numeste sufix al numarului natural b daca a este egal cu b sau daca b se poate obtine din a prin alipirea la stanga a unor noi cifre.
Fisierul bac.txt contine pe prima linie un numar natural x (x ∈ [100, 999]), iar pe a doua linie un sir de cel mult 105 numere naturale din intervalul [0, 109]. Numerele din sir sunt separate prin cate un spatiu.
Se cere sa se afiseze pe ecran ultimii doi termeni ai sirului, aflati pe pozitii consecutive in acesta, care il au drept sufix pe numarul x. Numerele sunt afisate in ordinea in care apar in sir, separate printr-un spatiu, iar daca nu exista doi astfel de termeni, se afiseaza pe ecran mesajul nu exista. Proiectati un algoritm eficient din punct de vedere al memoriei utilizate si al timpului de executare.
Exemplu: dacă fișierul contine numerele alaturate,
210
3445 210 893210 1245 1210 3210 15210 67120 20210 12
atunci pe ecran se afiseaza 3210 15210.
a. Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.
b. Scrieți programul C/C++ corespunzător algoritmului proiectat.
a.
——
b.
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("bac.txt");
int main()
{
unsigned int sufix, nr_1, nr_2, ultim = -1, precedent = -1;
fin >> sufix >> nr_1;
while(fin >> nr_2)
{
if(nr_1 % 1000 == sufix && nr_2 % 1000 == sufix)
{
ultim = nr_2;
precedent = nr_1;
}
nr_1 = nr_2;
}
if(ultim != -1)
cout << precedent << " " << ultim;
else
cout << "nu exista";
return 0;
}
