Pregătire cu un profesor

UNIVERSITATEA BABEŞ-BOLYAI
FACULTATEA DE MATEMATICĂ ŞI INFORMATICĂ
Concursul de admitere (nivel licență) - iulie 2017
Proba scrisă la Informatică
VARIANTA II
În atenția concurenților:
1. Rezolvările se vor scrie în pseudocod sau într-un limbaj de programare (Pascal/C/C++).
2. Primul criteriu în evaluarea rezolvărilor va fi corectitudinea algoritmului, iar apoi performanța din punct de
vedere al timpului de executare și al spațiului de memorie utilizat.
3. Este obligatorie descrierea și justificarea (sub) algoritmilor înaintea rezolvărilor. Se vor scrie, de asemenea,
comentarii pentru a uşura înţelegerea detaliilor tehnice ale soluției date, a semnificaţiei identificatorilor, a
structurilor de date folosite etc. Neîndeplinirea acestor cerințe duce la pierderea a 10% din punctajul aferent
subiectului.
4. Nu se vor folosi funcții sau biblioteci predefinite (de exemplu: STL, funcţii predefinite pe şiruri de caractere).
Subiectul I (35 puncte)
1. Degustare de ciocolată (20 puncte)
O companie de publicitate face reclamă la un nou sortiment de ciocolată și intenționează să distribuie mostre de
ciocolată la n (10 ≤ n ≤ 10 000 000) copii care sunt așezați într-un cerc. Angajații companiei își dau seama că
distribuirea de mostre tuturor copiilor ar costa foarte mult. În consecință, decid să distribuie mostre fiecărui al k-
lea (0 < k < n) copil din cei n, numărând copiii din k în k (atunci când numărătoarea ajunge la ultimul copil, ea
continuă cu primul copil și așa mai departe). În numărătoare se vor considera toți copiii, fie că au primit sau nu
ciocolată. Numărătoarea se oprește atunci când o ciocolată ar trebui distribuită unui copil care deja a primit.
Scrieți un subalgoritm care determină numărul copiilor (nr) care nu primesc mostre de ciocolată. Parametrii de
intrare sunt numerele naturale n și k, iar parametrul de ieșire va fi numărul natural nr.
Exemplu 1: dacă n = 12 și k = 9, atunci nr = 8 (primul, al 2-lea, al 4-lea, al 5-lea, al 7-lea, al 8-lea, al 10-lea, al 11-
lea copil nu primesc ciocolată).
Exemplu 2: dacă n = 15 și k = 7, atunci nr = 0 (toți copiii primesc ciocolată).
2. Reducere (15 puncte)
Se consideră șirurile a și b cu n (1 ≤ n ≤ 10 000), respectiv m (1 ≤ m ≤ 10 000) elemente numere naturale
mai mici decât 30 000. O subsecvență a unui șir este formată din elemente ale șirului aflate pe poziţii
consecutive în șirul dat. Spunem că șirul a „se poate reduce” la șirul b dacă există o împărţire a șirului a în
subsecvenţe disjuncte astfel încât:
 prin concatenare, în ordine, a tuturor subsecvențelor se obține șirul a;
 prin înlocuiri, în ordine, a tuturor subsecvenţelor cu suma elementelor lor se obţin, în ordine,
elementele șirului b.
Scrieți un subalgoritm care stabilește dacă șirul a se poate reduce sau nu la șirul b. În caz afirmativ, identificați
elementul din șirul b (și poziția k a acestui element) obținut prin însumarea valorilor din cea mai lungă
subsecvență a șirului a. Subalgoritmul are ca parametri de intrare cele două șiruri a și b, precum și lungimile lor
n și, respectiv, m. Parametrii de ieșire vor fi răspuns, k și nrMax, unde: răspuns va avea valoarea adevărat
dacă răspunsul la întrebare este afirmativ, respectiv fals, în caz contrar; k reprezintă indicele elementului din
șirul b care se obține însumând elementele din subsecvența de lungime maximă (nrMax). Dacă există mai multe
subsecvențe de lungime maximă, se va considera prima dintre ele. Dacă șirul a nu se poate reduce la șirul b, k și
nrMax vor avea fiecare valoarea -1.
Exemplul 1: dacă n = 12, a = (6, 3, 4, 1, 6, 4, 6, 1, 7, 1, 8, 7), m = 4 și b = (13, 7, 18, 16), atunci răspuns =
adevărat, deoarece 6 + 3 + 4 = 13, 1 + 6 = 7, 4 + 6 + 1 + 7 = 18, 1 + 8 + 7 = 16. Astfel, k = 3 și nrMax = 4.
Exemplul 2: dacă n = 17, a = (10, 12, 11, 2, 2, 3, 2, 3, 13, 3, 41, 5, 4, 5, 6, 5, 2), m = 6 și b = (33, 4, 15, 41, 25,
2), atunci răspuns = fals, deoarece 10 + 12 + 11 = 33, 2 + 2 = 4, dar 3 + 2 + 3 < 15, iar 3 + 2 + 3 + 13 > 15, deci
valoarea b3 = 15 nu se poate obține însumând elemente consecutive din șirul a.
Notă: În exemplele date șirurile sunt indexate începând cu 1.

Subiect · pagina 2

Subiectul II (15 puncte)
Se dǎ urmǎtorul subalgoritm unde n este parametru de intrare, iar p și i sunt parametri de ieșire (n, p, i - numere
naturale, 1 ≤ n ≤ 1 000 000, 0 ≤ p ≤ 1 000 000, 0 ≤ i ≤ 1 000 000):
Subalgoritm f(n, p, i):
Dacă n ≤ 9 atunci
Dacă n mod 2 = 0 atunci
{ n mod 2 calculeazǎ restul ȋmpǎrțirii lui n la 2}
p  n
i  0
altfel
p  0
i  n
SfDacă
altfel
f(n div 10, p, i)
{ n div 10 calculeazǎ câtul ȋmpǎrțirii lui n la 10}
Dacă n mod 2 = 0 atunci
p  p * 10 + n mod 10
altfel
i  i * 10 + n mod 10
SfDacă
sfDacă
SfSubalgoritm
a. Enunțați problema pe care o rezolvă
subalgoritmul dat.
b. Ce valori vor avea p și i după apelul
f(205 609, p, i)?
c. Scrieți o variantă iterativǎ (ne-recursi-
vă) a subalgoritmului dat respectând
antetul subalgoritmului din varianta
recursivă.
Subiectul III (40 puncte)
Prelucrări imagine
O imagine alb-negru este reprezentată codificat printr-un tablou bidimensional cu valori 0 (pixel alb) și 1
(pixel negru). Asupra imaginii se pot efectua transformări precum:
 Inversarea (I), adică valorile 0 se transformă în 1 și valorile 1 se transformă în 0;
 Rotirea cu 90 de grade în sensul acelor de ceasornic (R);
 Zoom (Z), adică fiecare pixel va fi expandat în 4 pixeli identici cu cel inițial.
O secvență de transformări se definește ca o succesiune de litere I, R și Z (în orice ordine).
Scrieți un program care, fiind dat un tablou bidimensional imagine având m linii și m coloane (m - număr
natural, 2 ≤ m ≤ 10) și o secvență s care conține cel mult cinci transformări, aplică aceste transformări și
afișează imaginea obținută în urma transformărilor.
Exemplu: dacă m = 3, imagine = și s = (R, I, R, Z), atunci rezultatul va fi .
Imaginile intermediare (după aplicarea succesivă a transformărilor R, I, R, Z) sunt:
, , , .
În rezolvare folosiți subprograme pentru:
a. citirea datelor de intrare de la tastatură (datele de intrare se consideră corecte în raport cu cerințele);
b. inversarea unei imagini;
c. rotirea cu 90 de grade a unei imagini;
d. aplicarea operației de zoom pe o imagine;
e. afișarea pe ecran a unei imagini.
Notă:
1. Toate subiectele sunt obligatorii.
2. Rezolvările trebuie scrise detaliat pe foile de examen (ciornele nu se iau în considerare).
3. Se acordă 10 puncte din oficiu.
4. Timpul efectiv de lucru este de 3 ore.1
1
1
1
1

Subiect · pagina 3

3
BAREM – VARIANTA II
OFICIU............................................................................................................................................... 10 puncte
SUBIECTUL I ................................................................................................................................... 35 puncte
1. 1. Degustare de ciocolată .............................................................................................................. 20 puncte
 V1: determinarea corectă a valorii nr (cu formula nr = n – n/cmmdc(n, k) ..................... 20 puncte
 V2: determinarea corectă a valorii nr (simulare, listă circulară) ...................................... 10 puncte
2. Reducere ........................................................................................................................................ 15 puncte
 parcurgerea în paralel a celor două șiruri ..................................................................................... 4 puncte
 calculul sumelor parțiale cu elemente din șirul a și verificarea egalității
cu elementul curent din șirul b ................................................................................................. 4 puncte
 identificarea subsecvenței (din șirul a) de lungime maximă ........................................................ 4 puncte
 test dacă suma parțială curentă depășește elementul curent din b .................................................. 1 punct
 test dacă s-a terminat parcurgerea elementelor din șirul a și suma parțială curentă
depășește elementul curent din șirul b ........................................................................................ 1 punct
 test dacă, inițial, șirul b are mai multe elemente decât șirul a ........................................................ 1 punct
SUBIECTUL II .................................................................................................................................. 15 puncte
Numǎrul format din cifrele pare și numărul format din cifrele impare ale numărului n
Cerința a.
 enunț problemă ............................................................................................................................. 5 puncte
Cerința b.
 rezultat calculat corect (p = 2060, i = 59)..................................................................................... 3 puncte
Cerința c.
 algoritm ....................................................................................................................................... 7 puncte
SUBIECTUL III Prelucrări imagine ............................................................................................... 40 puncte
Subprograme:
a. Citirea datelor de intrare de la tastatură........................................................................................ 4 puncte
 citirea imaginii .............................................................................................................. 2 puncte
 citirea secvenței de transformări ................................................................................... 2 puncte
b. inversarea unei imagini ................................................................................................................ 4 puncte
c. rotirea cu 90 de grade a unei imagini ........................................................................................... 8 puncte
d. aplicarea operației de zoom pe o imagine .................................................................................... 8 puncte
e. afișarea unei imagini .................................................................................................................... 2 puncte
Program principal ........................................................................................................................ 3 puncte
 determinarea rezultaului ............................................................................................................... 3 puncte
 comunicare prin parametri:
(signatura subalgorimilor și apelul corect) ............................................................................. 5 puncte
 lizibilitate:
• comentarii ....................................................................................................................... 1 punct
• indentare ......................................................................................................................... 1 punct
• denumiri sugestive .......................................................................................................... 1 punct

Subiect · pagina 4

O solutie posibila:
#include <iostream>
using namespace std;
/*************************************************************************************
Subiectul I.1. Degustare de ciocolata
*************************************************************************************/
//calculeaza si returneaza cmmdc a 2 numere naturale a si b
int cmmdc(int a, int b){
if ((a == b) && (a == 0))
return 1;
if (a * b == 0)
return a + b;
while (b != 0){
int c = b;
b = a % b;
a = c;
} //while
return a;
}
//determina si returneaza nr de copii care nu primesc ciocolata dintre cei n copii
//numarand din k in k. Putem să consideram numaratoarea in cerc ca o numaratoare
//liniara in mai multe siruri mici, fiecare cu n copii, obtinând un sir mare cu
//p copii (p fiind multiplu de n). Numaratoarea se termina atunci cand al n-lea
//copil (dintr-un sir mic) primeste ciocolata (astfel, urmatorul copil care ar
//trebui sa primeasca ciocolata va fi un al k-lea copil din urmatorul sir mic),
//deci p trebuie sa fie si multiplu de k. Asadar, p = cmmmc(n, k). Dintre cei
//p copii, au primit ciocolată exct p / k copii, deci copiii fara ciocolata sunt
//in numar de
//nr = n - p/k = n - cmmmc(n,k)/k = n - (n*k/cmmdc(n,k))/k = n - n/cmmdc(n,k)
int degustareCiocolata(int n, int k){
return n - n / cmmdc(n, k);
}
/*************************************************************************************
Subiectul I.2. Reducere
*************************************************************************************/
//verifica daca sirul a cu n numere naturale se poate reduce la sirul b cu m numere
//naturale si determina pozitia k din sirul b care retine elementul obtinut prin
//insumarea elementelor din cea mai lunga subsecventa (de lungime nrMax) din sirul a
bool seReduce(int n, int a[], int m, int b[], int &k, int &nrMax){
if (n < m)
return false; // sirul a are mai putine elemente decat sirul b
int i = 0; // index in sirul a
int j = 0; // index in sirul b
int sum = 0; // se va incerca obtinerea, pe rând, a elementelor din sirul b
// ca suma de elemente consecutive din sirul a
int nrInsumate = 0; // numarul elementelor din subsecventa curenta
nrMax = 0; // numarul maxim de elemente din subsecventele sirului a
// ale caror suma este egala cu un element din sirul b
while ((j < m) && (i < n)){ // cat timp nu s-a terminat niciunul dintre siruri
sum += a[i];
nrInsumate++;
if (sum == b[j]){
if (nrInsumate > nrMax){
nrMax = nrInsumate; // daca este cazul, se actualizeaza nrMax si k
k = j;
}
nrInsumate = 0; // eventual, va urma o subsecventa noua
sum = 0;
j++; i++;
} //if
else{
if (sum < b[j])
i++;
else
return false;
} //else
} //while

Subiect · pagina 5

5
if ((i < n) || (j < m)) // daca cel putin unul dintre cele doua siruri nu s-a epuizat
return false;
return true;
}
/*************************************************************************************
Subiectul II. Produsul a doua numere
*************************************************************************************/
//Subiectul II.a Numǎrul format din cifrele pare (p) și numărul format din cifrele
//impare (i) ale numărului n considerate de la stanga la dreapta
//Subiectul II.b f(205 609, p, i) => p = 2060, i = 59
//Subiectul II.c
void cifreIterativ(int n, int & pare, int & impare){
pare = 0;
impare = 0;
int putereImpare = 1; //putere lui 10 pentru formarea nr cu cifre impare
int puterePare = 1; //putere lui 10 pentru formarea nr cu cifre pare
while (n){
if (n & 1){ //daca n este impar
impare = impare + putereImpare * (n % 10);
n /= 10;
putereImpare *= 10;
} //if
else{
pare = pare + puterePare * (n % 10);
n /= 10;
puterePare *= 10;
} //else
} //while
}
/*************************************************************************************
Subiectul III Prelucrare imagine
*************************************************************************************/
const int DIMMAX = 320;
//inverseaza valorile unei matrici binare im cu m linii si m coloane
void inversare(int m, int im[][DIMMAX]){
for (int i = 0; i < m; i++){
for (int j = 0; j < m; j++){
im[i][j] = 1 - im[i][j];
} //for j
} //for i
}
//roteste o matrice im cu m linii si m coloane
void rotire(int m, int im[][DIMMAX]){
int copie[DIMMAX][DIMMAX];
for (int i = 0; i < m; i++){
for (int j = 0; j < m; j++){
copie[i][j] = im[i][j];
} //for j
} //for i
for (int i = 0; i < m; i++){
for (int j = 0; j < m; j++){
im[j][m - i - 1] = copie[i][j];
} //for j
} //for i
}
//mareste o matrice im cu m linii si m coloane
void zoom(int &m, int im[][DIMMAX]){
int imNoua[DIMMAX][DIMMAX];
int iNou = 0;
int jNou = 0;

Subiect · pagina 6

for (int i = 0; i < m; i++){
jNou = 0;
for (int j = 0; j < m; j++){
imNoua[iNou][jNou] = im[i][j];
imNoua[iNou][jNou + 1] = im[i][j];
imNoua[iNou + 1][jNou++] = im[i][j];
imNoua[iNou + 1][jNou++] = im[i][j];
} //for j
iNou += 2;
} //for i
m *= 2;
for (int i = 0; i < m; i++){
for (int j = 0; j < m; j++){
im[i][j] = imNoua[i][j];
} //for j
} //for i
}
//afiseaza o matrice im cu m linii si m coloane
void afisare(int m, int im[][DIMMAX]){
for (int i = 0; i < m; i++){
for (int j = 0; j < m; j++){
cout << im[i][j] << " ";
} //for j
cout << endl;
} //for i
}
//aplica o secventa s de k transformari asupra unei matrici im cu
//m linii si m coloane
void transformari(int k, char s[], int &m, int im[][DIMMAX]){
for (int i = 0; i < k; i++){
if (s[i] == 'I')
inversare(m, im);
if (s[i] == 'R')
rotire(m, im);
if (s[i] == 'Z')
zoom(m, im);
} //for i
}
//citeste o matrice im cu m linii si m coloane
void citireImagine(int &m, int im[][DIMMAX]){
cout << "m = "; cin >> m;
for (int i = 0; i < m; i++){
for (int j = 0; j < m; j++){
cin >> im[i][j];
} //for j
} //for i
}
//citeste o secventa s de k transformari
void citireTransformari(int &k, char s[]){
cout << " k = "; cin >> k;
for (int i = 0; i < k; i++)
cin >> s[i];
}
//programul principal
int main(){
int m = 0;
int im[DIMMAX][DIMMAX];
citireImagine(m, im);
int k = 0; char s[5];
citireTransformari(k, s);
transformari(k, s, m, im);
afisare(m, im);
return 0;
}

Deschide documentul original

Continuă pregătirea

Vezi arhiva completă

Examen de admitere · 2017Matematică · Sesiunea iulieDeschide fișa Concurs de pregătire · 2017Informatică · Concursul Mate-Info UBBDeschide fișa Concurs de pregătire · 2017Matematică · Concursul Mate-Info UBBDeschide fișa Examen de admitere · 2018Informatică · Sesiunea iulieDeschide fișa Examen de admitere · 2018Matematică · Sesiunea iulieDeschide fișa Examen de admitere · 2018Informatică · Sesiunea septembrieDeschide fișa

Răspunsuri directe

Ce trebuie să știi despre acest subiect?

Ce document de admitere este acesta?

Pagina prezintă examen de admitere din 2017 pentru Informatică, la Facultatea de Matematică și Informatică. Documentul este etichetat după instituție, facultate, program și tipul probei folosind inventarul public verificat. Consultă metodologia actuală a instituției pentru condițiile examenului viitor.

Există și barem sau răspunsuri pentru acest subiect?

Nu există un barem public asociat în inventarul verificat pentru acest document. ProfesorBun nu generează și nu inventează răspunsuri oficiale. Poți folosi subiectul pentru antrenament, dar corectarea trebuie făcută cu metodologia instituției, cu materiale oficiale suplimentare sau împreună cu un profesor.

Cum folosesc acest subiect în pregătirea pentru admitere?

Rezolvă documentul fără ajutor și respectă timpul prevăzut de metodologia examenului. Corectează cu baremul disponibil, marchează capitolele unde ai pierdut puncte și repetă exerciții similare. Compară apoi cu alte probe din aceeași facultate și confirmă programa curentă pe site-ul oficial al instituției.

Pregătire cu un profesor

Subiect și barem

Examen de admitere · Informatică · 2017

Despre acest subiect

Subiectul în format text

Subiect · pagina 1