Buna ziua si bine v-am regasit! De astazi in colo vom incepe sa rezolvam impreuna subiectele de informatica.
Data: iulie 2016
Profil: Matematica-Informatica
Limbaj: C++
Subiectul I.
1. Variabila x este de tip întreg. Indicaţi o expresie C/C++ care are valoarea 1 dacă şi numai dacă valoarea variabilei x are exact trei cifre.
a. x%1000==0 || x%100!=0 | Numarul 1000 nu respecta conditia
b. x/1000==0 || x/100!=0 | Numarul 1234 nu respecta conditia
c. x%1000==0 && x%100!=0 | Numarul 2017 nu respecta conditia
d. x/1000==0 && x/100!=0 | Corect: orice numar cuprins intre 100 si 999 respecta ambele conditii
2. Se consideră algoritmul alăturat, 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 valorile afişate în urma executării algoritmului dacă se citesc, în această ordine, numerele 11, 30 și 7.
Facem un tabel de valori (voi explica mai detaliat intr-un viitor video), si urmarim cu atentie conditiile
b. Scrieţi un set de valori care pot fi citite pentru variabilele m, n şi x, astfel încât, în urma executării algoritmului, să se afişeze două numere egale.
m=12 n=16 x=7 este un exemplu corect. Trebuie sa ne alegem un x, iar mai apoi sa cautam doua numere dupa urmatoarea idee: acestea trebuie sa fie aflate la egala distanta fata de un divizor al lui x. Distanta aceasta este “2” in cazul nostru, amandoua sunt la egala distanta fata de 14 – divizorul lui 7.
c. Scrieţi în pseudocod un algoritm echivalent cu cel dat, înlocuind structura cât timp…execută cu o structură repetitivă de alt tip.
citeste m, n, x p <- 0 --- executa --- daca m % x = 0 si n % x = 0 atunci ------ p <- x --- altfel ------ daca m % x = 0 atunci --------- n <- n - 1 ------ altfel --------- m <- m + 1 --- cat timp m > n sau p != 0
d. Scrieţi programul C/C++ corespunzător algoritmului dat.
unsigned int m, n, x, p;
p = 0;
while (m < n && p == 0)
{
if(m % x == 0 && n % x == 0)
p = x;
else
if(m % x == 0)
n = n - 1;
else
m = m + 1;
}
cout << m << " " << n;
Subiectul II.
1. În declararea alăturată, variabila m memorează anul fabricaţiei şi marca unei maşini. Indicaţi o expresie C/C++ care are valoarea 1 dacă şi numai dacă maşina a fost fabricată înainte de anul 1950.
a. m.an_fabricatie < 1950 | Corect: Deoarece asa se apeleaza o caracteristica unui struct. Avem o variabila “m” de tip masina, care are doua caracteristici, un an de fabricate si o marca. Pentru a accesa campul “an_fabricatie” din variabila noastra, vom apela la m.an_fabricatie
b. m.masina.an_fabricatie.m < 1950
c. m(an_fabricatie) < 1950
d. masina(an_fabricatie) < 1950
2. Matricea de adiacenţă a unui graf neorientat cu 5 noduri are 6 elemente nenule. Numărul minim de componente conexe ale grafului este:
Urmarim matricea de adiacenta si facem un desen astfel incat, sa avem cat mai putine componente conexe.
3. Un arbore cu 8 noduri, numerotate de la 1 la 8, are drept rădăcină nodul numerotat cu 7 şi muchiile [1,7], [2,5], [3,5], [3,6], [4,7], [5,7], [5,8]. Enumeraţi nodurile care sunt descendenţi direcţi („fii”) ai nodului 5.
Desenam mai intari arborele descris in enunt, dupa care analizam nodul 5. Acesta areca descendeti directi (sau fii), nodurile 2, 3 si 8.
4. În secvenţa de instrucțiuni de mai jos variabilele s1 și s2 memorează câte un şir cu cel mult 20 de caractere. Scrieţi ce se afişează pe ecran în urma executării secvenţei.
strcpy(s1,”informatica”); cout<<strlen(s1); | printf(”%d”,strlen(s1)); strcpy(s2,”mate”); strcat(s2,strstr(s1,”ma”)); cout<<s2; | printf(”%s”,s2);
Dupa primul strcpy, s1 va devenii “informatica”.
Dupa cel de-al doilea strcpy, s2 va devenii “mate”.
Acum stam si analizam cea de a 4-a linie. Functia strcat(a, b); stim ca lipeste doua siruri a si b. Deci dupa cuvantul “mate” urmeaza sa copiem rezultatul functiei strstr(s1, “ma”);. Stim ca cea din urma functie returneaza un pointer!! Deci in urma functiei strstr, cel de-al doilea sir va fi “matica”. Cele doua cuvinte lipite formeaza “matematica”.
In ordine, rezultatul este:
11 matematica
5. Scrieţi un program C/C++ care citeşte de la tastatură un număr natural, n (nÎ[2,102]), şi construieşte în memorie un tablou bidimensional, cu n linii şi n coloane, astfel:
· prima coloană conţine, în ordine strict crescătoare, numerele naturale din intervalul [1,n];
· toate elementele ultimei linii au valoarea n;
· oricare alt element este obţinut prin însumarea celor două elemente vecine cu el, aflate pe coloana anterioară, unul pe aceeaşi linie cu el, iar celălalt pe linia următoare, 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; //Declaram numarul natural citit
int tablou[105][105]; //Declaram matricea de maxim 105 elemente
cin >> n; //Citim numarul n de la tastatura
for(int i = 1; i <= n; i++) //Creeam prima coloana din matrice
tablou[i][1] = i;
for(int i = 1; i <= n; i++) //Creeam elementele ultimei coloane
tablou[n][i] = n;
for(int i = 2; i <= n; i++) //Parcurgem matricea invers
{
for(int j = 1; j <= n-1; j++)
tablou[j][i] = tablou[j][i-1] + tablou[j+1][i-1]; //Elementul curent este egal cu suma celor doua elemente din enunt
}
for(int i = 1; i <= n; i++) //Afisam matricea
{
for(int j = 1; j <= n; j++)
cout << tablou[i][j] << " ";
cout << "\n";
}
}
Subiectul III.
1. Subprogramul f este definit alăturat. Indicaţi ce se afişează în urma apelului de mai jos: f(2016);
n = 2016 | cout << 2016;
n = 201 | cout << 201;
n = 20 | cout << 20;
n = 2 | cout << 2;
n = 0
Prin urmare, raspunsul corect este c. 2016201202
2. Având la dispoziţie cinci tipuri de prăjituri, cu pere, cu mure, cu afine, cu fragi, cu zmeură, se utilizează metoda backtracking pentru a obţine toate posibilităţile de a forma platouri cu câte trei tipuri de prăjituri diferite, ştiind că în cadrul unui platou nu contează ordinea de aşezare a prăjiturilor şi că prăjiturile cu mure nu vor fi plasate pe acelaşi platou cu prăjiturile cu fragi. Primele patru soluţii obţinute sunt, în această ordine: (pere, mure, afine), (pere, mure, zmeură), (pere, afine, fragi), (pere, afine, zmeură). Scrieţi cea de a cincea şi cea de a şasea soluţie, în ordinea obţinerii lor.
Rezumam undeva toate elementele. Deci avem pere – mure – afine – fragi – zmeura. In total trebuie sa fie 3 tipuri de prajituri diferite. Trebuie sa fim atenti ca murele sa nu le plasam atunci cand avem fragi.
Primele 4 solutii sunt: (pere, mure, afine), (pere, mure, zmeură), (pere, afine, fragi), (pere, afine, zmeură).
Urmatoarea solutie este (pere, fragi, zmeura) deoarece aceasta este ordinea normala in cazul unui backtracing. Dupa care urmatoarea solutie (mure, afine, fragi), dar este in contradictie cu cerinta din enunt. Asadat, urmatoarea solutie dupa aceasta este (mure, afine, zmeura).
3. Subprogramul cifreImpare are un singur parametru, n, prin care primeşte un număr natural cu toate cifrele nenule (nÎ[1,109]). Subprogramul returnează numărul obţinut prin eliminarea tuturor cifrelor impare din n, respectiv -1 dacă nu există astfel de cifre sau dacă toate cifrele lui n sunt impare. Scrieţi definiţia completă a subprogramului.
int cifreImpare(unsigned int n)
{
int c, n_invers = 0, contor = 0; //Declaram variabilele
//Facem un contor sa numaram cate cifre impare are numarul nostru
while(n)
{
c = n % 10; //Aflam in "c" cifra curenta
if(c % 2 == 0) //Daca aceasta este para, formam inversul numarului
n_invers = n_invers * 10 + c;
else //Daca aceasta este impara o adaugam la contor
contor++; //Crestem contorul cu o unitate
n = n / 10; //Stergem ultima cifra din numar
}
if(contor == 0) //Daca nu avem cifre impare returnam -1
return -1;
while(n_invers) //Acum intoarcem numarul nostru, la forma lui initiala
{
c = n_invers % 10;
n = n * 10 + c;
n_invers = n_invers / 10;
}
return n;
}
4. Fişierul numere.in conţine pe prima linie un număr natural n (nÎ[2,109]), iar pe a doua linie un şir de cel mult 109 numere naturale din intervalul [1,n]. Numerele din şir sunt ordonate crescător şi sunt separate prin câte un spaţiu. Se cere să se determine valorile naturale distincte din intervalul [1,n] care NU se găsesc în şirul menţionat mai sus. Valorile determinate se afişează pe ecran în ordine strict crescătoare, separate prin câte un spaţiu. Dacă nu există astfel de valori, se afişează pe ecran mesajul Nu exista. Pentru determinarea valorilor cerute se utilizează un algoritm eficient din punctul de vedere al memoriei şi al timpului de executare.
a. Algoritmul nostru va retine tot timpul ultimul numar din vector si cel curent. Astfel incat, de fiecare data cand ajungem la un numar din fisier, afisam numerele intre ultimul numar citit si numarul prezent. Deoarece nu folosim un vector, nu folosim aproape deloc memorie. De asemenea, complexitatea timpului pentru acest algoritm este O(n).
b.
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("numere.in");
int main()
{
int n;
fin >> n; // citim prima oara numarul n
int ultimul_numar = 0, aparitii = 0; // memoram mereu ultimul numar citit in aceasta variabila
int numar;
while(fin >> numar) // citim pana la capatul fisierului
{
for(int i = ultimul_numar + 1; i < numar; i++) // afisam toate numerele de la ultimul numar citit pana la cel curent
{
afisari++;
cout << i << " ";
}
ultimul_numar = numar;
}
for(int i = numar + 1; i <= n; i++) // afisam numerele intre ultimul numar din fisier si pana la numarul nostru n
{
afisari++;
cout << i << " ";
}
if(afisari == 0)
cout << "Nu exista";
return 0;
}
