Data: model 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
Subiectul I.
1. Indicați valoarea expresiei C/C++ alăturate: 21/2*2-5
Efectuam pe rand calculele, respectand ordinea operatiilor, si vom obtine: 21 / 2 * 2 – 5 = 10 * 2 – 5 = 20 – 5 = 15 . Asadar raspunsul corect este c)
2.Variabila x este declarată alăturat. Indicați secvența care, în urma executării, afișează pe ecran ziua, luna și anul corespunzătoare unei date calendaristice memorate în variabila x.
struct data {
int zi, luna, an;
} x;
Raspunsul corect este: a) cout << x.zi << ” ” << x.luna << ” ” << x.an;
Deoarece pentru a accesa elementele dintr-un struct vom incepe cu variabila x iar mai apoi prin intermediul punctului pot sa accesez proprietati din structura noastra de date denumita “data”. Pentru mai multe detalii despre struct va puteti la urmatorul tutorial: Tipul struct in C++ | Teorie si probleme rezolvate
3. Subprogramul f este definit alăturat. Indicați valoarea f(3,1).
int f(int n, int x)
{
if(n != 0)
{
x = x + 1;
return f(n-1, x) - x;
}
return 0;
}
Parcurgem pe rand apelarea functiei recursive f(3, 1)
- f(3, 1) -> f(2, 2) – 2
- f(2, 2) -> f(1, 3) – 3
- f(1, 3) -> f(0, 4) – 4
- f(0, 4) -> 0
Iar dupa ce efectuam calculele vom obtine f(3, 1) = -9 , varianta corecta de raspuns fiind d).
4. Un arbore cu rădăcină are 8 noduri, numerotate de la 1 la 8, și muchiile [1,3], [1,7], [1,8], [2,4], [3,5], [3,6], [4,5]. Indicați numărul maxim de frunze ale arborelui, în funcție de rădăcina aleasă.
Desenam arborele descris in problema, alegand drept radacina nodul (1). In acest caz vom avea 4 frunze: 7, 8, 6 si 2. Asadar varianta corect este: b).
5. Un graf neorientat complet are 21 de noduri. Indicați numărul de muchii ce pot fi eliminate, astfel încât graful parțial obținut să fie conex și fără cicluri.
Calculam mai intai numarul de muchii totale, folosind formula pentru muchii in cazul grafurilor complete. Vom obtine total = ( (n – 1) * n ) / 2 asadar initial folosim 210 muchii.
Pentru a obtine un graf partial conex si fara cicluri, numarul minim de muchii ce pot fi folosite este 20 (daca punem nodurile unul dupa altul) . Asadar, putem elimina maxim 210 – 20 = 190 muchii. Varianta corecta este c)
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, k (numere naturale) p <- 1 dacă k=0 atunci --- nr <- -1 --- altfel ------ nr <- 0 ------ repeta --------- c <- n % 2; --------- n <- [n / 10] --------- daca c != 0 atunci ------------ nr <- nr + (n % 10) * p ------------ p <- p * 10 --------- altfel ------------ k <- k - 1 ------ pana cand n = 0 sau k = 0 scrie nr
a) Scrieți numărul afișat în urma executării algoritmului dacă se citesc, în această ordine, numerele 3845267 și 3.
Facem un tabel unde fiecare coloana reprezinta o variabila din codul pseudocod si vom obtine urmatorul rezultat dupa executarea algoritmului:
Asadar, raspunsul este: 46.
b) Daca pentru variabila k se citește 2, scrieți trei numere din intervalul [103,104) care pot fi citite pentru n astfel încât, pentru fiecare dintre acestea, în urma executării algoritmului, să se afișeze 20.
Observam ca algoritmul nostru construieste un numar compus din cifrele pare care se afla in stanga cifrelor impare. Pentru cazul nostru numarul 46, s-a format datorita cifrelor impare 5 si 7 (3845267 , 4 se afla in stanga cifrei impare 5, iar 6 se afla in stanga cifrei impare 7).
Asadar, pentru a obtine 20, trebuie sa avem un numar de forma 2a0b, unde a si b sunt cifre impare. Un posibil raspuns ar fi 2101 2303 si 2505.
c) Scrieţi programul C/C++ corespunzător algoritmului dat.
#include <iostream>
using namespace std;
int main()
{
unsigned int n, k, p, nr;
cin >> n >> k;
p = 1;
if(k == 0)
nr = - 1;
else
{
nr = 0;
do
{
unsigned int c = n % 2;
n = n / 10;
if(c != 0)
{
nr = nr + (n % 10) * p;
p = p * 10;
}
else
k = k - 1;
}
while(n != 0 && k != 0);
}
cout << nr;
return 0;
}
d) Scrieți în pseudocod un algoritm echivalent cu cel dat, înlocuind structura repeta…pâna când cu o structura repetitiva cu test inițial.
Inlocuim structura repetitiva repeta…pana cand cu structura cat timp.. executa negand complet expresia.
citește n, k (numere naturale) p <- 1 dacă k=0 atunci --- nr <- -1 --- altfel ------ nr <- 0 ------ cat timp n != 0 si k != 0 executa --------- c <- n % 2; --------- n <- [n / 10] --------- daca c != 0 atunci ------------ nr <- nr + (n % 10) * p ------------ p <- p * 10 --------- altfel ------------ k <- k - 1 scrie nr
2. Utilizând metoda backtracking se generează toate numerele din intervalul [104,105), cu cifrele în ordine strict crescătoare. Primele trei numere generate sunt 12345, 12346, 12347. Scrieți, în ordinea obținerii, ultimele trei numere generate care au prima cifră 4.
Folosind metoda backtracking, vom obtine:
Asadar, raspunsul corect este: 45689, 45789 si 46789
3. Variabila s memorează un șir cu cel mult 20 de caractere, iar celelalte variabile sunt de tip întreg. Scrieți ce se afișează pe ecran în urma executării secvenței alăturate.
k = 'a' - 'A';
strcpy(s, "A realizat tot");
for(i = strlen(s) - 1; i >= 0; i--)
if(strchr("aeiou", s[i]) != NULL)
{
s[i] = s[i] - k;
cout << s[i];
}
Observam ca aceasta bucata de cod transforma fiecare vocala cu litera mica intr-o vocala cu litera mare
Asadar, raspunsul este: OAIAE
Subiectul III.
1.Subprogramul prime are trei parametri:
– n, prin care primește un număr natural (n ∈ [4, 109])
– x și y, prin care furnizează cele mai mari două numere prime din intervalul [1, n) , x < y.
Scrieți definiția completă a subprogramului.
Exemplu: dacă n = 49, în urma apelului x = 43, y = 47.
In aceasta problema ni se da un numar natural n, iar noi trebuie sa intoarcem prin parametrii x si y ai aceleasi functii cele mai mare doua numere prime care sunt strict mai mici decat n. Pentru a rezolva aceasta problema vom parcurge descrescator toate numerele de la n la 1 si ne vom oprii in momentul in care gasim doua numere prime.
void prime(unsigned int n, unsigned int &x, unsigned int &y)
{
x = 0;
y = 0;
for(int i = n; i > 1; i--)
{
bool ePrim = true;
for(int div = 2; div < i / 2; div = div + 1)
{
if(i % div == 0)
ePrim = false;
}
if(ePrim == true && y == 0)
y = i;
else if(ePrim == true && y != 0 && x == 0)
x = i;
if(x != 0 && y != 0)
break;
}
}
2. Scrieți un program C/C++ care citește de la tastatură două numere naturale din intervalul [2, 102], m și n, și construiește în memorie un tablou bidimensional cu m linii și n coloane, cu proprietatea că parcurgându-l linie cu linie de sus în jos și fiecare linie de la stânga la dreapta, se obține șirul primelor m * n pătrate perfecte pare, ordonat strict descrescător, ca în exemplu.
Elementele tabloului obținut se afișează pe ecran, fiecare linie a tabloului pe câte o linie a ecranului, valorile de pe aceeași linie fiind separate prin câte un spațiu.
Exemplu: pentru m = 2, n = 3 se obține tabloul alăturat.
Prima observatie pe care o putem face este faptul ca pentru a obtine numere patrate perfecte pare, trebuie sa inmultim numere pare. Deoarece ridicand la patrat un numar impar, vom obtine tot un numar impar. Asadar, pentru a construii matricea vom incepe de la numarul (n * m * 2) – 2 si vom parcurge descrescator fiecare numar par.
#include <iostream>
using namespace std;
int main()
{
unsigned int matrice[101][101];
unsigned int m, n;
cin >> m >> n;
unsigned int nr_crt = (m * n * 2) - 2;
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
if(nr_crt % 2 == 0)
{
matrice[i][j] = nr_crt * nr_crt;
nr_crt = nr_crt - 2;
}
}
}
return 0;
}
3.Fișierul cheltuieli.in are cel mult 106 linii, fiecare linie conținând câte trei numere naturale din intervalul [1,102], reprezentând, în această ordine, date despre câte o achiziție: tipul produsului cumpărat, numărul de produse de acest tip cumpărate, respectiv prețul unui astfel de produs la acel moment. Numerele aflate pe aceeași linie sunt separate prin câte un spațiu.
Se cere să se afișeze pe ecran cea mai mare sumă cheltuită pentru toate produsele de același tip, precum și numărul de tipuri de produse pentru care s-a obținut această sumă. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul cheltuieli.in are conținutul alăturat, se afișează pe ecran: 26 2 (s-a cheltuit suma maximă 26 pentru produsele de tipul 1 și 4: 26 = 16 * 1 + 5 * 2 = 1 * 10 + 2 * 8)
a. Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.
b. Scrieți programul C/C++ corespunzător algoritmului proiectat.
a) Pentru a rezolva aceasta problema, ne vom folosii de un vector de aparitie putin modificat. In sensul ca in AP[i] vom stoca pretul total platit pentru produsul i. Deoarece codurile produselor sunt valori de la 1 la 100, nu vom utiliza foarte multa memorie. Dupa ce am calculat sumat totala cheltuita pentru fiecare produs, parcurgem vectorul de aparitii si numaram de cate ori am intalnit elementul maxim.
b)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cheltuieli.in");
unsigned int AP[101];
int main()
{
unsigned int produs, cantitate, pret;
unsigned int produs_max = 0;
while(fin >> produs >> cantitate >> pret)
{
AP[produs] = AP[produs] + cantitate * pret;
if(produs > produs_max)
produs_max = produs;
}
unsigned int suma_max = 0, total_produse = 0;
for(int i = 1; i <= produs_max; i++)
{
if(AP[i] > suma_max)
{
suma_max = AP[i];
total_produse = 0;
}
if(AP[i] == suma_max)
total_produse = total_produse + 1;
}
cout << suma_max << " " << total_produse;
return 0;
}
