Admitere Informatică Iași 2018 – Subiecte și rezolvări

Admitere Informatică Iași 2018 – Subiecte și rezolvări

Recent, a fost dată admiterea la Facultatea de Informatică din Iași. Puteți găsi subiectele din 2018 aici, iar baremul aici. Cum baremul nu oferă soluții complete ale problemelor, în acest articol voi prezenta rezolvările subiectelor date la admitere.

Subiectul I. Problema 1.

Variabilele uu vv zz tt memorează valori întregi astfel încât u<vu \lt v și z<tz \lt t Precizați care dintre expresiile C++ de mai jos, atunci când este adevărată, implică faptul că intersecția intervalelor [u,v)[u, v) și (z,t](z, t] este nevidă.

  1. (u > t) && (v > z)
  2. !((u > t) || (v > z))
  3. (u <= t) && (v == z)
  4. !((u > t) || (t > u))

Simplificând un pic expresiile de mai sus, folosind legile lui De Morgan (la B și D), obținem:

  1. u > t && v > z
  2. u <= t && v <= z
  3. u <= t && v == z
  4. u <= t && t <= u

Prima expresie implică faptul că începutul primului interval este strict mai mare decât sfârșitul celui de-al doilea. Asta înseamnă că intersecția intervalelor este mulțimea vidă. A doua expresie nu este suficient de bună; un contraexemplu este [1,2)[1, 2) (5,6](5, 6] A treia expresie nu funcționează niciodată, pentru că primul interval este deschis în dreapta, iar al doilea deschis în stânga. Chiar dacă v=zv = z intersecția lor este vidă. Ultima expresie implică faptul că uu și tt sunt egale, și cum primul interval îl conține pe uu și al doilea îl conține pe tt intersecția celor două intervale are cardinalul 11 și deci nenul. Prin urmare, răspunsul corect este D.

Subiectul I. Problema 2.

Se consideră subprogramul FF de mai jos, descris în pseudocod. Subprogramul primește două numere naturale nenule prin parametrii xx și yy și întoarce un număr natural când se oprește.

subprogram F(x, y)
(x, y - numere naturale nenule)
acc <- 0
cât timp x != 0
dacă x este impar atunci
acc <- acc + y
x <- x / 2
y <- y * 2
returnează acc

a) Care este valoarea returnată de subprogram pentru parametrii x=52x = 52 și y=5y = 5

Iată valorile variabilelor după fiecare intrare în while:

acc\mathit{acc}xxyy
0026261010
0013132020
2020664040
2020338080
10010011160160
26026000320320

Așadar, valoarea returnată de funcție este 260260

b) Care este cel mai mare număr prim yy astfel încât F(x,y)F(x, y) să returneze 231231

Dacă ne mai dăm niște exemple, se observă că funcția aceasta calculează produsul dintre parametrii săi. În timp logaritmic față de xx chiar. Cum descompunerea în factori primi a lui 231231 este 37113 \cdot 7 \cdot 11 răspunsul este 1111

c) Înlocuiți instrucțiunea x <- x / 2 cu o secvență de pseudocod echivalentă și care folosește ca operații aritmetice doar adunări sau scăderi repetate.

Trebuie să efectuăm o împărțire folosind o instrucțiune repetitivă. Ei bine, se știe că împărțirea este o scădere repetată. Mai exact, a/ba / b se obține scăzând din aa valoarea bb cât timp aa este mai mare sau egal cu bb câtul împărțirii va fi dat de numărul de pași efectuați. Iată secvența de pseudocod cerută:

Subiectul I. Problema 2. Punctul c.
cnt <- 0
cât timp x >= 2
x <- x - 2
cnt <- cnt + 1
x <- cnt

d) Scrieți o funcție C++ care implementează subprogramul FF dat.

Trebuie doar să traducem pseudocodul în C++. Iată funcția scrisă în C++:

Subiectul I. Problema 2. Punctul d.
int F(int x, int y) {
int acc = 0;
while (x) {
if (x % 2)
acc += y;
x /= 2;
y *= 2;
}
return acc;
}

Subiectul II. Problema 1.

Fie VV mulțimea tuturor secvențelor de lungime 88 formate doar din cifrele 00 și 11 Graful neorientat GG are drept vârfuri elementele lui VV și muchii doar între vârfuri reprezentând secvențe care diferă exact într-una dintre cele 88 poziții. Care este numărul total de muchii din GG

  1. 896896
  2. 10241024
  3. 17921792
  4. 20482048

Asta e o problemă destul de interesantă; nu are soluția chiar imediată. În primul rând, numărul de noduri ale grafului, adică numărul de secvențe binare de lungime 88 este 28=2562^8 = 256 Numărul de vecini ai fiecărui nod este 88 pentru că cele două extremități ale unei muchii pot diferi prin bitul de pe orice poziție cuprinsă între 00 și 77 Dar graful este neorientat, așa că trebuie să numărăm muchiile astfel încât să nu se repete.

Putem, de exemplu, ca pentru fiecare nod să numărăm doar vecinii săi mai mari lexicografic decât el. Un vecin este mai mare lexicografic dacă și numai dacă se obține prin înlocuirea unui bit 00 cu bitul 11 Deci, numărul de muchii pe care le numărăm pentru nodul respectiv este egal numărul de biți 00 ai lui. Prin urmare, răspunsul problemei este egal cu numărul de biți 00 din scrierea tuturor nodurilor. Acesta este egal cu jumătate din numărul total de biți, pentru că jumătate dintre noduri au valoarea 00 pe o anumită poziție, iar restul au 11 Cum 8256/2=10248 \cdot 256 / 2 = 1024 varianta corectă este B.

Subiectul II. Problema 2.

Un graf este ppcolorabil dacă pp este cel mai mic număr pentru care putem colora (eticheta) vârfurile sale folosind culori din mulțimea {1,2,,p}\{1, 2, \ldots, p\} astfel încât oricare două vârfuri adiacente să fie colorate diferit. Care este numărul minim de muchii ale unui graf 1010colorabil?

  1. 4545
  2. 5050
  3. 9090
  4. 100100

Prima observație este că în colorarea grafului, trebuie ca toate culorile disponibile să fie folosite, pentru că altfel ar exista un număr mai mic de culori necesare, ceea ce încalcă definiția unui ppsistem. Așadar, graful trebuie să aibă 1010 noduri. În plus, trebuie să existe muchie între oricare două noduri, pentru că altfel unul dintre cele două noduri ar putea fi colorat altfel, fiind necesare mai puține culori, și iar nu s-ar respecta definiția ppsistemului.

Deci, răspunsul este dat de numărul de muchii ale unui graf neorientat complet cu 1010 noduri. Adică 910/2=459 \cdot 10 / 2 = 45 Răspunsul final este A.

Subiectul II. Problema 3.

Considerăm o matrice AA de dimensiune n×mn \times m (n,m2\htmlClass{katexified}{(} n, m \ge 2 care conține numere naturale distincte două câte două. Matricea reprezintă terenul de joacă al unei broscuțe. Elementul de pe linia ii și coloana jj din matrice este înălțimea terenului la acea poziție. Broscuța vizitează o succesiune de poziții din teren în următorul fel: Broscuța se află inițial pe linia LL și coloana CC În orice poziție s-ar afla la un moment dat, broscuța efectuează un salt pe una dintre pozițiile vecine pe orizontală sau verticală.

Dintre acestea, broscuța va alege poziția care are înălțimea cea mai apropiată de înălțimea de pe poziția curentă (deci cu modulul diferenței dintre cele două înălțimi minim). În cazul în care există mai multe poziții vecine cu această proprietate, ea alege să sară pe cea cu înălțimea cea mai mică dintre acestea. Broscuța nu se oprește niciodată.

a) În exemplul de mai jos, dimensiunea terenului este 4×54 \times 5 Broscuța se află inițial la coordonatele (L,C)=(2,4)(L, C) = (2, 4) unde înălțimea este 6666 Scrieți înălțimile primelor 1010 poziții vizitate de broscuță, în ordinea vizitării acestora.

(5751707275565860667759549390768852617968)\begin{pmatrix} 57 & 51 & 70 & 72 & 75\\ 56 & 58 & 60 & \mathbf{66} & 77\\ 59 & 54 & 93 & 90 & 76\\ 88 & 52 & 61 & 79 & 68 \end{pmatrix}

Aplicând regula descrisă mai sus, primele 1010 înălțimi vizitate sunt 6666 6060 5858 5656 5757 5656 5757 5656 5757 și 5656 La primul pas, spre exemplu, se alege înălțimea corespunzătoare minimului dintre 66 2424 1111 și 66 Pentru diferența 66 avem 6060 și 7272 Se alege minimul dintre cele două înălțimi, deci 6060

b) Scrieți o funcție C++ care primește ca parametri matricea AA dimensiunile acesteia, nn și mm și numerele naturale LL și CC Funcția trebuie să returneze cea mai mică înălțime a unei poziții vizitate de broscuță de cel puțin două ori. Nu este necesară validarea parametrilor de intrare.

Se observă că nu toate celulele matricei vor fi neapărat vizitate. Prima dată când broscuța ajunge pentru a doua oară pe o anumită celulă, traseul ei începe să se repete, urmând să facă de o infinitate de ori aceleași mișcări făcute de la prima vizită a acelei celule până la a doua (exclusiv). Cu alte cuvinte, din clipa aceea se intră într-un ciclu infinit. Pentru calcularea minimului, ne interesează doar numerele de pe acel ciclu, pentru că doar ele sunt vizitate de cel puțin două ori.

Admitere Informatică Iași 2018 (Subiectul 2. Problema 3)

Folosim o matrice locală aux, de tip bool, unde reținem pe fiecare poziție true dacă și numai dacă am vizitat-o. Începem să parcurgem pozițiile matricei cum este descris în enunț. Când ajungem pe una vizitată deja, îi reținem valoarea în variabila val, pentru că de acolo începe ciclul. Reținem valorile pozițiilor vizitate până atunci în vectorul v, iar la final parcurgem ciclul folosind acest vector.

Subiectul II. Problema 3. Punctul b.
// (NMAX - 1) = valoarea maximă pe care o poate lua n
// (MMAX - 1) = valoarea maximă pe care o poate lua m
int findMin(int A[NMAX][MMAX], int n, int m, int L, int C) {
int val; // valoarea de la care începe ciclul infinit
bool aux[NMAX][MMAX] = {}; // aux este inițializată cu false
// Vectorul valorilor parcurse până la intrarea în ciclu:
int lg = 0;
int v[NMAX * MMAX];
// Vectorii de deplasare:
int dL[] = {-1, 0, 1, 0};
int dC[] = { 0, 1, 0, -1};
while (true) {
if (aux[L][C]) { // Am trecut deja pe aici.
val = A[L][C];
break;
}
else {
aux[L][C] = true; // Marcăm poziția drept vizitată
v[lg++] = A[L][C]; // și îi adăugăm valoarea în vector.
}
// Inițializăm coordonatele valorii căutate:
int colMin = C;
int linMin = L + (L > 1 ? -1 : 1); // Ne asigurăm că este una din matrice.
int dif = A[linMin][colMin] - A[L][C]; // Calculăm diferența înălțimilor.
int absMin = dif < 0 ? -dif : dif; // Inițializăm modulul minim al diferenței.
// Parcurgem vecinii poziției curente:
for (int i = 0; i < 4; i++) {
int lin = L + dL[i];
int col = C + dC[i];
// Dacă vecinul se află în interiorul matricei:
if (1 <= lin && lin <= n &&
1 <= col && col <= m) {
dif = A[lin][col] - A[L][C]; // diferența curentă
abs = dif < 0 ? -dif : dif; // modulul diferenței curente
// Dacă am găsit o valoare/ poziție mai bună:
if (abs < absMin ||
abs == absMin && A[lin][col] < A[linMin][colMin]) {
absMin = abs;
linMin = lin;
colMin = col;
}
}
}
// Actualizăm coordonatele curente:
L = linMin;
C = colMin;
}
// Inițializăm minimul căutat cu ultima valoare din vector:
int min = v[lg - 1];
// Parcurgem vectorul în sens invers, până la începutul ciclului:
for (int i = lg - 2; i >= 0; i--) {
min = v[i] < min ? v[i] : min;
// Am terminat!
if (v[i] == val)
return min;
}
}

Subiectul II. Problema 4.

Definim un cuvânt drept șir nevid format din cel mult 55 caractere ale alfabetului latin: {’a’,’b’,,’z’}\{\texttt{'a'}, \texttt{'b'}, \ldots, \texttt{'z'}\}

a) Scrieți o funcție C++ cu numele value\mathrm{value} care are ca argument de intrare un cuvânt și returnează un număr natural. Pentru oricare două cuvinte s1s1 și s2s2 funcția trebuie să satisfacă proprietatea s1=s2value(s1)=value(s2)s1 = s2 \Leftrightarrow \mathrm{value}(s1) = \mathrm{value}(s2) În cazul în care argumentul primit nu este cuvânt, funcția va returna 00

Vom reprezenta cuvintele prin șiruri de caractere (string-uri). Trebuie să găsim o funcție injectivă pe mulțimea tuturor cuvintelor. Cea mai simplă idee, inspirată din funcțiile de hashing, este să privim un cuvânt ca pe un număr scris în baza 2727 (lungimea alfabetului $ + 1$), și să îl convertim în baza 1010 Fiecărei litere îi asociem un număr cuprins între 11 și 2626 mai exact poziția sa din alfabet. Dacă am indexa pozițiile de la 00 și am lucra cu baza 2626 funcția n-ar mai fi injectivă. De exemplu, atât pentru "aaa"\texttt{"aaa"} cât și pentru "a"\texttt{"a"} s-ar returna 00

Subiectul II. Problema 4. Punctul a.
int value(char* str) {
int val = 0;
for (int i = 0; str[i]; i++)
val = val * 27 + str[i] - 'a' + 1;
return val;
}

b) Justificați faptul că implementarea funcției value\mathrm{value} este corectă.

Funcția value\mathrm{value} primește ca parametru un șir de caractere și returnează un număr natural, așa cum se cere în problemă. Funcția este injectivă deoarece unui număr scris într-o anumită bază îi corespunde exact un număr scris în altă bază. În cazul nostru, cele două baze de numerație sunt 2727 și respectiv 1010

Subiectul III. Problema 1.

Câte șiruri distincte formate din exact o literă AA două litere BB trei litere CC și patru litere DD există?

  1. 151200151200
  2. 75607560
  3. 1260012600
  4. 10241024

Asta e o simplă problemă de combinatorică. Putem pune litera AA pe 1010 poziții. Litera BB poate fi pusă pe două din restul de 99 poziții. Litera CC poate fi pusă pe trei dintre celelalte 77 poziții. Litera DD poate fi pusă pe patru dintre cele 44 poziții rămase. Răspunsul corect este C, și este dat de rezultatul următoarei formule:

C101C92C73C44C_{10}^1 \cdot C_9^2 \cdot C_7^3 \cdot C_4^4

Subiectul III. Problema 2.

Se consideră funcția recursivă FF de mai jos. Ce valoare va returna apelul F(53)F(53)

int F(int u) {
if (u == 0) {
return 0;
}
if (u % 2 != 0) {
return 2 * F(u / 2);
}
else {
return 1 + F(u / 2);
}
}

Trebuie să urmărim lanțul de apeluri recursive. Apelul F(53)F(53) funcționează cam așa:

F(53) =
2 * F(26) =
2 * (1 + F(13)) =
2 * (1 + (2 * F(6))) =
2 * (1 + (2 * (1 + F(3)))) =
2 * (1 + (2 * (1 + (2 * F(1))))) =
2 * (1 + (2 * (1 + (2 * (2 * F(0)))))) =
2 * (1 + (2 * (1 + (2 * (2 * 0))))) =
2 * (1 + (2 * (1 + (2 * 0)))) =
2 * (1 + (2 * (1 + 0))) =
2 * (1 + (2 * 1)) =
2 * (1 + 2) =
2 * 3 =
6

Deci, răspunsul este 66

Subiectul III. Problema 3.

Spunem că o matrice pătratică aa de dimensiune n2n \ge 2 având elemente numere naturale, are proprietatea TT dacă îndeplinește următoarele condiții:

  • (i) Pentru orice 2pn2 \le p \le n numărul de elemente nenule din submatricea formată din primele pp linii și pp coloane ale lui aa este 2p22p - 2
  • (ii) Pentru orice 1jin1 \le j \le i \le n fie a[i][j]=a[j][i]=0a[i][j] = a[j][i] = 0 fie a[i][j]=a[j][i]+1a[i][j] = a[j][i] + 1
  • (iii) Pentru orice linie a matricei, elementele nenule au aceeași valoare.

De exemplu, matricea pătratică de mai jos, de dimensiune 55 are proprietatea TT

(0110120000200200030020000)\begin{pmatrix} 0 & 1 & 1 & 0 & 1\\ 2 & 0 & 0 & 0 & 0\\ 2 & 0 & 0 & 2 & 0\\ 0 & 0 & 3 & 0 & 0\\ 2 & 0 & 0 & 0 & 0 \end{pmatrix}

a) Scrieți o funcție C++ care primește ca parametri un întreg n2n \ge 2 și o matrice pătratică de dimensiune nn Funcția va returna 11 dacă matricea satisface proprietatea TT 00 în caz contrar.

Verificăm, pe rând, fiecare condiție a proprietății TT Imediat ce ne dăm seama că una nu este îndeplinită, returnăm false.

Subiectul III. Problema 3. Punctul a.
// (NMAX - 1) = valoarea maximă pe care o poate lua n
bool check(int n, int a[NMAX][NMAX]) {
int cnt = 0; // numărul curent de elemente nenule
// Condiția (i):
for (int p = 2; p <= n; p++) {
for (int i = 1; i < p; i++) {
if (a[p][i]) cnt++;
if (a[i][p]) cnt++;
}
if (a[p][p])
cnt++;
if (cnt != 2 * p - 2)
return false;
}
// Condiția (ii):
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
if (!(!a[i][j] && !a[j][i] || a[i][j] == a[j][i] + 1))
return false;
// Condiția (iii):
for (int i = 1; i <= n; i++) {
// Căutăm primul p pentru care a[i][p] != 0:
for (int p = 1; !a[i][p]; p++);
for (int j = p + 1; j <= n; j++)
if (a[i][j] && a[i][j] != a[i][p])
return false;
}
return true;
}

b) Demonstrați că într-o matrice pătratică de dimensiune n2n \ge 2 care satisface proprietatea TT există cel puțin două linii având un singur element nenul.

Având în vedere că (bool) a[i][j] == (bool) a[j][i], putem considera că matricea dată este matricea de adiacență a unui graf neorientat cu nn noduri. Graful acesta este conex, deoarece fiecare nod este adiacent cu unul mai mic decât el (ca indice), conform condiției (ii). În plus, numărul lui de muchii este (2n2)/2(2 \cdot n - 2) / 2 adică n1n - 1 Având în vedere acestea, matricea dată este de fapt matricea de adiacență a unui arbore.

Dacă arborele are minim două frunze, atunci matricea are minim două linii cu o singură valoare nenulă, pentru că frunzele sunt adiacente la un singur nod. Dacă nu, arborele este practic o listă simplu înlănțuită. În acest caz, rădăcina și frunza vor reprezenta cele două linii cu o singură valoare nenulă.

c) Scrieți o funcție C++ care primește ca argumente un întreg n2n \ge 2 și o matrice pătratică de dimensiune nn care îndeplinește proprietatea TT Funcția va afișa cea mai lungă secvență de indecși (ik,,i2,i1=1)(i_k, \ldots, i_2, i_1 = 1) care satisface relația a[ij+1][ij]=a[ij][ij+1]+1a[i_{j + 1}][i_j] = a[i_j][i_{j + 1}] + 1 pentru orice 1j<k1 \le j \lt k Nu este necesară validarea parametrilor de intrare. Justificați corectitudinea algoritmului. Pentru exemplul de mai sus, funcția va afișa (4,3,1)(4, 3, 1) Nu se acordă puncte pentru soluții ce folosesc backtracking.

În exemplul dat se observă că dacă a[i][j]a[i][j] este nenul, atunci nivelul lui ii este a[i][j]a[i][j] De asemenea, întotdeauna primul nod este rădăcina arborelui, conform condiției (ii). Deci, trebuie determinat un lanț de la cea mai adâncă frunză la rădăcină. Ideea pe caz general este aproape la fel, doar că nu scrie nicăieri că nivelurile se indexează de la 11 Așadar, trebuie să avem grijă să ne oprim după ce am afișat nodul 11 și nu nodul de pe nivelul 11

Subiectul III. Problema 3. Punctul c.
// (NMAX - 1) = valoarea maximă pe care o poate lua n
void maxPath(int n, int a[NMAX][NMAX]) {
int levels[NMAX]; // nivelurile nodurilor
int leaf = 1; // Inițializăm frunza cu rădăcina.
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (a[i][j]) {
levels[i] = a[i][j]; // Actualizăm nivelul,
if (levels[i] > levels[leaf]) // și dacă e cazul,
leaf = i; // frunza.
break;
}
// Afișăm lanțul de la frunză la rădăcină:
cout << '(';
while (true) {
cout << leaf << ", ";
for (int j = 1; j <= n; j++)
if (a[j][leaf] && levels[j] == levels[leaf] - 1) {
leaf = j; // leaf devine nodul curent
break;
}
// Dacă am ajuns la rădăcină:
if (leaf == 1) {
cout << "1)\n";
break;
}
}
}

Voi ce părere aveți despre subiectele date la admiterea la Facultatea de Informatică din Iași, 2018? Mie mi se par ceva mai grele decât cele de anul trecut, dar în continuare suficient de accesibile. Dacă aveți vreo întrebare despre problemele rezolvate în acest articol, nu ezitați să o lăsați mai jos pentru a vă putea răspunde

PS: Wow, 2595 de cuvinte! Cred că merită un share articolul

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii