Pregătire cu un profesor
Glisează →Programează o ședință de cunoaștere
Subiect și barem
Sursa: Facultatea de Informatică – Universitatea de Vest din Timișoara
Subiectul și răspunsurile sunt în același PDF. Afișăm documentul complet, cu toate paginile.
Despre acest subiect
pregătire · Culegere oficială de probleme și rezolvări, 71 de pagini
Sursa documentelor: Facultatea de Informatică – Universitatea de Vest din Timișoara. Verifică răspunsurile cu baremul după ce rezolvi subiectul.
Subiectul și baremul în format text
Text extras automat din documentul original. Pentru formule, tabele, imagini și așezarea răspunsurilor, verifică întotdeauna PDF-ul.
Subiect și barem · 71 pagini
Subiect și barem · pagina 1
UNIVERSITATEA DE VEST DIN TIMIS¸OARA FACULTATEA DE MATEMATIC ˘A S¸I INFORMATIC ˘A CULEGERE DE PROBLEME PENTRU ADMITERE Informatic˘a TIMIS¸OARA 2021
Subiect și barem · pagina 2
Cuprins 1 Subiecte propuse ˆın cadrul sesiunilor de preg˘atire pentru bacalaure- at/admitere la facultate 3 1.1 Algoritmi de prelucrare a datelor simple . . . . . . . . . . . . . . . . . 3 1.2 Descompunerea unei probleme ˆın subprobleme . . . . . . . . . . . . . . 5 1.3 Algoritmi de prelucrare a tablourilor unidimensionale . . . . . . . . . . 7 1.4 Algoritmi de prelucrare a tablourilor bidimensionale . . . . . . . . . . . 12 1.5 Algoritmi recursivi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.6 Algoritmi de sortare. Algoritmi de c˘autare . . . . . . . . . . . . . . . . 16 1.7 Prelucr˘ari asupra ¸sirurilor de caractere . . . . . . . . . . . . . . . . . . 19 1.8 Structuri de date pentru grafuri . . . . . . . . . . . . . . . . . . . . . . 27 2 Subiecte date la Concursul FMI 30 2.1 Edit, ia a III-a (2017) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.2 Edit, ia a IV-a (2018) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.3 Edit, ia a V-a (2019) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.4 Edit, ia a VI-a (2021) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3 Subiecte date la examenul de admitere la facultate 54 3.1 Sesiunea Iulie 2016 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.2 Sesiunea Iulie 2017 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.3 Sesiunea Iulie 2018 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.4 Sesiunea Iulie 2019 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 2
Subiect și barem · pagina 3
Capitolul 1 Subiecte propuse ˆın cadrul sesiunilor de preg˘atire pentru bacalaureat/admitere la facultate 1.1 Algoritmi de prelucrare a datelor simple Tematic˘a Prelucr˘ari asupra cifrelor (extragerea ¸si analiza cifrelor unui num˘ar natural) Propriet˘at¸i de divizibilitate (verificare divizibilitate, determinarea celui mai mare divizor comun, verificare ¸si generare numere prime, descompunere ˆın factori primi) Calcule de sume ¸si produse Generarea de ¸siruri date prin relat¸ii de recurent¸˘a Probleme 1. Fie n un num˘ar natural nenul. Descriet¸i algoritmi pentru: (a) Determinarea sumei tuturor cifrelor lui n. De exemplu, pentru n = 26326 se obt¸ine valoarea 19. (b) Determinarea valorii obt¸inute prin inversarea cifrelor num˘arului n. De exem- plu, pentru valoarea 26326 se obt¸ine valoarea 62362. (c) Determinarea tuturor cifrelor binare ale lui n. (d) Determinarea tuturor divizorilor proprii ai lui n. (e) Afis, area mesajului ”da” dac˘a cea mai semnificativ˘a cifr˘a a unui num˘ar n este strict mai mare decˆat cifra unit˘at¸ilor sau mesajul ”nu” ˆın caz contrar. De exemplu, pentru n = 5832 se va afi¸sa ”da” pentru c˘a 5 > 2, iar pentru n = 4539 se va afi¸sa ”nu”. 3
Subiect și barem · pagina 4
2. Cifra destinului. Cifra destinului este cifra obt¸inut˘a prin adunarea cifrelor ce
intervin ˆın data na¸sterii; adunarea cifrelor rezultatului obt¸inut se repet˘a pˆan˘a se
ajunge la o singur˘a cifr˘a. De exemplu, pentru 01.02.1999 se obt¸ine: 1 + 2 + 1 +
9 + 9 + 9 = 31 → 3 + 1 = 4. Descriet¸i un algoritm care calculeaz˘a cifra destinului
pornind de la data nas, terii specificat˘a prin cele trei valori (zi, lun˘a, an).
3. Numere asemenea. Dou˘a numere naturale sunt asemenea dac˘a scrierile celor
dou˘a numere ˆın baza 10 au aceleas, i cifre. De exemplu, numerele 23326 s, i 623
sunt asemenea, deoarece mult, imea cifrelor este aceeas, i ({2, 3, 6}). Descriet¸i un
algoritm care preia o pereche de numere naturale s, i determin˘a dac˘a sunt sau nu
asemenea.
4. Conversie ˆıntre baze de numerat¸ie. Se consider˘a c˘a num˘arul natural nenul n
este reprezentat ˆın baza de numerat¸ie b1 (2 ≤ b1 ≤ 10) ¸si se dore¸ste construirea
num˘arului natural m care reprezint˘a aceea¸si valoare, ˆıns˘a ˆın baza b2 (2 ≤ b2 ≤
10). Atˆat num˘arul init¸ial cˆat ¸si cel convertit sunt specificate prin variabile ˆıntregi
(nu este posibil˘a utilizarea unui tablou pentru stocarea cifrelor). De exemplu,
pentru n = 2210 ¸si b1 = 3, b2 = 5 se obt¸ine m = 300.
5. Reguli de codificare. Se consider˘a un num˘ar natural n constituit din k ≥ 2 cifre
(n = ckck−1 . . . c1) ¸si se pune problema codific˘arii lui n prin schimbarea pozit¸iei
unor cifre f˘ar˘a a stoca cifrele lui n ˆıntr-un tablou. Descriet¸i algoritmi pentru
urm˘atoarele dou˘a variante de codificare:
(a) Permutare circular˘a a cifrelor. Fiind dat˘a o valoare p (1 ≤ p ≤ k − 1), s˘a se
construiasc˘a num˘arul m = cpcp−1 . . . c1ckck−1 . . . cp+1. De exemplu, pentru
n = 45612 ¸si p = 2 se obt¸ine m = 12456.
(b) Interschimbare a dou˘a cifre. Fiind date dou˘a valori p1 ¸si p2 (1 ≤ p2 ≤ p1 ≤
k − 1) s˘a se construiasc˘a num˘arul obt¸inut prin interschimbarea cifrelor de
pe pozit¸iile indicate de p1 ¸si p2 (din n = ckck−1 . . . cp1 . . . cp2 . . . c1 se obt¸ine
m = ckck−1 . . . cp2 . . . cp1 . . . c1), toate celelalte cifre r˘amˆanˆand pe pozit¸ia
lor init¸ial˘a. De exemplu, pentru n = 45612, p1 = 4, p2 = 2 se obt¸ine
m = 41652.
6. Pentru un num˘ar natural n, s˘a se scrie un algoritm care determin˘a num˘arul
maxim de divizori pe care ˆıi are un num˘ar din mult¸imea {2, 3, . . . , n}. De exem-
plu, dac˘a n = 12, num˘arul maxim de divizori este 5 (num˘arul 12 are 5 divizori:
2, 3, 4, 6, 12).
7. Descriet¸i un algoritm care, pentru dou˘a numere naturale nenule a ¸si b, determin˘a
numitorul ¸si num˘ar˘atorul fract¸iei ireductibile egale cu a
b .
8. S˘a se descrie un algoritm care verific˘a dac˘a un num˘ar n este prim sau nu, folosind
teorema lui Wilson. (Condit, ia necesar˘a s, i suficient˘a ca un num˘ar natural p, p > 1,
s˘a fie prim este ca (p − 1)! + 1 s˘a fie divizibil cu p.)
9. S˘a se descrie un algoritm care afi¸seaz˘a toate numerele prime dintr-un interval
dat [a, b], a, b numere naturale, a < b.
4Subiect și barem · pagina 5
10. Se consider˘a un num˘ar natural n > 2. Descriet¸i un algoritm care s˘a afis, eze toate numerele x mai mici decˆat n, care au proprietatea c˘a x − 1 s, i x + 1 sunt numere prime. Exemplu: pentru n = 43, se vor afis, a numerele: 4 6 12 18 30 42. 11. Scriet, i un algoritm care afi¸seaz˘a descompunerea unui num˘ar natural n ˆın factori primi. De exemplu, pentru n = 18, se va afi¸sa 2ˆ1 × 3ˆ2. 12. S˘a se scrie un algoritm care, pentru num˘arul natural n dat, determin˘a sumele: (a) S = 1 × 2 + 2 × 3 + 3 × 4... + n × (n + 1) (b) S = 1 × n + 2 × (n − 1) + 3 × (n − 2) + ... + n × 1 13. Estimat¸i cu precizia ε > 0 limitele s, irurilor urm˘atoare (pentru punctele (a) ¸si (b) se consider˘a c˘a x este o valoare dat˘a din intervalul (0, 1)): (a) sn = ∑n i=0 (−1)ix2i+1 (2i+1)! (b) sn = ∑n i=0 (−1)ix2i (2i)! (c) sn = ∑n i=1 1 (2i+1)2 Indicat¸ie. Calculul se opre¸ste atunci cˆand diferent¸a dintre doi termeni consecutivi ai s, irului este mai mic˘a decˆat constanta ε(|sn − sn−1| < ε, ε = 0.001). 14. S˘a se scrie un algoritm care determin˘a dac˘a un num˘ar natural dat m face parte din s, irul lui Fibonacci sau nu. S, irul lui Fibonacci este definit prin relat, iile: f (0) = 1, f (1) = 1, f (n) = f (n − 1) + f (n − 2), pentru n ≥ 2. Nu se vor folosi tablouri. 1.2 Descompunerea unei probleme ˆın subprobleme Tematic˘a Algoritmi de prelucrare a datelor simple ¸si exemple de utilizare a subprogramelor (funct¸ii ¸si proceduri) s, i a diferitelor tipuri de parametri (parametri de intrare, ies, ire, intrare/ies, ire) s, i variabile (locale, globale). Tipuri de prelucr˘ari: Prelucr˘ari asupra cifrelor (extragerea ¸si analiza cifrelor unui num˘ar natural) Prelucr˘ari ale unor secvent¸e de valori preluate secvent¸ial (f˘ar˘a s˘a fie stocate ˆın structuri de tip tablou) Prelucr˘ari asupra unor mult, imi de puncte ˆın plan, date prin coordonatele lor carteziene Evaluarea unui polinom specificat prin valorile coeficient, ilor Prelucr˘ari cu numere complexe 5
Subiect și barem · pagina 6
Probleme 1. Se asociaz˘a unui num˘ar natural n valoarea A(n) ca fiind suma factorialelor ci- frelor lui n (de exemplu, pentru n = 318, A(n) = 3! + 1! + 8!). (a) Pentru o valoare n dat˘a s˘a se calculeze A(n). Calculat¸i num˘arul de operat¸ii de ˆınmult¸ire efectuate. Propunet¸i o variant˘a care s˘a utilizeze un num˘ar cˆat mai mic de operat¸ii de ˆınmult¸ire. (b) Pentru o valoare natural˘a k (k < 9999) s˘a se determine cel mai mic num˘ar natural n cu proprietatea c˘a A(n) = k. 2. Determinat¸i cel mai mic ¸si cel mai mare num˘ar constituit din k cifre (k < 5) avˆand proprietatea c˘a suma cifrelor este S. Date de test: k = 3, S = 25; k = 4, S = 33; k = 4, S = 12. 3. Se pune problema gener˘arii unei valori naturale n pornind de la 0 ¸si folosind doar urm˘atoarele dou˘a operat¸ii: (i) dublarea valorii curente; (ii) incrementarea valorii curente. De exemplu, 5 = (0 + 1) × 2 × 2 + 1 se poate obt¸ine aplicˆand secvent¸a de operat¸ii: incrementare; dublare; dublare; incrementare, iar 12 = (((0+1)×2+1)×2)×2 se obt¸ine aplicˆand: incrementare, dublare, incrementare, dublare, dublare. (a) Pentru o valoare natural˘a n determinat¸i o secvent¸˘a de operat¸ii care permite generarea valorii. (b) Determinat¸i num˘arul minim de operat¸ii de incrementare ¸si dublare care permit generarea valorii n. 4. Se cite¸ste o secvent¸˘a de n perechi de valori reale (x1, y1), (x2, y2), . . . , (xn, yn) care reprezint˘a coordonatele vˆarfurilor unui poligon convex P1P2 . . . Pn (punctul Pi are coordonatele (xi, yi)) specificate ˆın ordine trigonometric˘a. S˘a se determine: (a) Perimetrul poligonului. (b) Aria poligonului. (c) Coordonatele vˆarfurilor celui mai mic dreptunghi, avˆand laturile paralele cu axele de coordonate, care cont¸ine poligonul. (d) Num˘arul efectiv de laturi ale poligonului (se presupune c˘a pot exista mai mult de dou˘a puncte consecutive coliniare). Date de test: P1(2, 5)P2(1, 4)P3(1, 2)P4(2, 1)P5(5, 1)P6(8, 1)P7(9, 3)P8(8, 5)P9(5, 5) 5. Se consider˘a polinomul de grad n cu coeficient¸i reali: P (z) = cnzn + cn−1zn−1 + · · · + c1z + c0 ¸si se pune problema calculului valorii polinomului pentru un num˘ar complex z = a + bi, specificat prin partea sa real˘a a ¸si coeficientul p˘art¸ii sale imaginare b. Valorile coeficient¸ilor se citesc succesiv ˆıncepˆand cu cn. Date de test: z = 2 + 3i, P (z) = 2z3 − 3z2 + z − 6. 6. Se cite¸ste succesiv o secvent¸˘a de n valori reale care cont¸ine cel put¸in o va- loare pozitiv˘a. S˘a se determine indicele de ˆınceput ¸si indicele de sfˆar¸sit ale unei subsecvent¸e de elemente consecutive care satisface: 6
Subiect și barem · pagina 7
(a) Este cea mai lung˘a subsecvent¸˘a cresc˘atoare din secvent¸a dat˘a.
(b) Suma elementelor subsecvent¸ei este maxim˘a (ˆın raport cu sumele altor
subsecvent¸e din secvent¸˘a).
Date de test: − 1, 2, 1, −1, 3, 4, 5, −3, 1, 4
2, −3, 1, 3, 4, −2, 1, 2, 3, −5
7. Se consider˘a un serviciu web la care utilizatorii se conecteaz˘a/deconecteaz˘a ¸si
se pune problema determin˘arii num˘arului maxim de utilizatori conectat¸i si-
multan pornind de la o secvent¸˘a de semnale de forma: 1 (s-a conectat un
utilizator), 0 (s-a deconectat un utilizator). De exemplu, pentru secvent¸a
1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0 num˘arul maxim de utilizatori conectat¸i este 5.
8. O secvent¸˘a de n valori reale preluate succesiv (f˘ar˘a a fi stocate ˆıntr-un ta-
blou): x0, x1, . . . , xn−1 trebuie “netezit˘a” prin mediere folosind o “fereastr˘a”
de dimensiune 3, adic˘a, pornind de la valorile din secvent¸˘a, se afi¸seaz˘a valorile
y1, y2, . . . , yn−2 care au proprietatea c˘a yi = (xi−1 + xi + xi+1)/3.
9. Se consider˘a relat¸ia de recurent¸˘a care define¸ste o secvent¸˘a de tip Collatz:
C(n) =
{n/2 dac˘a n este par
3n+1 dac˘a n este impar
Conjectura Collatz afirm˘a faptul c˘a pentru orice valoare de pornire n, secvent¸a
va ajunge la 1. Pentru un num˘ar natural n se define¸ste L(n) ca fiind lungimea
secvent¸ei, adic˘a num˘arul de elemente din secvent¸˘a pˆan˘a la ˆıntˆalnirea valorii 1
(inclusiv valoarea 1). Dou˘a numere, n1 ¸si n2, se consider˘a Collatz-echivalente
dac˘a L(n1) = L(n2). Pentru dou˘a valori naturale, a ¸si b (a < b), s˘a se determine
toate perechile de numere Collatz-echivalente din mult, imea {a, a + 1, . . . , b}.
10. Se consider˘a o funct¸ie integrabil˘a f : [a, b] → R ¸si se pune problema aproxim˘arii
integralei funct¸iei f pe intervalul [a, b] folosind o sum˘a Riemann “la stˆanga” cu
pasul h(n) = (b−a)/n : S(n) = h(n)(f (a)+f (a+h(n))+· · ·+f (b−h(n))). Fiind
date limitele intervalului, s˘a se calculeze S(n∗) (n∗ este prima valoare pentru care
|S(n∗) − S(n∗ − 1)| < 0.001).
1.3 Algoritmi de prelucrare a tablourilor unidimen-
sionale
Tematic˘a
Declararea s, i parcurgerea tablourilor unidimensionale
S, tergeri s, i inser˘ari de elemente
Verificarea unor propriet˘at, i
7Subiect și barem · pagina 8
Sortarea tablourilor Interclasarea tablourilor Secvent, e de vectori Probleme 1. Parcurgere ¸si construire tablouri. Se consider˘a dou˘a tablouri, A s, i B, avˆand fiecare n elemente numere ˆıntregi. S˘a se scrie cˆate o funct¸ie/procedur˘a cores- punz˘atoare urm˘atoarelor probleme: (a) Consider˘am c˘a A ¸si B au aceea¸si lungime: se cere s˘a se construiasc˘a un tablou C care cont¸ine elementele comune, care apar atˆat ˆın A cˆat ¸si ˆın B pe aceea¸si pozit¸ie, dac˘a nu exist˘a acela¸si element se va pune 0 ˆın tabloul C. (b) Calculeaz˘a suma elementelor din A care apar ¸si ˆın B pe aceea¸si pozit¸ie. (c) Construie¸ste un tablou D care cont¸ine pe pozit¸ia i suma elementelor cores- pondente din A ¸si B. Dac˘a au dimensiuni diferite, D va cont¸ine o copie a elementului din tabloul mai lung. 2. Conversii ˆıntre baze de numerat¸ie (utilizˆand tablouri). (a) Se consider˘a c˘a num˘arul natural nenul n este reprezentat ˆın baza 10 ¸si se dore¸ste construirea tabloului de caractere care sa cont¸in˘a cifrele num˘arului. (b) (generalizare a) Se consider˘a c˘a num˘arul natural nenul n este reprezentat ˆın baza 10 ¸si se dore¸ste construirea num˘arului m care reprezint˘a aceea¸si valoare, ˆıns˘a ˆın baza b (2 ≤ b ≤ 9). Num˘arul m va fi reprezentat printr-un s, ir de caractere. (c) Se consider˘a un tablou (B) de ˆıntregi care cont¸ine doar 0 sau 1. Tabloul cont, ine reprezentarea ˆın baza 2 a unui num˘ar natural ¸si se pune problema construirii unui tablou (H) care cont¸ine reprezentarea ˆın baza 16. De exem- plu, pentru B = 10110011 se obt¸ine H = B3. (d) Se consider˘a un ¸sir de caractere care cont¸ine reprezentarea ˆın baza 16 a unui num˘ar (alfabetul folosit este ‘0’, ‘1’,. . . , ‘A’,. . . ,‘F ’) ¸si se pune problema determin˘arii valorii corespunz˘atoare ˆın baza 10. De exemplu, pentru B9F se obt¸ine 2975. 3. Reprezentarea ˆın complement fat, ˘a de 2. Numerele ˆıntregi negative sunt repre- zentate intern prin regula complementului fat, ˘a de 2 care const˘a ˆın aplicarea urm˘atoarelor etape: i) se determin˘a reprezentarea ˆın binar a num˘arului f˘ar˘a semn s, i se complementeaz˘a tot, i bit, ii (un bit 0 se transform˘a ˆın 1, iar un bit 1 se transform˘a ˆın 0); ii) se adun˘a 1 la num˘arul anterior (folosind regulile de adu- nare ˆın baza 2). Ceea ce se obt, ine este reprezentarea intern˘a a num˘arului ˆıntreg negativ. Dac˘a se d˘a o reprezentare intern˘a hexazecimal˘a (0xA2B3C4D5), prin examinarea bitului de semn (cel mai din stˆanga) se decide dac˘a num˘arul este negativ sau nu. Dac˘a num˘arul este negativ, atunci se vor aplica aceleas, i reguli pentru a determina valoarea num˘arului. S˘a se scrie o funct, ie care s˘a compare dou˘a numere ˆıntregi pe 32 de bit, i pentru care se cunoas, te reprezentarea intern˘a ˆın hexazecimal. Funct, ia va returna 8
Subiect și barem · pagina 9
(a) −1 dac˘a primul num˘ar este mai mic decˆat al doilea;
(b) 0 dac˘a sunt egale;
(c) 1 dac˘a primul num˘ar este mai mare decˆat al doilea.
4. Definit, i un tablou cu numele de numere reale (tip double) de dimensiune 100.
Definit, i un ciclu ce va popula elementele tabloului cu urm˘atoarea secvent, ˘a:
1/(2 ∗ 3 ∗ 4), 1/(4 ∗ 5 ∗ 6), 1/(6 ∗ 7 ∗ 8), . . . pˆan˘a la 1/(200 ∗ 201 ∗ 202)
Presupunˆand c˘a numele tabloului este data, parcurget, i tabloul pentru a calcula
urm˘atoarea expresie:
data[0]−data[1]+data[2]−data[3] + · · · −data[99]
ˆInmult, it, i rezultatul obt, inut anterior cu 4.0 s, i ad˘augat, i 3.0 s, i afis, at, i rezultatul.
Recunoas, tet, i valoarea obt, inut˘a?
5. Gigel, Ionel s, i C˘alin, trei student, i de la Informatic˘a au pornit un StartUp de
succes ˆınpreun˘a. Fiecare s, tie cˆateva limbaje sau tehnici de programare: Gigel
s, tie n limbaje, Ionel s, tie m, iar C˘alin k. ˆInainte de a porni startup-ul cu propriul
lor proiect, pentru a face bani, s-au hot˘arˆat s˘a participe la orice proiect pe care
l-ar putea face de pe freelancer.com, ˆın orice combinat, ie posibil˘a. Fiecare astfel
de proiect necesit˘a o mult, ime de cunos, tint, e prezentate foarte clar ˆın descrierea
sa. S˘a presupunem c˘a se cunosc cerint, ele pentru 30 de proiecte, s˘a se scrie un
program care s˘a stabileasc˘a alocarea student, ilor la proiecte ˆın as, a fel ˆıncˆat s˘a
nu se suprapun˘a competent, ele (pentru fiecare proiect se stabiles, te dac˘a vor intra
singuri, cˆate doi sau tot, i trei ˆımpreun˘a).
Exemplu: Gigel s, tie {C, C#, OOP s, i Java}, Ionel {C, Python, C++, OOP} s, i
C˘alin {C++, OOP, Ruby}. Dac˘a se cunosc cerint, ele pentru
Proiect 1: {OOP, C, Ruby, Python} → este nevoie de tot, i 3 pentru acest
proiect.
Proiect 2: {C#, Java} → Gigel ˆıl poate face singur.
6. Planificare service auto. ˆIntr-un service auto exist˘a 5 elevatoare s, i 5 mecanici.
ˆIntr-o lun˘a se repar˘a ˆın acel service, ˆın medie, 200 de mas, ini. S, eful de service,
Gigel, este cel care planific˘a fiecare mas, in˘a s, tiind pentru fiecare intervent, ie cˆand
intr˘a ˆın service s, i cˆat dureaz˘a reparat, ia. Se cunosc datele din planificare, cˆand
intr˘a fiecare mas, in˘a s, i cˆat dureaz˘a intervent, ia (vor fi generate aleator), s, i mai
s, tim c˘a Gigel, atunci cˆand planific˘a, se uit˘a pe rˆand care elevator este liber s, i
ˆıl marcheaz˘a ˆın planificare. Dac˘a nu are niciunul disponibil, atunci, ˆımpreun˘a
cu clientul, alege o alt˘a dat˘a s, i or˘a disponibil˘a. ˆIntrebarea la care vrem s˘a
r˘aspundem este care din cele 5 elevatoare va fi folosit cel mai mult ˆın luna ce
urmeaz˘a s, i care vor fi mas, inile reparate, ˆın ordinea cronologic˘a a reparat, iilor.
Exemplu: Presupunem c˘a ˆın loc de 20 zile a cˆate 8 ore pe zi ne gˆandim la 160 de
ore pe lun˘a. Ca intrare vom primi 2 seturi de numere care specific˘a ora la care
ˆıncepe s, i cˆat dureaz˘a ˆıntervent¸ia pentru o ma¸sin˘a (1, 1, 5, 10, 7) ¸si (4, 6, 4, 3, 4) :
9Subiect și barem · pagina 10
Ma¸sina Ora start Durata 1 1 4 2 1 6 3 5 4 4 10 3 5 7 4 vom planifica astfel: 1, 1 + 4 → 5, 4 + 5 → 10, 10 + 3 1, 1 + 6 → 7, 7 + 4 7. Spal˘atorie auto self-service. La colt¸ul str˘azii exist˘a o sp˘al˘atorie auto self-service cu 5 locuri. Istoricul unei zile arat˘a ˆın felul urm˘ator: timpii de intrare ˆın sp˘al˘atorie : [8 : 00, 8 : 05, 8 : 05, 8 : 08, 8 : 32, 8 : 37, 8 : 43, 8 : 45 . . . ] num˘arul de fise folosite: [2, 3, 4, 2, 1, 2, 3, 4 . . . ] Se cere s˘a se genereze ˆıntˆai datele de intrare (istoricul unei zile la sp˘al˘atorie): (a) Se va genera ora s, i minutul pentru fiecare dintre timpii de intrare apoi se vor ordona cresc˘ator dup˘a or˘a s, i minute. (b) Se va genera aleator num˘arul de fise folosite, un num˘ar ˆıntre 1 s, i 5. S, tiind c˘a o fis˘a dureaz˘a 2 minute la care se va ad˘auga 1 minut, timpul pierdut pentru preg˘atire, se cere s˘a se implementeze funct, ii/proceduri co- respunz˘atoare urm˘atoarelor probleme: (c) S¸tiind c˘a o fis˘a cost˘a 2.5 lei s˘a se calculeze profitul zilei. (d) S˘a se determine pentru fiecare ma¸sin˘a care este ora la care iese din sp˘al˘atorie. (e) S˘a se determine pentru fiecare ma¸sin˘a dac˘a trebuie s˘a a¸stepte sau nu ca s˘a intre ˆıntr-o box˘a. (f) S˘a se determine care este cel mai lung timp de a¸steptare. 8. Clasament WTA. ˆIn acest moment conform https://www.tenisdecamp.ro/ clasament-wta-simplu/ ˆın clasamentul WTA la tenis feminin primele 10 ju- c˘atoare au urm˘atoarele puncte: 1 Australia Ashleigh Barty 8017 2 Czech Republic Karolina Pliskova 5940 3 Romania Simona Halep 5561 4 Japan Naomi Osaka 5496 5 Ukraine Elina Svitolina 5075 6 Canada Bianca Vanessa Andreescu 4935 7 Switzerland Belinda Bencic 4675 8 Czech Republic Petra Kvitova 4436 9 USA Serena Williams 4215 10 Holland Kiki Bertens 4165 10
Subiect și barem · pagina 11
Presupunem c˘a ˆın fiecare lun˘a va fi cˆate un concurs de GrandSlam s, i ¸stim c˘a pentru GrandSlam se pot cˆas, tiga urm˘atoarele puncte W F SF QF R16 R32 R64 R128 Q Q3 Q2 Q1 Points 2000 1300 780 430 240 130 70 10 40 30 20 2 (W=winner, F=Finalist, . . . ) Fiecare dintre juc˘atoarele din top 10 ar putea s˘a cˆas, tige oricare meci s, i oricare turneu. S-a terminat turneul, se cunosc rezultatele ¸si ce s-a ˆıntˆamplat anul trecut: Anul trecut Turneul actual 1 Ashleigh Barty W F 2 Karolina Pliskova QF W 3 Simona Halep F SF 4 Naomi Osaka SF SF 5 Elina Svitolina QF QF 6 Bianca Vanessa Andreescu R16 SF 7 Belinda Bencic QF QF 8 Petra Kvitova SF QF 9 Serena Williams R32 QF 10 Kiki Bertens SF QF Avˆand ˆın vedere c˘a fiecare punct cˆa¸stigat anterior trebuie ap˘arat, se pune ˆıntre- barea dac˘a Simona Halep va fi sau nu num˘arul 1 dup˘a acest turneu? 9. Analiz˘a zaruri. Bogdan are 2 zaruri cu cˆate 6 fet, e fiecare, unul albastru s, i unul ros, u. Le arunc˘a pe o mas˘a de 100 de ori s, i ˆıs, i noteaz˘a valorile obt, inute pentru fiecare zar ˆın parte (ˆın cˆate un tablou cu 100 de elemente pentru fiecare zar). S˘a se decid˘a care dintre cele 2 zaruri este cel mai echilibrat zar? Cel albastru sau cel ro¸su? Not˘a: Se va folosi formula entropiei lui Shannon pentru a determina cantitatea de informat, ie existent˘a ˆın fiecare zar. Zarul cu entropia mai mare este consi- derat mai echilibrat. Dac˘a (f1, f2, . . . , f6) reprezint˘a frecvent¸ele relative asoci- ate valorilor obt¸inute la aruncarea unui zar, regula de calcul a entropiei este −f1 × log2(f1) − f2 × log2(f2) − · · · − f6 × log2(f6), entropie mai mare ˆınseamn˘a mai echilibrat. 10. Sufix ¸si prefix comun. Fiind date dou˘a tablouri (a1, a2, . . . , am) ¸si (b1, b2, . . . , bn), cu numere ˆıntregi, s˘a se stabileasc˘a num˘arul maxim de elemente comune aflate la sfˆar¸situl lui a ¸si ˆınceputul lui b (de exemplu, a = (1, 4, 3, 5, 6, 7, 2) ¸si b = (6, 7, 2, 5, 1, 8) au 3 elemente comune, pe 6, 7 ¸si 2). 11. Date de na¸stere. Se consider˘a o list˘a care cont¸ine datele de na¸stere ale locuitorilor unui ora¸s (lista poate fi reprezentat˘a printr-un tablou cont¸inˆand structuri sau prin 3 tablouri corespunz˘atoare celor 3 componente ale date: (zi, lun˘a, an)). S˘a se determine: 11
Subiect și barem · pagina 12
(a) cea mai “mic˘a” dat˘a de na¸stere (corespunz˘atoare celui mai vˆarstnic locui- tor); (b) cea mai “mare” dat˘a de na¸stere (corespunz˘atoare celui mai tˆan˘ar locuitor); (c) cea/cele mai frecvent˘a/frecvente dat˘a/date de na¸stere (cea/cele care apa- re/apar de cele mai multe ori ˆın list˘a); (d) dac˘a exist˘a vreo zi ˆın perioada (1 ianuarie 1918 – 31 decembrie 2017) ˆın care nu e n˘ascut niciun locuitor. 1.4 Algoritmi de prelucrare a tablourilor bidimen- sionale Tematic˘a Construire, parcurgere ¸si transformare Operat¸ii cu matrici (adunare, ˆınmult¸ire) Verificare propriet˘at¸i (simetrie, matrici triunghiulare, matrici diagonale etc.) Aplicat, ii Probleme 1. S˘a se verifice dac˘a o valoare x se g˘ase¸ste ˆıntr-o matrice cu m linii s, i n coloane. Indicat, ie: Se parcurge matricea pe linii, apoi pe coloane, iar la prima ˆıntˆalnire a elementului c˘autat ne oprim. 2. Calculat, i suma s, i produsul a dou˘a matrici. Indicat, ie: ˆIn cazul adun˘arii, cele dou˘a matrici trebuie s˘a aib˘a aceeas, i dimensiune. ˆIn cazul produsului, num˘arul de coloane ale primei matrici trebuie s˘a fie egal cu num˘arul de linii ale celei de a doua. Matricea produs va avea num˘arul de linii al primei matrici s, i num˘arul de coloane al celei de a doua. 3. Calculat, i suma elementelor de pe diagonala principal˘a s, i produsul elementelor de pe diagonala secundar˘a. Indicat, ie: Pentru rezolvarea problemei, trebuie s˘a ne asigur˘am c˘a matricea este p˘atratic˘a. Elementele de pe diagonala principal˘a au indicii (i, i), iar cei de pe diagonala secundar˘a (i, n − i + 1), unde n este dimensiunea matricii. 4. S˘a se determine transpusa unei matrici. Indicat, ie: Transpusa unei matrici se obt, ine interschimbˆand liniile cu coloanele. 5. S˘a se elimine linia i ¸si coloana j dintr-o matrice cu m linii s, i n coloane. 6. Determinat, i dac˘a o matrice este simetric˘a (fat, ˘a de diagonala principal˘a, respectiv secundar˘a), triunghiular˘a (superior, respectiv inferior), diagonal˘a. 12
Subiect și barem · pagina 13
7. S˘a se verifice dac˘a o matrice p˘atratic˘a de dimensiune n × n este p˘atrat magic
(suma elementelor de pe fiecare linie, coloan˘a, diagonala principal˘a ¸si diagonala
secundar˘a este aceea¸si ¸si este egal˘a cu n2(n2+1)
2 ¸si memoreaz˘a toate valorile de la
1 la n2).
Exemplu:
6 1 8
7 5 3
2 9 4
.
Contraexemple:
6 0 8
7 5 3
2 9 4
,
5 10 5
11 5 4
3 3 14
.
8. Se citesc de la tastatur˘a dimensiunile unei matrici s, i elementele ei. Se cere
transformarea matricii prin inversarea ordinii elementelor ˆın cadrul fiec˘arei linii.
Exemplu: Pentru matricea
1 2 3 4 5
3 4 1 2 1
2 3 4 1 8
se obt, ine
5 4 3 2 1
1 2 1 4 3
8 1 4 3 2
.
9. Pentru o matrice cu n linii s, i m coloane, care memoreaz˘a numere ˆıntregi, modificat, i
ordinea elementelor astfel ˆıncˆat parcurgˆand matricea de sus ˆın jos ¸si de la stˆanga
la dreapta aceasta s˘a cont¸in˘a mai ˆıntˆai elementele negative, apoi pe cele pozitive.
Se va analiza atˆat varianta ˆın care se poate utiliza un tablou adit, ional (cu m × n
elemente), cˆat s, i varianta ˆın care nu se utilizeaz˘a tablou adit, ional.
Exemplu: Pentru matricea
−5 6 −8 3
2 −9 1 −6
8 1 −8 −2
se obt, ine
−5 −9 −8 −8
−6 −2 1 2
8 1 3 6
.
10. Se consider˘a o ret¸ea de n calculatoare ¸si o matrice p˘atratic˘a de dimensiune n care
cont¸ine elemente din {0, 1} completate astfel: a[i, j] = 1 dac˘a calculatorul i este
conectat direct cu calculatorul j ¸si a[i, j] = 0 ˆın caz contrar. Scriet¸i algoritmi
care verific˘a dac˘a:
(a) ret¸eaua este complet conectat˘a (a[i, j] = 1 pentru fiecare pereche (i, j) de
valori diferite)
(b) ret¸eaua este de tip inel (a[i, i + 1] = a[i + 1, i] = 1 pentru fiecare i din
1, . . . , n − 1 ¸si a[n, 1] = a[1, n] = 1, iar celelalte elemente sunt nule)
(c) ret¸eaua este de tip stea (exist˘a un i∗ cu proprietatea c˘a a[i, i∗] = a[i∗, i] = 1,
pentru orice i 6 = i∗, iar celelalte elemente sunt nule).
Not˘a: Consider˘am c˘a un calculator nu este conectat cu el ˆınsus, i, astfel c˘a a[i, i] =
0, pentru fiecare i.
11. Se consider˘a o imagine color de dimensiune n×n pixeli. S, tiind c˘a fiec˘arui pixel ˆıi
corespund trei valori din mult, imea {0, 1, . . . , 255} (cˆate una pentru fiecare dintre
cele trei canale de culoare - ros, u, verde s, i albastru) propunet, i o structur˘a de date
pentru stocarea imaginii. Descriet, i un algoritm care:
(a) transform˘a imaginea color ˆıntr-o imagine pe nivele de gri folosind pentru
fiecare pixel regula:
13Subiect și barem · pagina 14
gri = max (ros, u,verde,albastru)+min(ros, u,verde,albastru) 2 (b) construies, te histograma (tabelul cu frecvent, ele corespunz˘atoare valorilor pixelilor) asociat˘a imaginii pe nivele de gri (c) determin˘a valoarea medie folosind histograma construit˘a la punctul (b) (d) transform˘a imaginea pe nivele de gri ˆın imagine alb-negru (alb are codul 1, negru are codul 0) folosind valoarea determinat˘a la punctul (c) ca valoare de prag (dac˘a valoarea pixelului din imaginea pe nivele de gri este mai mic˘a decˆat valoarea medie atunci valoarea pixelului ˆın imaginea alb-negru este 0, altfel este 1) (e) verific˘a dac˘a imaginea alb-negru construit˘a la punctul anterior cont, ine pixeli negri pe diagonala principal˘a s, i pe cea secundar˘a s, i pixeli albi ˆın rest. Indicat, ie: Putem asimila o imagine cu 3 matrici, Mr – matricea pixelilor ros, ii, Mv – matricea pixelilor verzi, Ma – matricea pixelilor albas, tri. Atunci structura de date este tuplul format din cele 3 matrici. Pentru rezolvarea punctului (a) se folosesc 2 funct, ii auxiliare de calcul al maximului/minimului dintre dou˘a numere, iar ca operat, ie principal˘a este adunarea de matrici. La punctul (b) se t, ine cont de faptul c˘a tabloul de frecvent, e are lungimea de 256. Punctele (b) s, i (c) sunt aplicat, ii la adunarea a dou˘a matrici, conceptul de adunare a elementelor din matrice. Punctele (d) s, i (e) testeaz˘a propriet˘at, i ale matricilor. 12. Se consider˘a o matrice p˘atratic˘a cu n linii s, i n coloane. Descriet, i cˆate un algoritm pentru: (a) afis, area elementelor din matrice linie dup˘a linie (b) afis, area elementelor din matrice coloan˘a dup˘a coloan˘a (c) afis, area elementelor din matrice diagonal˘a dup˘a diagonal˘a (pornind de la elementul de pe prima linie ultima coloan˘a s, i parcurgˆand fiecare diagonal˘a paralel˘a cu diagonala principal˘a pornind de sus ˆın jos). De exemplu, pentru o matrice cu 4 linii s, i 4 coloane s, i elemente a[i, j], aces- tea vor fi afis, ate ˆın urm˘atoarea ordine: a[1, 4], a[1, 3], a[2, 4], a[1, 2], a[2, 3], a[3, 4], a[1, 1], a[2, 2], a[3, 3], a[4, 4], a[2, 1], a[3, 2], a[4, 3], a[3, 1], a[4, 2], a[4, 1]. (d) afis, area elementelor ˆın spiral˘a pornind de la elementul de pe prima linie s, i prima coloan˘a s, i parcurgˆand matricea ˆın sensul acelor de ceasornic. Pentru exemplul de mai sus, ordinea de afis, are va fi: a[1, 1], a[1, 2], a[1, 3], a[1, 4], a[2, 4], a[3, 4], a[4, 4], a[4, 3], a[4, 2], a[4, 1], a[3, 1], a[2, 1], a[2, 2], a[2, 3], a[3, 3], a[3, 2]. 1.5 Algoritmi recursivi Tematic˘a Descrierea algoritmilor recursivi Tehnici recursive 14
Subiect și barem · pagina 15
Proceduri s, i funct, ii recursive Analiza complexit˘at, ii algoritmilor recursivi Exemple Probleme 1. S˘a se determine cel mai mare divizor comun a dou˘a numere naturale (cmmdc) folosind o implementare recursiv˘a a algoritmului lui Euclid bazat pe sc˘aderi repetate. 2. S˘a se determine cel mai mare divizor comun a dou˘a numere naturale (cmmdc) folosind o implementare recursiv˘a a algoritmului lui Euclid bazat pe ˆımp˘art, iri repetate. 3. ˆIn matematic˘a, factorialul unui num˘ar natural n (folosit adesea ˆın algebr˘a, com- binatoric˘a s, i analiza matematic˘a), notat cu n!, este produsul tuturor numerelor naturale mai mici sau egale cu n. Prin convent, ie, 0! este egal cu 1. S˘a se scrie o funct, ie recursiv˘a pentru calculul valorii factorialului unui num˘ar ˆıntreg dat. 4. Cu ajutorul unei funct, ii recursive, s˘a se verifice dac˘a un num˘ar natural este factorialul unui alt num˘ar natural. 5. S, irul lui Fibonacci este un s, ir de numere naturale ˆın care, cu except, ia primilor doi termeni egali cu 1, ceilalt, i termeni reprezint˘a suma celor doi anteriori. Acest s, ir este unul dintre cele mai populare s, iruri specificate printr-o relat, ie de recurent, ˘a. (a) S˘a se scrie o funct, ie recursiv˘a care determin˘a valoarea termenului din s, ir de un rang specificat. (b) S˘a se scrie o funct, ie recursiv˘a care determin˘a rangul primului termen care atinge sau dep˘as, es, te o valoare dat˘a. 6. Se consider˘a un num˘ar natural n. Scriet, i cˆate o funct, ie recursiv˘a pentru: (a) Calculul sumei cifrelor num˘arului n (b) Calculul produsului cifrelor nenule ale num˘arului n 7. ˆInt, elegem prin r˘asturnatul unui num˘ar, num˘arul obt, inut atunci cˆand cifrele se parcurg ˆın ordinea invers˘a celei naturale (cea mai din stˆanga cifr˘a este cifra unit˘at, ilor, urm˘atoarea spre dreapta este cifra zecilor s, .a.m.d.). S˘a se scrie o funct, ie recursiv˘a care genereaz˘a r˘asturnatul unui num˘ar natural primit ca para- metru. 8. Scriet, i o funct, ie recursiv˘a care verific˘a dac˘a num˘arul natural primit ca parametru poate fi scris ca sum˘a de termeni din s, irul lui Fibonacci. 9. S˘a se scrie o funct, ie recursiv˘a pentru descompunerea ˆın factori primi a unui num˘ar natural. 10. S˘a se scrie o funct, ie recursiv˘a pentru calculul valorii lui 2 la puterea n. 15
Subiect și barem · pagina 16
11. Scriet, i o funct, ie recursiv˘a pentru calculul combin˘arilor de n luate cˆate k. 12. S˘a se calculeze, folosind funct, ii recursive, sumele: S1 = 1 + 1/2 + 1/3 + · · · + 1/n S2 = 1/2 + 2/1 + 2/3 + 3/2 + · · · + n/(n + 1) + (n + 1)/n 13. Scriet, i o funct, ie recursiv˘a care primes, te ca parametru un num˘ar natural n s, i returneaz˘a num˘arul obt, inut din n prin eliminarea cifrelor pare. De exemplu, pentru n = 134467, funct, ia returneaz˘a 137. 14. Se consider˘a un num˘ar natural care cont, ine cel mult 9 cifre s, i se pune problema determin˘arii num˘arului de cifre distincte ale num˘arului. Rezolvat, i problema folosind una sau mai multe funct, ii recursive. De exemplu, pentru n = 41242, se obt, ine 3 (cifrele distincte sunt 4, 1, 2). 1.6 Algoritmi de sortare. Algoritmi de c˘autare Tematic˘a Sortare prin insert, ie Sortare prin select, ie Metoda BubbleSort (sortarea prin interschimbare sau metoda bulelor) Sortare prin num˘arare Tehnica interclas˘arii Metoda QuickSort (sortarea rapid˘a folosind tehnica “Divide et impera”) C˘autare secvent, ial˘a C˘autare binar˘a Probleme 1. S˘a se scrie un program care ordoneaz˘a cresc˘ator elementele din prima jum˘atate a unui vector s, i descresc˘ator elementele din a doua jum˘atate. Num˘arul de elemente ale vectorului este par. Exemplu: Vectorul 8 2 9 4 5 7 dup˘a sortare devine 2 8 9 7 5 4. 2. Se consider˘a un set de obiecte caracterizate prin dimensiune ¸si culoare (sunt trei culori posibile: ro¸su, alb, albastru). S˘a se ordoneze obiectele dup˘a culoare (prima dat˘a obiectele ro¸sii, apoi cele albe ¸si la final cele albastre) astfel ˆıncˆat obiectele cu aceea¸si culoare s˘a fie ordonate cresc˘ator dup˘a dimensiune. Exemplu 16
Subiect și barem · pagina 17
Intrare: (4, alb), (3, ros, u), (6, ros, u), (5, albastru), (2, alb), (2, ros, u), (4, albastru), (1, ros, u) Ies, ire: (1, ros, u), (2, ros, u), (3, ros, u), (6, ros, u), (2, alb), (4, alb), (4, albastru), (5, albastru) Indicat, ie: Culoarea este reprezentat˘a ca s, ir de caractere. 3. Se dau ˆın˘alt, imile a n copii, numerotat, i de la 1 la n, exprimate prin numere naturale. Afis, at, i numerele de ordine ale copiilor ˆın ordinea cresc˘atoare a ˆın˘alt, imii lor. Exemplu Intrare: 80, 160, 120, 110, 90, 70, 100 Ies, ire: 6, 1, 5, 7, 4, 3, 2 4. Adaptat, i algoritmul de sortare prin num˘arare pentru ordonarea descresc˘atoare a unui tablou. 5. Scriet¸i o funct¸ie/procedur˘a care transform˘a un tablou unidimensional cu ele- mente numere reale, primit ca parametru, astfel ˆıncˆat elementele aflate pe pozit¸ii pare s˘a fie ordonate descresc˘ator, iar cele aflate pe pozit¸ii impare s˘a fie ordonate cresc˘ator (pozit¸iile sunt contorizate ˆıncepˆand cu 0, primul element este pe pozit¸ie par˘a, al doilea pe pozit¸ie impar˘a etc.). De exemplu, tabloul [5, 1, 7, 6, 2, 1, 8, 3] se transform˘a ˆın [8, 1, 7, 1, 5, 3, 2, 6]. 6. Se d˘a un vector x cu n elemente numere naturale, ordonate cresc˘ator, s, i un vector y cu m elemente, de asemenea numere naturale. Verificat, i pentru fiecare element al vectorului y dac˘a apare ˆın x. Indicat, ie: Folosit, i c˘autarea binar˘a s, i c˘autarea secvent, ial˘a. 7. Se dau n numere naturale distincte. Determinat¸i cˆate triunghiuri distincte pot avea lungimile laturilor printre aceste numere. Exemplu Intrare: 5 (num˘arul de elemente) s, i 3 5 10 7 6 (elementele tabloului), Ies, ire: 7 8. Se consider˘a dou˘a mult, imi A s, i B reprezentate prin tablouri avˆand elementele specificate ˆın ordine strict cresc˘atoare. S˘a se construiasc˘a tablourile ce cont, in reuniunea s, i intersect, ia lui A s, i B. Indicat, ie: Folosit, i tehnica interclas˘arii. 9. Se dau dou˘a ¸siruri, cu n, respectiv m elemente, numere naturale. Primul ¸sir este ordonat cresc˘ator, iar al doilea este ordonat descresc˘ator. S˘a se afi¸seze, ˆın ordine cresc˘atoare, valorile pare din cele dou˘a ¸siruri. Exemplu 17
Subiect și barem · pagina 18
Intrare: 5 (num˘arul de elemente ale s, irului 1), 2 4 7 37 42 (elementele
s, irului 1)
8 (num˘arul de elemente ale s, irului 2), 88 88 67 45 42 32 4 1 (elementele
s, irului 2)
Ies, ire: 2 4 4 32 42 42 88 88
Indicat, ie: Folosit, i tehnica interclas˘arii.
10. Se d˘a un num˘ar natural x s, i dou˘a tablouri a s, i b, cu n, respectiv m elemente,
numere naturale, ordonate strict cresc˘ator. S˘a se afis, eze, ˆın ordine cresc˘atoare,
multiplii lui x care se afl˘a doar ˆın unul dintre cele dou˘a s, iruri.
Indicat, ie: Se parcurg cele dou˘a tablouri ˆın paralel (ˆın manier˘a balansat˘a).
Dac˘a a[i] = b[j] atunci se ignor˘a s, i se progreseaz˘a ˆın ambele tablouri,
Altfel se verific˘a dac˘a valoarea mai mic˘a (dintre a[i] s, i b[j]) este multiplu al
lui x (dac˘a este, se ret, ine valoarea) s, i se progreseaz˘a ˆın tabloul care cont, ine
valoarea mai mic˘a.
11. La sect, ia de ˆımpachetare a produselor dintr-o fabric˘a lucreaz˘a n muncitori. Fie-
care muncitor ˆımpacheteaz˘a acelas, i tip de produs s, i, pentru fiecare, se cunoas, te
timpul necesar pentru ˆımpachetarea unui obiect. S˘a se determine durata minim˘a
de timp ˆın care vor ˆımpacheta cei n muncitori cel put, in M obiecte.
Exemplu
Intrare: 6 (num˘ar muncitori), 60 (num˘ar obiecte), 4 7 3 6 7 1 (durate)
Ies, ire: 30
Indicat, ie: Se simuleaz˘a cˆate un “cronometru” pentru fiecare muncitor utilizˆand
un vector ale c˘arui elemente se incrementeaz˘a pˆan˘a ajung la valoarea cores-
punz˘atoare timpului necesar ˆımpachet˘arii unui obiect (moment ˆın care se mar-
cheaz˘a faptul c˘a s-a finalizat ˆımpachetarea unui obiect s, i se reseteaz˘a “cronome-
trul”).
12. Fiind dat un tablou de numere ˆıntregi nesortate, transformat, i tabloul astfel ˆıncˆat
s˘a fie sortat ˆın form˘a de “und˘a”. Un tablou arr[0...n − 1] este sortat ˆın form˘a
de und˘a dac˘a arr[0] ≥ arr[1] ≤ arr[2] ≥ arr[3] ≤ arr[4] ≥ ....
Exemplu
Intrare: arr[] = {10, 5, 6, 3, 2, 20, 100, 80}
Ies, ire: arr[] = {10, 5, 6, 2, 20, 3, 100, 80} sau {20, 5, 10, 2, 80, 6, 100, 3} sau
alt tablou care respect˘a aceast˘a form˘a
Intrare: arr[] = {20, 10, 8, 6, 4, 2}
Ies, ire: arr[] = {20, 8, 10, 4, 6, 2} sau {10, 8, 20, 2, 6, 4} sau alt tablou care
respect˘a aceast˘a form˘a
Indicat, ie: Se ordoneaz˘a cresc˘ator tabloul, dup˘a care se interschimb˘a valorile
elementelor vecine (primul cu al doilea, al treilea cu al patrulea, al cincilea cu al
s, aselea etc.).
18Subiect și barem · pagina 19
13. Fiind dat˘a o mult, ime de intervale, verificat, i dac˘a se suprapun dou˘a dintre acestea.
Exemplu
Intrare: arr[] = {[1, 3], [5, 7], [2, 4], [6, 8]}
Ies, ire: Adev˘arat. Intervalele [1, 3] s, i [2, 4] se suprapun
Intrare: arr[] = {[1, 3], [7, 9], [4, 6], [10, 13]}
Ies, ire: Fals. Nu exist˘a nicio pereche de intervale care s˘a se suprapun˘a
Indicat, ie: Se ordoneaz˘a intervalele cresc˘ator dup˘a momentul de start s, i se com-
par˘a limita superioar˘a a unui interval cu limita inferioar˘a a intervalului urm˘ator.
Dac˘a prima valoare este mai mare decˆat a doua, atunci exist˘a suprapunere.
14. Se consider˘a un vector de numere distincte init, ial sortat ˆın ordine cresc˘atoare.
Vectorul a fost rotit ˆın sensul acelor de ceasornic de k ori. Pornind de la vectorul
rotit, determinat, i valoarea lui k.
Exemplu:
Intrare: v = {15, 18, 2, 3, 6, 12},
Ies, ire: 2
Explicat, ie: Vectorul init, ial este {2, 3, 6, 12, 15, 18}. Din el se obt, ine vectorul dat
dup˘a 2 rotat, ii.
Indicat, ie: Se determin˘a cel mai mic indice i cu proprietatea c˘a valoarea ele-
mentului de pe pozit, ia i este mai mare decˆat valoarea elementului de pe pozit, ia
i + 1.
1.7 Prelucr˘ari asupra ¸sirurilor de caractere
Tematic˘a
Algoritmi de prelucrare a s, irurilor de caractere:
Separarea unui text ˆın cuvinte.
Analiza propriet˘at, ilor unui s, ir de caractere (de exemplu, num˘arul de consoane/
vocale cont, inute, anagrame etc.).
Verificarea satisfacerii unor reguli ˆın construirea unui ¸sir de caractere.
G˘asirea de s, abloane ˆın text.
Observat, ie: Problemele se vor rezolva f˘ar˘a a folosi funct, ii predefinite de prelucrare
a s, irurilor de caractere.
19Subiect și barem · pagina 20
Probleme 1. Se d˘a un text de maxim 256 de caractere. S˘a se afle urm˘atoarele informat, ii despre textul dat. (a) Cˆate propozit, ii cont, ine textul? Separatorii de propozit, ie se consider˘a ca- racterele: “”, “!” s, i “?”. Obiectiv: Identificarea propozit, iilor din text Indicat, ie: Se va defini o funct, ie care primes, te ca parametru textul s, i va ˆıntoarce num˘arul de propozit, ii din text. ˆIn cadrul funct, iei se declar˘a un tablou cu separatorii de propozit, ie. Apoi se parcurge textul caracter cu caracter s, i se verific˘a dac˘a caracterul curent se afl˘a ˆın tabloul de separatori. Dac˘a da se va incrementa o variabil˘a care ret, ine num˘arul de propozit, ii din text. Observat, ie: Se presupune c˘a nu exist˘a 2 separatori de propozit, ie unul dup˘a altul de exemplu textul “Of!!!!!” nu este valid. (b) Pentru fiecare dintre propozit, iile din text s˘a se determine num˘arul de cu- vinte. Cuvintele unei propozit, ii sunt separate printr-un singur spat, iu. Scri- et, i o funct, ie care ˆıntoarce cea mai lung˘a propozit, ie din text (lungimea unei propozit, ii este definit˘a ca fiind num˘arul de cuvinte pe care le cont, ine). Obiectiv: Identificarea cuvintelor din text, calcul maximului dintr-o secvent, ˘a de valori Indicat, ie: Se va defini o funct, ie care primes, te ca parametru textul s, i va ˆıntoarce num˘arul maxim de cuvinte dintr-o propozit, ie. ˆIn cadrul funct, iei se declar˘a un tablou cu separatorii de propozit, ie. Apoi se parcurge textul caracter cu caracter s, i se verific˘a dac˘a caracterul curent este spat, iu. Dac˘a da, se va incrementa o variabil˘a care ret, ine num˘arul de cuvinte din text. Observat, ie: Atent, ie la ultimul cuvˆant din text, dac˘a dup˘a el nu este spat, iu nu se va num˘ara. (c) Scriet, i o funct, ie care returneaz˘a num˘arul de vocale s, i consoane din textul dat. Obiectiv: Parcurgerea unui text, num˘ararea caracterelor care apart, in unei mult, imi Indicat, ie: Se va defini o funct, ie care primes, te ca parametri textul s, i dou˘a referint, e ˆın care se vor stoca (ˆıntoarce) num˘arul de consoane s, i num˘arul de vocale. ˆIn cadrul funct, iei se declar˘a un tablou care cont, ine vocalele (litere mari s, i mici). Apoi se parcurge textul caracter cu caracter s, i se verific˘a dac˘a caracterul curent este ˆın intervalul [‘a’ . . . ‘z’] sau [‘A’ . . . ‘Z’]. Dac˘a este liter˘a, se verific˘a dac˘a apart, ine mult, imii de vocale ¸si, ˆın caz afirmativ, se cres, te num˘arul de vocale, altfel se cres, te num˘arul de consoane. 2. Anagrame (un cuvˆant este anagrama altui cuvˆant dac˘a este constituit din aceleas, i litere dar ˆın alt˘a ordine). De exemplu, “arc” este anagram˘a a cuvˆantului “rac”. 20
Subiect și barem · pagina 21
(a) S˘a se scrie o funct, ie care s˘a verifice dac˘a, ˆıntr-o pereche de cuvinte, un cuvˆant este anagrama celuilalt cuvˆant. Obiectiv: Verificarea propriet˘at, ilor unui cuvˆant Indicat, ie: Se va defini o funct, ie care primes, te ca parametri dou˘a cuvinte (s, iruri de caractere) s, i ˆıntoarce o valoare care specific˘a dac˘a cuvintele sunt sau nu anagrame. Dac˘a cuvintele nu au aceeas, i lungime ele nu sunt anagrame. Dac˘a cuvintele au aceeas, i lungime: se construiesc vectori de frecvent, e pentru fiecare cuvˆant (de cˆate ori apare o liter˘a ˆın cuvˆant); se verific˘a dac˘a vectorii de frecvent, e sunt identici, iar ˆın caz afirmativ cuvintele sunt anagrame. Observat, ie: O alt˘a implementare se poate baza pe construirea mult, imii de litere pentru fiecare cuvˆant ˆın ordine cresc˘atoare s, i apoi se verific˘a dac˘a cele dou˘a mult, imi sunt identice. (b) S˘a se scrie o funct, ie care verific˘a dac˘a o mult, ime de cuvinte este format˘a din anagrame ale aceluias, i cuvˆant. De exemplu, mult, imea “arc”, “rac”, “car” satisface proprietatea cerut˘a. Obiectiv: Verificarea propriet˘at, ilor unei mult, imii Indicat, ie: Se va defini o funct, ie care primes, te ca parametri o mult, ime de cuvinte (tablou de s, iruri de caractere) s, i ˆıntoarce o valoare care specific˘a dac˘a toate cuvintele din mult, ime sunt anagrame. Se defines, te o variabil˘a care va stoca o valoare (o numim esteAnagrama) care reprezint˘a faptul c˘a presupunem c˘a proprietatea pe care vrem sa o verific˘am este adev˘arat˘a. Se parcurge mult, imea de cuvinte ˆıncepˆand cu al doilea element al mult, imii s, i se verific˘a dac˘a primul element al mult, imii s, i elementul curent sunt ana- grame (folosind funct, ia definit˘a mai sus). Dac˘a nu sunt, atunci valoarea variabilei esteAnagrama se modific˘a pentru a reflecta c˘a proprietatea nu mai este satisf˘acut˘a. (c) S˘a se scrie o funct, ie care afis, eaz˘a pentru o mult, ime de cuvinte toate perechile de cuvinte anagrame. Obiectiv: Generarea submult, imilor unei mult, imi care verific˘a o proprietate Indicat, ie: Se va defini o funct, ie care primes, te ca parametri o mult, ime de cuvinte (tablou de s, iruri de caractere) s, i va afis, a submult, imile formate din cuvinte anagramate. Pentru a rezolva problema putem s˘a consider˘am un tablou de aparit, ii care s˘a ne spun˘a dac˘a cuvˆantul a fost sau nu folosit (afis, at). Se parcurge tabloul de cuvinte s, i, pentru fiecare cuvˆant, se verific˘a dac˘a exist˘a un alt cuvˆant care este anagrama acestuia (folosind funct, ia anterioar˘a care verific˘a dac˘a dou˘a cuvinte sunt anagrame). Un cuvˆant deja afi¸sat este marcat (ret¸inut ˆın tabloul de aparit¸ii) . 3. S˘a se genereze pentru un cuvˆant dat toate prefixele s, i sufixele acelui cuvˆant. Exemplu: pentru cuvˆantul “paranteza” 21
Subiect și barem · pagina 22
prefixele sunt “p”, “pa”, “par”, “para”, “paran”, “parant”, “parante”, “pa- rantez” Obiectiv: Generarea unor s, iruri care satisfac anumite propriet˘at, i Indicat, ie: Problema este asem˘an˘atoare cu problema afis, ˘arii elementelor unei matrici aflate sub diagonala principal˘a Sufixele sunt “a”, “za”, “eza”, “teza”, “nteza”, “anteza”, “ranteza”, “aran- teza” Indicat, ie: Problema este asem˘an˘atoare cu problema afis, ˘arii elementelor unei matrici aflate deasupra diagonalei principale 4. Se d˘a un tablou de cuvinte, format doar din litere mici. Afis, at, i s, irul de litere din care sunt formate cuvintele ˆın ordinea descresc˘atoare a literelor. Exemplu: pentru mult, imea de cuvinte “ana”, “are”, “mere” se obt, ine rrnmeeeaaa. Obiectiv: Folosire tablou de frecvent, e Indicat, ie: Se va defini o funct, ie care primes, te ca parametru un tablou de cuvinte (eventual lungimea tabloului). Se va declara un tablou ˆın care s˘a se poat˘a ret, ine frecvent, a de aparit, ie a fiec˘arei litere ˆın tabloul de cuvinte. Elementele tabloului vor fi init, ializate cu 0. Se vor parcurge toate elementele tabloului si pentru fiecare element (cuvˆant) se vor parcurge literele din care este format s, i se va incrementa ˆın tabloul de frecvent, e valoarea care corespunde indexului din tablou atas, at literei. De exem- plu dac˘a litera a apare de 3 ori ˆın text, frecvent, a atas, at˘a literei a va fi 3. Dup˘a construirea tabloului de frecvent, e, acesta se va parcurge de la sfˆars, it spre ˆınceput s, i, pentru fiecare valoare diferit˘a de 0, se va crea un ciclu pentru a afis, a litera de n ori. 5. Se d˘a un text s, i un cuvˆant pe care vrem s˘a ˆıl c˘aut˘am ˆın text. Propunet, i funct, ii care realizeaz˘a urm˘atoarele variante de c˘aut˘ari: (a) Identific˘a prima aparit, ie a cuvˆantului ˆın text s, i returneaz˘a indexul la care ˆıncepe cuvˆantul c˘autat (nu folosit, i ˆın implementarea algoritmului funct, ii deja implementate ˆın biblioteci care realizeaz˘a acelas, i lucru). ˆIn cazul ˆın care cuvˆantul nu este prezent ˆın text va ˆıntoarce valoarea −1. De exemplu, pentru textul “Ana are mere” ¸si cuvˆantul “are” se va returna 4, iar pentru cuvˆantul “care” se va returna −1. Obiectiv: G˘asirea unui subs, ir ˆıntr-un subs, ir (g˘asirea primei aparit, ii) Indicat, ie: Se defines, te o funct, ie care are ca parametri dou˘a cuvinte (s, iruri de caractere) s, i va ˆıntoarce indexul la care ˆıncepe prima aparit, ie a subs, irului ˆın s, ir (de exemplu pentru s, irul “abcdabcghbc” subs, irul “bc” se g˘ases, te pentru prima dat˘a la pozit, ia 1, ˆın cazul ˆın care indicii ˆıncep cu 0). Pentru rezolvare se poate folosi algoritmul fort, ei brute care presupune par- curgerea secvent, ial˘a a primului s, ir (caracter cu caracter) s, i verificarea fap- tului dac˘a nu cumva subs, irul ˆıncepe la acea pozit, ie. (b) Identific˘a toate aparit, iile cuvˆantului ˆın text s, i returneaz˘a un tablou care cont, ine indecs, ii la care ˆıncepe cuvˆantul c˘autat. Obiectiv: G˘asirea unui subs, ir ˆıntr-un subs, ir (g˘asirea tuturor aparit, iilor) 22
Subiect și barem · pagina 23
Indicat, ie: De exemplu, pentru s, irul “abcdabcghbc” subs, irul “bc” se g˘ases, te pe pozit, iile [1, 5, 9]. Se repet˘a prelucrarea de la subpunctul anterior. (c) Identific˘a ultima aparit, ie a cuvˆantului ˆın text s, i returneaz˘a indexul la care ˆıncepe cuvˆantul c˘autat, ˆın caz contrar va ˆıntoarce valoarea −1. Obiectiv: G˘asirea unui subs, ir ˆıntr-un subs, ir (g˘asirea ultimei aparit, ii) Indicat, ie: De exemplu, pentru s, irul “abcdabcghbc” subs, irul “bc” se g˘ases, te pe pozit, ia 9. Pentru rezolvare se poate folosi algoritmul fort, ei brute care presupune par- curgerea secvent, ial˘a a primului s, ir (caracter cu caracter) s, i verificarea faptu- lui dac˘a nu cumva subs, irul ˆıncepe la acea pozit, ie. ˆIn acest caz, pentru a face algoritmul put, in mai eficient, ˆın unele cazuri, se poate porni cu verificarea de la sfˆars, itul s, irului. 6. Elevii unei clase trebuie s˘a trimit˘a rezolv˘arile temelor la informatic˘a sub forma unei arhive zip care trebuie s˘a respecte urm˘atorul s, ablon de denumire clasaX nume premune zi-luna-an.zip. Temele care sunt trimise s, i nu res- pect˘a acest format de numire nu vor fi corectate. Exemplu: Dac˘a elevul Ionescu Ion din clasa a noua trimite urm˘atorul fis, ier clasa9 ionescu ion 02-04-2018.zip, tema lui va fi luat˘a ˆın considerare pentru corectare. Dac˘a elevul Vasilescu Vasile din clasa a unsprezecea trimite urm˘atorul fis, ier clasa 11 vasilescu vasile 02-03 2018.zip, tema lui nu va fi luat˘a ˆın considerare pentru corectare. Cerint, e: (a) Definit, i o funct, ie care permite profesorului s˘a verifice dac˘a numele fis, ierului trimis este corect sau nu (validarea se va face doar din punctul de vedere al structurii denumirii). Obiectiv: Verificarea dac˘a un s, ir de caractere respect˘a un s, ablon (pattern) Indicat, ie: Se va c˘auta, pentru ˆınceput, dac˘a exist˘a s, iruri de caractere preci- zate care trebuie s˘a se reg˘aseasc˘a pe anumite pozit, ii. De exemplu, subs, irul “clasa” trebuie s˘a fie la ˆınceputul cuvˆantului, iar subs, irul “.zip” la sfˆars, itul cuvˆantului. Apoi trebuie identificat, i separatorii, ˆın exemplul curent “ ” (liniut, ˘a de subliniere) s, i “-” (cratim˘a). Apoi se verific˘a dac˘a subs, irurile dintre aces, tia respect˘a regulile impuse de s, ablon. (b) Profesorul s, i-a construit un tablou cu nume de fis, iere. Determinat, i cˆate fis, iere cu formatul corect au fost trimise. Obiectiv: Verificarea ˆındeplinirii unei propriet˘at, i a elementelor unui tablou Indicat, ie: Se va defini o funct, ie care primes, te ca parametru tabloul de cuvinte, eventual s, i lungimea tabloului s, i ˆıntoarce num˘arul de cuvinte din s, ir care respect˘a s, ablonul definit mai sus. Obiectiv: Crearea unui nou s, ir de caractere pe baza propriet˘at, ilor unui alt s, ir de caractere 23
Subiect și barem · pagina 24
Indicat, ie: Se va parcurge tabloul de cuvinte s, i se va folosi funct, ia definit˘a la punctul (a) pentru a verifica dac˘a fiecare element al tabloului respect˘a sau nu s, ablonul. Dac˘a ˆıl respect˘a, atunci se va cres, te valoarea variabilei ˆın care se ret, ine num˘arul de elemente care respect˘a s, ablonul. (c) Ajutat, i profesorul s˘a creeze o statistic˘a care s˘a ˆıi spun˘a cˆate teme are de corectat la fiecare clas˘a pornind de la tablourile cu nume de fis, iere cores- punz˘atoare diferitelor clase (cˆate fis, iere ˆın formatul corect au fost trimise pentru fiecare clas˘a). Obiectiv: Creare de tabele de frecvent, ˘a, identificare chei ale tabelului de frecvent, ˘a Inidicat, ie: Pentru a simplifica problema, vom presupune c˘a clasele sunt de la 0 la 12 (s, i ˆın s, coal˘a exist˘a o singur˘a clas˘a pentru fiecare an). ˆIn acest caz, ne putem folosi de ideea de la tabloul de frecvent, e pentru a num˘ara cˆat, i elevi au submis fis, iere ˆın formatul corect, pentru fiecare clas˘a. Observat, ie: ˆIncercat, i s˘a rezolvat, i problema ˆın cazul general, cˆand nu s, tim cˆate clase de aceleas, i fel sunt ˆın s, coal˘a (de exemplu, exist˘a clasele 9A, 9B, 9C s, i clasele 10A, 10B). 7. Se dores, te reducerea num˘arului de caractere pe care este stocat un text (compri- marea textului) prin ˆınlocuirea caracterelor succesive care se repet˘a cu caracterul care se repet˘a s, i num˘arul de repet˘ari. De exemplu, textul “abbcdeeeeff” va de- veni “ab2cde4f”. (a) Propunet, i un algoritm de comprimare a unui text. Obiectiv: Modific˘ari asupra unui s, ir de caractere (inserare/s, tergere) Obiectiv: Crearea unui nou s, ir de caractere pe baza propriet˘at, ilor unui alt s, ir de caractere Indicat, ie: Se defines, te o funct, ie care primes, te ca parametru un s, ir de ca- ractere s, i returneaz˘a noul s, ir de caractere. Se parcurge caracter cu caracter s, irul init, ial s, i dac˘a dou˘a litere succesive sunt identice, atunci se m˘ares, te un contor ˆın care se stocheaz˘a num˘arul de litere identice g˘asite pˆan˘a ˆın momentul curent, iar dac˘a dou˘a litere succesive sunt diferite, atunci se adaug˘a, ˆın noul s, ir, litera. Dac˘a num˘arul de aparit, ii este mai mare ca 1 se adaug˘a s, i el, apoi se reseteaz˘a contorul la 1 deoarece s-a g˘asit o nou˘a liter˘a. (b) Pornind de la un text comprimat, propunet, i un algoritm prin care obt, inet, i textul init, ial (de exemplu, “ab2cde4f2” devine “abbcdeeeeff”). Obiectiv: Generarea unui s, ir de caractere care respect˘a anumite propriet˘at, i Indicat, ie: Se defines, te o funct, ie care primes, te ca parametru un s, ir de ca- ractere s, i returneaz˘a noul s, ir de caractere. Obiectiv: ˆInlocuirea unui subs, ir de caractere cu alt subs, ir de caractere ˆıntr- un s, ir Indicat, ie: Se defines, te o funct, ie care primes, te ca argumente dou˘a s, iruri de caractere (unul reprezint˘a cuvˆantul init, ial s, i cel˘alalt cuvˆantul ˆın p˘as˘areasc˘a) s, i ˆıntoarce o valoare de adev˘ar care specific˘a dac˘a cuvˆantul init, ial a fost corect transformat ˆın p˘as˘areasc˘a. 24
Subiect și barem · pagina 25
Se parcurge, caracter cu caracter, s, irul init, ial s, i dac˘a caracterul e liter˘a, atunci se adaug˘a la noul s, ir, iar dac˘a e cifr˘a, atunci se transform˘a ˆın num˘ar pentru a afla num˘arul de repet˘ari al literei. Dup˘a ce am aflat num˘arul de repet˘ari ale literei, ad˘augam la noul s, ir litera, de num˘arul de ori identificat. Observat, ie: Num˘arul de caractere care se repetaa poate fi mai mare de 9, deci rezult˘a c˘a cifrele sunt formate din dou˘a sau mai multe caractere. 8. Elevii unei clase s, i-au propus s˘a ˆınvet, e limba p˘as˘areasc˘a astfel ˆıncˆat au nevoie de un program care s˘a verifice dac˘a, pornind de la un cuvˆant, au identificat corect cuvˆantul ˆın limba p˘as˘areasc˘a. Scriet, i o funct, ie care verific˘a dac˘a cuvˆantul din p˘as˘areasc˘a este corect identificat/codificat. Funct, ia primes, te ca parametri cuvˆantul ˆın limba p˘as˘areasc˘a s, i cuvˆantul init, ial s, i ˆıntoarce o valoare de adev˘ar ˆın funct, ie de codificare. Codificarea ˆın limba p˘as˘areasc˘a presupune ˆınlocuirea fiec˘arei vocale astfel: “v” devine “vpv” ¸si p˘astrarea nemodificat˘a a consoanelor (de exemplu, “a” devine “apa”, iar “e” devine “epe”). De exemplu, cuvˆantul “capre”, ˆın p˘as˘areasc˘a, este “capaprepe”. Indicat, ie: Se va codifica cuvˆantul init, ial ˆın p˘as˘areasc˘a, apoi se vor verifica dac˘a cele dou˘a cuvinte sunt identice. 9. S˘a se verifice c˘a un cuvˆant este palindrom (citit de la dreapta la stˆanga s, i de la stˆanga la dreapta este acelas, i cuvˆant). De exemplu, cuvˆantul “caiac” este palindrom, iar cuvˆantul “cor” nu este. (a) Propunet, i o variant˘a iterativ˘a de rezolvare a problemei. Obiectiv: Verificarea propriet˘at, ilor unui s, ir de caractere, varianta iterativ˘a Indicat, ie: Se defines, te o funct, ie care primes, te ca argument un s, ir de ca- ractere s, i ˆıntoarce o valoare de adev˘ar care spune dac˘a funct, ia este sau nu palindrom. Se pornes, te cu doi iteratori: unul de la sfˆars, itul s, irului s, i unul de la ˆınceputul s, irului. Atˆata timp cˆat caracterele de pe pozit, iile indicate de cei doi iteratori sunt egale, se descres, te iteratorul care pornes, te de la sfˆars, itul s, irului s, i se cres, te iteratorul de la ˆınceputul s, irului, iar dac˘a cei doi iteratori ajung s˘a se dep˘as, easc˘a ˆınseamn˘a c˘a este palindrom, altfel nu. (b) Propunet, i o variant˘a recursiv˘a de rezolvare a problemei. Obiectiv: Verificarea propriet˘at, ilor unui s, ir de caractere, varianta recursiv˘a 10. Ionel scrie poezii, dar face mici gres, eli de tehnoredactare. Vom ˆıncerca s˘a ˆıl ajut˘am pe Ionel s˘a corecteze gres, elile le tehnoredactare. Dac˘a versurile poeziei sunt stocate ˆıntr-un tablou de s, iruri de caractere (fiecare element din tablou cont, ine un vers), trebuie s˘a corect˘am urm˘atoarele probleme: Obiectiv: Ad˘augarea/s, tergerea de caractere dintr-un s, ir de caractere, generarea de sufixe (a) Deoarece dorim s˘a folosim cˆat mai put, ine caractere pentru a stoca poezia, va trebui s˘a verific˘am dac˘a exist˘a caractere albe (spat, ii s, i/sau taburi) la ˆınceputul s, i sfˆars, itul fiec˘arui vers s, i s˘a le elimin˘am. Indicat, ie: Se defines, te o funct, ie care primes, te ca argument poezia (un tablou de s, iruri de caractere), eventual num˘arul de versuri (dimensiunea tabloului). 25
Subiect și barem · pagina 26
Se va parcurge fiecare vers al poeziei s, i pentru fiecare vers: se verific˘a dac˘a ultimele caractere ale versului sunt caractere albe s, i se s, terg prin deplasarea terminatorului de s, ir; se verific˘a dac˘a primele caractere sunt caractere albe: dac˘a da, atunci se deplaseaz˘a versul cu un caracter la stˆanga. (b) Din gres, eal˘a, Ionel a ad˘augat mai multe caractere albe (spat, ii s, i taburi) ˆıntre dou˘a cuvinte, acestea trebuie ˆınl˘aturate (de exemplu, “ O, ce p˘acat , o, ce p˘acat”, “C˘a n-a fost fotografiat”, “ acel moment ˆın˘alt, ˘ator”, “Cˆand, singur cuc, Apolodor”, “ a g˘aurit cu un topor”, “ Peret, ii marelui vapor!...” se transform˘a ˆın “O, ce p˘acat , o, ce p˘acat”, “C˘a n-a fost fotografiat”, “Acel moment ˆın˘alt, ˘ator”, “Cˆand, singur cuc, Apolodor”, ”A g˘aurit cu un topor”, “Peret, ii marelui vapor!...”. Indicat, ie: Se defines, te o funct, ie care primes, te ca argument poezia (un tablou de s, iruri de caractere), eventual num˘arul de versuri (dimensiunea tabloului). Se va parcurge fiecare vers al poeziei s, i, pentru fiecare vers, se verific˘a, caracter cu caracter, dac˘a dou˘a caractere succesive sunt caractere albe: dac˘a da, atunci se deplaseaz˘a restul versului cu un caracter la stˆanga. (c) Fiecare vers trebuie s˘a ˆınceap˘a cu liter˘a mare de tipar. Indicat, ie: Se defines, te o funct, ie care primes, te ca argument poezia (un tablou de s, iruri de caractere), eventual num˘arul de versuri (dimensiunea tabloului). Se va parcurge fiecare vers al poeziei s, i, pentru fiecare vers, se verific˘a dac˘a primul caracter este liter˘a mic˘a: dac˘a da, atunci se transform˘a ˆın liter˘a mare (de exemplu, prin sc˘aderea num˘arului de caractere dintre literele mici s, i literele mari). (d) O alt˘a problem˘a este legat˘a de faptul c˘a uneori ˆınainte de caracterele ’,’, ’ ?’, ’ !’ sau ’.’ s-a l˘asat un spat, iu liber s, i acesta trebuie eliminat sau s-a uitat s˘a se lase spat, iu dup˘a virgul˘a, punct, semnul exclam˘arii s, i semnul ˆıntreb˘arii. De exemplu, “Cˆand , singur cuc,Apolodor” trebuie ˆınlocuit cu “Cˆand, singur cuc, Apolodor”. Indicat, ie: Se defines, te o funct, ie care primes, te ca argument poezia (un tablou de s, iruri de caractere), eventual num˘arul de versuri (dimensiunea tabloului). Se va parcurge fiecare vers al poeziei s, i, pentru fiecare vers, se verific˘a dac˘a caracterul curent este unul din caracterele: .,?!, iar dac˘a da: Se verific˘a dac˘a ˆınaintea lui este spat, iu: dac˘a da, atunci se deplaseaz˘a s, irul r˘amas cu o pozit, ie la dreapta; Se verific˘a dac˘a dup˘a el este spat, iu: dac˘a nu, atunci se deplaseaz˘a s, irul r˘amas cu o pozit, ie la dreapta s, i se adaug˘a spat, iul (Atent, ie: dac˘a este spat, iu trebuie s˘a deplas˘am la dreapta; dup˘a ultimul caracter nu trebuie s˘a ad˘aug˘am spat, iu). (e) Verificat, i tipul de rim˘a al poeziei: ˆımperecheat˘a (aabb), ˆıncrucis, at˘a (abab), ˆımbr˘at, is, at˘a (abba), monorima (aaaa) sau alb˘a, ˆın restul cazurilor. Spunem c˘a dou˘a cuvinte “rimeaz˘a” dac˘a sufixele ˆıncepˆand de la ultima vocal˘a sunt identice, sufixele trebuie s˘a aib˘a lungimea strict mai mare ca 1. Indicat, ie: Se defines, te o funct, ie care primes, te ca argument poezia (un tablou de s, iruri de caractere), din poezie lu˘am ˆın considerare doar primele patru versuri (pe baza lor determin˘am tipul de rim˘a). 26
Subiect și barem · pagina 27
Pentru fiecare vers din cele patru se ret, ine sufixul. Dup˘a ce s-au obt, inut sufixele, se verific˘a tipul de rim˘a. 11. Determinat, i num˘arul de cuvinte “magice” dintr-o propozit, ie. Cuvintele propo- zit, iei sunt separate de spat, ii. Un cuvˆant (L1L2L3...Ln−1Ln) este “magic” dac˘a satisface urm˘atoarea proprietate |Li − Li+1| = |Ln−i − Ln−i−1|, pentru oricare i = 1...n. De exemplu, ˆın propozit, ia “Miss Arora teaches us malayalam bdwy” sunt 4 astfel de cuvinte: Arora, us, Malayalam, bdwy. Indicat, ie: Se defines, te o funct, ie care primes, te ca argument propozit, ia (un s, ir de caractere), se parcurg literele propozit, iei, iar cˆand se ˆıntˆalnes, te caracterul spat, iu, se consider˘a c˘a s-a g˘asit un cuvˆant s, i se verific˘a proprietatea de cuvˆant “magic”. 1.8 Structuri de date pentru grafuri Tematic˘a Concepte s, i modalit˘at, i de reprezentare pentru grafuri neorientate, grafuri orientate, arbori Reprezentarea grafurilor neorientate, a grafurilor orientate ¸si a arborilor Algoritmi de traversare ¸si analiz˘a a grafurilor ¸si arborilor Propriet˘at¸i ale grafurilor Aplicat¸ii Probleme 1. Se cite¸ste un graf neorientat din fi¸sierul muchii.txt ˆın care avem pe prima linie num˘arul n de noduri ¸si cel de muchii separate prin spat¸iu, iar pe fiecare din liniile urm˘atoare avem nodurile unei muchii separate prin spat¸iu. Se presupune c˘a n ≤ 50. (a) Pentru fiecare nod, afi¸sat¸i gradul ¸si muchiile incidente la acel nod. (b) Afi¸sat¸i num˘arul de noduri ¸si matricea de adiacent¸˘a a grafului. 2. Se citesc dou˘a grafuri neorientate, unul cu n ≤ 100 vˆarfuri ¸si m muchii, iar cel˘alalt cu k ≤ 100 vˆarfuri ¸si r muchii, ambele reprezentate prin lista de muchii. S˘a se determine dac˘a al doilea graf este subgraf al primului graf. 3. Se d˘a un graf neorientat cu n ≤ 100 noduri, pentru care se cunoa¸ste matricea de adiacent¸˘a a. S˘a se determine componentele conexe ale grafului ¸si apoi s˘a se indice: (a) num˘arul de componente conexe (b) pentru fiecare component˘a conex˘a: 27
Subiect și barem · pagina 28
nodurile care fac parte din componenta respectiv˘a dac˘a are sau nu un ciclu. 4. Se d˘a un graf neorientat cu n ≤ 50 noduri, pentru care se cunoa¸ste matricea de adiacent¸˘a a. Determinat¸i num˘arul minim de culori cu care se pot colora nodurile grafului astfel ˆıncˆat oricare dou˘a noduri adiacente s˘a aibe culori diferite. Afi¸sat¸i pentru fiecare culoare nodurile care se coloreaz˘a cu ea. 5. Se cite¸ste un graf orientat din fi¸sierul muchii.txt ˆın care avem pe prima linie num˘arul n de noduri ¸si cel de muchii separate prin spat¸iu, iar pe fiecare din liniile urm˘atoare avem nodurile unei muchii separate prin spat¸iu. Se presupune c˘a n ≤ 50. Apoi se cite¸ste de la consol˘a un num˘ar ˆıntreg m astfel ˆıncˆat 0 < m ≤ n. S˘a se afi¸seze: (a) Cˆate subgrafuri cu m noduri ale grafului citit sunt circuite elementare. (b) Num˘arul maxim de muchii al unui subgraf cu m noduri. 6. Se d˘a un graf orientat cu n ≤ 50 noduri, care se cite¸ste dintr-un fi¸sier text muchii.txt ˆın care avem pe prima linie num˘arul n de noduri ¸si cel de muchii se- parate prin spat¸iu, iar pe fiecare din liniile urm˘atoare avem nodurile unei muchii separate prin spat¸iu. S, tiind c˘a: Un drum hamiltonian este un drum care viziteaz˘a fiecare nod al grafului exact o dat˘a. Un ciclu hamiltonian este un ciclu care viziteaz˘a fiecare nod o singur˘a dat˘a (cu except, ia nodului care este s, i primul s, i ultimul). Un graf care cont, ine un ciclu hamiltonian se numes, te graf hamiltonian. Un drum eulerian este un drum care traverseaz˘a fiecare muchie exact o dat˘a. Un ciclu eulerian este un ciclu care parcurge fiecare muchie exact o dat˘a. Un graf care cont, ine un ciclu eulerian este numit graf eulerian. s˘a se determine (a) Dac˘a graful este hamiltonian. Dac˘a este, s˘a se afi¸seze un circuit hamilto- nian. (b) Dac˘a graful este eulerian. Dac˘a este, s˘a se afi¸seze un circuit eulerian. 7. Se d˘a un arbore binar cu ≤ 100 noduri reprezentat prin vectorii de descendent¸i S ¸si D. Pentru fiecare nod i, S[i] este descendentul stˆang al nodului i, ¸si D[i] este descendentul drept al nodului i. Dac˘a S[i] = 0 atunci nodul i nu are descendent stˆang, iar dac˘a D[i] = 0 atunci nodul i nu are descendent drept. Afi¸sat¸i pe rˆanduri separate: Frunzele arborelui Nodurile cu un singur descendent direct Nodurile cu 2 descendent¸i direct¸i 8. Se d˘a un arbore binar cu ≤ 100 noduri reprezentat prin vectorii T ¸si P: T[i] este nodul tat˘a al nodului i; dac˘a nodul i nu are nod tat˘a atunci T[i] = 0. 28
Subiect și barem · pagina 29
P[i] = −1 dac˘a nodul i este descendent stˆang; P[i] = 1 dac˘a nodul i este descendent drept. Calculat¸i ¸si afi¸sat¸i vectorii S ¸si D de descendent¸i ai nodurilor grafului: S[i] este descendentul stˆang al nodului i, ¸si D[i] este descendentul drept al nodului i. Dac˘a S[i] = 0 atunci nodul i nu are descendent stˆang, iar dac˘a D[i] = 0 atunci nodul i nu are descendent drept. 9. Se cite¸ste un graf conex neorientat cu n ≤ 100 noduri ¸si m muchii etichetate prin costui pozitive. Graful se cite¸ste dintr-un fi¸sier text muchii.txt ˆın care avem pe prima linie num˘arul n de noduri ¸si num˘arul m de muchii separate prin spat¸iu, iar pe fiecare din liniile urm˘atoare avem nodurile ¸si costul unei muchii separate prin spat¸iu. Se presupune c˘a ˆın fi¸sier, muchiile apar ˆın ordinea cresc˘atoare a costului lor. S˘a se determine un arbore de acoperire cu cost minim al grafului citit, ¸si s˘a se afi¸seze muchiile acestuia. 29
Subiect și barem · pagina 30
Capitolul 2
Subiecte date la Concursul FMI
2.1 Edit, ia a III-a (2017)
1. Un num˘ar natural nenul este considerat binar simetric dac˘a reprezentarea sa ˆın
baza 2 este un s, ir simetric (prima cifr˘a binar˘a coincide cu ultima, a doua cu
penultima etc.). De exemplu, 27 este binar simetric ˆıntrucˆat s, irul binar cores-
punz˘ator 110011 este simetric.
(a) Scriet, i o funct, ie (C/C++/Pascal) care primes, te ca parametru de intrare un
num˘ar natural s, i returneaz˘a num˘arul de cifre binare (de exemplu, 27 are 5
cifre binare).
(b) Scriet, i o funct, ie (C/C++/Pascal) care primes, te ca parametru de intrare un
num˘ar natural n s, i o valoare k cuprins˘a ˆıntre 1 s, i num˘arul de cifre binare
ale lui n s, i returneaz˘a cifra binar˘a de ordin k (cifra binar˘a de ordin 1 este
cea mai put, in semnificativ˘a).
(c) Scriet, i o funct, ie (C/C++/Pascal) care primes, te ca parametru de intrare un
num˘ar natural s, i returneaz˘a 1 dac˘a num˘arul este binar simetric s, i 0 ˆın caz
contrar. Pentru verificarea propriet˘at, ii nu se vor folosi tablouri.
2. Se consider˘a un s, ir de numere ˆıntregi distincte, nu neap˘arat ordonat, s, i se pune
problema descompunerii sale ˆıntr-un numar cˆat mai mic de subs, iruri cresc˘atoare
astfel ˆıncˆat fiecare element din s, irul init, ial s˘a se afle exact ˆıntr-un subs, ir, iar ordi-
nea relativ˘a dintre elementele s, irului init, ial s˘a se conserve s, i ˆın cazul subs, irurilor.
De exemplu, s, irul init, ial (13, 4, 21, 16, 18, 5, 3) se poate descompune ˆın subs, irurile
{(13, 21), (4, 16, 18), (5), (3)} sau ˆın subs, irurile {(13, 16, 18), (4, 5), (21), (3)}.
(a) Propunet, i o metod˘a de construire a subs, irurilor.
(b) Scriet, i programul (C/C++/Pascal) care implementeaz˘a metoda propus˘a.
Programul va citi de la tastatur˘a s, irul de numere s, i va afis, a subs, irurile
determinate.
3. Se consider˘a o matrice p˘atratic˘a de dimensiune n × n cu elemente numere reale
s, i se pune problema reorganiz˘arii ei astfel ˆıncˆat la parcurgerea elementelor ˆın
spiral˘a, pornind de la elementul din colt, ul din stˆanga sus, ˆın sensul acelor de
ceasornic, s˘a se obt, in˘a un s, ir ordonat cresc˘ator.
30Subiect și barem · pagina 31
(a) Scriet, i o funct, ie/procedur˘a (C/C++/Pascal) care construies, te un tablou ordonat cresc˘ator ce cont, ine toate cele n2 elemente ale matricii. (b) Scriet, i o funct, ie/procedur˘a (C/C++/Pascal) care plaseaz˘a elementele din tabloul construit la etapa anterioar˘a, sub forma unei spirale care ˆıncepe din colt, ul Stˆanga-sus al matricii, ˆın sensul acelor de ceasornic. Exemplu: Intrare: 1 4 2 5 3 5 7 9 0 8 7 4 1 3 5 2 Rezultat: (a) 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 5, 7, 7, 8, 9 (b) 4. Se consider˘a o succesiune de (n − 1 celule care cont, in operatori de inegalitate (“<”, respectiv“>”) s, i se dores, te s˘a se plaseze toate valorile naturale 1, 2, . . . , n ˆıntre celule (inclusiv ˆınaintea primeia s, i dup˘a ultima) astfel ˆıncˆat orice triplet de elemente consecutive < num˘ar, operator, num˘ar > s˘a exprime relat, ia corect˘a dintre cele dou˘a numere. Exemplu: Pentru succesiunea de operatori: > < < > > < se poate obt, ine (solut, ia nu este unic˘a): 2 > 1 < 3 < 6 > 5 > 4 < 7 Scriet, i un program (C/C++/Pascal) care cites, te de la tastatur˘a secvent, a de ope- ratori (ca s, ir de caractere) s, i afis, eaz˘a o secvent, ˘a de valori s, i operatori intercalate care satisfac cerint, ele (pentru exemplul de mai sus se cites, te “><<>><” s, i se afis, eaz˘a 2 > 1 < 3 < 6 > 5 > 4 < 7). Not˘a: 1. Pentru funct, ii/proceduri se vor specifica parametrii s, i se vor declara variabilele locale (dac˘a este cazul). 2. ˆIn cazul fiec˘arei probleme se va descrie ideea de rezolvare ˆın limbaj natural sau se vor pune comentarii explicative ˆın cadrul codului. 31
Subiect și barem · pagina 32
BAREM Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. Problema 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15 pct. (a) (definire funct, ie, declarat, ii - 1p, calcul corect num˘ar bit, i - 4p) . . . . . . 5 pct (b) (definire funct, ie, declarat, ii - 1p, calcul corect cifra binar˘a - 4p) . . . . . .5 pct (c) (definire funct, ie, declarat, ii - 1p, verificare simetrie - 4p) . . . . . . . . . . . . .5 pct Problema 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25 pct. (a) (descrierea unei metode corecte de construire a subs, irurilor) . . . . . . . 10 pct (b) (declarat, ii - 1p, citire s, ir - 1p, afis, are subs, iruri - 3p, construire subs, iruri - 10p) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 pct Problema 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .30 pct. (a) (definire funct, ie, declarat, ii - 1p, parcurgere matrice - 2p, construire tablou ordonat - 7p) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct (b) (construire matrice cu elemente plasate corect) . . . . . . . . . . . . . . . . . . . . 20 pct Problema 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20 pct. (declarat, ii - 1p, citire s, ir operatori - 1p, construirea unui s, ir de valori ce satisface restrict, iile - 15p, afis, are secvent, a de valori si operatori intercalate - 3p) 32
Subiect și barem · pagina 33
2.2 Edit, ia a IV-a (2018)
1. (30p)
(a) (5p) Se consider˘a funct, ia f : N∗ × N∗ → N definit˘a prin:
f (m, n) =
{m dac˘a m < n
f(m-n, n) dac˘a m ≥ n
i. Scriet, i o funct, ie recursiv˘a ˆın C/Pascal care primes, te doi parametri m
s, i n de tip ˆıntreg s, i returneaz˘a valoarea f (m, n);
ii. Ce returneaz˘a funct, ia atunci cˆand este apelat˘a pentru dou˘a valori na-
turale nenule?
(b) (5p) Se s, tie c˘a orice num˘ar natural nenul poate fi scris, ˆın mod unic, ca
o sum˘a de termeni distinct, i care sunt puteri naturale ale 2. De exemplu,
9 = 23 + 20, 15 = 23 + 22 + 21 + 20, 32 = 25. Scriet, i o funct, ie care primes, te
ca parametru un num˘ar natural nenul, n, s, i returneaz˘a returneaz˘a num˘arul
de termeni distict, i din descompunerea lui n ca sum˘a de puteri ale lui 2.
(c) (5p) Se consider˘a un num˘ar natural mare (ce cont, ine cel put, in 100 de cifre)
specificat prin secvent, a cifrelor sale, (ck, ck−1, . . . , c1, c0) (cu ck cifra cea
mai semnificativ˘a s, i c0 cifra cea mai put, in semnificativ˘a). Scriet, i o funct, ie
care primes, te ca parametri num˘arul de cifre s, i un tablou ce cont, ine cifrele
num˘arului s, i returneaz˘a 1 dac˘a num˘arul este divizibil cu 15 s, i 0 ˆın caz
contrar.
(d) (5p) Se consider˘a o matrice p˘atratic˘a A cu n linii s, i n coloane s, i se presupune
c˘a elementele aflate sub diagonala principal˘a sunt stocate ˆıntr-un tablou
prin parcurgerea linie cu linie a matricii. Tabloul va cont, ine elementele
a21, a31, a32, a41, a42, a43 . . . . Presupunˆand c˘a indicii tabloului pornesc de la
1, stabilit, i care este indicele ˆın tablou al elementului aij din matrice (i > j) :
i. (j − 2)(j − 1)/2 + i;
ii. (i − 2)(i − 1)/2 + j;
iii. (i − 2)(j − 1)/2 + i;
iv. (j − 2)(i − 1)/2 + j;
v. niciuna dintre variante nu e corect˘a.
(e) (5p) Coeficientul de “palindromitate” al unui s, ir de numere naturale (b1, b2,
. . . , bk) se defines, te ca fiind num˘arul minim de operat, ii de incrementare
care ar trebui aplicate unor elemente din s, ir, astfel ˆıncˆat s, irul s˘a devin˘a
palindrom (b1 = bk, b2 = bk−1 etc.).
i. Scriet, i relat, ia matematic˘a de calcul a coeficientului de “palindromi-
tate”;
ii. Scriet, i o funct, ie care primes, te ca parametru un tablou cu valori naturale
s, i returneaz˘a valoarea coeficientului.
(f) (5p) Se consider˘a un graf neorientat cu n = 6 noduri specificat prin lista
muchiilor sale: (1, 2), (1, 3), (2, 3), (2, 4), (3, 6), (4, 5), (4, 6), (5, 6).
i. Desenet, i graful.
33Subiect și barem · pagina 34
ii. Este graful conex?
iii. Care este num˘arul minim de muchii care ar trebui eliminate pentru
ca graful s˘a devin˘a conex? Dat, i un exemplu de muchii prin a c˘aror
eliminare graful devine neconex.
2. (20p) Se consider˘a un set de n (10 ≤ n ≤ 100) segmente de dreapt˘a specificate
prin coordonatele extremit˘at, ilor lor care sunt stocate ˆıntr-o matrice A cu n linii
s, i 4 coloane avˆand elemente numere reale. Fiecare linie din matrice cont, ine coor-
donatele a dou˘a puncte ˆın plan: ai1 s, i ai2 reprezint˘a abscisa, respectiv ordonata
primei extremit˘at, i, iar ai3 s, i ai4 reprezint˘a abscisa, respectiv ordonata celei de a
doua extremit˘at, i.
(a) (5p) Scriet, i o funct, ie/procedur˘a care afis, eaz˘a num˘arul de segmente de dreap-
t˘a orizontale s, i num˘arul de segmente de dreapt˘a verticale.
(b) (5p) S, tiind c˘a lungimea unui segment determinat de dou˘a puncte avˆand co-
ordonatele (xi, yi), respectiv (xj , yj ) este √(xi − xj )2 + (yi − yj )2, scriet, i o
funct, ie care primes, te ca parametri coordonatele a dou˘a puncte s, i returneaz˘a
lungimea segmentului determinat de ele.
(c) (10p) Scriet, i o funct, ie/procedur˘a care transform˘a matricea A, astfel ˆıncˆat
liniile sale s˘a fie ordonate cresc˘ator dup˘a lungimea segmentului pe care ˆıl
reprezint˘a.
3. (20p) Pentru un num˘ar natural n definim d(n) ca fiind suma dintre n s, i suma
cifrelor sale. De exemplu, d(75) = 75 + 7 + 5 = 87. Num˘arul n este considerat
generator pentru d(n) (75 este generator pentru 87). Un num˘ar natural nenul m
este considerat auto-num˘ar dac˘a nu exist˘a niciun num˘ar n < m cu proprietatea
c˘a n este generator pentru m (adic˘a m 6 = d(n) pentru orice n < m).
(a) (5p) Scriet, i o funct, ie care primes, te un num˘ar natural n s, i returneaz˘a valoa-
rea lui d(n).
(b) (10p) Scriet, i o funct, ie care determin˘a num˘arul maxim de generatori pe care
ˆıi poate avea un num˘ar cu k cifre (2 ≤ k ≤ 4).
(c) (5p) Scriet, i o funct, ie/procedur˘a care afis, eaz˘a toate auto-numerele care au
cel mult k cifre (2 ≤ k ≤ 4).
4. (20p) Se consider˘a un set S de m s, iruri de caractere ce cont, in simboluri din
mult, imea {a, b} s, i se pune problema identific˘arii unor subs, iruri cˆat mai lungi
care verific˘a s, ablonul “anban”=“aa . . . a︸ ︷︷ ︸
n ori
b aa . . . a︸ ︷︷ ︸
n ori
” (n ≥ 1). De exemplu, ˆın s, irul
“abbaaabaaabaab” cel mai lung subs, ir care respect˘a s, ablonul este “aaabaaa” (cu
n = 3).
(a) (10p) Scriet, i o funct, ie care primes, te ca parametru un s, ir de caractere s, i
returneaz˘a valoarea n corespunz˘atoare celui mai lung subs, ir care respect˘a
s, ablonul. Dac˘a un astfel de subs, ir nu exist˘a, se returneaz˘a 0.
(b) (10p) Declarat, i o variabil˘a ˆın care se poate stoca setul de s, iruri de caractere.
Scriet, i o funct, ie care afis, eaz˘a cel mai lung subs, ir care respect˘a s, ablonul s, i
este comun tuturor s, irurilor din setul S.
34Subiect și barem · pagina 35
Not˘a: 1. Limbajul de programare este la alegere ˆıntre C/C++ s, i Pascal. 2. Pentru fiecare dintre funct, iile/subprogramele scrise se vor specifica toate decla- rat, iile de variabile globale s, i locale necesare s, i se vor pune comentarii explicative. NU este necesar˘a scrierea programului principal s, i nici preluarea datelor prin citire. BAREM Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. Problema 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .30 pct. 1a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (i. descriere corect˘a a funct, iei recursive - 3p; ii. funct, ia determin˘a restul ˆımp˘art, irii ˆıntregi a lui m la n - 2p) 1b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declararea corect˘a a funct, iei, a variabilelor locale s, i returnarea rezultatului - 1p; contorizarea num˘arului de cifre egale cu 1 din reprezentarea ˆın baza 2 a num˘arului - 4p) 1c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declararea corect˘a a funct, iei, a variabilelor locale s, i returnarea rezultatului - 1p; verificare divizibilitate cu 3 (suma tuturor cifrelor este divizibil˘a cu 3) - 2p; verificare divizibilitate cu 5 (cifra cea mai put, in semnificativ˘a este 0 sau 5) - 2p) 1d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (ii. pozit, ia elementului aij ˆın tablou este (i − 2)(i − 1)/2 + j - 5p) 1e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (i. ∑[k/2] i=1 |bi − bk−i+1| - 2p; ii. declararea corect˘a a funct, iei, a variabilelor locale s, i returnarea rezultatului - 1p; calculul corect al coeficientului - 2p) 1f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (i. desen corect al grafului - 1p; ii. da, graful este conex - 1p; iii. trebuie eliminate minim dou˘a muchii - 2p; exemplu corect de muchii eliminate (de exemplu, (2, 4) s, i (3, 6) - 1p) Problema 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20 pct. 2a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declararea corect˘a a funct, iei, a variabilelor locale s, i afis, area rezultatelor - 1p; contorizarea corect˘a a segmentelor orizontale (segmentul i este orizontal dac˘a ai2 = ai4 , respectiv vertical dac˘a ai1 = ai3 ) - 4p) 2b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declararea corect˘a a funct, iei, a variabilelor locale s, i returnarea rezultatului - 1p; descrierea corect˘a a calculului lungimii unui segment - 4p) 35
Subiect și barem · pagina 36
2c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. (declararea corect˘a a funct, iei, a variabilelor locale/globale - 1p; implementarea corect˘a a algoritmului de sortare folosind funct, ia de la punctul (b) drept criteriu de sortare - 9p) Problema 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20 pct. 3a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declararea corect˘a a funct, iei, a variabilelor locale s, i returnarea rezultatului - 1p; calcul sum˘a cifre - 3p; calcul corect d(n) - 1p) 3b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. (declararea corect˘a a funct, iei, a variabilelor locale s, i afis, area rezultatelor - 1p; construirea unui tabel de frecvent, e corespunz˘ator valorilor de tip d(i) calculate pentru valori ale lui i cuprinse ˆıntre 1 s, i 10k − 1 - 7p; determinarea valorii maxime din tabelul de frecvent, e - 2p) 3c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declararea corect˘a a funct, iei, a variabilelor locale s, i afis, area rezultatelor - 1p; generarea corect˘a a auto-numerelor (de exemplu, parcurgˆand tabelul de frecvent, e construit la punctul anterior) - 4p) Problema 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20 pct. 4a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. (declararea corect˘a a funct, iei, a variabilelor locale s, i returnarea rezultatului - 1p; analiza tuturor subs, irurilor care respect˘a s, ablonul (de exemplu, pornind de la un subs, ir de forma “aba” s, i extinzˆandu-l ˆınspre stˆanga s, i dreapta cˆat este posibil) - 6p; determinarea corect˘a a parametrului n corespunz˘ator s, ablonului de lungime maxim˘a - 3p) 4b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. (declararea unei variabile care stocheaz˘a setul de s, iruri de caractere - 2p; declararea corect˘a a funct, iei s, i a variabilelor locale - 1p; determinarea pentru fiecare s, ir din set a lungimii maxime a unui subs, ir care respect˘a s, ablonul (folosind funct, ia de la punctul (a)) - 3p; determinarea valorii minime dintre lungimile maxime determinate - 2p; afis, area corect˘a a s, ablonului comun - 2p) 36
Subiect și barem · pagina 37
2.3 Edit, ia a V-a (2019)
1. (50p)
(a) (10p) Se consider˘a dou˘a numere naturale nenule x s, i y. S˘a se construiasc˘a
cel mai mare num˘ar z care este constituit din cifrele distincte care apar
atˆat ˆın x cˆat s, i ˆın y. De exemplu, pentru x = 46106 s, i y = 12156 se obt, ine
z = 61. Pentru determinarea lui z se vor scrie urm˘atoarele subprograme
(funct, ii/proceduri):
i. Un subprogram care primes, te ca parametru valorile x s, i y s, i construies, te
un tablou c cu 10 elemente avˆand proprietatea: c[i] = 1 dac˘a i este cifr˘a
comun˘a celor dou˘a numere s, i 0 ˆın caz contrar.
ii. Un subprogram care primes, te ca parametru tabloul c construit la punc-
tul i. s, i returneaz˘a num˘arul z.
(b) (10p) Se consider˘a o bucat˘a dreptunghiular˘a de tabl˘a de lungime m s, i l˘at, ime
n (m s, i n sunt numere naturale) s, i se pune problema sect, ion˘arii ei exacte
ˆıntr-un num˘ar cˆat mai mic de buc˘at, i identice de form˘a p˘atrat˘a.
i. Descriet, i pe scurt s, i argumentat, i modul ˆın care poate fi calculat˘a lun-
gimea laturii p˘atratului s, i num˘arul minim de t˘aieturi necesare pentru
a obt, ine toate p˘atratele.
ii. Scriet, i un subprogram care primes, te ca parametri valorile m s, i n s, i
afis, eaz˘a :
A. num˘arul minim de p˘atrate;
B. num˘arul minim de t˘aieturi.
(c) (5p) Se consider˘a funct, ia f : N × N → N definit˘a prin:
f (a, b) =
0 dac˘a b = 0
f(2a, [b/2]) dac˘a b > 0, b este par
f(2a, [b/2]+a dac˘a b > 0, b este impar
unde [x] reprezint˘a partea ˆıntreag˘a a num˘arului x.
i. Care este valoarea funct, iei f pentru:
A. a = 3, b = 4;
B. a = 4, b = 3;
C. a s, i b dou˘a numere naturale arbitrare.
ii. Scriet, i o funct, ie recursiv˘a pentru calculul valorii f (a, b) pentru dou˘a
numere naturale a s, i b.
(d) (5p) Se consider˘a o matrice A cu m linii s, i n coloane s, i elemente din {0, 1}
care descrie relat, ia de prietenie pe o platform˘a social˘a (Aij = Aji = 1 dac˘a
i este prieten cu j s, i 0 ˆın caz contrar). Scriet, i un subprogram (funct, ie) care
primes, te ca parametru matricea s, i afis, eaz˘a persoana (persoanele) care au
num˘arul maxim de prieteni.
(e) (5p) Se pune problema acoperirii unei table de dimensiune 2 × m folosind
piese de dimensiune 1 × 2 sau 2 × 1. Fie V (m) num˘arul de variante ˆın care
poate fi acoperit˘a tabla de piese.
37Subiect și barem · pagina 38
i. Care dintre urm˘atoarele afirmat, ii este corect˘a? A. V (m) = C2 m; B. V (m) = m!; C. V (1) = 1, V (2) = 2, V (m) + V (m − 1) + V (m − 2), pentru m > 2; D. V (1) = 1, V (m) = 2V (m − 1), pentru m > 1. ii. Argumentat, i alegerea f˘acut˘a la punctul i. (f) (15p) Se consider˘a un set de n puncte ˆın plan date prin coordonatele lor car- teziene (numere ˆıntregi) stocate ˆın dou˘a tablouri x s, i y s, i se pune problema determin˘arii num˘arului de linii drepte care trec prin originea sistemului de axe de coordonate s, i cont, in cele n puncte. i. Scriet, i un subprogram (funct, ie/procedur˘a) care ordoneaz˘a tablourile x s, i y cresc˘ator dup˘a valoarea y/x (se presupune c˘a toate valorile x sunt nenule). Dup˘a ordonare, punctele vor fi ˆın ordinea cresc˘atoare a pantei dreptei determinat˘a de origine s, i punctul respectiv. ii. Scriet, i o funct, ie care primes, te tablourile x s, i y ordonate s, i returneaz˘a num˘arul de linii distincte care trec prin origine s, i cont, in toate cele n puncte. 2. (25p) Primarul oras, ului WWW dores, te s˘a instaleze o camer˘a de luat vederi ˆın oras, . Se consider˘a c˘a oras, ul are form˘a dreptunghiular˘a, cu str˘azi paralele s, i perpendi- culare situate la distant, e egale. Dreptunghiul corespunz˘ator oras, ului s, i str˘azile aferente sunt modelate printr-o gril˘a cu dimensiunea M × N (2 ≤ M, N ≤ 1000), ˆın nodurile c˘areia sunt plasate cl˘adirile (fiecare cl˘adire este modelat˘a printr-un “bet, is, or” de grosime neglijabil˘a a c˘arui ˆın˘alt, ime este egal˘a cu ˆın˘alt, imea cl˘adirii din acel punct). Camera de luat vederi urmeaz˘a s˘a fie instalat˘a la nivelul solului ˆın colt, ul stˆanga-sus (NORD-VEST) al oras, ului (punctul de coordonate (0, 0), unde nu se g˘ases, te nicio cl˘adire) s, i se presupune c˘a se poate roti complet ˆın orice plan relativ la pozit, ia ˆın care a fost instalat˘a. O camer˘a de luat vederi poate supraveghea cl˘adiri doar dac˘a le poate identifica part, ial sau integral. De exemplu, considerˆand un oras, de dimensiune 3×3, ˆın care ˆın˘alt, imile cl˘adirilor sunt cele marcate ˆın Figura 2.1, camera de luat vederi situat˘a la nivelul solului va putea identifica pe direct, ia SUD ambele cl˘adiri (de ˆın˘alt, ime 1 s, i 3), pe direct, ia EST va putea identifica doar cl˘adirea de ˆın˘alt, ime 3, iar pe direct, ia SUD-EST va vedea doar cl˘adirea de ˆın˘alt, ime 2 situat˘a pe diagonal˘a. Un alt exemplu de cl˘adiri vizibile pe o direct, ie dat˘a este ilustrat ˆın Figura 2.2 (cl˘adirile marcate cu linie continu˘a sunt vizibile, cela marcate cu linie ˆıntrerupt˘a sunt invizibile). (a) (15p) Scriet, i o funct, ie (denumit˘a viewSoutEast care primes, te ca parametri o matrice O ce cont, ine ˆın˘alt, imile cl˘adirilor s, i returneaz˘a num˘arul de cl˘adiri care pot fi supravegheate pe direct, iile EST, SUD s, i SUD-EST de c˘atre camera plasat˘a ˆın colt, ul (0, 0) la nivelul solului. (b) (5p) Se consider˘a o camer˘a de luat vederi care poate identifica cl˘adiri ˆıntr-o direct, ie arbitrar˘a (definit˘a de pozit, ia camerei (0, 0) s, i o pozit, ie specificat˘a (k1, k2) - corespunz˘atoare primei cl˘adiri pe aceast˘a direct, ie). Scriet, i for- mula general˘a a pozit, iei cl˘adirilor aflate pe direct, ia determinat˘a de (0, 0) s, i (k1, k2). 38
Subiect și barem · pagina 39
Figura 2.1 Figura 2.2
(c) (5p) Folosind funct, ia viewSouthEast s, i presupunˆand c˘a este definit˘a funct, ia
viewDir (care are ca parametri matricea O, valorile k1, k2 s, i returneaz˘a
num˘arul de cl˘adiri vizibile pe direct, ia definit˘a de (k1, k2)), descriet, i funct, ia
viewAll care returneaz˘a num˘arul total de cl˘adiri care pot fi supravegheate
atunci cˆand camera este instalat˘a ˆın (0, 0) la nivelul solului.
3. (15p) Fie P o permutare a numerelor de la 1 la n (n ∈ N). Not˘am cu SU S(P )
num˘arul minim de subs, iruri cresc˘atoare (elementele dintr-un subs, ir nu sunt
neap˘arat consecutive ˆın permutarea init, ial˘a) ˆın care poate fi descompus˘a P.
Not˘am, de asemenea, cu LDS(P ) lungimea celui mai lung subs, ir descresc˘ator al
lui P.
Exemplu: Fie P = {31254}. Atunci SU S(P ) = 2, pentru c˘a P nu e un s, ir
cresc˘ator (prin urmare, SU S(P ) > 1), dar putem descompune P ˆın P1 = (35)
s, i P2 = (124). De aemenea, LDS(P ) = 2, pentru c˘a P are subs, irul descresc˘ator
(32) (de lungime 2), dar P nu are subs, iruri descresc˘atoare de lungime 3.
(a) (3p) S˘a se argumenteze c˘a pentru orice permutare P, are loc SU S(P ) ≥
LDS(P ).
(b) (10p) Scriet, i un subprogram care construies, te o descompunere a unei per-
mut˘ari P ˆıntr-un num˘ar minim de subs, iruri cresc˘atoare.
(c) (2) Demonstrat, i, folosind rezultatul de la punctul (a), c˘a subprogramul
descris la punctul (b) realizeaz˘a descompunerea lui P ˆıntr-un num˘ar minim
de subs, iruri cresc˘atoare.
Not˘a:
1. Limbajul de programare este la alegere ˆıntre C/C++ s, i Pascal.
2. Pentru fiecare dintre subprogramele (funct, ii, proceduri) scrise se vor specifica
toate declarat, iile de variabile globale s, i locale necesare s, i se vor pune comentarii
explicative. NU este necesar˘a scrierea programului principal s, i nici preluarea
datelor prin citire.
39Subiect și barem · pagina 40
BAREM Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. Problema 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .50 pct. 1a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. 1(a)i. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declarat, ii variabile locale/globale, definire corect˘a subprogram (inclusiv lista de parametri) - 1p; algoritm corect de extragere a cifrelor - 2p; algoritm corect de construire a tabloului c care indic˘a corect cifrele comune - 2p) 1(a)ii. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declarat, ii variabile locale/globale, definire corect˘a subprogram (inclusiv lista de parametri) - 1p; algoritm corect de extragere a cifrelor - 2p; algoritm corect de parcurgere a elementelor tabloului c - 2p; algoritm corect de construire a num˘arului z - 2p) 1b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. 1(b)i. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (lungimea laturii este d = cmmd(m, n); num˘arul minim de t˘aieturi este m/d−1 (pe vertical˘a), respectiv n/d − 1 (pe orizontal˘a)) 1(b)ii. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 pct. (declarat, ii variabile locale/globale, definire corect˘a subprogram (inclusiv lista de parametri) - 1p; algoritm corect de calcul a celui mai mare divizor comun - 3p; algoritm corect de calcul a num˘arului de t˘aieturi s, i afis, area rezultatelor - 1p) 1c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. 1(c)i. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 pct. A. 12; B. 12; C. a ∗ b 1(c)ii. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 pct. (definire corect˘a a funct, iei (inclusiv lista de parametri s, i returnare rezultat) - 1p; implementare corect˘a a funct, iei recursive - 2p) 1d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declarat, ii variabile locale/globale, definire corect˘a subprogram (inclusiv lista de parametri) - 1p; parcurgere corect˘a a matricii s, i determinarea num˘arului maxim de prieteni (suma maxim˘a pe linie sau coloan˘a) - 2p; determinarea corect˘a s, i afis, area indicilor de linie (coloan˘a) pentru care suma este maxim˘a - 2p) 1e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. 1(e)i. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 pct. (R˘aspuns corect: C.) 1(e)ii. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 pct. (Dac˘a m = 1 atunci este o singur˘a posibilitate (o pies˘a de forma 2 × 1). Dac˘a ultima pies˘a completat˘a este de forma 2 × 1 atunci sunt V (m − 1) variante de 40
Subiect și barem · pagina 41
a completa primele m − 1 coloane. Dac˘a ultima pies˘a completat˘a este de forma 1 × 2 atunci penultima trebuie s˘a fie de aceeas, i form˘a s, i sunt V (m−2) variante de a completa primele m − 2 coloane. Deci dac˘a m > 2 are loc V (m) = V (m − 1) + V (m − 2).) 1f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 pct. 1(f)i. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 pct. (declarat, ii variabile locale/globale, definire corect˘a subprogram (inclusiv lista de parametri) - 1p; implementarea corect˘a a unui algoritm de sortare simultan˘a a tablourilor x s, i y (cu proprietatea c˘a y[i]/x[i] ≤ y[i + 1]/x[i + 1] - 6p) 1(f)ii. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 pct. (declarat, ii variabile locale/globale, definire corect˘a subprogram (inclusiv lista de parametri s, i returnarea rezultatului) - 1p; parcurgerea tablourilor sortate s, i con- torizarea corect˘a a num˘arului de linii (de exemplu, contorizˆand num˘arul de elemente (x[i], y[i]) cu proprietatea c˘a y[i] ∗ x[i + 1] 6 = y[i + 1] ∗ x[i] s, i ad˘augˆand 1) - 7p) Problema 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25 pct. 2a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 pct. (declarat, ii variabile locale/globale, definire corect˘a subprogram (inclusiv lista de parametri) - 1p; algoritm corect de contorizare a cl˘adirilor - 8p; implementarea corect˘a a parcurgerii cl˘adirilor pe direct, iile SUD, EST, SUD-EST - 6p) Idee de contorizare a num˘arului de cl˘adiri vizibile pe o direct, ie dat˘a (folosind propriet˘at, i referitoare la asem˘anarea triungiurilor): Pas 1. se pornes, te de la prima cl˘adire pe direct, ia dat˘a: m ← 1; Pas 2. se parcurg cl˘adirile k, pˆan˘a la prima cl˘adire pentru care hk/dk > hm/dm (sau pˆan˘a cˆand s-au parcurs toate cl˘adirile), unde hi = ˆın˘alt, ime cl˘adire, iar di este distant, a de la cl˘adirea i la punctul unde se afl˘a camera (ˆıntrucˆat cl˘adirile sunt la distant, e egale este suficient s˘a se considere di = i; fiecare cl˘adire k pentru care hk/dk < hm/dm se contorizeaz˘a ca fiind vizibil˘a. Pas 3. dac˘a exist˘a o cl˘adire k cu proprietatea hk/dk > hm/dm atunci m ← k (aceast˘a cl˘adire devine referint, ˘a ˆın raportul de asem˘anare) s, i se reia de la Pas 2. 2b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (Regula de calcul a pozit, iei cl˘adirii i pe direct, ia definit˘a de (0, 0) s, i (k1, k2) este: (k1 ∗ i, k2 ∗ i) - 5p) 2c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declarat, ii variabile locale/globale, definire corect˘a subprogram (inclusiv lista de parametri) - 1p; algoritm corect de contorizare s, i apeluri corecte ale funct, iilor viewSouthEast, viewDir - 4p) Problema 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15 pct. 3a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 pct. (Idee: Fie Q un subs, ir descresc˘ator al lui P de lungime LDS(P ). ˆIn orice descompunere a lui P ˆın subs, iruri cresc˘atoare, termenii din Q trebuie s˘a apar˘a ˆın subs, iruri diferite. Prin urmare, SU S(P ) ≥ LDS(P ).) 41
Subiect și barem · pagina 42
3b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. (declarat, ii variabile locale/globale, definire corect˘a subprogram (inclusiv lista de parametri) - 1p; parcurgere corect˘a a elementelor permut˘arii - 1p; algoritm corect de construire a subs, irurilor - 6p; completare corect˘a a subs, irurilor ˆın structura de date pentru care s-a optat (matrice, liste etc.) - 2p) Idee: se poate aplica o strategie de tip “greedy”: se parcurg elementele per- mut˘arii s, i se adaug˘a fiecare la primul subs, ir compatibil (ˆın care ultimul element ad˘augat este mai mic decˆat elementul curent), init, iind un nou subs, ir dac˘a ad˘augarea la unul existent nu este posibil˘a. 3c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 pct. (Fie m num˘arul de subs, iruri construite folosind algoritmul de la punctul (b). Vom demonstra c˘a m ≤ LDS(P ) (corectitudinea rezultˆand din proprietatea de la punctul (a) s, i aceast˘a observat, ie). Pentru aceasta e suficient s˘a cre˘am un subs, ir des- cresc˘ator care cont, ine un element din fiecare subs, ir creat folosind algoritmul “greedy” de la punctul (b). S˘a consider˘am ultimul element xm ad˘augat ˆın ultimul subs, ir Sm. xm a fost ad˘augat ˆın Sm (s, i nu ˆın Sm−1 pentru c˘a a existat un element xm−1 > xm ˆın Sm−1 la momentul ˆın care l-am ad˘augat pe xm (xm−1 “nu a permis” ad˘augarea lui xm ˆın subs, irul Sm−1). Pe de alt˘a parte, xm−1 este ˆın Sm−1 pentru c˘a exist˘a xm−2 ˆın Sm−2, cu xm−2 > xm−1 care “nu a permis” ca xm−1 s˘a fie ad˘augat ˆın subs, irul Sm−2 s, .a.m.d. ˆIn acest fel, am construit un s, ir descresc˘ator x1 > x2 > · · · > xm, xi ∈ Si.) 42
Subiect și barem · pagina 43
2.4 Edit, ia a VI-a (2021) 1. Se consider˘a funct, ia T descris˘a mai jos care primes, te un parametru ˆıntreg s, i returneaz˘a o valoare ˆıntreag˘a (operatorii DIV s, i MOD specific˘a cˆatul, respectiv restul ˆımp˘art, irii ˆıntregi). funct, ie T(n) dac˘a n=1 atunci returneaz˘a 1 sf dac˘a S ← 0 m ← n DIV 2 dac˘a n M OD 2 = 0 atunci m ← m − 1 sf dac˘a i ← 1 c^at timp i <= m execut˘a S ← S + T (i) ∗ T (n − i) i ← i + 1 sf c^at timp dac˘a n M OD 2 = 0 atunci x ← T (n/2) returneaz˘a 2 ∗ S + x ∗ x altfel returneaz˘a 2 ∗ S sf dac˘a sf funct, ie Ce valoare va returna funct, ia dac˘a este apelat˘a pentru n = 5? (a) 61 (b) 23 (c) 12 (d) 14 R˘aspuns corect (e) 15 2. Se consider˘a urm˘atoarea secvent, ˘a de prelucr˘ari prin care se completeaz˘a elemen- tele unui tablou a: pentru i ← 1, 200 execut˘a a[i] ← i ∗ i − i sf pentru Cˆate dintre elementele tabloului a au cifra unit˘at, ilor egal˘a cu 0? (a) 20 43
Subiect și barem · pagina 44
(b) 21 (c) 79 (d) 80 R˘aspuns corect (e) 81 (f) 82 Indicat, ie: Se determin˘a cˆate numere sunt multiplu de 5 de la 1 la 200 s, i de la 0 zero 199. 3. Pentru decorarea cu pitici artizanali a unei gr˘adini avem la dispozit, ie 130 de lei. S, tiind c˘a un pitic mare cost˘a 50 lei, un pitic mijlociu cost˘a 25 lei s, i un pitic mic cost˘a 10 lei, cˆate variante de decorare pot fi identificate astfel ˆıncˆat s˘a nu r˘amˆan˘a mai mult de 9 lei neutilizat, i? (a) 12 R˘aspuns corect (b) 10 (c) 13 (d) 5 Indicat, ie: Se poate construi arborele de parcurgere a spat, iului solut, iilor pornind de la nodul cu suma total˘a s, i ramificˆand prima dat˘a dup˘a pitici mari (pot fi 2, 1 sau 0), dupa aceea pentru pitici medii (de restul banilor se cump˘ar˘a pitici mici ca sa nu r˘amˆan˘a rest mai mare ca 9): 2 mari → 1 sau 0 medii (2 variante) 1 mare → 3, 2, 1, 0 medii (4 variante) 0 mari → 5, 4, 3, 2, 1, 0 medii (6 variante) ˆIn total 12 variante. 4. Cˆate zerouri are la sfˆars, it 2021! (factorialul num˘arului 2021)? (a) 202 (b) 420 (c) 500 (d) 501 (e) 503 R˘aspuns corect Indicat, ie: Se vor num˘ara numerele pˆan˘a la 2021 care sunt multipli de 5. Fiecare multiplu de 5 va ad˘auga un 0. Fiecare multiplu de 52 va ad˘auga cˆate un 0 ˆın plus pentru c˘a a fost deja num˘arat ca s, i multiplu de 5. Se va continua cu multiplii lui 53, apoi 54. 2021 / 5 = 404 2021 / 25 = 80 2021 / 125 = 16 2021 / 625 = 3 total = 503 44
Subiect și barem · pagina 45
5. Se consider˘a secvent, a de instruct, iuni care transform˘a un tablou x ce cont, ine n
valori reale:
pentru i ← 1, n − 1 execut˘a
dac˘a x[i] > x[i + 1] atunci
aux ← x[i]
x[i] ← x[i + 1]
x[i + 1] ← aux
sf dac˘a
sf pentru
Care dintre urm˘atoarele propriet˘at, i este satisfacut˘a de c˘atre elementele tabloului
x dup˘a execut, ia secvent, ei de mai sus?
(a) x[n] ≤ x[i] pentru orice i ∈ {1, 2, . . . , n}
(b) x[n] ≥ x[i] pentru orice i ∈ {1, 2, . . . , n} R˘aspuns corect
(c) x[i] ≤ x[i + 1] pentru orice i ∈ {1, 2, . . . , n − 1}
(d) x[i] ≥ x[i + 1] pentru orice i ∈ {1, 2, . . . , n − 1}
(e) x[1] ≤ x[i] pentru orice i ∈ {1, 2, . . . , n}
(f) x[1] ≥ x[i] pentru orice i ∈ {1, 2, . . . , n}
Indicat, ie: Prin interschimbarea elementelor vecine, valoarea maxim˘a va fi pla-
sat˘a pe ultima pozit, ie.
6. Se consider˘a un text stocat ˆıntr-un s, ir de caractere, s, cu n elemente indexate
ˆıncepˆand cu 1. Se pune problema transform˘arii s, irului de caractere prin elimina-
rea spat, iilor multiple (de exemplu s, irul de caractere ”un sir” este transformat
ˆın ”un sir”).
i ← 1
c^at timp i < n execut˘a
k ← 0
c^at timp s[i] =′ ′ execut˘a k ← k + 1; i ← i + 1; sf c^at timp
dac˘a k > 1 atunci
〈 fragment pseudocod 〉
n ← n − k + 1
i ← i − k
sf dac˘a
i ← i + 1
sf c^at timp
Care dintre fragmentele de cod asigur˘a eliminarea spat, iilor adit, ionale?
45Subiect și barem · pagina 46
(a) R˘aspuns corect j ← i c^at timp j <= n execut˘a s[j − k + 1] ← s[j] j ← j + 1 sf c^at timp (b) R˘aspuns corect j ← i h ← i − k + 1 c^at timp j <= n execut˘a s[h] ← s[j] j ← j + 1 h ← h + 1 sf cat timp (c) j ← i c^at timp j <= n execut˘a s[j − k] ← s[j] j ← j + 1 sf c^at timp (d) Niciuna din variantele propuse nu este corect˘a 7. Se consider˘a o secvent, ˘a de n valori naturale stocate ˆıntr-un tablou x cu elemente indexate ˆıncepˆand cu 1. ˆIn ipoteza c˘a secvent, a cont, ine exact o valoare egal˘a cu 0 se dores, te transformarea tabloului prin permutare circular˘a ˆınspre stˆanga, astfel ˆıncˆat valoarea 0 s˘a ajung˘a pe prima pozit, ie (de exemplu secvent, a (2, 1, 3, 0, 5, 4) este transformat˘a ˆın (0, 5, 4, 2, 1, 3)): i ← 1 c^at timp x[?a] 6 = 0 execut˘a aux ←?b pentru i ← 2, n execut˘a x[?c] ← x[?d] sf pentru x[?e] ← aux sf c^at timp Care dintre urm˘atoarele variante de completare a pseudocodului de mai sus asigur˘a cerint, a problemei? (a) ?a → 1, ?b → x[1], ?c → i − 1, ?d → i, ?e → n R˘aspuns corect (b) ?a → i, ?b → x[1], ?c → i − 1, ?d → i, ?e → n (c) ?a → 1, ?b → x[i], ?c → i − 1, ?d → i, ?e → n (d) ?a → n, ?b → x[n], ?c → i, ?d → i − 1, ?e → 1 46
Subiect și barem · pagina 47
(e) Niciuna din variante nu este corect˘a. 8. Pentru care din urm˘atoarele apeluri funct, ia F va returna valoarea 1? Varianta C int F(int n, int x) if (n<2) return 1; else if (n % 2 == 0) return F(n/x,x+1); else return 0; Varianta Pascal function F(n,x:integer):integer; begin if (n<2) then F := 1 else if (n MOD x=0) then F := F(n DIV x, x+1) else F := 0; end; (a) F (5040, 2) R˘aspuns corect (b) F (24, 2) R˘aspuns corect (c) F (25, 2) (d) F (36, 2) 9. Ce valoare va avea variabila k ˆın urma execut, iei secvent, ei de prelucr˘ari pentru un num˘ar natural nenul n (operatorul DIV produce cˆatul ˆımp˘art, irii ˆıntregi, iar [x] reprezint˘a partea ˆıntreaga a num˘arului x)? k ← 0 c^at timp n > 0 execut˘a n ← n/2 k ← k + 1 sf c^at timp (a) n/2 (b) [log2n] (c) n (d) [log2n] + 1 R˘aspuns corect 47
Subiect și barem · pagina 48
10. Se consider˘a matricea A = [ 1 1 1 0 ] Care este valoarea elementului de pe prima linie, prima coloan˘a (elementul din stˆanga sus) din matricea A100 = A ∗ A ∗ . . . ∗ A (de 100 de ori) (a) 100 (b) 1 (c) elementul cu indicele 100 din s, irul dat prin relat, ia de recurent˘a: f0 = 1, f1 = 1, fn = fn−1 + fn−2 R˘aspuns corect (d) elementul cu indicele 99 din s, irul dat prin relat, ia de recurent˘a: f0 = 1, f1 = 1, fn = fn−1 + fn−2 (e) 2100 11. Se consider˘a funct, ia recursiv˘a: funct, ie F (a) dac˘a a <= 3 returneaza 1 altfel returneaza F (a − 1) + F (a − 2) + F (a − 3) sf daca sf functie De cˆate ori se calculeaz˘a F(4) dac˘a primul apel este F(10)? (a) 25 (b) 24 R˘aspuns corect (c) 28 (d) 15 12. Ce va afis, a subprogramul de mai jos ˆın cazul apelului F(27)? subprogram F (n) dac˘a n <= 0 atunci afis, are(0) altfel afis, are( n ) F (n − 5) afis, are( n ) sf dac˘a sf subprogram 48
Subiect și barem · pagina 49
(a) 0 2 7 12 17 22 27 (b) 27 22 17 12 7 2 0 2 7 12 17 22 27 R˘aspuns corect (c) 27 22 17 12 7 2 -2 2 7 12 17 22 27 (d) 25 20 15 10 5 0 5 10 15 20 25 (e) 27 22 17 12 7 2 0 13. Se consider˘a un num˘ar natural n constituit din k + 1 cifre (n = ckck−1 . . . c1c0). Care sunt cifrele num˘arului m construit prin secvent, a de prelucr˘ari de mai jos ˆın ipoteza c˘a k=3? (operatorii DIV s, i MOD permit calculul cˆatului respectiv restului ˆımp˘art, irii ˆın domeniul numerelor ˆıntregi) p ← 1 m ← n M OD 10 n ← n DIV 10 q ← 1 c^at timp n 6 = 0 execut˘a q ← q + 1 pentru i ← 1, q execut˘a p ← p ∗ 10 sf pentru m ← (n M OD 10) ∗ p + m n ← n DIV 10 sf c^at timp (a) c00c10c20c3 (b) c30c20c10c0 (c) c300c20c1c0 (d) c3000c200c10c0 R˘aspuns corect (e) c0000c100c20c3 14. De cˆate ori se execut˘a instruct, iunea x ← x + 1 ˆın secvent, a de mai jos? x ← 0 pentru i ← 2, N execut˘a pentru j ← 1, i − 1 execut˘a x ← x + 1 sf pentru sf pentru (a) N (N − 1) (b) N (N − 1)/2 R˘aspuns corect 49
Subiect și barem · pagina 50
(c) N (N + 1)/2 (d) (N − 1)(i − 1) Indicat, ie: Num˘arul de execut, ii ale liniei x ← x + 1 este dat de calculul urm˘atoarei sume ∑N i=2 ∑i−1 j=1 1 = ∑N −1 i=1 i. 15. Se consider˘a un tabloul t cu n elemente indexate ˆıncepˆand cu 1 s, i urm˘atoarea secvent, ˘a de prelucr˘ari aplicate asupra elementelor tabloului: i ← 1 j ← n c^at timp i < j execut˘a c^at timp (t[i] > 0 si i <= n) execut˘a i ← i + 1 sf c^at timp c^at timp (t[j] < 0 si j >= 1) execut˘a j ← j − 1 sf c^at timp dac˘a i < j atunci aux ← t[i] t[i] ← t[j] t[j] ← aux sf dac˘a sf c^at timp Ce efect are secvent, a de prelucr˘ari asupra tabloului t? (a) Ordoneaz˘a cresc˘ator tabloul t (b) Plaseaz˘a elementele pozitive ˆın prima parte a tabloului t R˘aspuns corect (c) Nu se poate spune nimic despre structura tabloului t (d) Ordoneaz˘a decresc˘ator tabloul t (e) Plaseaz˘a elementele negative ˆın prima parte a tabloului t Problema 1 Se consider˘a un dreptunghi de dimensiune 2 × n (dou˘a linii s, i n coloane) s, i se dores, te acoperirea dreptunghiului cu piese de domino de forma 2 × 1 sau 1 × 2. 1. Propunet, i o funct, ie care determin˘a num˘arul de modalit˘at, i de acoperire exact˘a a dreptunghiului cu piese (nu pot s˘a r˘amˆan˘a port, iuni neacoperite iar piesele nu pot dep˘as, i conturul dreptunghiului). 2. ˆIn ipoteza c˘a dou˘a dintre celulele dreptunghiului aflate in colt, uri opuse sunt inaccesibile (de exemplu celula (1, 1) s, i celula (2, n) sau celule (2, 1) s, i celula (1, n)), propunet, i o funct, ie care determin˘a num˘arul de modalit˘at, i de acoperire exact˘a a dreptunghiului cu piese (exceptˆand celulele din cele dou˘a colt, uri). Prezentat, i pe scurt ideea de rezolvare s, i descriet, i solut, ia ˆın pseudocod sau ˆıntr-un limbaj de programare la alegere (C/C++, Pascal, Python). 50
Subiect și barem · pagina 51
Idee de rezolvare 1. Considerˆand dreptunghiul de dimensiune n se poate ˆıncepe acoperirea fie cu: 1 - o pies˘a plasat˘a vertical, caz ˆın care problema se reduce la o problem˘a de dimensiune n − 1 2 - dou˘a piese plasate orizontal, caz ˆın care problema se reduce la o problem˘a de dimensiune n − 2 Prin urmare formula de calcul a num˘arului de variante posibile este: C(1) = 1 C(2) = 2 (se pot pune orizontal sau vertical) C(n) = C(n-1) + C(n-2) (de tip Fibonacci) 2. Se analizeaz˘a paritatea lui n, dac˘a n este par nu exist˘a varianta de acoperire f˘ar˘a s˘a se suprapun˘a piesele. Dac˘a n este impar exist˘a o singura posibilitate de acoperire cu piese plasate orizontal (nu se poate pune nicio pies˘a vertical˘a). BAREM Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 pct. (a) Descrierea ideii de rezolvare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 pct. Implementarea funct, iei: Declarat, ii de variabile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 pct. Implementare corect˘a C(1) = 1, C(2) = 2, C(n) = C(n − 1) + C(n − 2) 2 pct. Definirea corect˘a a funct, iei s, i returnarea rezultatului . . . . . . . . . . . . . . . . . . 1 pct. (b) Descrierea ideii de rezolvare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 pct. Declarat, ii, definire s, i implementare corect˘a a subprogramului . . . . . . . . . . . . . .1 pct. Problema 2 Se consider˘a dou˘a secvent, e de cˆate n valori naturale a1, a2, . . ., an respectiv b1, b2, . . ., bn. Se pune problema determin˘arii unei permut˘ari de ordin n, p = (p(1), p(2), . . . , p(n)) astfel ˆıncˆat suma |a1 −bp(1)|+|a2 −bp(2)|+. . .+|an −bp(n)| s˘a fie cˆat mai mare. Descriet, i un algoritm care permite obt, inerea permut˘arii s, i sumei corespunz˘atoare. De exemplu, pentru a = (5, 9, 12, 4) s, i b = (7, 2, 15, 5) o permutare care satisface cerint, a este p = (1, 4, 2, 3), suma fiind |5 − 7| + |9 − 5| + |12 − 2| + |4 − 15| = 27. Prezentat, i pe scurt ideea de rezolvare, justificat, i c˘a ideea este corect˘a s, i descriet, i solut, ia ˆın pseudocod sau ˆıntr-un limbaj de programare la alegere (C/C++, Pascal, Python). 51
Subiect și barem · pagina 52
Idei de rezolvare Varianta 1: Pentru construirea permut˘arii se parcurg elementele lui a ˆın ordine des- cresc˘atoare s, i a lui b ˆın ordine cresc˘atoare. La primul pas se va completa ˆın permutare p[pozmaxa ] = pozminb s, i se continua procesul. Varianta 2: Generarea tuturor permut˘arilor s, i selectarea celei de sum˘a maxim˘a (va- rianta aceasta este ineficient˘a). BAREM Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 pct. Idee rezolvare - specificare modului de obt, ine al permut˘arii . . . . . . . . . . . . . . . . . . . 2 pct. Argumentarea corectitudinii algoritmului propus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 pct. Declarat, ii de variabile care descriu structurile utilizate . . . . . . . . . . . . . . . . . . . . . . . .1 pct. Construirea corect˘a a permutarii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 pct. Calculul corect al sumei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 pct. Problema 3 Pentru un grup de n persoane se cunosc perechile de persoane care intr˘a frecvent ˆın contact (fac parte din aceeas, i familie sau lucreaz˘a ˆımpreun˘a). ˆIn contextul r˘aspˆandirii unei epidemii se consider˘a c˘a toate persoanele care au intrat ˆın contact cu o persoan˘a infectat˘a devin infectate. Cunoscˆand care este pacientul 0 determinat, i num˘arul de persoane care au fost infectate. Exemplu: n = 7 s, i perechile de persoane care intr˘a ˆın contact sunt: (P1, P2), (P1, P4), (P1, P7), (P3, P6) s, i (P5, P6). ˆIn ipoteza c˘a pacientul zero este P2 modul de r˘aspˆandire al infect, ie este: la etapa 1 se infecteaz˘a P1, la etapa 2 se infecteaz˘a P4 s, i P7 s, i procesul de r˘aspˆandire a infect, iei se opres, te deoarece nu mai exist˘a persoane neinfectate care au intrat ˆın contact cu o persoan˘a infectat˘a, num˘arul de persoane infectate fiind 4. Prezentat, i pe scurt ideea de rezolvare s, i descriet, i solut, ia ˆın pseudocod sau ˆıntr-un limbaj de programare la alegere (C/C++, Pascal, Python). Idei de rezolvare Varianta 1: Relat, iile dintre persoane se pot reprezenta sub forma unui graf, iar num˘arul de noduri (determinat prin parcurgere ˆın adancime sau ˆın l˘at, ime) din sub- graful care cont, ine persoana zero reprezint˘a solut, ia problemei. 52
Subiect și barem · pagina 53
Varianta 2: Pentru a reprezenta contactele se poate folosi o matrice (m), mi,j = 1 dac˘a persoana i a intrat ˆın contact cu persoana j. Pentru a determina num˘arul de persoane infectate se poate folosi un vector (v) care stocheaz˘a informat, ia dac˘a persoana este infectat˘a sau nu. Se pornes, te de la persoana zero (p0) s, i se caut˘a persoanele cu care este ˆın contact mp0,k = 1, k = 1, n. ˆIn prima etap˘a se marcheaz˘a ca infectate toate persoanele aflate ˆın contact direct cu pacientul p0. La etapa urm˘atoare se marcheaz˘a ca infectate toate persoanele neinfectate care sunt ˆın contact direct cu cele infectate la etapa anterioar˘a. Procesul va continua pˆan˘a cˆand nu mai apar persoane nou infectate. BAREM Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 pct. Idee rezolvare - descrierea procesului de r˘aspˆandire a infect, iei . . . . . . . . . . . . . . . . . 2 pct. Descrierea structurilor de date folosite s, i declarat, ii . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 pct. Implementarea algoritmului de r˘aspˆandire a infect, iei . . . . . . . . . . . . . . . . . . . . . . . . . . 4 pct. Determinarea corect˘a a num˘arului de persoane infectate . . . . . . . . . . . . . . . . . . . . . . 1 pct. 53
Subiect și barem · pagina 54
Capitolul 3
Subiecte date la examenul de
admitere la facultate
3.1 Sesiunea Iulie 2016
1. (a) (5p) Scriet, i o funct, ie C/C++/Pascal care primes, te ca parametru o valoare
natural˘a n din mult, imea {0, . . . , 255} s, i returneaz˘a valoarea m calculat˘a
dup˘a regula:
m =
{n/2 dac˘a n este par
128+(n-1)/2 dac˘a n este impar
(b) (5p) Se consider˘a un p˘atrat de latur˘a L al c˘arui vˆarf din stˆanga jos are coor-
donatele (x0, y0). Se pune problema verific˘arii dac˘a un punct de coordonate
(x, y) se afl˘a sau nu ˆın interiorul p˘atratului. Scriet, i o funct, ie C/C++/Pascal
care primes, te ca parametri de intrare valorile reale L, x0, y0, x, y s, i retur-
neaz˘a 1 dac˘a punctul se afl˘a ˆın interiorul p˘atratului s, i 0 ˆın caz contrar.
(c) (5p) Scriet, i o funct, ie C/C++/Pascal care primes, te 6 parametri (a, b, c, x, y,
z) care reprezint˘a lungimile laturilor a dou˘a triunghiuri (a, b, c reprezint˘a
lungimile laturilor primului triunghi, iar x, y, z lungimile laturilor celui de
al doilea triunghi) s, i returneaz˘a 1 dac˘a triunghiurile sunt asemenea s, i 0 ˆın
caz contrar. Lungimile laturilor fiec˘arui triunghi sunt numere naturale s, i
sunt enumerate ˆıntr-o ordine arbitrar˘a.
(d) (5p) Se consider˘a o tabl˘a caroiat˘a ce cont, ine N × N (N > 3) p˘atr˘at, ele din
care se elimin˘a dou˘a p˘atr˘at, ele aflate ˆın extremit˘at, ile uneia dintre diagonale.
Se dores, te acoperirea tablei cu piese de domino de dimensiune 2 × 1 (care
pot fi plasate pe orizontal˘a sau vertical˘a).
Cˆand este posibil˘a acoperirea exact˘a a tablei cu piese?
i. cˆand N este impar;
ii. cˆand N este par;
iii. pentru nicio valoare a lui N ;
iv. pentru orice valoare a lui N.
54Subiect și barem · pagina 55
2. Adresele de e-mail de la UVT au urm˘atoarea structur˘a: prenume.nume@e-uvt.ro
(numele s, i prenumele cont, in doar litere mici).
(a) (10p) Scriet, i o funct, ie C/C++/Pascal care primes, te ca parametru un s, ir
de caractere ce cont, ine simbolul @ s, i returneaz˘a 1 dac˘a s, irul reprezint˘a o
adres˘a de e-mail care respect˘a structura de la UVT s, i 0 ˆın caz contrar.
(b) (10p) Scriet, i o funct, ie (procedur˘a) C/C++/Pascal care primes, te ca pa-
rametru un s, ir de caractere ce reprezint˘a o adres˘a de e-mail de la UVT
corect˘a s, i afis, eaz˘a prenumele s, i numele separate de un spat, iu, fiecare dintre
ele ˆıncepˆand cu majuscul˘a.
Exemplu: pentru adresa ioan.popescu@e-uvt.ro se va afis, a Ioan Popescu.
3. Doi prieteni, Geo s, i Leo, joac˘a urm˘atorul joc: pe o foaie este scris˘a o list˘a de
M numere naturale nenule mai mici decˆat 10000. La ˆınceputul jocului, Geo s, i
Leo aleg fiecare cˆate trei numere prime impare distincte, mai mici decˆat 100. La
fiecare rund˘a se trece la urm˘atorul num˘ar din list˘a, notat cu N, s, i fiecare dintre
cei doi juc˘atori ˆıs, i recalculeaz˘a scorul dup˘a urm˘atoarea regul˘a: se adaug˘a cˆate
1 punct pentru fiecare factor din descompunerea ˆın produs de factori primi a
num˘arului N care se reg˘ases, te printre cele 3 numere prime pe care le-a ales la
ˆınceput, se scade cˆate un punct pentru fiecare dintre numerele sale prime care
nu apare ˆın descompunerea ˆın produs de factori primi a num˘arului N. Cˆas, tig˘a
juc˘atorul care are punctajul cel mai mic la terminarea tuturor numerelor de pe
foaie.
Exemplu: dac˘a num˘arul N este 150, iar Geo a ales la ˆınceput numerele prime
3, 5 s, i 13, va primi un total de 2 puncte: 1 punct pentru 3, 2 puncte pentru 5 s, i
−1 punct pentru 13.
Scriet, i urm˘atoarele funct, ii (C/C++/Pascal) utile pentru calculul scorului ununi
juc˘ator:
(a) (5p) estePrim(x) - o funct, ie care returneaz˘a 1 dac˘a x este prim s, i impar,
respectiv 0 ˆın caz contrar.
(b) (5p) esteFactorPrim(N, x) - o funct, ie care returneaz˘a 1 dac˘a x apare ˆın
descompunerea ˆın produs de factori primi a lui N, respectiv 0 ˆın caz contrar;
se va utiliza funct, ia estePrim descris˘a la punctul (a).
(c) (5p) puncte(N, x) - o funct, ie care returneaz˘a num˘arul de puncte primite
pentru perechea (N, x); se va utiliza funct, ia esteFactorPrim descris˘a la
punctul (b).
(d) (5p) punctaj(listaNumere, nr1, nr2, nr3) - o funct, ie care returneaz˘a
scorul corespunz˘ator listei de numere pentru juc˘atorul care a ales nume-
rele prime init, iale nr1, nr2 s, i nr3, determinat folosind funct, ii dintre cele
descrise anterior.
4. Se consider˘a o imagine pe niveluri de gri, A, reprezentat˘a printr-o matrice cu 50
de linii s, i 50 de coloana care cont, ine valori din mult, imea {0, . . . , 255} (valoarea
unui element din matrice reprezint˘a nivelul de gri al pixelului corespunz˘ator din
imagine).
55Subiect și barem · pagina 56
(a) (10p) Scriet, i o funct, ie (procedur˘a) C/C++/Pascal care, pornind de la ma- tricea A (variabil˘a global˘a), construies, te histograma imaginii (un tablou unidimensional H cu 256 de elemente ˆın care elementul de pe pozit, ia i cont, ine num˘arul de elemente din matricea A care au valoarea i). (b) (10p) Scriet, i o funct, ie C/C++/Pascal care primes, te ca parametru tabloul cu histograma imaginii determinat˘a la punctul (a) s, i returneaz˘a nivelul mediu de gri, g, (calculat ca medie ponderat˘a a elementelor din matricea A : g = (H[0]×0+H[1]×1+· · ·+H[255]×255)/(H[0]+H[1]+· · ·+H[255])). (c) (10p) Scriet, i o funct, ie (procedur˘a) C/C++/Pascal care primes, te ca para- metri matricea A s, i nivelul mediu de gri g, determinat la punctul (b), s, i construies, te o matrice B de aceleas, i dimensiuni cu A cu proprietatea c˘a elementul de pe linia i s, i coloana j este egal cu 1 dac˘a elementul cores- punz˘ator din matricea A este mai mare sau egal cu g, respectiv este egal cu 0 dac˘a elementul corespunz˘ator din A este mai mic decˆat g. BAREM Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. Problema 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20 pct. 1a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declararea corect˘a a funct, iei s, i returnarea rezultatului - 1p; calculul corect al valorii m - 4p) 1b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declararea corect˘a a funct, iei s, i returnarea rezultatului - 1p; specificarea co- rect˘a a condit, iei de punct interior (x ∈ (x0, x0 + L) s, i y ∈ (y0, y0 + L)) - 4p) 1c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declararea corect˘a a funct, iei s, i returnarea rezultatului - 1p; verificarea corect˘a a condit, iei de asem˘anare a triunghiurilor (se transform˘a variabilele astfel ˆıncˆat a ≤ b ≤ c s, i x ≤ y ≤ z dup˘a care se verific˘a condit, ia de proport, ionalitate a lungimilor laturilor: a/x = b/y = c/z sau a × y = b × x s, i b × z = c × y) - 4p) 1d (iii) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. Problema 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20 pct. 2a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. (declararea corect˘a a funct, iei s, i returnarea rezultatului - 1p; verificarea corect˘a a structurii de adres˘a UVT (subs, irurile ce corespund prenumelui s, i numelui sunt nevide s, i cont, in doar litere mici - 2p, exist˘a un singur punct ˆınainte de simbolul @ - 2p, iar subs, irul de dup˘a simbolul @ coincide cu “e-uvt.ro” - 5p)) 2b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. (declararea corect˘a a funct, iei (procedurii)- 1p; afis, area prenumelui - 4p s, i numelui - 4p ˆıncepˆand cu majuscule - 1p) Problema 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20 pct. 56
Subiect și barem · pagina 57
3a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declararea corect˘a a funct, iei s, i returnarea rezultatului - 1p; verificarea corect˘a a propriet˘at, ii de num˘ar impar - 1p s, i de num˘ar prim - 3p) 3b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declararea corect˘a a funct, iei s, i returnarea rezultatului - 1p; verificarea corect˘a a faptului c˘a x este factor prim al lui N - 4p) 3c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declararea corect˘a a funct, iei s, i returnarea rezultatului - 1p; calculul corect al num˘arului de puncte - 4p) 3d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declararea corect˘a a funct, iei s, i returnarea rezultatului - 1p; calculul corect al scorului: parcurgerea listei cu numere - 2p, apelul corect al funct, iei punctaj - 2p) Problema 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .30 pct. 4a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. (declararea corect˘a a matricii A - 1p; declararea corect˘a a tabloului H - 1p; declararea corect˘a a funct, iei (procedurii) - 1p; completarea corect˘a a tabloului H - 7p) 4b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. (declararea corect˘a a funct, iei s, i returnarea rezultatului - 1p; calculul corect al mediei ponderate - 9p) 4c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. (declararea corect˘a a matricii B - 1p; declararea corect˘a a funct, iei (procedurii) - 1p; construirea corect˘a a matricii B - 8p) 57
Subiect și barem · pagina 58
3.2 Sesiunea Iulie 2017 1. (10p) O matrice p˘atratic˘a se consider˘a matrice de tip X dac˘a toate elementele sale sunt nule cu except, ia celor care se afl˘a pe una dintre cele dou˘a diagonale. (a) (5p) Pentru o matrice p˘atratic˘a A de dimensiune n (n ≤ 10) se consider˘a urm˘atorul algoritm al c˘arui scop este s˘a verifice dac˘a A este matrice de tip X : corect ← 1 pentru i ← 1, n execut˘a pentru j ← 1, n execut˘a dac˘a < . . . condit, ie referitoare la A, i s, i j · · · > atunci corect ← 0 Completat, i condit, ia (< . . . condit, ie referitoare la A, i s, i j · · · >) din pseudocod astfel ˆıncˆat variabila corect s˘a aib˘a valoarea 1 dac˘a matricea este de tip X s, i valoarea 0 altfel. (b) (5p) Scriet, i o funct, ie C/C++/Pascal care implementeaz˘a algoritmul de la punctul (a) s, i returneaz˘a valoarea variabilei corect. 2. (10p) Se consider˘a urm˘atoarea relat, ie de recurent, ˘a (pentru n s, i k numere natu- rale): f (n, k) = 0 dac˘a n < k sau n = 0 1 dac˘a n > 0 s, i (n = k sau k = 0) f(n-1,k)+f(n-1,k-1) dac˘a n > 0 s, i k < n (a) (2p) Ce valoare are f (4, 2)? (b) (3p) Ce calcul descrie relat, ia de recurent, ˘a (pentru 1 ≤ k ≤ n)? Aleget, i raspunsul corect dintre: i. ∑n−1 i=k i + ∑n−1 i=k−1 i; ii. Ck n ; iii. 2 ∑n−1 i=1 i + ∑k−1 i=1 i + ∑k i=1 i; iv. Ak n (c) (5p) Scriet, i o funct, ie recursiv˘a ˆın C/C++/Pascal care implementeaz˘a re- lat, ia de recurent, ˘a (primes, te parametrii n s, i k s, i returneaz˘a valoarea lui f (n, k)). 3. (35p) Se consider˘a o secvent, ˘a cu k (k ≤ 1000) numere naturale stocat˘a ˆıntr-un tablou unidimensional S. (a) (10p) Scriet, i o funct, ie C/C++/Pascal care primes, te ca parametri pe k s, i S s, i efectueaz˘a urm˘atoarele prelucr˘ari: i. completeaz˘a o variabil˘a global˘a L (tablou unidimensional) care cont, ine num˘arul de elemente din fiecare subsecvent, ˘a cu valori de aceeas, i pari- tate; 58
Subiect și barem · pagina 59
ii. returneaz˘a num˘arul N de subsecvent, e identificate Exemplu: Pentru secvent, a (5, 1, 3, 2, 4, 7, 6, 4, 10, 8, 3) tabloul L va con- t, ine valorile (3, 2, 1, 4, 1), iar funct, ia va returna 5. (b) (10p) Scriet, i un subprogram C/C++/Pascal care primes, te ca parametri indicii, i1 s, i i2 (se presupune c˘a i1 ≤ i2, a dou˘a elemente din S s, i ordoneaz˘a cresc˘ator subtabloul din tabloul S (considerat variabil˘a global˘a) determinat de cei doi indici. Exemplu: ˆIn cazul ˆın care indicii pornesc de la 0, pentru secvent, a (5, 1, 3, 2, 4, 7, 6, 4, 10, 8, 3) s, i i1 = 6, i2 = 9, dup˘a ordonare, variabila S va cont, ine (5, 1, 3, 2, 4, 7, 4, 6, 8, 10, 3). (c) (10p) Folosind rezultatele obt, inute apelˆand funct, ia de la punctul (a) s, i apelˆand subprogramul de la punctul (b) s˘a se transforme tabloul S ast- fel ˆıncˆat toate subsecvent, ele de numere de aceeas, i paritate s˘a fie ordo- nate cresc˘ator. Secvent, a (5, 1, 3, 2, 4, 7, 6, 4, 10, 8, 3) se va transforma ˆın (1, 3, 5, 2, 4, 7, 4, 6, 8, 10, 3). (d) (5p) Ana s, i Maria joac˘a urm˘atorul joc: fiind dat˘a o secvent, ˘a de numere naturale fiecare juc˘ator trebuie s˘a elimine subsecvet, a de numere de aceeas, i paritate de la ˆınceputul secvent, ei curente. Pentru secvent, a (5, 1, 3, 2, 4, 7, 6, 4, 10, 8, 3), dup˘a mutarea primului juc˘ator, secvent, a devine (2, 4, 7, 6, 4, 10, 8, 3), dup˘a mutarea celui de al doilea, devine (7, 6, 4, 10, 8, 3) etc. Ju- c˘atorul care elimin˘a ultima subsecvent, ˘a pierde jocul. Ambele juc˘atoare au acces la ˆıntreaga secvent, ˘a. Ana are dreptul s˘a decid˘a dac˘a vrea s˘a ˆınceap˘a jocul sau dac˘a o las˘a pe Maria s˘a ˆınceap˘a. Ce informat, ii despre secvent, a sunt suficiente pentru Ana pentru a putea lua decizia care garanteaz˘a c˘a va cˆas, tiga? Descriet, i, ˆın limbaj natural, regula de decizie corespunz˘atoare. 4. (35p) Un careu Sudoku este un tablou bidimensional cu 9 linii s, i 9 coloane ce cont, ine cifre cuprinse ˆıntre 1 s, i 9. Careul este considerat corect completat dac˘a satisface urm˘atoarele propriet˘at, i (vezi exemplul de mai jos): (i) fiecare linie s, i fiecare coloan˘a cont, ine cifre distincte; (ii) fiecare dintre cele 9 subtablouri cu 3 linii s, i 3 coloane (care acoper˘a ˆın mod disjunct tabloul de 9 × 9) cont, ine cifre disctincte. (a) (10p) Scriet, i o funct, ie C/C++/Pascal care primes, te ca parametru un tablou unidimensional cu 9 elemente s, i verific˘a dac˘a elementele sunt cifre distincte (se presupune c˘a elementele sunt numere naturale ˆıntre 1 s, i 9). Funct, ia va returna valoarea 1 dac˘a tabloul satisface proprietatea cerut˘a s, i 0 ˆın caz contrar. (b) (2p) Declarat, i o variabil˘a cu numele S ˆın care s˘a poat˘a fi stocat tabloul bidimensional cu 9 linii s, i 9 coloane. (c) (5p) Scriet, i o funct, ie C/C++/Pascal care primes, te ca parametru indicii corespunz˘atori celulei din stˆanga sus, respectiv ale celulei din dreapta jos a unui subtablou de 3 × 3 elemente din tabloul S s, i verific˘a dac˘a elementele subtabloului specificat sunt cifre distincte (se presupune c˘a elementele sunt numere naturale ˆıntre 1 s, i 9). Funct, ia va returna valoarea 1 dac˘a subtabloul specificat satisface proprietatea cerut˘a s, i 0 ˆın caz contrar. Este permis˘a utilizarea funct, iei de la punctul (a). 59
Subiect și barem · pagina 60
(d) (15p) Scriet, i un subprogram C/C++/Pascal care foloses, te funct, iile definite la (a) s, i (c) s, i care verific˘a dac˘a tabloul stocat ˆın variabila global˘a S cores- punde unui careu Sudoku completat corect. Subprogramul va afis, a “Careu corect” dac˘a sunt satisf˘acute propriet˘at, ile, respectiv “Careu incorect” dac˘a nu sunt satisf˘acute. (e) (3p) Presupunˆand c˘a ˆıntr-un subtablou 3 × 3 sunt completate k elemente (1 < k < 9) cu valori specificate, care este num˘arul de subtablouri distincte (care satisfac condit, ia de Sudoku) ce pot fi obt, inute prin completarea celor 9 − k elemente? Aleget, i r˘aspunsul corect dintre: i. Ak 9 ; ii. A9−k 9 ; iii. Ck 9 ; iv. C9−k 9 ; v. k!; vi. (9 − k)!. Exemplu de careu completat corect: 6 8 2 1 9 4 3 5 7 7 3 1 5 6 8 9 2 4 4 9 5 7 2 3 8 6 1 8 2 7 9 3 5 1 4 6 5 1 9 6 4 7 2 8 3 3 6 4 2 8 1 5 7 9 9 5 6 4 1 2 7 3 8 2 4 8 3 7 9 6 1 5 1 7 3 8 5 6 4 9 2 Sursa: http://www.rasfoiesc.com/familie/copii/Ghid-Sudoku-Regulile-jocului69.php 60
Subiect și barem · pagina 61
BAREM Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. Problema 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10 pct. 1a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (Condit, ia ((i = j sau i + j = n + 1) s, i Aij = 0) sau (i 6 = j s, i i + j 6 = n + 1 s, i Aij 6 = 0)) 1b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declararea corect˘a a funct, iei, a variabilelor locale s, i returnarea rezultatului - 1p; descrierea corect˘a a parcurgerii matricii - 2p; specificarea corect˘a a condit, iei s, i completarea variabilei corect - 1p) Problema 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10 pct. 2a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 pct. R˘aspuns corect: 6 2b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 pct. R˘aspuns corect: ii. 2c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declararea corect˘a a funct, iei, a variabilelor locale s, i returnarea rezultatului - 1p;implementarea corect˘a a relat, iei de recurent, ˘a - 4p) Problema 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .35 pct. 3a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. (declararea corect˘a a funct, iei s, i a variabilelor locale - 2p; completarea corect˘a a tabloului L - 6p; determinarea s, i returnarea num˘arului de subsecvent, e - 2p) 3b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. (declararea corect˘a a subprogramului s, i a variabilelor locale - 1p; implemen- tarea corect˘a a algoritmului de sortare - 9p) 3c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. (declararea variabilelor utilizate - 1p; parcurgerea tabloului S - 3p; stabilirea indicilor corespunz˘atori s, i apelul corect a subprogramului de la punctul (b) - 6p) 3d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. R˘aspuns: este suficient s˘a se cunoasc˘a num˘arul de subsecvent, e de valori cu aceeas, i paritate (valoarea N ); regula de decizie: “dac˘a N este par atunci Ana ˆıncepe jocul, altfel o las˘a pe Maria s˘a ˆınceap˘a”. Problema 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .35 pct. 4a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. Variant˘a de rezolvare: se construies, te un tabel de frecvent, e corespunz˘ator naturale cuprinse ˆıntre 1 s, i 9 s, i se verific˘a dac˘a toate elementele tabloului de frecvent, e sunt egale cu 1. 61
Subiect și barem · pagina 62
(declararea corect˘a a funct, iei, a variabilelor locale s, i returnarea rezultatului - 1p; verificarea condit, iei c˘a elementele au valori distincte - 9p) 4b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 pct. (declararea corect˘a a tabloului bidimensional S - 2p) 4c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. Variant˘a de rezolvare: se construies, te un tablou unidimensional cont, inˆand elementele subtabloului s, i se apeleaz˘a funct, ia de la punctul (a) (declararea corect˘a a funct, iei, a variabilelor locale s, i returnarea rezultatului - 1p; parcurgerea corect˘a a elementelor subtabloului - 2p; verificarea condit, iei c˘a ele- mentele au valori distincte - 2p) 4d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 pct. (declararea corect˘a a subprogramului s, i a variabilelor locale - 1p; verifica- rea propriet˘at, ii la nivel de linii - 3p; verificarea propriet˘at, ii la nivel de coloane - 3p; verificarea propriet˘at, ii la nivel de subtablouri - 8p) 4e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 pct. R˘aspuns: vi. (9 − k)! 62
Subiect și barem · pagina 63
3.3 Sesiunea Iulie 2018 1. (40p) (a) (5p) Se consider˘a suma S = 1 − 1/3 + 1/5 − 1/7 + 1/9 − . . . (primul termen este 1, al doilea termen este −1/3 etc.). i. Care este expresia corespunz˘atoare celui de al k−lea termen? A. 1/(2k − 1); B. 1/(2k + 1); C. (−1)k/(2k − 1); D. (−1)k+1/(2k − 1); E. (−1)k+1/(2k + 1). ii. Scriet, i o funct, ie ˆın C/C++/Pascal care primes, te ca parametru un num˘ar natural n ≥ 2 s, i returneaz˘a suma primilor n termeni din S. (b) (5p) Un num˘ar natural este considerat tip “dublu-unu” dac˘a reprezentarea sa ˆın baza 2 cont, ine exact o pereche de cifre consecutive egale cu 1 (numerele 3 = (11)2, 6 = (110)2 sunt de tip “dublu-unu”, dar numerele 5 = (101)2 s, i 7 = (111)2 nu sunt de acest tip). i. Cˆate numere de tip “dublu-unu” sunt ˆın intervalul (0, 2d)? ii. Care dintre urm˘atoarele afirmat, ii este adev˘arat˘a pentru orice num˘ar n de tip “dublu-unu” din (0, 2d) : A. exist˘a 1 ≤ k ≤ d astfel ˆıncˆat n = 2k − 2k−1; B. exist˘a 1 ≤ k < d astfel ˆıncˆat n = 2k + 2k−1; C. exist˘a 0 < k < d astfel ˆıncˆat n = 2k+1 + 2k−1; D. exist˘a 1 ≤ k < d astfel ˆıncˆat n = 2k + 1. (c) (10p) Se consider˘a un serviciu web la care utilizatorii se conecteaz˘a/deco- necteaz˘a s, i se pune problema determin˘arii num˘arului maxim de utilizatori conectat, i simultan pornind de la o secvent, ˘a de semnale de forma: 1 (s-a conectat un utilizator), 0 (s-a deconectat un utilizator). De exemplu, pen- tru secvent, a 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0 num˘arul maxim de utilizatori conectat, i simultan este 5. Scriet, i o funct, ie C/C++/Pascal care primes, te un tablou de semnale precum s, i num˘arul acestora s, i returneaz˘a num˘arul maxim de utilizatori conectat, i simultan. (d) (10p) Pentru un num˘ar natural nenul n se pune problema determin˘arii num˘arului de zerouri finale (de exemplu, 304500 cont, ine dou˘a zerouri finale, 30245 cont, ine 0 zerouri finale). i. Scriet, i o funct, ie C/C++/Pascal (nerecursiv˘a) care primes, te ca para- metru num˘arul n s, i returneaz˘a num˘arul de zerouri finale. ii. Scriet, i o funct, ie C/C++/Pascal recursiv˘a care efectueaz˘a aceeas, i pre- lucrare. (e) (10p) Se consider˘a c˘a un text a fost tehnoredactat folosind o tastatur˘a defect˘a care “multiplic˘a” simbolurile tastate s, i se pune problema “cur˘at, irii” acestui text prin eliminarea caracterelor ˆın exces (se presupune c˘a textul cont, ine doar cuvinte ˆın care nu intervin simboluri consecutive identice). 63
Subiect și barem · pagina 64
De exemplu, textul “Acccceessttta eesttte uuun exxeeemmpplluu” trebuie
transformat ˆın “Acesta este un exemplu”. Considerˆand c˘a textul este stocat
ˆıntr-un tablou cu elemente de tip caracter scriet, i:
i. o funct, ie/procedur˘a care construies, te un nou tablou de caractere care
cont, ine textul cur˘at, at (pentru exemplul de mai sus noul tablou va avea
22 de caractere s, i va cont, ine “Acesta este un exemplu”);
ii. o funct, ie/procedur˘a care transform˘a tabloul init, ial astfel ˆıncˆat pe pri-
mele pozit, ii s˘a fie textul curat (ˆın exemplul de mai sus noul cont, inut al
tabloului este “Acesta este un exempluuuun exxeeemmppllluu”). Nu
este permis˘a utilizarea unui tablou adit, ional.
2. (25p) Se consider˘a un set de n oras, e, numerotate de la 1 la n (n ≤ 50), s, i o
“hart˘a” a conexiunilor aeriene dintre aceste oras, e stocat˘a sub forma unei matrici
A cu n linii s, i n coloane ˆın care elementul aij este 1 dac˘a exist˘a conexiune direct˘a
ˆıntre oras, ele i s, i j s, i este 0 dac˘a nu exist˘a conexiune direct˘a (se presupune c˘a
aii = 0 s, i aij = aji pentru orice i s, i j din mult, imea {1, 2, . . . , n}).
Exemplu: Se consider˘a 5 oras, e s, i matricea de conectivitate direct˘a:
A =
0 1 0 0 1
1 0 0 1 1
0 0 0 1 1
0 1 1 0 1
1 1 1 1 0
(a) Scriet, i o funct, ie/procedur˘a care construies, te tabloul D care cont, ine pentru
fiecare oras, num˘arul de conexiuni directe (D[i] cont, ine num˘arul de conexiuni
directe care pornesc din oras, ul i). Exemplu: D = [2, 3, 2, 3, 4].
(b) Scriet, i o funct, ie/procedur˘a care primes, te ca parametru tabloul D s, i afis, eaz˘a
oras, ele ˆın ordinea descresc˘atoare a num˘arului de conexiuni directe. Exem-
plu: valorile afis, ate sunt 5, 2, 4, 1, 3.
(c) Scriet, i o funct, ie/procedur˘a care primes, te ca parametri matricea conexiuni-
lor s, i indicii a dou˘a oras, e (i s, i j) s, i afis, eaz˘a toate variantele de a ajunge din
oras, ul i ˆın oras, ul j f˘acˆand cel mult o escal˘a. Exemplu: pentru i = 2, j = 5
se afis, eaz˘a: (2, 5), (2, 1, 5), (2, 4, 5).
(d) Scriet, i o funct, ie/procedur˘a care calculeaz˘a matricea B = A2 = A × A.
(e) ˆIn ipoteza c˘a fiecare oras, este conectat direct cu cel put, in un alt oras, ,
care dintre urm˘atoarele afirmat, ii, referitoare la elementele matricii B, este
adev˘arat˘a?
i. bii = 0 s, i bij = bji pentru orice i s, i j din mult, imea {1, 2, . . . , n};
ii. bii > 1 pentru orice i din mult, imea {1, 2, . . . , n} s, i exist˘a cel put, in o
pereche de (i, j) cu proprietatea c˘a bij 6 = bji;
iii. bii cont, ine num˘arul de conexiuni directe ale oras, ului i. Argumentat, i
r˘aspunsul selectat.
3. (25p) Un lucr˘ator preia pachete (de dimensiuni diferite) de pe o band˘a s, i le
stivuies, te astfel ˆıncˆat s˘a nu pun˘a niciodat˘a un pachet peste unul de dimensiune
mai mic˘a (dac˘a un pachet nu poate fi plasat pe niciuna dintre stivele existente
64Subiect și barem · pagina 65
este creat˘a o nou˘a stiv˘a). De exemplu, dac˘a dimensiunile pachetelor, ˆın ordi- nea ˆın care sosesc pe band˘a, sunt [3, 1, 2, 6, 5, 7, 4] atunci stivele constituite sunt [3, 1], [2], [6, 5, 4], [7]. (a) Propunet, i o structur˘a de date pentru reprezentarea stivelor s, i scriet, i o funct, ie/procedur˘a care primes, te ca parametri num˘arul de pachete s, i un tablou cu dimensiunile acestora s, i care distribuie pachetele pe stive astfel ˆıncˆat num˘arul de stive create s˘a fie cˆat mai mic (fiecare pachet este plasat pe prima stiv˘a pe care este posibil). (b) Presupunˆand c˘a num˘arul de stive create este k justificat, i faptul c˘a cel mai lung subs, ir strict cresc˘ator din tabloul dimensiunilor are k elemente (ele- mentele din subs, ir nu sunt neap˘arat consecutive, dat trebuie s˘a fie ˆın aceeas, i ordine ca ˆın s, irul init, ial; de exemplu, [1, 2, 6, 7] este un subs, ir strict cresc˘ator al s, irului [3, 1, 2, 6, 5, 7, 4]). Scriet, i o funct, ie/procedur˘a care construies, te un subs, ir strict cresc˘ator de lungime maxim˘a. BAREM Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. Problema 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .40 pct. 1a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. 1(a)i. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 pct. (R˘aspuns corect: D.) 1(a)ii. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 pct. (declararea corect˘a a funct, iei, a variabilelor locale s, i returnarea rezultatului - 1p; descrierea corect˘a a calculului sumei - 2p) 1b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. 1(b)i. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 pct. (R˘aspuns corect: d − 1) 1(b)ii. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 pct. (R˘aspuns corect: B.) 1c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. (declararea corect˘a a funct, iei, a variabilelor de lucru s, i returnarea rezultatului - 1p; parcurgerea corect˘a a tabloului cu semnale - 2p; actualizarea corect˘a a num˘arului de utilizatori activi - 3p; determinarea valorii maxime - 4p) 1d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. 1(d)i. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declararea corect˘a a funct, iei, a variabilelor de lucru s, i returnarea rezultatului - 1p; calculul corect al num˘arului de zerouri finale - 4p) 1(d)ii. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 pct. 65
Subiect și barem · pagina 66
(declararea corect˘a a funct, iei, a variabilelor de lucru s, i returnarea rezultatului - 1p; condit, ie corect˘a pentru ies, irea din apelul recursiv - 1p; apel recursiv corect - 1p; calculul corect al num˘arului de zerouri finale - 2p) 1e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. 1(e)i. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declararea funct, iei/procedurii s, i a variabilelor utilizate - 1p; construirea co- rect˘a a noului tablou - 4p) 1(e)ii. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 pct. (declararea funct, iei/procedurii s, i a variabilelor utilizate - 1p; transformarea corect˘a a tabloului - 4p) Problema 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25 pct. 2a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declararea corect˘a a funct, iei/procedurii s, i a variabilelor utilizate - 1p; calculul sumei elementelor de pe fiecare linie (sau determinarea num˘arului de valori egale cu 1 de pe fiecare linie) s, i stocarea corect˘a ˆın tabloul D - 4p) 2b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 pct. (declararea corect˘a a funct, iei/procedurii s, i a variabilelor utilizate - 1p; im- plementarea corect˘a a unei metode de sortare - 5p; asigurarea concordant, ei dintre elementele tabloului D s, i numerele de ordine ale oras, elor - 1p; afis, area numerelor de ordine ale oras, elor ˆın ordinea cerut˘a - 1p) 2c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declararea corect˘a a funct, iei/procedurii s, i a variabilelor utilizate 1p; afis, area traseului direct (dac˘a exist˘a) - 1p; afis, area tuturor traseelor cu o escal˘a - 3p) 2d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declararea corect˘a a funct, iei/procedurii s, i a variabilelor utilizate 1p; calculul corect al produsului - 4p) 2e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 pct. (r˘aspuns corect: iii. - 1p; argumentare: bii = ∑n k=1 aik · aki reprezint˘a num˘arul oras, elor k conectate direct cu oras, ul i (aik = 1) - 1p) Problema 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25 pct. 3a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 pct. (definirea unei structuri de date adecvate - 5p; declararea corect˘a a funct, iei/ procedurii s, i a variabilelor utilizate - 1p; parcurgerea tabloului cu dimensiuni s, i com- pletarea structurii - 9p) 3b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. (justificarea faptului c˘a un subs, ir strict cresc˘ator nu poate avea mai mult de un element ˆın aceeas, i stiv˘a - 2p; declararea corect˘a a funct, iei/procedurii s, i a variabilelor utilizate - 1p; construirea unui subs, ir strict cresc˘ator - 7p) 66
Subiect și barem · pagina 67
3.4 Sesiunea Iulie 2019
1. (35p)
(a) (10p)
i. (5p) Scriet, i o funct, ie ˆın C/C++/Pascal care returneaz˘a 1 dac˘a un
num˘ar ˆıntreg pozitiv primit ca parametru este prim s, i 0 ˆın caz con-
trar.
ii. (5p) Se consider˘a un tablou x cu n numere ˆıntregi pozitive. Scriet, i o
funct, ie/procedur˘a ˆın C/C++/Pascal care afis, eaz˘a toate perechile de
indici (i, j) (i ≤ i < j ≤ n) pentru care suma x[i] + x[j] este num˘ar
prim (se va folosi funct, ia de la punctul precedent).
(b) (10p) Se consider˘a o funct, ie f : {1, 2, . . . , m} → {1, 2, . . . , n}, (m, n ∈
N, m ≥ n) specificat˘a prin tabloul valorilor sale: v este un tablou uni-
dimensional cu m elemente ˆın care v[i] = f [i] (se presupune c˘a indicele
tabloului pornes, te de la 1).
i. (2.5p) Care dintre urm˘atoarele propriet˘at, i este suficient˘a pentru a ga-
ranta faptul c˘a funct, ia f este bijectiv˘a?
A. m = n;
B. m = n S, I v are elemente distincte (v[i] 6 = v[j] pentru orice i 6 = j);
C. m = n SAU v are elemente distincte (v[i] 6 = v[j] pentru orice
i 6 = j);
ii. (2.5p) Cˆate funct, ii bijective pot fi definite pe o mult, ime {1, 2, . . . , m}?
A. m;
B. m2;
C. m!;
D. C2
m;
E. A2
m.
iii. (5p) Scriet, i o funct, ie ˆın C/C++/Pascal care primes, te ca parametru un
num˘ar natural m ≥ 2 s, i un tablou v cu m elemente s, i care returneaz˘a
1 dac˘a v are toate elementele distincte s, i 0 ˆın caz contrar.
(c) (10p) O secvent, ˘a de cifre binare este considerat˘a “complementar-concate-
nat˘a” dac˘a poate fi construit˘a astfel: se pornes, te de la cifra 0 s, i la fiecare
etap˘a, secvent, a curent˘a este concatenat˘a cu complementara ei. Exemple de
astfel de secvent, e sunt:
Num˘ar de ordine Secvent, a
1: 0
2: 01
3: 0110
4: 01101001
5: 0110100110010110
. . . . . .
67Subiect și barem · pagina 68
i. (1p) Care dintre afirmat, iile referitoare la o secvent, ˘a “complementar-
concatenat˘a” este adev˘arat˘a?
A. num˘arul de elemente egale cu 1 din secvent, a cu num˘arul de ordine
n (n ≥ 2) este n − 1;
B. num˘arul de elemente egale cu 0 din secvent, a cu num˘arul de ordine
n (n ≥ 2) este 2(n − 2);
C. num˘arul de elemente egale cu 1 din secvent, a cu num˘arul de ordine
n (n ≥ 2) este 2n−1;
D. num˘arul de elemente egale cu 1 din secvent, a cu num˘arul de ordine
n (n ≥ 2) este 2n−2.
ii. (4p) Scriet, i o funct, ie ˆın C/C++/Pascal care primes, te ca parametri in-
dicii i s, i j a dou˘a elemente dintr-un tablou (variabil˘a global˘a) ce cont, ine
valori din {0, 1} (astfel ˆıncˆat num˘arul de elemente din subtabloul definit
de i s, i j este un num˘ar par) s, i returneaz˘a 1 dac˘a cele dou˘a jum˘at˘at, i ale
subtabloului definit de i s, i j sunt complementare s, i 0 ˆın caz contrar (de
exemplu, ˆın tabloul (0, 0, 1, 0, 0, 1, 0, 1, 1, 0,1, 0)) subtabloul specificat
prin indicii i = 3 s, i j = 10 satisface proprietatea, dar subtabloul cores-
punz˘ator din (0, 0, 1, 0, 0, 1, 0, 1, 0, 1,1, 0) nu satisface proprietatea.
iii. (5p) Scriet, i o funct, ie recursiv˘a care verific˘a dac˘a un tablou este o
secvent, ˘a “complementar-concatenat˘a”. Tabloul va fi considerat vari-
abil˘a global˘a (cu n elemente, unde n este o putere a lui 2), iar funct, ia
va primi ca parametri doi indici care specific˘a port, iunea din tablou care
va fi analizat˘a ˆın cadrul apelului curent.
(d) (5p) Se consider˘a c˘a asupra unui tablou unidimensional a cu 2 ≤ n ≤
100 elemente din mult, imea {1, 2, . . . , n} init, ial definit astfel ˆıncˆat a[i] = i
(se presupune c˘a indicii ˆıncep de la 1) a fost aplicat˘a o transformare prin
deplasare circular˘a c˘atre dreapta sau stˆanga cu k pozit, ii (1 ≤ k < n). Se
pune problema determin˘arii lui k pornind de la tabloul transformat f˘ar˘a a
efectua comparat, ii ˆıntre elementele tabloului.
i. (2.5p) Care dintre urm˘atoarele afirmat, ii sunt adev˘arate?
A. dac˘a deplasarea este la dreapta atunci k = n − x[n]
B. dac˘a deplasarea este la stˆanga atunci k = n − x[n]
C. dac˘a deplasarea este la dreapta atunci k = x[1] − 1
D. dac˘a deplasarea este la stˆanga atunci k = x[1] − 1
E. indiferent de sensul deplas˘arii k = n − x[n]
F. indiferent de sensul deplas˘arii k = x[1] − 1
G. nu se poate determina k f˘ar˘a a efectua comparat, ii ˆıntre elementele
tabloului
ii. (2.5p) Dac˘a se cunoas, te doar tabloul transformat, este posibil s˘a se
determine sensul deplas˘arii? Argumentat, i.
2. (25p) Se consider˘a o expresie algebric˘a ce poate cont, ine ca operanzi doar sim-
bolurile x, y s, i z, iar ca operatori doar + s, i −. Se presupune c˘a expresia ˆıncepe
ˆıntotdeauna cu un operand (de exemplu, x + y − z + y + z + y s, i z + x + y − x
sunt expresii valide, dar −z + x + y − x, zx + y − x, z + −y − x nu sunt valide).
Se presupune c˘a expresia este reprezentat˘a printr-un tablou unidimensional (E)
68Subiect și barem · pagina 69
cu elemente de tip caracter. S˘a se scrie cˆate o funct, ie/procedur˘a care primes, te
tabloul de caractere, precum s, i num˘arul de elemente din acesta (N ) s, i efectueaz˘a
prelucr˘arilre:
(a) (10p) Returneaz˘a 1 dac˘a expresia este valid˘a s, i 0 ˆın caz contrar.
(b) (15p) Presupunˆand c˘a expresia este valid˘a, afis, eaz˘a varianta simplificat˘a a
expresiei (de exemplu, pentru x + y − x + y + z + y varianta simplificat˘a
este x + 3y, iar pentru y + x − z + x este 2x + y − z).
Pentru fiecare dintre funct, ii, pe lˆang˘a implementarea ˆın C/C++/Pascal, se va
descrie pe scurt ideea de rezolvare.
3. (30p) Se consider˘a c˘a o imagine alb-negru este reprezentat˘a printr-o matrice I cu
M linii s, i N coloane s, i elemente din {0, 1} (0 corespunde cu alb s, i 1 corespunde
cu negru) s, i se presupune c˘a imaginea cont, ine un disc alb pe fond negru, astfel
ˆıncˆat discul este ˆıncadrat de cel put, in o linie s, i o coloan˘a de elemente egale cu 1
(vezi Figura 1a).
(a) (10p) Scriet, i o funct, ie cu numele Verific care primes, te ca parametru un
tablou unidimensional cu elemente din {0, 1} s, i num˘arul de elemente din
tablou s, i returneaz˘a: 0 dac˘a toate elementele din tablou sunt egale cu 1; 1
dac˘a tabloul este de forma {1, . . . , 1, 0, . . . , 0, 1, . . . , 1} (cel put, in un zero
ˆıncadrat de cel put, in un unu); 2 dac˘a tabloul cont, ine cel put, in dou˘a port, iuni
de elemente egale cu 0 separate prin cel put, in un element egal cu 1 (de exem-
plu, (1, 1, 0, 0, 1, 0, 1) s, i (1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1) au aceast˘a proprietate);
(b) (10p) Scriet, i o funct, ie care are acces la matricea I (considerat˘a variabil˘a
global˘a) s, i foloses, te funct, ia Verific descris˘a la punctul (a) pentru a deter-
mina diametrul discului exprimat ˆın num˘ar de linii ale matricii (vezi Figura
3.1).
(c) (10p) Se presupune c˘a la achizit, ia imaginii ar fi putut interveni erori astfel c˘a
interiorul discului alb poate cont, ine pete negre (vezi Figura 3.2). Prezentat, i
pe scurt ideea unei metode care s˘a permit˘a verificarea prezent, ei unor pete
negre ˆın interiorul discului. Implementat, i ideea ˆıntr-o funct, ie care are acces
la matricea I s, i returneaz˘a 1 dac˘a discul nu cont, ine pete negre s, i 0 ˆın caz
contrar.
Indicat, ie: se poate folosi funct, ia de la punctul (a).
Figura 3.1 Figura 3.2
69Subiect și barem · pagina 70
Not˘a: Pentru fiecare dintre funct, iile/procedurile scrise se vor specifica toate decla- rat, iile de variabile globale s, i locale necesare s, i se vor pune comentarii explicative. NU este necesar˘a scrierea programului principal s, i preluarea datelor prin citire. BAREM Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. Problema 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .35 pct. 1a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. 1(a)i. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declararea corect˘a a funct, iei, a variabilelor de lucru s, i returnarea rezultatului - 1p; descrierea corect˘a a algoritmului de verificare dac˘a un num˘ar este prim - 4p) 1(a)ii. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declararea corect˘a a funct, iei/procedurii s, i a variabilelor de lucru - 1p; des- crierea corect˘a a algoritmului de determinare a perechilor care au suma num˘ar prim - 3p; afis, area perechilor - 1p) 1b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. 1(b)i. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 pct. (R˘aspuns corect: B.) 1(b)ii. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 pct. (R˘aspuns corect: C.) 1(b)iii. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declararea corect˘a a funct, iei, a variabilelor de lucru s, i returnarea rezultatului - 1p; descrierea corect˘a a algoritmului de verificare dac˘a elementele vectorului sunt distincte - 4p) 1c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. 1(c)i. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 pct. (R˘aspuns corect: D.) 1(c)ii. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 pct. (declararea corect˘a a funct, iei, a variabilelor de lucru s, i returnarea rezultatului - 1p; descrierea corect˘a a algoritmului de verificare dac˘a jum˘at˘at, ile tabloului sunt complementare - 3p) 1(c)iii. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. (declararea corect˘a a funct, iei, a variabilelor de lucru s, i returnarea rezultatului - 1p; condit, ie corect˘a pentru ies, irea din apelul recursiv - 1p; apel recursiv corect - 1p; verificarea propriet˘at, ii de tablou complementar - 2p) 1d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 pct. 1(d)i. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 pct. 70
Subiect și barem · pagina 71
(R˘aspunsuri corecte: A., D.) 1(d)ii. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 pct. (Nu este posibil s˘a se determine sensul transform˘arii deoarece acelas, i rezultat poate fi obt, inut prin deplasarea la dreapta cu k pozit, ii s, i prin deplasarea la stˆanga cu h pozit, ii. De exemplu, pentru n = 5, tabloul (3, 4, 5, 1, 2) se poate obt, ine atˆat prin deplasare la dreapta cu k = 3 pozit, ii cˆat s, i prin deplasare la stˆanga cu h = 2 pozit, ii). Problema 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25 pct. 2a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. (declararea corect˘a a funct, iei, a variabilelor de lucru s, i returnarea rezultatului - 1p; descrierea corect˘a a algoritmului de verificare dac˘a expresia este valid˘a - 7p; descriere idee de rezolvare - 2p) 2b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 pct. (declararea corect˘a a funct, iei/procedurii s, i a variabilelor de lucru - 1p; deter- minarea corect˘a a coeficient, ilor operanzilor (x, y s, i z) - 6p; afis, area corect˘a a expresiei simplificate: verificare existent, ˘a operand - 3p; analiz˘a semn - 3p; descriere idee de rezolvare - 2p) Problema 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .30 pct. 3a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. (declararea corect˘a a funct, iei s, i a variabilelor de lucru - 1p; descrierea corect˘a a algoritmului de verificare c˘a toate elementele din tablou sunt egale cu 1 - 3p; descrierea corect˘a a algoritmului de verificare c˘a exist˘a cel put, in un zero ˆıncadrat de 1 - 5p; returnarea rezultatului - 1p) 3b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. (declararea corect˘a a funct, iei s, i a variabilelor de lucru - 1p; descrierea corect˘a a algoritmului de determinare a indicilor liniilor de unde ˆıncepe s, i unde se termin˘a discul (de exemplu, linia i1 s, i linia i2) - 8p; calculul diametrului (de exemplu, i2 − i1 + 1) s, i returnarea rezultatului - 1p) 3c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct. (descriere idee de rezolvare - 2p; declararea corect˘a a funct, iei, a variabilelor de lucru s, i returnarea rezultatului - 1p; descrierea corect˘a a algoritmului de verificare dac˘a discul cont, ine sau nu pete, prin parcurgerea liniilor matricii, apelˆand funct, ia de la punctul (a) - 7p) 71
Continuă pregătirea
Vezi arhiva completăAlte subiecte de la aceeași facultate
Examen de admitere · 2026Informatică · Subiect și barem în același documentDeschide fișa Examen de admitere · 2026Matematică · Subiect și barem în același documentDeschide fișa Model de pregătire · 2026Matematică · Model oficial 1Deschide fișa Model de pregătire · 2026Matematică · Model oficial 2Deschide fișa Model de pregătire · 2026Matematică · Model oficial 3Deschide fișa Model de pregătire · 2026Matematică · Model oficial de grilăDeschide fișa
Răspunsuri directe
Ce trebuie să știi despre acest subiect?
Ce document de admitere este acesta?
Pagina prezintă model de pregătire din 2026 pentru Informatică, la Facultatea de 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?
Da. Pagina include baremul sau răspunsurile publice asociate acestui subiect, afișate separat ori în același document atunci când sursa le publică împreună. Verifică fiecare rezolvare după ce ai terminat varianta și urmărește exact criteriile de punctare indicate de instituție.
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.