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

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

În acest articol voi prezenta rezolvările subiectelor date în anul 2015 la admitere la Facultatea de Informatică din Iași. Aici puteți găsi baremul. Cred că patru modele de rezolvări sunt suficiente ca să vă pregătiți pentru examenul de pe 21 iulie. Rezolvările din ultimii trei ani le găsiți la următoarele link-uri: 2018, 2017, 2016.

Subiectul I. Problema 1.

Numerele reale xx yy zz și tt satisfac inegalitățile x<yx \lt y și z<tz \lt t Precizați care dintre expresiile C++ de mai jos este echivalentă cu faptul că intervalele închise [x,y][x, y] și [z,t][z, t] au intersecția nevidă ([x,y][z,t]\htmlClass{katexified}{(} [x, y] \cap [z, t] \neq \varnothing

  1. !((z > y) || (t < x))
  2. (x <= z) || (y >= t)
  3. !((x < z) && (t < y))
  4. !((x > t) || (y > z))

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

  1. z <= y && t >= x
  2. x <= z || y >= t
  3. x >= z || t >= y
  4. x <= t && y <= z

Varianta corectă este A, intersecția celor două intervale fiind [max(x,z),min(y,t)][\max(x, z), \min(y, t)] B este greșită pentru că returnează true când y<zy \lt z C returnează true când x>tx \gt t ceea ce iarăși nu este bine. D returnează false când x<z<y<tx \lt z \lt y \lt t

Subiectul I. Problema 2.

Se consideră algoritmul de mai jos, descris în pseudocod.

citește n (număr natural)
x <- n % 10; m <- 1; s <- 1
cât timp n > 9 execută
n <- [n / 10]; y <- n % 10
dacă (y - x) * m < 0 atunci
dacă m > 0 atunci
m <- -1
altfel
s <- 0
x <- y
scrie s

a) Scrieți valoarea afișată de algoritm dacă numărul nn citit este 213521213521

Răspunsul este 00 și iată cum se ajunge la el:

xxyymmss
11221111
22551111
55331-111
33111-111
11221-100

b) Care este cel mai mic număr natural format din patru cifre distincte care poate fi citit în variabila nn astfel încât algoritmul să afișeze valoarea 11

Acum trebuie să înțelegem ce face de fapt algoritmul dat. Ei bine, acesta verifică dacă numărul nn este un munte, adică dacă cifrele sale (de la dreapta la stânga) cresc până într-un punct, iar apoi descresc. În yy se reține cifra curentă a lui nn iar în xx cifra precedentă. mm reprezintă semnul pe care trebuie să-l aibă diferența curentă dintre yy și xx Inițial aceasta trebuie să fie pozitivă, iar apoi negativă. Prin (y - x) * m < 0 se verifică dacă s-a produs o schimbare de semn a diferenței cifrelor. Dacă da, avem două cazuri: Dacă mm era 11 acum trebuie să devină 1-1 însă dacă era deja 1-1 înseamnă că cifrele au reînceput să crească, încâlcând proprietatea de munte. La final, variabila ss ne spune dacă nn este munte sau nu. Deci, răspunsul la această cerință este cel mai mic număr munte format din 44 cifre distincte, adică 12301230

c) Scrieți o secvență de instrucțiuni care să folosească doar operații de adunare și scădere și care să fie echivalentă cu instrucțiunea n <- [n / 10].

Nu este prima oară când văd o problemă dată la admitere unde trebuie folosit faptul că împărțirea este o scădere repetată. Pentru a-l împărți pe nn la 1010 numărăm în cntcnt de câte ori putem scădea 1010 din el astfel încât să rămână pozitiv, iar la final, copiem valoarea din cntcnt în nn

Subiectul I. Problema 2. Punctul c.
cnt <- 0
cât timp n >= 10 execută
n <- n - 10
cnt <- cnt + 1
n <- cnt

d) Scrieți programul C++ corespunzător algoritmului dat.

Un răspuns corect este:

Subiectul I. Problema 2. Punctul d.
#include <iostream>
using namespace std;
int main() {
int n; cin >> n;
int x = n % 10, m = 1, s = 1;
while (n > 9) {
n /= 10;
y = n % 10;
if (m > 0)
m = -1;
else
s = 0;
x = y;
}
cout << s << '\n';
return 0;
}

Subiectul II. Problema 1.

Care este numărul maxim de noduri de grad 33 într-un graf neorientat cu 55 noduri?

  1. 22
  2. 33
  3. 44
  4. 55

Numărul maxim de noduri de grad 33 într-un graf neorientat cu 55 noduri este 44 și se atinge când 44 dintre noduri formează un subgraf complet, iar al 55lea nod rămâne izolat. Deci, varianta corectă este C.

Subiectul II. Problema 1.

Subiectul II. Problema 2.

Fie un graf neorientat cu mulțimea nodurilor {1,2,,2015}\{1, 2, \ldots, 2015\} Două noduri ii și jj sunt unite printr-o muchie dacă și numai dacă max(i,j)=2min(i,j)\max(i, j) = 2 \min(i, j) sau max(i,j)=2min(i,j)+1\max(i, j) = 2 \min(i, j) + 1 Care este numărul de muchii ale acestui graf?

  1. 20152015
  2. 20162016
  3. 20142014
  4. 20142015/22014 \cdot 2015 \mathbin{/} 2

Reformulând proprietatea dată, în graf există muchia [i,j][i, j] cu j>ij \gt i dacă și numai dacă [j/2]=i[j / 2] = i Evident, pentru fiecare număr jj din mulțimea nodurilor există exact un ii astfel încât [j/2]=i[j / 2] = i și deci fiecărui număr îi corespunde exact o muchie. Excepție face 11 deoarece [1/2]=0[1 / 2] = 0 care nu aparține mulțimii nodurilor. Așadar, răspunsul este 20142014 varianta corectă fiind C. Se observă că graful dat este arbore, pentru că numărul muchiilor este cu 11 mai mic decât numărul nodurilor.

Subiectul II. Problema 3.

Considerăm codificarea binară a caracterelor, în care fiecărui simbol îi revine reprezentarea pe 8 biți a codului său ASCII. De exemplu, caracterului 'A', având codul ASCII 65, îi va corespunde reprezentarea binară 01000001. Scrieți un program C++ care să conțină următoarele funcții:

  1. Funcția convert_char primește ca argument un caracter și construiește un tablou cu 8 elemente 0 sau 1, reprezentând codificarea binară a caracterului primit.

  2. Funcția convert_string primește ca argument un șir de caractere s și construiește o matrice cu n linii și 8 coloane (unde n este lungimea șirului s), linia i a matricei reprezentând codificarea binară a caracterului de pe poziția i din șir.

  3. Funcția submatrix_size primește ca argument o matrice m formată doar din elemente 0 și 1 (precum și dimensiunile sale) și determină dimensiunea celei mai mari submatrice pătratice a lui m conținând elemente având toate aceeași valoare (fie 0, fie 1).

Observație: Funcțiile pot avea și alte argumente față de cele specificate mai sus.

Programul va citi de la tastatură un șir de caractere s și va afișa rezultatul determinat de funcția submatrix_size aplicată pe matricea construită de convert_string aplicată asupra lui s.

Exemplu: Pentru șirul de caractere s = "IDEEA", se va afișa 3, matricea corespunzătoare fiind:

m=(0100100101000100010001010100010101000001)m = \begin{pmatrix} 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1\\ 0 & 1 & \mathbf{0} & \mathbf{0} & \mathbf{0} & 1 & 0 & 0\\ 0 & 1 & \mathbf{0} & \mathbf{0} & \mathbf{0} & 1 & 0 & 1\\ 0 & 1 & \mathbf{0} & \mathbf{0} & \mathbf{0} & 1 & 0 & 1\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}

O problemă de implementare destul de simplă. În enunț scrie că funcțiile pot avea și alți parametri pe lângă cei dați, așa că am transmis toate tablourile ca parametri. Pentru convert_char aflu valoarea fiecărui bit al lui chr, folosind operații pe biți, și îl pun la poziția corespunzătoare în vectorul bin. În funcția convert_string nu fac decât să apelez convert_char pentru fiecare linie a matricei.

În funcția submatrix_size parcurg matricea, iar pentru fiecare poziție (i,j)(i, j) aflu lungimea maximă a unei submatrice pătratice cu colțul stânga-sus în (i,j)(i, j) Pentru asta am apelat o funcție auxiliară, ij_length. În această funcție încerc să măresc cât mai mult lungimea submatricei curente, având grijă să nu ies din matricea mare. La fiecare pas verific dacă vreun element proaspăt adăugat la submatrice este diferit de m[i][j]m[i][j] Dacă da, lungimea actuală nu este validă, răspunsul fiind len1len - 1 La finalul funcției, trebuie de asemenea returnat len1len - 1 căci poate n-am întâmpinat niciun element diferit de m[i][j]m[i][j] pentru nicio valoare posibilă a lui lenlen

Subiectul II. Problema 3.
#include <cstring>
#include <iostream>
using namespace std;
const int SMAX = 100;
// (SMAX - 1) = lungimea maximă a șirului de caractere
void convert_char(char chr, bool bin[8]) {
for (int i = 0; i < 8; i++)
bin[7 - i] = chr & (1 << i);
}
void convert_string(char* s, bool bin[SMAX][8]) {
for (int i = 0; s[i]; i++)
convert_char(s[i], bin[i]);
}
int ij_length(int x, int y, bool m[SMAX][8], int i, int j) {
for (int len = 2; i + len <= x && j + len <= y; len++)
for (int k = 0; k < len; k++) {
if (m[i + k][j + len - 1] != m[i][j]) return len - 1;
if (m[i + len - 1][j + k] != m[i][j]) return len - 1;
}
return len - 1;
}
int submatrix_size(int x, int y, bool m[SMAX][8]) {
int sol = 0;
for (int i = 0; i < x; i++)
for (int j = 0; j < y; j++) {
int len = ij_length(x, y, m, i, j);
if (len > sol)
sol = len;
}
return sol;
}
char str[SMAX];
bool mat[SMAX][8];
int main() {
cin >> str;
convert_string(str, mat);
cout << submatrix_size(strlen(str), 8, mat) << '\n';
return 0;
}

Complexitatea funcției submatrix_size este O(n4)O(n^4) dar cum numărul de coloane ale matricei este limitat la 88 o putem considera O(n2)O(n^2) cu o constantă foarte mare (576=8362\htmlClass{katexified}{(} 576 = 8 \cdot 36 \cdot 2 88 de la lenlenul maxim, 362=(89/2)236 \cdot 2 = (8 \cdot 9 / 2) \cdot 2 de la verificările corespunzătoare fiecărui lenlen de la 11 la 88 Cred că această soluție ar fi obținut punctaj maxim, dar eu unul aș fi aplicat un algoritm mult mai bun, ce folosește programare dinamică, cu constanta 22

Fie următoarea dinamică: dp[i][j]=\mathrm{dp}[i][j] = dimensiunea maximă a unei submatrice pătratice care conține numai elemente cu valoarea xx și care are colțul din dreapta-jos în (i,j)(i, j) Recurența este destul de cunoscută:

dp[i][j]={min(dp[i1][j],dp[i][j1],dp[i1][j1])+1pentru m[i][j]=x0altfel\mathrm{dp}[i][j] = \begin{cases} \min(\mathrm{dp}[i - 1][j], \mathrm{dp}[i][j - 1], \mathrm{dp}[i - 1][j - 1]) + 1 & \text{pentru } m[i][j] = x\\ 0 & \text{altfel} \end{cases}

Explicația este că dp[i1][j]+1\mathrm{dp}[i - 1][j] + 1 ne spune care e lungimea maximă pe verticală, dp[i][j1]+1\mathrm{dp}[i][j - 1] + 1 pe orizontală, iar dp[i1][j1]+1\mathrm{dp}[i - 1][j - 1] + 1 pe diagonală. Dintre cele trei valori trebuie să alegem minimul, ca să fim siguri că submatricea nu conține niciun element diferit de xx Vom construi așadar două dinamici: una pentru 00 și una pentru 11 De aici vine constanta 22 din spatele complexității de O(n2)O(n^2) Iată implementarea acestei idei:

Subiectul II. Problema 3.
int min(int x, int y, int z) {
int mn = x < y ? x : y;
return mn < z ? mn : z;
}
int max(int x, int y, int z) {
int mx = x > y ? x : y;
return mx > z ? mx : z;
}
int submatrix_size(int x, int y, bool m[SMAX][8]) {
int sol = 1;
int dp0[SMAX][8], dp1[SMAX][8];
for (int j = 0; j < y; j++) { dp0[0][j] = !m[0][j]; dp1[0][j] = m[0][j]; }
for (int i = 1; i < x; i++) { dp0[i][0] = !m[i][0]; dp1[i][0] = m[i][0]; }
for (int i = 1; i < x; i++)
for (int j = 1; j < y; j++) {
dp0[i][j] = (m[i][j] ? 0 : min(dp0[i - 1][j], dp0[i][j - 1], dp0[i - 1][j - 1]) + 1);
dp1[i][j] = (m[i][j] ? min(dp1[i - 1][j], dp1[i][j - 1], dp1[i - 1][j - 1]) + 1 : 0);
sol = max(sol, dp0[i][j], dp1[i][j]);
}
return sol;
}

Subiectul II. Problema 4.

Fie mulțimea S={1,2,,n}S = \{1, 2, \ldots, n\} unde n4n \ge 4 este un număr natural multiplu de 44 Scrieți un program C++ care:

  1. Citește de la tastatură numărul n4n \ge 4 precum și un număr natural pp (1pn/2\htmlClass{katexified}{(} 1 \le p \le n / 2 În cazul în care condițiile impuse nu sunt îndeplinite, va fi afișat mesajul "date invalide".

  2. Partiționează mulțimea dată SS în două submulțimi disjuncte AA și BB (S=AB\htmlClass{katexified}{(} S = A \cup B AB=A \cap B = \varnothing astfel încât suma elementelor din AA să fie egală cu suma elementelor din BB

  3. Elimină elementul pp din mulțimea SS și creează o nouă partiție A,BA', B' (eventual, modificând partiția creată la punctul b) astfel încât S{p}=ABS \setminus \{p\} = A' \cup B' AB=A' \cap B' = \varnothing și suma elementelor din AA' este egală cu suma elementelor din BB' În cazul în care acest lucru nu este posibil, va fi afișat mesajul "partitie inexistenta".

Exemplu: Pentru n=8n = 8 S={1,2,3,4,5,6,7,8}S = \{1, 2, 3, 4, 5, 6, 7, 8\} partiția inițială este A={1,3,6,8}A = \{1, 3, 6, 8\} B={2,4,5,7}B = \{2, 4, 5, 7\} Dacă p=1p = 1 sau p=3p = 3 va afișa "partitie inexistenta". Dacă p=2p = 2 partiția modificată este A={3,6,8}A' = \{3, 6, 8\} B={1,4,5,7}B' = \{1, 4, 5, 7\} Dacă p=4p = 4 partiția modificată este A={2,6,8}A' = \{2, 6, 8\} B={1,3,5,7}B' = \{1, 3, 5, 7\}

Prima cerință este trivială, așa că trecem la b: Observăm că dacă cuplăm 11 cu nn 22 cu n1n - 1 33 cu n2n - 2 etc., obținem n/2n / 2 perechi de sume egale. Cum nn este multiplu de 44 n/2n / 2 va fi număr par, așa că putem pune o jumătate dintre perechi în mulțimea AA și cealaltă jumătate în mulțimea BB Structura mulțimilor va fi:

A={1,3,,n/21,n/2+2,n/2+4,,n}B={2,4,,n/2,n/2+1,n/2+3,,n1} A = \{1, 3, \ldots, n / 2 - 1, n / 2 + 2, n / 2 + 4, \ldots, n\}\\ B = \{2, 4, \ldots, n / 2, n / 2 + 1, n / 2 + 3, \ldots, n - 1\}

Să notăm cu sum(X)sum(X) suma elementelor din mulțimea XX Prima observație cu privire la cerința c este că dacă pp este impar, nu există soluție. Motivul este că suma numerelor de la 11 la nn (să o notăm cu 2S2 \cdot S este pară, din moment ce nn este multiplu de 44 Dacă din SS îl scădem pe pp care este impar, vom obține un număr impar, deci sum(A)sum(A) și sum(B)sum(B) nu vor putea fi egale. Dacă în schimb pp este par, trebuie să echilibrăm cele două mulțimi astfel încât sum(A)=sum(B)=Sp/2sum(A') = sum(B') = S - p / 2 (Din mulțimea AA o vom forma pe AA' iar din BB pe BB' Avem de analizat următoarele două cazuri:

  • pBp \in B p/2p \mathbin{/} 2 impar. Avem p/2Ap \mathbin{/} 2 \in A așa că putem să-l mutăm pe p/2p \mathbin{/} 2 din AA în BB Obținem sum(A)=sum(A)p/2=Sp/2sum(A') = sum(A) - p \mathbin{/} 2 = S - p \mathbin{/} 2 și sum(B)=sum(B)p+p/2=Sp/2sum(B') = sum(B) - p + p \mathbin{/} 2 = S - p \mathbin{/} 2

  • pBp \in B p/2p \mathbin{/} 2 par. Avem p/2+1Ap \mathbin{/} 2 + 1 \in A Putem să-i ducem pe p/2+1p \mathbin{/} 2 + 1 și pe 11 din AA în BB iar pe 22 din BB în AA Obținem astfel sum(A)=sum(A)p/211+2=Sp/2sum(A') = sum(A) - p \mathbin{/} 2 - 1 - 1 + 2 = S - p \mathbin{/} 2 și sum(B)=sum(B)p+p/2+1+12=Sp/2sum(B') = sum(B) - p + p \mathbin{/} 2 + 1 + 1 - 2 = S - p \mathbin{/} 2

Atenție la restricția pn/2p \le n / 2 Eu inițial n-am băgat-o în seamă, așa că am luat patru cazuri în loc de două. Pentru a înțelege pe deplin ce am făcut mai sus, trebuie să vă luați un exemplu precum n=16n = 16 și să analizați pe hârtie fiecare dintre cele două cazuri. Iată cum arată implementarea în C++ a acestor idei:

Subiectul II. Problema 4.
#include <iostream>
using namespace std;
const int NMAX = 101;
// 2 * (NMAX - 1) = valoarea maximă a lui n
int n, p;
int lgA1, A1[NMAX], lgB1, B1[NMAX]; // A, B
int lgA2, A2[NMAX], lgB2, B2[NMAX]; // A', B'
int main() {
cin >> n >> p;
if (!(n >= 4 && n % 4 == 0 && 1 <= p && p <= n / 2)) {
cout << "date invalide\n";
return 0;
}
lgA1 = lgB1 = n / 2;
for (int i = 1, j = 1; i <= n / 4; i++, j += 2) {
A1[i] = j;
B1[i] = j + 1;
}
for (int i = n / 4 + 1, j = n / 2 + 2; i <= n / 2; i++, j += 2) {
A1[i] = j;
B1[i] = j - 1;
}
cout << "A: "; for (int i = 1; i <= lgA1; i++) cout << A1[i] << ' '; cout << '\n';
cout << "B: "; for (int i = 1; i <= lgB1; i++) cout << B1[i] << ' '; cout << '\n';
if (p % 2) {
cout << "partitie inexistenta\n";
return 0;
}
if (p / 2 % 2) {
for (int i = 1; i <= lgA1; i++)
if (A1[i] != p / 2)
A2[++lgA2] = A1[i];
for (int i = 1; i <= lgB1; i++)
if (B1[i] == p)
B2[++lgB2] = p / 2;
else
B2[++lgB2] = B1[i];
}
else {
A2[++lgA2] = 2;
for (int i = 2; i <= lgA1; i++)
if (A1[i] != p / 2 + 1)
A2[++lgA2] = A1[i];
B2[++lgB2] = 1;
for (int i = 2; i <= lgB1; i++)
if (B1[i] == p)
B2[++lgB2] = p / 2 + 1;
else
B2[++lgB2] = B1[i];
}
cout << "A': "; for (int i = 1; i <= lgA2; i++) cout << A2[i] << ' '; cout << '\n';
cout << "B': "; for (int i = 1; i <= lgB2; i++) cout << B2[i] << ' '; cout << '\n';
return 0;
}

Subiectul III. Problema 1.

Într-o urnă se află 44 bile de culoare albă și 33 bile de culoare neagră. Se extrag bilele pe rând și se reține secvența de 77 culori obținută. Câte astfel de secvențe distincte sunt?

  1. 210210
  2. 3535
  3. 7070
  4. 840840

Cum bilele sunt de doar două culori, putem spune că două secvențe de bile diferă dacă șirurile formate din pozițiile ce conțin bile albe diferă. Numărul secvențelor din urmă este C4+34=35C_{4 + 3}^4 = 35 Varianta corectă este B.

Subiectul III. Problema 2.

Pentru funcțiile F1 și F2 definite mai jos, ce valoare va returna apelul F1(34)?

int F2(int x);
int F1(int x) {
if (x < 7)
return 3 + x;
else
return 2 + F2(x - 2);
}
int F2(int x) {
if (x < 10)
return 3 * x;
else
return 2 * F1(x / 2);
}

Ca de obicei, la acest tip de exercițiu trebuie să urmărim lanțul de apeluri recursive. De data asta avem parte de o situație un pic mai specială, pentru că ni se dau două funcții indirect recursive: F1 apelează pe F2, iar F2 pe F1. Apropo, funcția F2 a trebuit declarată înainte de a defini funcția F1, pentru că în definiția ei, F1 se folosește de F2.

F1(34)
= 2 + F2(32)
= 2 + 2 * F1(16)
= 2 + 2 * (2 + F2(14))
= 2 + 2 * (2 + 2 * F1(7))
= 2 + 2 * (2 + 2 * (2 + F2(5)))
= 2 + 2 * (2 + 2 * (2 + 3 * 5))
= 74

Subiectul III. Problema 3.

Un puzzle Minesweeper este o matrice de nn linii și mm coloane care conține la fiecare poziție numărul 00 (reprezentând un loc liber) sau 1-1 (reprezentând o mină). Pozițiile adiacente poziției (i,j)(i, j) sunt:

{(i1,j1),(i1,j),(i1,j+1),(i,j1),(i,j+1),(i+1,j1),(i+1,j),(i+1,j+1)}{0,,n1}×{0,,m1}\small \{(i - 1, j - 1), (i - 1, j), (i - 1, j + 1), (i, j - 1), (i, j + 1), (i + 1, j - 1), (i + 1, j), (i + 1, j + 1)\}\\ \small \cap \, \{0, \ldots, n - 1\} \times \{0, \ldots, m - 1\}

O poziție (i,j)(i, j) din matrice este periculoasă dacă cel puțin o poziție din cele maxim 88 poziții adiacente conține o mină. Fie (l,c)(l, c) o poziție în matrice. Zona sigură este compusă din toate pozițiile accesibile din (l,c)(l, c) urmând un drum format din poziții nepericuloase adiacente.

Zona activă conține toate pozițiile zonei sigure și pozițiile adiacente zonei sigure. Matricea rezultat are aceleași dimensiuni cu puzzle-ul și este definită astfel:

  • Dacă (l,c)(l, c) conține o mină, matricea rezultat va fi chiar puzzle-ul inițial.
  • Dacă (l,c)(l, c) nu conține o mină dar este periculoasă, matricea rezultat conține 2-2 peste tot cu excepția poziției (l,c)(l, c) care conține numărul de mine vecine.
  • Altfel, matricea rezultat conține pe fiecare poziție (i,j)(i, j) din zona activă numărul de mine adiacente poziției (i,j)(i, j) și 2-2 în celelalte poziții.
Exemplu(I)(II)(III)(IV)
Puzzle(1001001000000100)\begin{pmatrix} -1 & 0 & 0 & -1\\ 0 & 0 & \mathbf{-1} & 0\\ 0 & 0 & 0 & 0\\ 0 & -1 & 0 & 0 \end{pmatrix}(0000011000000000)\begin{pmatrix} 0 & 0 & 0 & 0\\ 0 & -1 & -1 & 0\\ 0 & \mathbf{0} & 0 & 0\\ 0 & 0 & 0 & 0 \end{pmatrix}(1000000000110101)\begin{pmatrix} -1 & 0 & \mathbf{0} & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & -1 & -1\\ 0 & -1 & 0 & -1 \end{pmatrix}(1000000000000001)\begin{pmatrix} -1 & 0 & 0 & 0\\ 0 & 0 & 0 & \mathbf{0}\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & -1 \end{pmatrix}
Poziția (l,c)(l, c)(1,2)(1, 2)(2,1)(2, 1)(0,2)(0, 2)(1,3)(1, 3)
Rezultat(1001001000000100)\begin{pmatrix} -1 & 0 & 0 & -1\\ 0 & 0 & -1 & 0\\ 0 & 0 & 0 & 0\\ 0 & -1 & 0 & 0 \end{pmatrix}(2222222222222222)\begin{pmatrix} -2 & -2 & -2 & -2\\ -2 & -2 & -2 & -2\\ -2 & 2 & -2 & -2\\ -2 & -2 & -2 & -2 \end{pmatrix}(2100222222222222)\begin{pmatrix} -2 & 1 & 0 & 0\\ -2 & 2 & 2 & 2\\ -2 & -2 & -2 & -2\\ -2 & -2 & -2 & -2 \end{pmatrix}

a) Scrieți matricea rezultat pentru exemplul (IV).

Ne aflăm în cazul al treilea, pentru că poziția dată nu conține mină, și nu este nici periculoasă. Zona activă este reprezentată de toate celulele matricei, cu excepția celor cu valoarea 1-1 Pe pozițiile periculoase punem 11 pentru că sunt adiacente cu o singură mină, în locul celor cu mină punem 2-2 iar pe celelalte le lăsăm 00

(2100110000110012)\begin{pmatrix} -2 & 1 & 0 & 0\\ 1 & 1 & 0 & 0\\ 0 & 0 & 1 & 1\\ 0 & 0 & 1 & -2 \end{pmatrix}

b) Scrieți în limbajul C++ o funcție care, primind la intrare un puzzle, calculează o matrice (de aceleași dimensiuni cu puzzle-ul) care conține 00 pe pozițiile nepericuloase și 11 pe pozițiile periculoase.

Funcția va primi ca parametri dimensiunile n și m, și două matrice: puzzle (cea inițială), și danger (cea pe care trebuie să o construim). Pur și simplu parcurgem vecinii fiecărei celule din puzzle și verificăm dacă aceasta este vecină cu măcar o mină.

Subiectul III. Problema 3. Punctul b.
// NMAX = valoarea maximă a lui n
// MMAX = valoarea maximă a lui m
void buildDanger(int n, int m, int puzzle[NMAX][MMAX], int danger[NMAX][MMAX]) {
// Vectorii de deplasare:
int addLin[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int addCol[] = {0, 1, 1, 1, 0, -1, -1, -1};
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
danger[i][j] = 0;
for (int k = 0; k < 8; k++) {
int x = i + addLin[k], y = j + addCol[k]; // vecinul curent
if (!(0 <= x && x < n && 0 <= y && y < m)) // Am ieșit din matrice.
continue;
if (puzzle[x][y] == -1) {
danger[i][j] = 1;
break;
}
}
}
}

c) Scrieți în limbajul C++ o funcție care:

  • Primește ca argument o matrice reprezentând puzzle-ul Minesweeper și poziția (l,c)(l, c)
  • Construiește matricea rezultat după cum este descris mai sus.

Verificăm mai întâi în ce situație ne aflăm. Primul caz este banal, pur și simplu copiem matricea. În al doilea caz, numărăm vecinii lui (l,c)(l, c) ca la punctul precedent, iar în rest punem 2-2 Cazul al treilea este mai special, pentru că trebuie să determinăm zona activă. Putem face asta printr-o parcurgere BFS pe matrice (Algoritmul lui Lee), sau printr-un DFS pe matrice (flood fill). Eu am ales să fac fill, pentru că este mai ușor de implementat, fiind o funcție recursivă.

Subiectul III. Problema 3. Punctul c.
// NMAX = valoarea maximă a lui n
// MMAX = valoarea maximă a lui m
void fill(int i, int j, int n, int m, int puzzle[NMAX][MMAX], int answer[NMAX][MMAX]) {
int addLin[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int addCol[] = {0, 1, 1, 1, 0, -1, -1, -1};
// Numărăm vecinii cu mină:
answer[i][j] = 0;
for (int k = 0; k < 8; k++) {
int x = i + addLin[k], y = j + addCol[k];
if (!(0 <= x && x < n && 0 <= y && y < m))
continue;
if (puzzle[x][y] == -1)
answer[i][j]++;
}
if (answer[i][j] > 0) // Suntem pe marginea zonei active.
return; // Vizităm pozițiile periculoase, dar nu ne expandăm din ele.
for (int k = 0; k < 8; k++) {
int x = i + addLin[k], y = j + addCol[k];
if (!(0 <= x && x < n && 0 <= y && y < m))
continue;
if (answer[x][y] == -2) // Dacă n-am vizitat celula:
fill(x, y, n, m, puzzle, answer);
}
}
void buildAnswer(int n, int m, int puzzle[NMAX][MMAX], int l, int c, int answer[NMAX][MMAX]) {
int addLin[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int addCol[] = {0, 1, 1, 1, 0, -1, -1, -1};
if (puzzle[l][c] == -1)
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
answer[i][j] = puzzle[i][j];
else {
// Numărăm vecinii cu mină:
int cnt = 0;
for (int k = 0; k < 8; k++) {
int x = l + addLin[k], y = c + addCol[k];
if (!(0 <= x && x < n && 0 <= y && y < m))
continue;
if (puzzle[x][y] == -1)
cnt++;
}
if (cnt) { // Dacă zona este periculoasă:
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
answer[i][j] = -2;
answer[l][c] = cnt;
}
else {
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
answer[i][j] = -2;
fill(l, c, n, m, puzzle, answer);
}
}
}

Gata și cu subiectele date la admitere în 2015. Dacă aveți vreo întrebare legată de problemele din acest articol, nu ezitați să o lăsați într-un comentariu mai jos :smile:

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