Data: iulie 2019
Profil: Matematica-Informatica
Limbaj: C++
Tutoriale Recomandate:
- Cum iei cat mai multe puncte la Bacalaureatul de Informatica
- Despre recursivitate in informatica
- Tipul struct in C++ | Teorie si probleme rezolvate
- Algoritm pentru descompunerea unui numar in cifre C++
Subiectul I.
1. Indicați numerele pe care le pot memora variabilele întregi x şi y, astfel
încât valoarea expresiei C/C++ alăturate să fie 1: x / 2 + x % y – x / y == 0
a. x=4 şi y=2 => inlocuind obtinem 4 /2 + 4 % 2 – 4 / 2 = 2 + 0 – 2 = 0
b. x=6 şi y=3 => inlocuind obtinem 6 / 2 + 6 % 3 – 6 / 3 = 3 + 0 – 2 = 1
c. x=8 şi y=4 => inlocuind obtinem 8 / 2 + 8 % 4 – 8 / 4 = 4 + 0 – 2 = 2
d. x=10 şi y=0 => inlocuind obintem 10 / 2 + 10 % 0 – 10 / 0 = 5 + 10 – oo = -oo
2. Subprogramul f este definit alăturat. Valoarea lui f(6) este:
int f(int n)
{
if(n <= 2)
return n;
if(n % 2 == 1)
return f(n-2) - f(n-1);
return f(n-1) - f(n-2);
}
Facem tabelul si urmarim cum se schimba pe rand valorile
Asadar raspunsul final este b. 5
3. Variabila x este de tip char şi memorează o literă mică a alfabetului englez. Indicați expresia
C/C++ care are valoare nenulă dacă şi numai dacă litera memorată în variabila x este o vocală. Se consideră vocale literele a, e, i, o, u.
a. strcmp(x,”aeiou”)==0 -> aceasta functie cumpara caracterul nostru x cu sirul “aeiou” – drept urmare nu este corecta
b. strchr(“aeiou”, x) -> aceasta functie cauta in sirul “aeiou” caracterul x. In cazul in care se regaseste caracterul in acel sir (adica daca este o vocala) – va returna un pointer catre acesta
c. ‘a’ <= x && x <= ‘u’ -> aceasta conditie verifica daca x se afla intre ‘a’ si ‘u’. De exemplu daca x era ‘b’, atunci functia ar fi returnat 1, ceea ce nu convine enuntului
d. x == a || x == e || x == i || x == o || x == u -> aceasta conditie verifica daca variabila noastra x este egala cu variabila a. Daca am fi avut ‘a’ in loc de a, aceasta varianta de raspuns ar fi fost corecta
4. Utilizând metoda backtracking, se generează, în ordine strict descrescătoare, toate numerele
naturale de câte patru cifre distincte din mulţimea {0, 1, 2, 3, 4, 5}. Primele șase numere generate sunt, în această ordine: 5432, 5431, 5430, 5423, 5421, 5420. Al şaptelea număr generat este:
Generam pe rand solutiile si trebuie sa avem grija sa nu repetam cifre. De asemenea, pentru usurinta, vom scrie cifrele invers atunci cand generam backtrackingul. Solutia corecta este b. 5413
5. Un graf neorientat are 20 de noduri şi 10 muchii. Numărul maxim de componente conexe pe care le poate avea acest graf este:
Inainte de a rezolva aceasta problema trebuie sa ne gandim cum putem obtine un numar maxim de componente conexe (= insule). Trebuie sa utilizam cat mai putine noduri si in acelasi timp cat mai multe muchii. Drept urmare vom face un graf complet (deoarece aceasta figura utilizeaza numarul maxim de muchii avand un numar mic de noduri).
Numaram componentele conexe si obtinem 1 (graful complet) + 15 (insulele formate din nodurile 6..20) = c. 16 componente conexe
Subiectul II.
1. S-a notat cu a%b restul împărţirii numărului natural a la numărul natural nenul b.
citeşte m,n,p,q (numere naturale nenule, p≤q) s1 <- 0; s2 <- 0 cât timp p <= q execută --- dacă p % m = 0 sau p % n = 0 atunci ------ s1 <- s1 + 1 --- dacă p % m = 0 şi p % n = 0 atunci ------ s2 <- s2 + 1 --- p <- p + 1 s <- s1 - 2 * s2 scrie s
a) Scrieţi valoarea afişată dacă se citesc, în această ordine, numerele 4, 3, 11 și 25.
Urmarim pe rand tabelul cu valori. Mare atentie: trebuie sa actualizam si s1 atunci cand actualizam s2.
La final obtinem 7 – 2 * 2 = 3
b) Dacă pentru m, n și p se citesc numerele 3, 5, respectiv 1, scrieţi două numere care pot fi citite pentru q astfel încât, în urma executării algoritmului, pentru fiecare dintre acestea, valoarea afişată să fie 10.
Daca analizam algoritmul ajungem la urmatoarea concluzie:
- Se adauga +1 in s1 de fiecare data cand intalnim un multiplu de 3 sau un multiplu de 5
- Se scade -2 din s1 de fiecare data cand intalnim un multiplu de 15.
Multiplii de a lui 3: 3, 6, 9, 12, 15, 18, 21, 24
Multiplii de a lui 5: 5, 10, 15, 20, 25
Cele doua multimi intersectate ne va da sirul: 3, 5, 6, 9, 10, 12, 15, 18, 20, 21, 24, 25 (care contine 12 elemente). Deoarece regasim un 15 (multiplu de 3 si de 5) in sir, vom scadea -2 din numarul elementelor si vom obtine 10. Asadar, o varianta de raspuns este 25 si 26.
c) Scrieţi programul C/C++ corespunzător algoritmului dat.
#include <iostream>
using namespace std;
int main()
{
unsigned int m, n, p, q, s;
unsigned int s1 = 0, s2 = 0;
cin >> m >> n >> p >> q;
while(p <= q)
{
if(p % m == 0 || p % n == 0)
s1 = s1 + 1;
if(p % m == 0 && p % n == 0)
s2 = s2 + 1;
p = p + 1;
}
s = s1 - 2 * s2;
cout << s;
return 0;
}
d) Scrieţi în pseudocod un algoritm, echivalent cu cel dat, înlocuind structura cât timp…execută cu o structură repetitivă de tip pentru…execută.
citeşte m,n,p,q (numere naturale nenule, p≤q) s1 <- 0; s2 <- 0 pentru i <- p, q --- dacă i % m = 0 sau i % n = 0 atunci ------ s1 <- s1 + 1 --- dacă i % m = 0 şi i % n = 0 atunci ------ s2 <- s2 + 1 s <- s1 - 2 * s2 scrie s
2. Un graf orientat cu 6 vârfuri, numerotate de la 1 la 6, are arcele (1,2), (1,4), (2,5), (2,6),
(3,5), (4,1), (5,1), (6,5). Scrieţi un drum elementar de lungime maximă din graful dat.
Facem graful descris in enunt:
Avem drumul elementar de lungime maxima 4: 4, 1, 2, 6, 5
3. Variabila fig, declarată alăturat, memorează lungimea razei unui cerc și coordonatele centrului acestuia, în sistemul de coordonate xOy. Scrieți o secvență de instrucțiuni prin care se iniţializează variabila fig, astfel încât cercul corespunzător acesteia să aibă raza 1 și centrul în originea sistemului de coordonate.
struct punct
{
float x,y;
};
struct cerc
{
struct punct centru;
float raza;
} fig;
fig.centru.x = 0; fig.centru.y = 0; fig.raza = 1;
Subiectul III.
1. Subprogramul Impare are un singur parametru, n, prin care primește un număr natural
(n∈[1,109]), cu cel puțin o cifră impară. Subprogramul înlocuiește fiecare cifră impară a lui n cu cea mai mare cifră pară strict mai mică decât ea (astfel cifra 1 se înlocuieşte cu cifra 0, cifra 3 cu cifra 2 etc.) și furnizează numărul obținut tot prin parametrul n. Scrieți definiția completă a
subprogramului.
Exemplu: dacă n=235690, atunci, după apel, n=224680, iar dacă n=15690, atunci, după apel, n=4680.
Pentru a rezolva aceasta problema folosim descompunerea unui numar in cifre si construirea unui rasturnat. Verificam daca cifra curenta este impara, iar daca este impara scadem unu din aceasta (pentru a obtine cea mai mica cifra para). Construim rasturnatul numarului, iar la final, mai rasturnam numarul o data pentru a obtine numarul initial.
De asemenea, trebuie sa verificam daca numarul nostru initial are ultima cifra 0, deoarece in urma rasturnarii s-ar putea sa o pierdem. Daca avea ultima cifra 0, inmultim numarul obtinut de noi cu 10 pentru a adauga cifra inapoi.
unsigned int Impare(unsigned int &n)
{
unsigned int rasturnat = 0;
unsigned int noulN = 0;
unsigned int copieN = n;
while(n != 0)
{
unsigned int cifra = n % 10;
n = n / 10;
unsigned int cifraNoua;
if(cifra % 2 == 1)
cifraNoua = cifra - 1;
else
cifraNoua = cifra;
rasturnat = rasturnat * 10 + cifraNoua;
}
while(rasturnat != 0)
{
unsigned int cifra = rasturnat % 10;
rasturnat = rasturnat / 10;
noulN = noulN * 10 + cifra;
}
if(copieN % 10 == 0)
noulN = noulN * 10;
n = noulN;
}
2. Un tablou bidimensional cu număr impar de coloane este numit simetric faţă de coloana din mijloc dacă, pe fiecare linie a tabloului, elementele dispuse simetric faţă de elementul din mijloc al liniei respective au valori egale. Scrieţi un program C/C++ care citeşte de la tastatură două numere naturale din intervalul [3,21], m şi n (n impar), şi elementele unui tablou bidimensional cu m linii şi n coloane, numere naturale din intervalul [0,104]. Programul afişează pe ecran mesajul DA, dacă tabloul este simetric faţă de coloana din mijloc, sau mesajul NU în caz contrar.
Exemplu: pentru m=4, n=5 și tabloul alăturat, se afişează pe ecran DA
Pentru a rezolva aceasta problema vom parcurge doar prima jumatate a matricei si vom verifica pe rand elementele cu cea de a doua jumatate. Ne folosim de o variabila care initial este setata cu 1. Daca gasim prima pereche de numere ce nu este simetrica, atunci toata matricea nu este simetrica. La final verificam variabila noastra si afisam raspunsul.
#include <iostream>
using namespace std;
int main()
{
unsigned int matrice[1000][1000];
int n, m;
cin >> m >> n;
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
cin >> matrice[i][j];
}
}
int matriceSimetrica = 1;
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n / 2; j++)
{
if(matrice[i][j] != matrice[i][n - j - 1])
matriceSimetrica = 0;
}
}
if(matriceSimetrica == 1)
cout << "DA";
else
cout << "NU";
return 0;
}
3. Un termen al unui șir de numere se numește vârf local al acestuia dacă nu există niciun alt termen mai mare sau egal cu el care să îl preceadă în șir sau dacă este egal cu termenul vecin anterior, iar acesta este vârf local. Fișierul bac.txt conține un șir format din cel puțin două și cel mult 106 numere naturale din intervalul [0,103], separate prin câte un spațiu. Se cere să se afișeze pe ecran, separate prin câte un spațiu, toate vârfurile locale ale șirului aflat în fișier. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al spațiului de memorie utilizat.
Exemplu: dacă fișierul conține numerele 7 4 9 10 10 10 8 10 10 8 30
se afișează pe ecran 7 9 10 10 10 30
a) Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.
b) Scrieți programul C/C++ corespunzător algoritmului proiectat.
Pe masura ce citim numerele, verificam daca numarul curent este mai mare decat varful local. Daca este mai mare, updatam acest varf. Daca in schimb este egal cu varful local, iar varful local este vecinul numarului curent, updatam varful local.
Algoritmul este eficient din punct de vedere al memoriei deoarece nu stocam intregul sir in memorie. Folosim fiecare variabila declarata. De asemenea, algoritmul mai este eficient si din punct de vedere al timpului de executie, fiind liniar in timp, avand complexitatea O(n) unde n este numarul maxim de elemente din fisier.
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("bac.txt");
int main()
{
unsigned int nr;
unsigned int nrAnterior = 0;
unsigned int varfLocal = 0, pozitieVarfLocal = 0;
unsigned int pozitie = 1;
while(fin >> nr)
{
if(nr > varfLocal)
{
varfLocal = nr;
pozitieVarfLocal = pozitie;
cout << nr << " ";
}
else if(nr == nrAnterior && varfLocal == nr && pozitieVarfLocal == pozitie - 1)
{
varfLocal = nr;
pozitieVarfLocal = pozitie;
cout << nr << " ";
}
pozitie = pozitie + 1;
nrAnterior = nr;
}
return 0;
}
