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 u, v, z, t memorează valori întregi astfel încât u < v și z < t. Precizați care dintre expresiile C++ de mai jos, atunci când este adevărată, implică faptul că intersecția intervalelor [u, v) și (z, t] este nevidă.

  • A. (u > t) && (v > z)
  • B. !((u > t) || (v > z))
  • C. (u <= t) && (v == z)
  • D. !((u > t) || (t > u))

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

  • A. u > t && v > z
  • B. u <= t && v <= z
  • C. u <= t && v == z
  • D. 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), (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 == z, intersecția lor este vidă. Ultima expresie implică faptul că u și t sunt egale, și cum primul interval îl conține pe u și al doilea îl conține pe t, intersecția celor două intervale are cardinalul 1, și deci nenul. Prin urmare, răspunsul corect este D.

Subiectul I. Problema 2.

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

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

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

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

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

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 x chiar. Cum descompunerea în factori primi a lui 231 este 3 * 7 * 11, răspunsul este 11.

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 / b se obține scăzând din a valoarea b cât timp a este mai mare sau egal cu b; câtul împărțirii va fi dat de numărul de pași efectuați. Iată secvența de pseudocod cerută:

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

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

Subiectul II. Problema 1.

Fie V mulțimea tuturor secvențelor de lungime 8, formate doar din cifrele 0 și 1. Graful neorientat G are drept vârfuri elementele lui V și muchii doar între vârfuri reprezentând secvențe care diferă exact într-una dintre cele 8 poziții. Care este numărul total de muchii din G?

  • A. 896
  • B. 1024
  • C. 1792
  • D. 2048

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 8, este 28 = 256. Numărul de vecini ai fiecărui nod este 8, pentru că cele două extremități ale unei muchii pot diferi prin bitul de pe orice poziție cuprinsă între 0 și 7. 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 0 cu bitul 1. Deci, numărul de muchii pe care le numărăm pentru nodul respectiv este egal numărul de biți 0 ai lui. Prin urmare, răspunsul problemei este egal cu numărul de biți 0 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 0 pe o anumită poziție, iar restul au 1. Cum 8 * 256 / 2 = 1024, varianta corectă este B.

Subiectul II. Problema 2.

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

  • A. 45
  • B. 50
  • C. 90
  • D. 100

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 p-sistem. Așadar, graful trebuie să aibă 10 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 p-sistemului.

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

Subiectul II. Problema 3.

Considerăm o matrice A de dimensiune n × m (n, m ≥ 2), care conține numere naturale distincte două câte două. Matricea reprezintă terenul de joacă al unei broscuțe. Elementul de pe linia i și coloana j 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 L și coloana C. Î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 × 5. Broscuța se află inițial la coordonatele (L, C) = (2, 4), unde înălțimea este 66. Scrieți înălțimile primelor 10 poziții vizitate de broscuță, în ordinea vizitării acestora.

$$\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 10 înălțimi vizitate sunt 66, 60, 58, 56, 57, 56, 57, 56, 57 și 56. La primul pas, spre exemplu, se alege înălțimea corespunzătoare minimului dintre 6, 24, 11 și 6. Pentru diferența 6 avem 60 și 72. Se alege minimul dintre cele două înălțimi, deci 60.

b) Scrieți o funcție C++ care primește ca parametri matricea A, dimensiunile acesteia, n și m, și numerele naturale L și C. 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 4.

Definim un cuvânt drept șir nevid format din cel mult 5 caractere ale alfabetului latin: {'a', 'b', …, 'z'}.

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

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 27 (lungimea alfabetului + 1), și în convertim în baza 10. Fiecărei litere îi asociem un număr cuprins între 1 și 26, mai exact poziția sa din alfabet. Dacă am indexa pozițiile de la 0, și am lucra cu baza 26, funcția n-ar mai fi injectivă. De exemplu, atât pentru "aaa", cât și pentru "a", s-ar returna 0.

b) Justificați faptul că implementarea funcției value este corectă.

Funcția 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 27 și respectiv 10.

Subiectul III. Problema 1.

Câte șiruri distincte formate din exact o literă A, două litere B, trei litere C și patru litere D există?

  • A. 151200
  • B. 7560
  • C. 12600
  • D. 1024

Asta e o simplă problemă de combinatorică. Putem pune litera A pe 10 poziții. Litera B poate fi pusă pe două din restul de 9 poziții. Litera C poate fi pusă pe trei dintre celelalte 7 poziții. Litera D poate fi pusă pe patru dintre cele 4 poziții rămase. Răspunsul corect este C, și este dat de rezultatul următoarei formule:

$$C_{10}^{1} \cdot C_{9}^{2} \cdot C_{7}^{3} \cdot C_{4}^{4}$$

Subiectul III. Problema 2.

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

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

Deci, răspunsul este 6.

Subiectul III. Problema 3.

Spunem că o matrice pătratică a, de dimensiune n ≥ 2, având elemente numere naturale, are proprietatea T dacă îndeplinește următoarele condiții:

  • i. Pentru orice 2 ≤ p ≤ n, numărul de elemente nenule din submatricea formată din primele p linii și p coloane ale lui a este 2p - 2.
  • ii. Pentru orice 1 ≤ j ≤ i ≤ n, fie a[i][j] = a[j][i] = 0, fie a[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 5, are proprietatea T:

$$\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 n ≥ 2 și o matrice pătratică de dimensiune n. Funcția va returna 1 dacă matricea satisface proprietatea T, 0 în caz contrar.

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

b) Demonstrați că într-o matrice pătratică de dimensiune n ≥ 2 care satisface proprietatea T, 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 n 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 (2 * n - 2) / 2, adică n - 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 n ≥ 2 și o matrice pătratică de dimensiune n care îndeplinește proprietatea T. Funcția va afișa cea mai lungă secvență de indecși (ik, …, i2, i1 = 1) care satisface relația a[ij + 1][ij] = a[ij][ij + 1] + 1, pentru orice 1 ≤ j < 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). Nu se acordă puncte pentru soluții ce folosesc backtracking.

În exemplul dat se observă că dacă a[i][j] este nenul, atunci nivelul lui i este 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 1. Așadar, trebuie să avem grijă să ne oprim după ce am afișat nodul 1, și nu nodul de pe nivelul 1.

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 😉

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!