Data: iulie 2017
Profil: Matematica-Informatica
Limbaj: C++
Subiectul I.
1. Indicaţi o expresie C/C++ care are valoarea 1 dacă şi numai dacă numărul natural memorat în variabila întreagă x are exact o cifră.
a. x%10==x – Corect: Deoarece x % 10 extrage ultima cifra dintr-un numar.
b. x/10==x
c. x%10==x/10
d. (x%10)/10==x
2. Se consideră algoritmul alăturat, reprezentat în pseudocod.
citeste n pentru i <- 1, n executa --- pentru j <- 1, n executa ------ daca i = j sau i + j = n + 1 atunci --------- scrie '#' ------ altfel --------- scrie j
a. Scrieţi ce se afișează dacă se citește numărul 3.
n = 3 i = 1 j = 1 scrie # i = 1 j = 2 scrie 2 i = 1 j = 3 scrie # i = 2 j = 1 scrie 1 i = 2 j = 2 scrie # i = 2 j = 3 scrie 3 i = 3 j = 1 scrie # i = 3 j = 2 scrie 2 i = 3 j = 3 scrie #
Rezultatul final fiind: #2#1#3#2#
b. Scrieți un număr care poate fi citit, astfel încât, în urma executării algoritmului numărul de simboluri # afișate să fie 100.
Deoarece pentru n = 3 avem aproximativ 5 simboluri # putem trage urmatoarele concluzii. Numarul de # afisate este de doua ori mai mic decat n. Deoarece avem nevoie de 100 simblouri “#” n-ul nostru va fi 50.
c. Scrieţi în pseudocod un algoritm echivalent cu cel dat, înlocuind adecvat prima structură pentru…execută cu o structură repetitivă cu test inițial.
citeste n i <- 1 cat timp i <= n executa --- pentru j <- 1, n executa ------ daca i = j sau i + j = n + 1 atunci --------- scrie '#' ------ altfel --------- scrie j --- i <- i + 1
d. Scrieţi programul C/C++ corespunzător algoritmului dat.
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(i == j || i + j == n + 1)
cout << "#";
else
cout << j;
}
}
}
Subiectul II.
1. Indicați șirul afișat pe ecran în urma executării instrucțiunii următoare:
cout<<strstr(”veni,vidi,vici”,”vi”);
Cum am mai discutat despre pointeri si in rezolvarea altor subiecte, acesta se pozitioneaza in momentul in care a gasit subsirul.
In cazul nostru avem sirul: veni,vidi,vici si subsirul vi.
Acesta gaseste prima oara sirul “vi” in subsirul “vidi, vici”. Asadar raspunsul este b) vidi,vici.
2. Se consideră un graf neorientat cu 7 noduri şi 21 de muchii. Indicaţi numărul minim de muchii care pot fi eliminate, astfel încât graful parţial obţinut să aibă două componente conexe, cu cel puţin două noduri fiecare.
Facem urmatoarea observatie: un graf neorientat cu 7 noduri si 21 de muchii este un graf complet (adica pot ajunge direct dintr-un nod in altul).
Fiecare nod este legat prin exact 6 muchii cu celalalte noduri. Noi trebuie sa obtinem inca o componenta conexa, deci avem nevoie de cel putin doua noduri. Pentru a obtine doua noduri izolate trebuie sa eliminam 5 munchii de la primul nod si 5 muchii de la cel de-al doilea nod. Cea de a 6-a muchie fiind muchia ce leaga cele doua noduri.
Asadar, eliminam 10 muchii in total.
3. În declararea alăturată, variabila x memorează numele unui elev şi cele două medii semestriale obținute de acesta la informatică. Scrieţi o secvență de instrucțiuni C/C++ în urma executării căreia să se afişeze pe ecran prima literă a numelui și, pe linia următoare, media anuală la informatică a acestui elev.
struct elev
{
char nume[30];
int media1, media2;
} x;
Exemplu: dacă elevul are numele Popescu, iar cele două medii sunt sunt 9, respectiv 10, se afișează pe ecran
P
9.5
cout << x.nume[0] << "\n"; cout << (float) ((x.media1 + x.media2) / 2);
4. Într-un graf orientat două circuite sunt distincte dacă ele diferă prin cel puţin un arc. Scrieți matricea de adiacență a unui graf orientat cu 5 vârfuri şi 6 arce, care are două circuite elementare distincte.
Luam exemplul de mai sus. Avem 5 varfuri cu 6 arce intr-un graf orientat. Vom scrie matricea acesteia de adiacenta. Voi numerota nodurile in sensul acelor de ceasornic.
Tinand cont de exemplul de mai sus, avem urmatoarea matrice:
5. Scrieţi un program C/C++ care citeşte de la tastatură două numere naturale din intervalul [3,50], n şi m, și elementele unui tablou bidimensional cu n linii şi m coloane, numere naturale din intervalul [0,104]. Programul modifică în memorie tabloul dat, atribuind valoarea elementului aflat pe ultima linie și pe ultima coloană a tabloului fiecărui element aflat pe conturul acestuia (pe prima linie, ultima linie, prima coloană, ultima coloană), apoi afişează pe ecran tabloul modificat, câte o linie a tabloului pe câte o linie a ecranului, elementele fiecărei linii fiind separate prin câte un spaţiu.
Exemplu: dacă n=5, m=4 și tabloul este
#include <iostream>
using namespace std;
int main()
{
unsigned int n, m;
unsigned int matrice[50][50];
cin >> n >> m;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cin >> matrice[i][j];
unsigned int ultimulElement = matrice[n - 1][m - 1];
for(int i = 0; i < n; i++)
{
matrice[0][i] = ultimulElement;
matrice[n - 1][i] = ultimulElement;
}
for(int i = 0; i < n; i++)
{
matrice[i][0] = ultimulElement;
matrice[i][m - 1] = ultimulElement;
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
cout << matrice[i][j] << " ";
}
cout << "\n";
}
return 0;
}
Subiectul III.
1. Utilizând metoda backtracking se generează, în ordine strict crescătoare, toate numerele de trei cifre din mulţimea {1, 2, 5, 7, 8}, numere cu proprietatea că au cel mult două cifre impare. Primele şapte numere generate sunt, în această ordine: 112, 118, 121, 122, 125, 127, 128. Al optulea număr generat este:
b. 152 – o sa urmeze un tutorial special in care o sa explic cum functioneaza backtracking-ul.
2. Subprogramul f este definit alăturat. Scrieţi valorile f(3,9) şi f(1,1000).
int f(int x,int y)
{
if(x*5>y/5)
return x;
return f(x*5,y/5);
}
Pentru f(3, 9) se va afisa 3 – deoarece 15 > 1.
Pentru f(1, 1000) vom avea rezultatul (5 > 200) – care este fals, deci executam f(5, 200).
Vom avea rezultatul (25 > 40) – care de asemenea este fals, deci vom executa f(25, 40).
Ultima comparatie va fi (125 > 8) – care este adevarata, unde se va returna 25.
3. Subprogramul duplicare are un singur parametru, n, prin care primește un număr natural (n ∈ [1,104)). Subprogramul furnizează, prin același parametru, numărul obţinut din n prin inserarea, după fiecare cifră pară din scrierea lui, a unei cifre egale cu jumătate din aceasta. Scrieți definiția completă a subprogramului.
Exemplu: dacă n=2380 după apel, n=2138400, iar dacă n=35 după apel, n=35.
void duplicare(unsigned int &nr)
{
unsigned int vector[10];
unsigned int total = 0;
unsigned int invers = 0;
unsigned int c;
while(nr)
{
c = nr % 10;
if(c % 2 == 0)
vector[total++] = c / 2;
vector[total++] = c;
nr = nr / 10;
}
for(int i = total - 1; i >= 0; i--)
nr = nr * 10 + vector[i];
}
Ideea este urmatoarea: descompunem numarul in cifre si il plasam intr-un vector. Daca cifra este para, se mai insereaza o cifra: jumatatea acesteia.
Am apelat la un vector deoarece daca numarul are cifre de 0 la final, nu putem sa construim inversul – deoarece un numar nu poate incepe cu 0.
Mai departe, parcurgem vectorul invers si construim numarul nostru final.
4. Numim secvență pară într-un șir o succesiune de termeni ai șirului cu proprietatea că sunt numere pare și că se află pe poziții consecutive în șir; orice secvență are cel puțin doi termeni și este maximală în raport cu proprietatea precizată (dacă i se adaugă un alt termen, secvența își pierde această proprietate). Lungimea secvenței este egală cu numărul termenilor săi. Fişierul bac.txt conţine un şir de cel mult 106 numere naturale din intervalul [0,109]. Numerele din şir sunt separate prin câte un spaţiu. Se cere să se afişeze pe ecran numărul de secvențe pare de lungime maximă din șir. Proiectați un algoritm eficient din punctul de vedere al spațiului de memorie utilizat şi al timpului de executare.
Exemplu: dacă fişierul bac.txt conţine valorile 1 2 3 4 6 10 2 8 5 7 9 4 6 10 121 20 4 11 10 2 5 2 6 8 10 16 se afişează pe ecran numărul 2.
a) Descrieţi în limbaj natural algoritmul proiectat, justificând eficienţa acestuia.
Algoritmul este urmatorul: de fiecare cand citim un numar, il analizam. Daca numarul curent si numarul precedent sunt amandoua pare, crestem lungimea sirului curent. In caz contrar, resetam lungimea sirului, deoarece nu s-a mai indeplinit conditia.
Mai apoi, analizam daca lungimea sirului este maxima, iar daca este maxima, incrementam numarul de aparitii.
Algoritmul are complexitatea liniara O(n) – unde n este numarul total de numere din fisierul bac.txt. Ca si spatiu, complexitatea este O(1) deoarece folosim doar 4 variabile auxiliare indiferent de numarul de elemente din fisier.
b) Scrieţi programul C/C++ corespunzător algoritmului descris.
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("bac.txt");
int main()
{
unsigned int lungimeSir = 0;
unsigned int lungimeSirMaxim = 0;
unsigned int aparitii = 0;
unsigned int numar;
unsigned int numarprecedent = -1;
while(fin >> numar)
{
if(numar % 2 == 0 && numarprecedent % 2 == 0)
lungimeSir++;
else
lungimeSir = 0;
numarprecedent = numar;
if(lungimeSir > lungimeSirMaxim)
{
lungimeSirMaxim = lungimeSir;
aparitii = 0;
}
if(lungimeSir == lungimeSirMaxim)
aparitii++;
}
cout << aparitii;
return 0;
}
