Data: simulare 2017
Profil: Matematica-Informatica
Limbaj: C++
Subiectul I.
1. Expresia C/C++ alăturată are valoarea: 17/3/2%17
a. 0
b. 2 – Corect: Tinem cont de ordinea operatiilor in C++, si efectuam calculele in ordine. 17/3 este 5 , mai apoi 5 / 2 este 2. Restul impartirii lui 2 la 17 este 2.
c. 10
d. 17
2. Algoritmul alăturat este reprezentat în pseudocod. S-a notat cu a%b restul împărţirii numărului natural a la numărul natural nenul b.
a. Scrieţi ce se afişează dacă se citesc, în această ordine, numerele 15, 3 şi 4.
Urmarim tabelul de valori de mai jos:
| n | a | b | x | ok | x%a | x%b |
| 15 | 3 | 4 | 1 | 0 | 0 | 0 |
| 15 | 3 | 4 | 2 | 0 | 0 | 0 |
| 15 | 3 | 4 | 3 | 0 | 1 | 0 |
| 15 | 3 | 4 | 4 | 1 | 0 | 1 |
| 15 | 3 | 4 | 5 | 1 | 0 | 0 |
| 15 | 3 | 4 | 6 | 1 | 1 | 0 |
| … | … | … | … | … | … | … |
| 15 | 3 | 4 | 14 | 1 | 0 | 0 |
| 15 | 3 | 4 | 15 | 1 | 1 | 0 |
Acest algoritm parcurge toate numerele intre x si n. Atunci cand le parcurge verifica daca acesta se imparte exact doar la a sau doar la b. Asadar, parcurgem toate numerele de la 1 la 15 si verificam care dintre acestea se impart exact doar la 3 sau doar la 4.
Numerele 3 4 6 8 9 15 se impart exact doar la 3 sau doar la 4. De exemplu 12, este un numar ce este incorect doarece se imparte exact si la 3 si la 4.
b. Scrieţi două seturi distincte de date de intrare astfel încât, în urma executării algoritmului, pentru fiecare dintre acestea să se afişeze valoarea 0.
15 3 3
20 4 4
Deoarece numerele a si b sunt egale intre ele, niciodata nu se va implinii conditia de la inceput iar variabila ok va ramane la valoarea presetata (0).
c. Scrieţi în pseudocod un algoritm echivalent cu cel dat, înlocuind adecvat structura cât timp…execută cu o structură repetitivă de tip pentru…execută.
citeste n, a, b ok <- 0 pentru x <- 1, n executa --- daca x % a = 0 si x % b != 0 sau x % a != 0 si x % b = 0 atunci ------ scrie x, ' ' ------ ok <- 1 daca ok = 0 atunci --- scrie 0
d. Scrieţi programul C/C++ corespunzător algoritmului dat.
unsigned int n, a, b, x, ok;
cin >> n >> a >> b;
ok = 0;
x = 1;
while(x <= n)
{
if((x % a == 0 && x % b != 0) || (x % a != 0 && x % b == 0))
{
cout << x << " ";
ok = 1;
}
x = x + 1;
}
if(ok == 0)
cout << 0;
Subiectul II.
1. Variabila s din secvența următoare permite memorarea unui şir de cel mult 20 de caractere.
strcpy(s,"tezauriza"); cout<<strstr(s,"za");
Functia strstr returneaza un pointer catre locul in care a fost gasit subsirul de caractere “za” in cuvantul “tezauriza”.
Asadar, raspunsul este zauriza (subpunctul d).
2. Matricea de adiacenţă a unui graf neorientat cu 7 noduri are 10 elemente nenule. Numărul maxim de componente conexe ale grafului este:
Avand 10 casute nenule (diferite de 0) intr-o matrice de adiacenta inseamna ca avem 5 legaturi intre noduri (am fi avut 10 legaturi daca ar fi fost vorba despre un graf orientat).
Trebuie sa ne gandim cum putem construii cele 5 legaturi astfel incat sa obtinem un numar maxim de componente conexe.
Asadar, raspunsul se observa din desen si aceasta este c) 4.
3. Se consideră arborele cu 8 noduri, numerotate de la 1 la 8, cu rădăcina 5 şi muchiile [1,5], [2,7], [3,7], [3,8], [4,5], [5,7], [6,7]. Enumeraţi nodurile care sunt descendenţi direcţi („fii”) ai nodului 7.
Desenam arborele descris in enunt. Descendentii directi ai nodului 7 sunt: 2, 3 si 6.
4. Variabila m memorează simultan, pentru fiecare dintre cele 20 de mașini oferite spre închiriere, următoarele date: anul fabricației mașinii (număr natural) și tipul de carburant al acesteia (șir de maximum 50 de caractere). Știind că expresiile C/C++ de mai jos au ca valori anul fabricației celei de a treia mașini, respectiv tipul de carburant al acesteia, scrieți definiția unei structuri cu eticheta masina, care permite memorarea datelor despre o mașină, și declarați corespunzător variabila m.
m[2].an m[2].carburant
struct masina{
int an;
char carburant[50];
}m[20];
Deoarece trebuie sa memoram doua caracteristici simultan (anul fabricatiei si tipul de carburant), va trebuii sa folosim tipul de date “struct”. Definim o variabila struct pe care o vom denumii masina. Ii atribuim doua caracteristici: anul de fabricatie si tipul de carburant (care este un sir de 50 de caractere).
Inainte sa terminam problema, trebuie sa fim atenti la inca un detaliu: ne trebuie 20 de exemplare. Drept urmare, declaram un vector “m” cu 20 de elemente. Fiecare element din vectorul “m” fiind de tip “masina”.
5. Scrieţi un program C/C++ care citeşte de la tastatură un număr natural n (n ∈ [2,20]) şi construieşte în memorie un tablou bidimensional cu n linii şi n coloane în care:
– ultima coloană conţine numerele naturale din intervalul [1,n], în ordine strict descrescătoare;
– toate elementele primei linii au valoarea n;
– oricare alt element este obţinut prin însumarea celor două elemente vecine cu el, unul aflat pe coloana din dreapta, pe aceeaşi linie cu el, iar celălalt pe aceeaşi coloană cu el, dar pe linia anterioară, ca în exemplu.
Programul afişează pe ecran tabloul obţinut, fiecare linie a tabloului pe câte o linie a ecranului, elementele fiecărei linii fiind separate prin câte un spaţiu.
#include <iostream>
using namespace std;
int main()
{
unsigned int n;
unsigned matrice[20][20];
cin >> n;
for(int i = 0; i < n; i++)
matrice[0][i] = n;
for(int i = 1; i < n; i++)
matrice[i][n - 1] = n - i;
for(int i = 1; i < n; i++)
{
for(int j = n - 2; j >= 0; j--)
matrice[i][j] = matrice[i - 1][j] + matrice[i][j + 1];
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
cout << matrice[i][j] << " ";
cout << "\n";
}
return 0;
}
Deoarece n este un numar natural, il declaram unsigned int.
Primul for seteaza toatele elementele de pe prima linie pe valoare n. Cel de-al doilea for de asemenea seteaza elementele de pe ultima coloana conform enuntului.
Dupa ce am construit “scheletul matricei”, putem sa trecem la generarea celorlalte elemente. Primul element ce va fi generat este penultimul numar de pe cea de a doua linie (deoarece doar pentru acest element cunoastem in prezent ambii vecini – mai multe detalii in video!).
Subiectul III.
1. Subprogramul f este definit alăturat. Indicați ce se afişează în urma apelului de mai jos: f(6);
void f(int x)
{
cout<<x;
if(x>3)
{
f(x-2);
cout<<x;
}
}
Trecem pe foaie fiecare etapa din functia noastra recursiva si vom obtine:
f(6): 6
— f(4): 4
—- f(2): 2
— 4
6
Asadar solutia corecta este c) 64246
2. Se utilizează metoda backtracking pentru a obţine toate buchetele formate din câte trei tipuri de flori de primăvară din mulțimea {brândușă, iasomie, lalea, liliac, margaretă}, astfel încât iasomia și liliacul nu vor fi plasate în același buchet. Știind că în cadrul unui buchet nu contează ordinea de aşezare a florilor, primele patru soluţii obţinute sunt, în această ordine: (brândușă, iasomie, lalea), (brândușă, iasomie, margaretă), (brândușă, lalea, liliac), (brândușă, lalea, margaretă). Scrieţi cea de a cincea şi cea de a şasea soluţie, în ordinea obţinerii lor.
Vom numerota fiecare instrument floare cu cate o cifra. Si vom scrie mai jos cum se deruleaza un algoritm pentru generarea unor submultimi utilizand metoda backtracking.
1 - brandusa 2 - iasomie 3 - lalea 4 - liliac 5 - margareta 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 - 1 4 5 2 3 4 - 2 3 5
Avand in vedere ca cifrele 2 si 4 nu trebuie sa se afle in aceasi solutie, raspunsul final este 1 4 5 si 2 3 5, adica: (brandusa, liliac, margareta) si (iasomie, lalea, margareta).
3. Subprogramul ranguri are un singur parametru, n, prin care primeşte un număr natural (n ∈ [0,109]). Subprogramul returnează numărul de cifre ale lui n care sunt egale cu pozițiile pe care le ocupă în scrierea acestuia. Pozițiile sunt numerotate de la dreapta la stânga, iar cifra unităților ocupă poziția 0. Scrieţi definiţia completă a subprogramului.
Exemplu: dacă n=6594270, subprogramul returnează numărul 4.
Programul este urmatorul, si vom discuta pe baza acestuia:
int ranguri(int n)
{
int c;
int contor = 0;
int total = 0;
while(n != 0)
{
c = n % 10;
n = n / 10;
if(c == contor)
total++;
contor++;
}
return total;
}
Deoarece algoritmul de descompunere a unui numar in cifre functioneaza in sens invers ne vom ajuta de acest lucru. Vom declara un contor care se va incrementa cu o unitate de fiecare data cand trecem la o cifra noua (in acest fel vom numara pozitia fiecarei cifre).
Cunoscand pozitia fiecarei cifre, si cifra insasi, vom verifica daca acestea sunt egale intre ele, si vom incrementa numarul total cu unu.
La final trebuie sa returnam rezultatul total. Va las mai jos si desfasurarea algoritmului, pe care il puteti regasii si in video.
n: 6594270 c: 0 contor: 0 total: 1 n: 659427 c: 7 contor: 1 total: 1 n: 65942 c: 2 contor: 2 total: 2 n: 6594 c: 4 contor: 3 total: 2 n: 659 c: 9 contor: 4 total: 2 n: 65 c: 5 contor: 5 total: 3 n: 6 c: 6 contor: 6 total: 4
4. Fișierul bac.in conține pe prima linie două numere naturale din intervalul [2,104], m și n, iar pe fiecare dintre următoarele două linii câte un șir de m, respectiv n numere naturale din intervalul [0,109], ordonate strict crescător. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu. Se cere să se afișeze pe ecran, în ordine strict descrescătoare, numerele pare care apar în cel puțin unul dintre cele două șiruri. Numerele afișate sunt separate prin câte un spațiu, iar dacă nu există niciun astfel de număr, se afișează pe ecran mesajul nu exista. Pentru determinarea numerelor cerute se va utiliza un algoritm eficient din punctul de vedere al timpului de executare.
a.
Algoritmul ales de noi este un algoritm cu complexitate liniara O(n + m). Acesta interclaseaza mai intai cei doi vectori, utilizandu-ne de faptul ca acestia sunt sortati inca de la inceput. Dupa ce algoritmul nostru interclaseaza cei doi vectori, parcurgem vectorul final in sens opus.
Inainte de a afisa numarul, verificam mai intai daca acesta a mai fost afisat inainte, si daca acesta este par.
b.
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("bac.in");
int main()
{
unsigned int n, m;
unsigned int v1[1000], v2[1000];
unsigned int solutie[2000];
fin >> n >> m;
for(int i = 0; i < n; i++)
fin >> v1[i];
for(int i = 0; i < m; i++)
fin >> v2[i];
int k = 0, i = 0, j = 0;
while(i < n && j < m)
{
if(v1[i] < v2[j])
{
solutie[k] = v1[i];
k++;
i++;
}
else
{
solutie[k] = v2[j];
k++;
j++;
}
}
if(i < n)
{
for(int l = i; l < n; l++)
{
solutie[k] = v1[l];
k++;
}
}
else
{
for(int l = j; l < m; l++)
{
solutie[k] = v2[l];
k++;
}
}
int ultimulNumar = -1;
for(int i = k - 1; i >= 0; i--)
{
if(solutie[i] != ultimulNumar && solutie[i] % 2 == 0)
{
ultimulNumar = solutie[i];
cout << solutie[i] << " ";
}
}
return 0;
}
