Data: model 2019
Profil: Matematica-Informatica
Limbaj: C++
Subiectul I.
1. Variabila întreagă n memorează un număr natural. Indicați expresia C/C++ care are valoarea 1 dacă şi numai dacă numărul memorat în n este divizibil cu 20, dar NU şi cu 19: !(n%20!=0 || n%19==0)
Deoarece avem o expresie negata, trebuie sa inversam toate interogarile pe care le stim, astfel incat, expresia alaturata devine (n%20 == 0 && n % 19 != 0)
Asadar, analizam variantele de raspuns, iar cea corecta este: d. !(n%20!=0 || n%19==0)
2. Subprogramul f este definit mai jos. Indicați apelul care determină afişarea, în ordine strict descrescătoare, a tuturor divizorilor proprii pozitivi ai numărului 1000 (divizori diferiți de 1 și de 1000).
void f (int n, int d)
{
if (d < n / 2)
f(n, d + 1);
if (n % d == 0)
cout << d <<’ ’;
}
Analizam functia recursiva si observam faptul ca al doilea if se executa doar daca n se imparte exact la d. Avand n-ul 1000, singura varianta de raspuns corecta este: a. f(1000, 2);
3. Utilizând metoda backtracking, se generează toate parfumurile formate prin amestecarea a câte 3 esențe distincte din mulţimea {agar, geranium, iasomie, paciuli, tuberoze}. Primele patru soluţii obţinute sunt, în această ordine: (agar, geranium, iasomie), (agar, geranium, paciuli), (agar, geranium, tuberoze) şi (agar, iasomie, paciuli). Indicaţi soluția generată imediat înainte de (geranium, iasomie, paciuli).
Codificam raspunsurile noastre:
1 – agar
2 – geranium
3 – iasomie
4 – paciuli
5 – tuberoze
Variantele de raspuns devin: (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4). Solutia generata inainte de (geranium, iasomie, paciuli) – adica (2, 3, 4) este (1, 4, 5) – adica b. (agar, paciuli, tuberoze)
4. Un arbore cu 10 noduri, numerotate de la 1 la 10, este reprezentat prin vectorul de „taţi” (6,5,7,5,9,9,6,7,0,5). Numărul nodurilor de tip “frunză” ale arborelui este:
Reprezentam arborele descris in problema mai jos:
Enunt Subiectul 1 – Problema 4
5. Un graf neorientat are 10 muchii și este conex. Numărul maxim de noduri ale sale este:
Un graf conex este un graf in care oricum am alege 2 noduri, exista un drum intre ele. Cu alte cuvinte, nu avem “insule”. Pentru a obtine cat mai multe noduri, folosind 10 muchii, putem lega 11 noduri dupa in felul urmator:
Enunt Subiectul 1 – Problema 5
Asadar, raspunsul corect este: d. 11
Subiectul II.
1. Se consideră algoritmul alăturat, reprezentat în pseudocod.
citeste n k <- 1 cat timp n >= 1 executa --- daca n > k atunci i <- k --- altfel i <- n --- n <- n - i --- cat timp i >= 1 executa ------ scrie k, ' '; i <- i - 1 --- k <- k + 1
a) Scrieţi valorile afişate dacă se citește numărul 7.
Raspunsul corect: 1, 2, 2, 3, 3, 3, 4 – pentru explicatia completa – urmariti videoul de mai sus.
b) Scrieţi cel mai mic și cel mai mare număr care pot fi citite astfel încât, în urma executării algoritmului, pentru fiecare dintre acestea, ultima valoare afişată să fie 10.
Observam urmatoarea idee: n-ul nostru va fi pe rand 7, 6, 4 si 1. Daca facem diferentele intre doua numere consecutive, observam ca acestea sunt: 1, 2 si 3. Asadar, exista o conexiune intre diferente si numerele afisate pe ecran.
Pentru a afisa prima oara 10, diferenta intre doua numere trebuie sa fie 9. Calculam (9*10) / 2 si obtinem 45. Pentru numarul 45, ultimul numar afisat va fi 9. Asadar, 46 este numarul nostru minim.
Aplicam aceeasi logica pentru a determina numarul maxim: 55.
c) Scrieţi programul C/C++ corespunzător algoritmului dat.
#include <iostream>
using namespace std;
int main()
{
unsigned int n;
int k, i;
cin >> n;
k = 1;
while(n >= 1)
{
if(n > k)
i = k;
else
i = n;
n = n - i;
while(i >= 1)
{
cout << k << " ";
i = i - 1;
}
k = k + 1;
}
return 0;
}
d) Scrieţi în pseudocod un algoritm, echivalent cu cel dat, înlocuind una dintre structurile cât timp…execută cu o structură repetitivă de alt tip.
citeste n k <- 1 repeta --- daca n > k atunci i <- k --- altfel i <- n --- n <- n - i --- cat timp i >= 1 executa ------ scrie k, ' '; i <- i - 1 --- k <- k + 1 pana cand n < 1
2. Pentru un număr complex se memorează următoarele date: partea reală și partea imaginară (numere reale). Variabila z memorează simultan date pentru fiecare dintre cele 20 de numere complexe. Știind că expresia C/C++ de mai jos are valoarea sumei dintre partea reală și partea imaginară ale primului număr complex dintre cele precizate, scrieți definiția unei structuri cu eticheta complex care să permită memorarea datelor unui număr complex, și declarați corespunzător variabila z.
z[0].pre+z[0].pim
struct complex {
int pre;
int pim;
}z[20];
3. Variabilele i şi j sunt de tip întreg, iar variabila a memorează un tablou bidimensional cu 5 linii şi 5 coloane, numerotate de la 1 la 5, având iniţial toate elementele nule. Fără a utiliza alte variabile decât cele menționate, 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 alăturat.
Enunt Subiectul 2 – Problema 3
Daca am fi avut posibilitatea sa stocam inca o variabila “v” pe care o initializam cu 1, totul ar fi decurs foarte simplu, insa in enunt se specifica faptul ca nu avem voie cu alte variabile. Asadar, trebuie sa ne folosim doar de i si j. Observam ca daca din fiecare linie am scadea (i * 5) atunci toate liniile ar arata la fel.
for(i=1;i<=5;i++)
for(j=1;j<=5;j++)
a[i][j] = (i - 1) * 5 + j;
Subiectul III.
1. Subprogramul CifrePrime are un singur parametru, n, prin care primeşte un număr natural (n∈[0,109]). Subprogramul returnează suma cifrelor prime ale lui n. Scrieţi definiţia completă a subprogramului.
Exemplu: dacă n=1235405, atunci subprogramul returnează 15, iar dacă n=140, atunci subprogramul returnează 0.
int CifrePrime(unsigned int n)
{
int suma = 0;
while(n)
{
int c = n % 10;
if(c == 2 || c == 3 || c == 5 || c == 7) // Cifre Prime
suma = suma + c;
n = n / 10;
}
return suma;
}
Observam faptul ca lucram doar cu cifre, asadar nu este necesar sa scriem o functie separata care sa verifice daca cifrele sunt prime, deoarece nu avem decat 4 cazuri.
2. Intr-un text cu cel mult 100 de caractere, cuvintele sunt formate numai din litere mici ale alfabetului englez și sunt separate prin unul sau mai multe spații.
Scrieți un program C/C++ care citește de la tastatură un astfel de text, cu cel puțin trei cuvinte, și construiește în memorie un șir de caractere format din prima consoană a primului cuvânt, urmată de prima vocală a celui de al doilea cuvânt, respectiv de ultima literă a ultimului cuvânt, în ordinea în care acestea apar în text. Șirul obținut se afișează pe ecran, iar dacă nu se poate obține un astfel de șir, se afișează pe ecran mesajul nu exista. Se consideră vocale literele a, e, i, o, u.
Exemplu: pentru textul el prefera sa mearga la schi
se afișează pe ecran șirul lei
iar pentru textul ei prefera sa mearga la schi
se afișează pe ecran mesajul nu exista
#include <iostream>
using namespace std;
int main()
{
char s[101];
cin.get(s, 101);
char rezultat[4];
rezultat[3] = '\0';
int cuvant_curent = 1;
char *cuvant = strtok(s, " ");
while(cuvant != NULL)
{
if(cuvant_curent == 1)
{
bool consoana = false;
for(int i = 0; i < strlen(cuvant); i++)
{
if(cuvant[i] != 'a' && cuvant[i] != 'e' && cuvant[i] != 'i' && cuvant[i] != 'o' && cuvant[i] != 'u')
{
rezultat[0] = cuvant[i];
consoana = true;
}
}
if(consoana == false)
{
cout << "nu exista";
return 0;
}
}
if(cuvant_curent == 2)
{
bool vocala = false;
for(int i = 0; i < strlen(cuvant); i++)
{
if(cuvant[i] == 'a' || cuvant[i] == 'e' || cuvant[i] == 'i' || cuvant[i] == 'o' || cuvant[i] == 'u')
{
rezultat[1] = cuvant[i];
vocala = true;
break;
}
}
if(vocala == false)
{
cout << "nu exista";
return 0;
}
}
rezultat[2] = cuvant[strlen(cuvant) - 1];
cuvant = strtok(NULL, " ");
cuvant_curent++;
}
cout << rezultat;
return 0;
}
3. Un interval este numit prieten de grad n al unui șir dacă sunt exact n termeni ai șirului cu valori din interval și dacă toate numerele întregi care aparțin intervalului sunt valori ale unor termeni ai șirului. Fișierul bac.txt conține un șir de cel mult 106 numere naturale din intervalul [0,102], separate prin câte un spațiu. Se cere să se afișeze pe ecran numărul maxim n cu proprietatea că există un interval prieten de grad n al șirului aflat în fișier. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul conține numerele
10 10 11 3 4 2 49 4 2 3 21 2 27 12 13 14 15 5
atunci se afișează pe ecran 8 (intervalului [2,5] îi aparțin 8 termeni ai șirului)
a) Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.
b) Scrieți programul C/C++ corespunzător algoritmului proiectat.
a) Declaram un vector de aparitii ce contine 100 de elemente. Pe masura ce citim un numar, incrementam pozitia din vectorul de apariti. De exemplu daca “2” apare de 7-ori, atunci v[2] va fi 7. Dupa ce am construit vectorul de aparitii, parcurgem fiecare element din el si calculam lungimea fiecarui interval in care nu se gasesc “0”-uri. La final, afisam cea mai mare valoare ce am obtinut-o.
Algoritmul este eficient din punct de vedere al executarii, avand o complexitate O(N) – unde N este numarul maxim din sir – in cazul nostru – 100.
b)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("bac.txt");
int v[101];
int main()
{
int nr;
while(fin >> nr)
v[nr]++;
int lungime = 0;
int lungime_maxima = 0;
for(int i = 0; i <= 100; i++)
{
if(v[i] == 0)
lungime = 0;
else
lungime = lungime + v[i];
if(lungime > lungime_maxima)
lungime_maxima = lungime;
}
cout << lungime_maxima;
return 0;
}
