Data: model 2017
Profil: Matematica-Informatica
Limbaj: C++
Subiectul I.
1. Valoarea expresiei C/C++ alăturate 5+7/2 este:
a. 6
b. 8 | Corect: Tinem cont de ordinea operatiilor in C++, si facem mai intai impartirea. 7/2 este 3 (NU 3.5 – deoarece impartim doua numere de tip int). 5+3 = 8
c. 8.5
d. 9
2. Algoritmul alăturat este reprezentat în pseudocod.
a. Scriei valorile afisate dacă se citesc, în această ordine, numerele 65 și 80.
Facem un tabel de valori, si urmarim cu atentie conditiile.
Cum functioneaza acest algoritm?
- Pentru inceput, acesta citeste doua numere de la tastatura, p si q, vom descoperii mai tarziu ca aceste numere reprezinta un interval!
- Vom avea o variabila x care se va plimba cu cate o unitate intre p si q. Toate operatiile se vor efectua asupra lui x.
- Copiem variabila x in y, si ne vom juca cu y in continuare.
- In c retinem ultima cifra a lui y. Iar pe rand, verificam daca fiecare cifra a lui y (incepand cu coada) este egala cu c.
- In momentul cand y = 0 (cand toate cifrele unui numar sunt egale), afisam x (= variabila cu care noi ne plimbam)
Astfel incat algoritmul se reduce la urmatoarea intrebare: “care numere cu toate cifrele egale se afla intre 65 si 80?” Raspunsul este simplu: 66 si 77.
b. Dacă pentru variabila p se citeste numărul 1234, scriei cel mai mare număr de patru cifre care poate fi citit pentru variabila q astfel încât, în urma executării algoritmului, să se afiseze 5 numere.
Deoarece am redus algoritmul la o simpla intrebare, putem sa traducem cerinta.
Pornind de la numarul 1234, pana unde ne putem intinde, astfel incat sa avem doar 5 numere cu toate cifrele egale. Pai urmatoarele numere cu cifrele egale vor fi 2222, 3333, 4444, 5555, 6666, 7777, 8888, si asa mai departe. Dar pentru ca ne trebuie doar primele 5 numere, inseamna ca algoritmul nostru va trebuii sa se opreasca dupa 6666. In enunt se specifica ca se doreste cel mai mare numar, asa ca mergem pana la 7776.
c. Scriei în pseudocod un algoritm, echivalent cu cel dat, în care să se înlocuiască structura cât timp…execută cu o structură de tip pentru…execută.
Structura pentru…executa este structura “for” din C++. Deoarece am specifiat in subpunctul a ca aceasta problema se reduce la un interval, putem spune ca vom avea in C++ un “for” de genul for(int i = x; i <= q; i++).
citeste p, q x <- q pentru i <- x, q executa --- y <- x --- c <- y % 10 --- cat timp y != 0 si y % 10 = c executa ------ y <- [y / 10] --- daca y = 0 atunci ------ scrie x, ' ' --- x <- x + 1
d. Scrieti programul C/C++ corespunzător algoritmului dat.
unsigned int p, q, x, y, c;
cin >> p >> q;
x = p;
while(x <= q)
{
y = x;
c = y % 10;
while(y != 0 && y % 10 == c)
y = y / 10;
if(y == 0)
cout << x << " ";
x = x + 1;
}
Subiectul II.
1. Se consideră arborele cu 8 noduri, numerotate de la 1 la 8, reprezentat prin vectorul de „tati”: (3, 0, 2, 2, 4, 4, 2, 4). Un nod care este „frate” al nodului 4 este:
Desenam mai intai arborele descris in enunt. 4 are ca si frati, nodurile 3 si 7. Prin urmare, raspunsul corect este c. 7
2. Se consideră un graf orientat cu 15 arce si fără circuite. Numărul minim de vârfuri ale grafului este:
Pentru a rezolva problema, haideti sa lamurim doi termeni noi.
Ce este un arc? Un arc este o muchie, o legatura intre doua noduri.
Ce este un circuit? Un circuit este un drum in care primul si ultimul element din drum coincid.
Ideea principala in aceasta problema a fost sa construim un graf complet (in care oricare doua noduri sunt conectate).
Formula pentru un graf complet este: n * (n – 1) / 2 unde n este numarul de noduri al grafului.
Aplicam formula, si orientam sensul arcelor (= muchiilor) astfel inca sa nu se creeze nici un circuit.
3. Variabilele f si fd, declarate alăturat, memorează în câmpurile x si y numărătorul, respectiv numitorul câte unei fractii. Scrieti o secventă de instructiuni care să memoreze în variabila fd fractia obtinută prin scăderea fracției 1/2017 din fracția memorată în variabila f.
Pentru a scadea doua fractii, trebuie mai intai sa le aducem la un numitor comun. Deoarece nu trebuie ca fractia sa fie ireversibila (sa nu se mai poata simplifica), vom amplifica fiecare fractie cu numitorul celeilalte.
fd.y = 2017 * f.y; // Numitorul fractiei fd va fi produsul intre numitorul primei fractii si 2017 fd.x = (f.x * 2017) - (1 * f.y) // Numaratorul fractiei va fi diferenta intre noile numaratoare ale celor doua fractii
4. Reprezentați grafic și prin matrice de adiacență un graf conex neorientat cu 5 noduri,numerotate de la 1 la 5, dintre care 3 noduri au gradul 1.
5. Un text are cel mult 100 de caractere, iar cuvintele sale sunt formate doar din litere mici ale alfabetului englez si sunt separate prin câte un spațiu. Scrieti un program C/C++ care citeste de la tastatură un text de tipul precizat mai sus si îl transformă în memorie prin înlocuirea fiecărui cuvânt format din număr par de litere cu simbolul #. Programul afisează pe ecran textul obtinut sau mesajul nu exista dacă textul citit nu conține astfel de cuvinte.
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
char text[105], text_copie[105]; //Declaram textul
cin.getline(text, 105); //Citim TOATA linia introdusa la tastatura
strcpy(text_copie, text); //Facem o copie de rezerva a textului
int cuvintePare = 0; //Numaram cate cuvinte pare exista
char *pointer; //Declaram pointer-ul pe care il vom folosii pentru cuvinte
pointer = strtok(text, " "); //Spargem textul, dupa fiecare spatiu
while(pointer != NULL)
{
if(strlen(pointer) % 2 == 0) //Verificam cuvantul curent sa aiba un numar par de litere
cuvintePare++; //Incrementam contorul cu o unitate
pointer = strtok(NULL, " ");
}
if(cuvintePare != 0)
{
pointer = strtok(text_copie, " "); //Spargem textul de rezerva, dupa fiecare spatiu
while(pointer != NULL)
{
if(strlen(pointer) % 2 == 0) //Cuvantul curent are un numar par de litere
cout << "# ";
else //Cuvantul curent are un numar impar de litere
cout << pointer << " ";
pointer = strtok(NULL, " ");
}
}
else //Cazul "nu exista"
cout << "Nu exista.";
return 0;
}
Subiectul III.
1. Utilizând metoda bactracking se generează toate submultimile cu cel mult patru instrumente muzicale din multimea {clarinet, corn, flaut, oboi, saxofon}. Primele șase solutii generate sunt, în această ordine: {clarinet}, {clarinet, corn}, {clarinet, corn, flaut}, {clarinet, corn, flaut, oboi}, {clarinet, corn, flaut, saxofon}, {clarinet, corn, oboi}. Cea de a opta solutie este:
Vom numerota fiecare instrument cu cate o cifra. Si vom scrie mai jos cum se deruleaza un algoritm pentru generarea unor submultimi utilizand metoda backtracking.
1 - clarinet 2 - corn 3 - flaut 4 - oboi 5 - saxofon 1 1 2 1 2 3 1 2 3 4 1 2 3 5 1 2 4 1 2 4 5 1 2 5
Avand in vedere ca cifrele 1, 2, 5 reprezinta instrumentele clarinet, corn si saxofon, solutia corecta este c).
2. Subprogramul f este definit alăturat. Scrieti ce se afisează în urma apelului f(12);
Scriem pe o foaie fiecare pas din algoritm, si urmarim cu atentie toate conditiile. (sa nu uitati ca si in interiorul for-ului se afla o conditie)
Raspunsul final fiind 2 2 3 3 2 4 6.
3. Subprogramul nrDiv are doi parametri, a și b (a≤b), prin care primeste câte un număr natural din intervalul [1,1.000.000.000]. Subprogramul returnează numărul valorilor din intervalul [a,b] care pot fi scrise ca produs de două numere naturale consecutive. Scrieti definitia completă a subprogramului.
Programul este urmatorul, si vom discuta pe baza acestuia:
unsigned int nrDiv(unsigned int a, unsigned int b)
{
int contor = 0;
int radical_a = sqrt(a);
for(int i = radical_a; i * (i + 1) <= b; i++)
contor++;
return contor;
}
Cum arata un numar descris in enunt?
[math]n*(n+1)[/math]
Varianta initiala ar fi fost sa pornim de la 1 la 1 miliard si sa descompunem fiecare numar in divizori, dupa care sa analizam divizorii. Este totusi o metoda foarte ineficienta din punct de vedere al timpului, pentru ca putem deduce cateva idei matematice. Prima idee matematica este urmatoarea
[math]n^2 < n*(n+1) < (n+1)^2 [/math]
Adica numarul nostru “special” se afla intre doua patrate perfecte. Ce se intampla daca scriu sqrt(a) ? Voi obtine cel mai mic numar “special”. De exemplu, radical din 10 este 3 (lucram pe numere intregi). Asta inseamna ca urmatorul numar special este 3 * 4.
Pe aceasta idee pornim un for de la radical din a, si pana la b. For-ul va construii in interior ecuatia n * (n+1) si va verifica la fiecare pas daca este mai mica decat b. De asemenea, am declarat un contor pentru a putea tine evidenta structurii for.
Atentie: La Bacalaureat in general (depinde de corectori / barem) se puncteaza oricare metoda de rezolvare, cat timp functioneaza. Eu am decis sa va prezint o metoda mai eficienta si usoara de inteles.
4. Se consideră sirul definit alăturat (unde n și x sunt numere naturale nenule, iar x este impar). De exemplu, pentru x=21 șirul este: 21, 22, 43, 44, 87, 88, 175, 176 ….
Se citesc de la tastatură două numere naturale din intervalul [1,109], x și y, cu cel mult nouă cifre, unde x are semnificația precizată mai sus, iar y este un termen al sirului dat, si se cere să se scrie în fisierul text bac.txt, în ordine strict descrescătoare, separați prin câte un spațiu, toti termenii sirului care sunt mai mici sau egali cu y. Pentru determinarea termenilor ceruti se utilizează un algoritm eficient din punctul de vedere al memoriei si al timpului de executare.
Primul nostru gand este sa folosim un algoritm recursiv, dar avand in vedere ca este foarte greu de gandit doar pe foaie, ar trebuii sa abordam problema altfel. Enuntul ne ajuta ca sa privim aceasta problema cu alti ochi. Trebuie sa afisam numerele in ordine descrescatoare, de la ultimul numar obtinut, la numarul nostru de plecare (21). Daca analizam sirul, vedem ca este o succesiune de numere pare si impare.
Ce se afla asadar inainte de un numar par? Un numar care este mai mic cu o unitate. Putem vedea asta la orice numar par. Inainte de 176 este 175. Inainte de 88 este 87, si inainte de 44 este 43.
Ce se afla inainte de un numar impar? Un numar care este egal cu jumatate din numarul urmator. De exemplu inainte de 43 se afla 22 ( 43 + 1 impartit la 2). Inainte de 87 se afla 44 ( 87 + 1 impartit la 2). Ati prins ideea? Daca as fi destul de stapan pe matematica, v-as demonstra ideea de mai sus matematic.
a. Algoritmul ales de noi este un algoritm cu complexitate liniara O(n). Acesta construieste sirul in mod descrescator, pornind de la y si oprindu-se la x. Pe baza relatiei de recurenta din enunt, am dedus urmatoarea observatie: numarul precedent este egal cu numarul curent – 1 (daca numarul curent este par), sau numarul precedent este egal cu jumatate din numarul urmator (daca numarul curent este impar). Pentru ca nu stocam decat numarul curent in memorie, algoritmul ales de noi este foarte eficient si din punct de vedere al timpului de executie si din punct de vedere al memoriei.
b.
#include <iostream>
#include <fstream>
using namespace std;
ofstream fout("bac.txt");
int main()
{
unsigned int x, y;
cin >> x >> y;
unsigned int numar_curent = y;
while(x <= numar_curent)
{
fout << numar_curent << " ";
if(numar_curent % 2 == 0) //Daca numarul curent este par
numar_curent = numar_curent - 1;
else //Daca numarul curent este impar
numar_curent = (numar_curent + 1) / 2;
}
return 0;
}
