Despre acest subiect
primăvară · Concursul Mate-Info UBB
Sursa documentelor: FMI UBB – subiecte din anii precedenți. Pentru acest subiect nu este disponibil un barem public.
Se încarcă profesorii disponibili…
Subiect și barem
Se deschide documentul PDF… Deschide PDF
Acest subiect nu are un barem public asociat.
Concurs de pregătire · Informatică · 2017
Facultatea de Matematică și Informatică · UBB
Înapoi la arhivăSubiectul în format text
Text extras automat din documentul original. Pentru formule, tabele, imagini și așezarea răspunsurilor, verifică întotdeauna PDF-ul.
Subiect · 6 pagini
Subiect · pagina 1
1 UNIVERSITATEA BABEŞ-BOLYAI FACULTATEA DE MATEMATICĂ ŞI INFORMATICĂ Concurs Mate-Info - 1 aprilie 2017 Proba scrisă la Informatică VARIANTA I Î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 acestei 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. Rază (20 puncte) Avem la dispoziție un chenar dreptunghiular format din oglinzi. O rază de lumină pornește din colțul stânga jos al dreptunghiului sub un unghi de 45o față de latura de jos a dreptunghiului și lovește latura de sus sau latura din dreapta. Aici se reflectă (pornește spre o altă latură tot sub un unghi de 45o față de latura de care s-a lovit). Își continuă drumul până când ajunge într-un colț al dreptunghiului. Scrieți un subalgoritm care calculează de câte ori (nrSchimb) raza își schimbă direcția de mers până când se oprește într-un colț. Punctul de pornire nu se numără. Parametri de intrare ai subalgoritmului sunt lungimea (1 < a < 10 000) și lățimea (1 < b < 10 000) dreptunghiului, iar nrSchimb va fi parametru de ieșire. Exemplu 1: dacă a = 8 și b = 3, atunci nrSchimb = 9. Exemplu 2: dacă a = 8 și b = 4, atunci nrSchimb = 1. 2. Numere cu „forță” (15 puncte) Un număr natural nenul nr are forța k dacă în reprezentarea sa binară există exact k cifre egale cu 1. De exemplu, numărul 23 are forța 4 (în reprezentarea sa binară există 4 cifre egale cu 1). Fiind dat un șir de numere, numim grup de forță k al său un subșir de elemente din șirul dat care au forța k, elementele fiind considerate în ordinea din șirul inițial. De exemplu, pentru șirul s = (7, 12, 3, 13, 24, 19), grupul de forță k = 2 este (12, 3, 24). Scrieți un subalgoritm care determină toate grupurile de forță care se pot forma cu elementele șirului x. Parametrii de intrare sunt șirul de numere naturale nenule x cu elemente distincte mai mici decât 30 000 și lungimea n a șirului (1 < n < 100). Parametrii de ieșire vor fi nrGr (numărul grupurilor) și grupuri (grupurile formate, ordonate crescător după forța lor). Exemplu: dacă n = 6 și x = (12, 3, 24, 16, 15, 32), atunci nrGr = 3 și grupuri va fi (16, 32), (12, 3, 24), (15). Subiectul II (15 puncte) Se dă următorul subalgoritm care are ca parametri de intrare trei numere naturale a, b și nr, fiecare fiind mai mic decât 10 000. Subalgoritm f(a, b, nr): k 0 CâtTimp b < nr execută k k + 1 b a + b a b - a SfCâtTimp returnează k SfSubalgoritm 6 1 9 4 7 3 0 8 5 2
Subiect · pagina 2
2 a. Enunțați problema pe care o rezolvă subalgoritmul dat dacă este apelat cu a = 1 și b = 0. b. Ce valoare returnează apelul f(1,0,10)? c. Scrieți o variantă recursivă a subalgoritmului dat, respectând antetul subalgoritmului din varianta iterativă (ne-recursivă). Subiectul III (40 puncte) Prefix Cifra de control a unui număr natural se determină calculând suma cifrelor numărului, apoi suma cifrelor sumei și așa mai departe până când suma obținută reprezintă un număr cu o singură cifră. De exemplu, cifra de control a numărului 182 este 2 (1 + 8 + 2 = 11, 1 + 1 = 2). Un număr p format din exact k cifre este prefix al unui număr q cu cel puțin k cifre dacă numărul format din primele k cifre ale numărului q (parcurse de la stânga la dreapta) este egal cu p. De exemplu, 17 este prefix al lui 174, iar 1713 este prefix al lui 1 713 242. Se consideră un număr nr natural (0 < nr ≤ 30 000) și o matrice (un tablou bidimensional) A cu m linii și n coloane (0 < m ≤ 100, 0 < n ≤ 100), avȃnd ca elemente numere naturale mai mici decât 30 000. Scrieți un program care determină și afișează cel mai lung prefix al numărului nr care se poate construi folosind cifrele de control corespunzătoare elementelor din matricea dată. O astfel de cifră de control poate fi folosită de oricâte ori în construirea prefixului. Dacă nu se poate construi un prefix, programul va afișa mesajul „nu există prefix”. Exemplu: dacă avem nr = 12319, m = 3 și n = 4 și matricea , cel mai lung prefix este 1231, cifrele de control fiind: Element din matrice 182 12 274 22 1 98 56 5 301 51 94 Cifră control 2 3 4 4 1 8 2 5 4 6 4 În rezolvare folosiți subprograme pentru: a. citirea datelor de intrare de la tastatură; b. determinarea cifrei de control asociată unui număr; c. determinarea celui mai lung prefix; d. afișarea pe ecran a celui mai lung prefix sau a mesajului corespunzător dacă acesta nu a putut fi găsit. 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.
Subiect · pagina 3
3 BAREM – VARIANTA I OFICIU............................................................................................................................................... 10 puncte SUBIECTUL I ................................................................................................................................... 35 puncte 1. Rază ................................................................................................................................................ 20 puncte Varianta 1: determinarea corectă a valorii nrSchimb bazată pe utilizarea cmmdc(a, b) ....... 20 puncte cmmdc(a, b) (sau cmmmc(a,b)).............................................................................................. 5 puncte calculul valorii nrSchimb .................................................................................................... 15 puncte Varianta 2: determinarea corectă a valorii nrSchimb cu alt algoritm corect (simulare) ....... 15 puncte 2. Numere cu „forță” ......................................................................................................................... 15 puncte stabilirea forței unui număr .................................................................................................... 5 puncte determinarea numărului grupurilor de elemente cu aceeași forță (nrGr) și a componenței lor (grupuri) ................................................................................................ 10 puncte SUBIECTUL II .................................................................................................................................. 15 puncte Numărul numerelor Fibonacci mai mici decât numărul nr dat Cerința a. enunț problemă ...................................................................................................................... 5 puncte Cerința b. rezultat calculat corect (7)...................................................................................................... 3 puncte Cerința c. algoritm ................................................................................................................................. 3 puncte autoapel corect ....................................................................................................................... 2 puncte condiție de oprire din recursivitate ........................................................................................ 2 puncte SUBIECTUL III ................................................................................................................................ 40 puncte Prefix Subprograme: citirea datelor de intrare ......................................................................................................... 3 puncte determinarea cifrei de control asociată unui număr ............................................................... 5 puncte determinarea celui mai lung prefix ...................................................................................... 15 puncte afișarea celui mai lung prefix/mesaj ...................................................................................... 3 puncte Program principal: ............................................................................................................................... 3 puncte comunicare prin parametri: (signatura subalgorimilor și apelul corect) .............................................................................. 5 puncte lizibilitate: comentarii ................................................................................................................. 2 puncte indentare ................................................................................................................... 2 puncte denumiri sugestive .................................................................................................... 2 puncte
Subiect · pagina 4
4
UNIVERSITATEA BABEŞ-BOLYAI
FACULTATEA DE MATEMATICĂ ŞI INFORMATICĂ
Concurs Mate-Info - 1 aprilie 2017
Proba scrisă la Informatică
VARIANTA I
// SUBIECTUL I.1
//determina cmmdc a 2 numere a si b
int cmmdc(int a, int b){
if ((a == b) && (a == 0)){
return 1;
}
if (a * b == 0){
return a + b;
}
while (a != b){
if (a > b)
a -= b;
else
b -= a;
}
return a;
}
// calcularea numărului de schimbări de direcție a razei
int raza(int a, int b){
int nrSchimb;
int d = cmmdc(a, b);
nrSchimb = b / d + a / d - 2;
return nrSchimb;
}
// SUBIECTUL I.2
const int MAXSIZE = 100;
const int MAXCIF = 32;
// calcularea fortei unui numar
int calculForta(int nr){
int forta = 0;
do{
nr &= nr - 1; // „și” logic intre nr si nr-1
forta++;
} while (nr);
return forta;
}
//gruparea numerelor pe clase de forta
//grupurile se vor memora intr-un tablou bidimensional
//fiecare linie i corespunde grupului de forta i
//primul element de pe linia i reprezinta dimensiunea grupului de forta i
//urmatoarele elemente sunt numerele din sirul x cu forta i
void forte(int n, int x[], int &nrGr, int grupuri[][MAXSIZE]){
for (int i = 1; i < MAXCIF; i++) // inițializarea tabloului grupuri
grupuri[i][0] = 0;
nrGr = 0;
for (int i = 0; i < n; i++){
int forta = calculForta(x[i]); // determinarea forței elementului x[i]
if (grupuri[forta][0] == 0)
nrGr++;
int pos = grupuri[forta][0] + 1;
grupuri[forta][pos] = x[i];
grupuri[forta][0]++;
}
}Subiect · pagina 5
5
// SUBIECTUL II
int fRec(int a, int b, int nr){
if (b < nr)
return fRec(b, a + b, nr) + 1; // (*)
else
return 0;
}
// SUBIECTUL III
const int MAX = 100;
const int NRMAXCIFRE = 10;
//citirea unui numar
void citireNumar(int &nr){
cin >> nr;
}
//citirea elementelor unei matrici
void citireMatrice(int &m, int &n, int A[][MAX]){
cin >> m >> n;
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++)
cin >> A[i][j];
}
}
//citirea numarului si a elementelor din matrice
void citireDate(int &nr, int &m, int &n, int A[][MAX]){
citireNumar(nr);
citireMatrice(m, n, A);
}
//calcularea cifrei de control a unui numar
int cifraControl(int x){
while (x > 9){
int y = x;
int s = 0;
while (y > 0){
s += y % 10;
y /= 10;
}
x = s;
}
return x;
}Subiect · pagina 6
6
//determinarea prefixului maxim
//matricea se parcurgere o singură dată și se construiește un vector de apariții
//pentru cifrele de control corespunzătoare elementelor din matrice.
//Se rețin într - un vector cifrele numărului dat(nr).
//Se parcurge vectorul acestor cifre(începând cu cifra cea mai semnificativă) și
//se verifică apariția cifrelor în vectorul de apariții construit anterior
int prefixMaxCifre(int nr, int m, int n, int A[][MAX], int cifre[], int &nrCifre){
bool aparitii[NRMAXCIFRE];
int i = 0;
for (i = 0; i < 10; i++) // initializarea vectorului de frecvente
aparitii[i] = 0;
for (i = 0; i < m; i++){
for (int j = 0; j < n; j++){
aparitii[cifraControl(A[i][j])] = 1; // aparitia cifrei de control
} // corespunzatoare elementelui din matricea A
}
nrCifre = 0; // numarul cifrelor numarului nr dat
while (nr > 0){
cifre[nrCifre++] = nr % 10; // elementele sirului cifrelor numarului nr dat
nr /= 10;
}
i = nrCifre - 1; // parcurgem sirul cifrelor
while ((i >= 0) && (aparitii[cifre[i]])) // cifra de control = cu cifra curenta din nr
i--;
return nrCifre - i - 1;
}
//se afiseaza prefixul maxim de lungime lung cu cifre din vectorul de cifre
void afisarePrefix(int lung, int cifre[], int nrCifre){
if (lung == 0)
cout << "nu exista prefix";
for (int i = 0; (i < lung && i < nrCifre); i++)
cout << cifre[nrCifre - i - 1];
cout << endl;
}
int main(){
int nr = -1;
int m = -1;
int n = -1;
int A[MAX][MAX];
citireDate(nr, m, n, A);
int cifre[NRMAXCIFRE];
int nrCifre = 0;
int lung = prefixMaxCifre(nr, m, n, A, cifre, nrCifre);
afisarePrefix(lung, cifre, nrCifre);
return 0;
}Continuă pregătirea
Vezi arhiva completăAlte subiecte de la aceeași facultate
Examen de admitere · 2017Informatică · Sesiunea iulieDeschide fișa Examen de admitere · 2017Matematică · Sesiunea iulieDeschide 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ă concurs de pregătire 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.
