Pregătire cu un profesor
Glisează →Programează o ședință de cunoaștere
Subiect și barem
Se deschide documentul PDF… Deschide PDF
Acest subiect nu are un barem public asociat.
Model de pregătire · Informatică · 2026
Facultatea de Matematică și Informatică · UBB
Înapoi la arhivăDespre acest subiect
pregătire · Culegere cu aproximativ 900 de probleme și 10 teste de antrenament
Sursa documentelor: FMI UBB – subiecte din anii precedenți. Pentru acest subiect nu este disponibil un barem public.
Subiectul în format text
Text extras automat din documentul original. Pentru formule, tabele, imagini și așezarea răspunsurilor, verifică întotdeauna PDF-ul.
Subiect · 674 pagini
Mai jos sunt primele 100 pagini din 674. Documentul integral rămâne disponibil în PDF.
Unele pagini conțin imagini sau text care nu poate fi extras complet. Consultă originalul pentru acele pagini.
Subiect · pagina 1
Admiterea la Facultatea de Matematic˘a s, i Informatic˘a Universitatea Babes, -Bolyai Cluj-Napoca Probleme s, i teste preg˘atitoare Informatic˘a
Subiect · pagina 2
Probleme s, i Teste Gril˘a de Informatic˘a pentru Admiterea la Facultatea de Matematic˘a s, i Informatic˘a Universitatea Babes, -Bolyai 2026 Coordonatori – autori: drd. prof. Ioan Daniel Pop stud. Rares, Cotoi stud. Cristian Cret, u Autori: stud. Mircea M˘aierean stud. Mara Ielciu stud. Luca Cret, u stud. Mihai Gheorghes, mast. Paul Somes, an stud. Luca Tudor stud. Paul Dobrescu Contribuitori: prof. univ. dr. Dios, an Laura prof. univ. dr. Pop Horia conf. univ. dr. S, erban Camelia lect. dr. Andor Camelia lect. dr. C˘alin Alina lect. dr. Chis˘alit¸˘a-Cret¸u Camelia lect. dr. Cioban Vasile lect. dr. Ionescu Clara lect. dr. Lups, a Dana lect. dr. Mures, an Horea lect. dr. Dragos, Radu drd. Berciu Liviu drd. Ciprian-Viorel Stupinean drd. Dicu M˘ad˘alina drd. Ion Iulia drd. M˘adut, a Adrian-Pavel drd. Manole Alexandru drd. V˘aran Andrei prog. Dragomir Manuel prog. Sarkozi Melisa Alexandra prog. Zoltan R˘azvan stud. Danis, C˘at˘alin stud. Deaconu Mihai stud. Ceangˆar Alexandru stud. Gas, par Daria
Subiect · pagina 3
Prefat, ˘a Aceast˘a carte se adreseaz˘a elevilor de liceu care doresc s˘a ˆıs, i aprofundeze cunos, tint, ele de Informatic˘a s, i s˘a se preg˘ateasc˘a ˆın mod eficient pentru examenul de admitere la Fa- cultatea de Matematic˘a s, i Informatic˘a a Universit˘at, ii Babes, -Bolyai din Cluj-Napoca, la disciplina Informatic˘a. Fiecare capitol din programa oficial˘a a examenului de Admitere este aprofundat ˆın dou˘a p˘art, i: ˆIn prima parte sunt prezentate toate conceptele teoretice aferente capitolu- lui, al˘aturi de exemple concrete s, i elemente grafice explicative, iar a doua parte cont, ine probleme de antrenament specifice capitolului, dup˘a modelul problemelor prezente la exa- men. Mai apoi, sunt prezentate problemele de la toate sesiunile de admitere s, i de la toate edit, iile concursului Mate-Info UBB dintre anii 2021 s, i 2024, al˘aturi de solut, iile aferente. Ultima parte a c˘art, ii cont, ine 10 teste de antrenament a cˆate 24 de probleme gril˘a, res- pectˆand cu exactitate modelul subiectelor de la examen. Toate aceste probleme cont, in, de asemenea, rezolv˘ari s, i explicat, ii, la finalul c˘art, ii. Init, iativa s, i efortul principal de realizare a acestei c˘art, i se datoreaz˘a urm˘atorilor student, i: Rares, -Andrei Cotoi, Cristian-Emanuel Cret, u, Mircea M˘aierean, Mara Ielciu, Tudor-Luca Cret, u, Mihai Gheorghes, , Luca Tudor, Paul Dobrescu s, i Paul Somes, an. Aces, tia au propus probleme, au redactat solut, ii s, i au editat materialul sub coordonarea drd. prof. preuniv. Ioan Daniel Pop, cu sprijinul departamentului de Informatic˘a s, i al comisiei de admitere nivel licent, ˘a, coordonat˘a de conf. univ. dr. Dan Mircea Suciu (prodecan). Le mult, umim tuturor cadrelor didactice s, i student, ilor care au contribuit la realizarea ma- terialului prin propunerea de probleme, redactarea de solut, ii s, i realizarea de corecturi. Adres˘am mult, umiri speciale pentru ajutorul acordat lect. dr. Clara Ionescu, conf. dr. Camelia S, erban s, i conf. dr. Marcel S, erban (decan). ˆIi rug˘am pe cei care observ˘a erori (care aproape sigur s-au strecurat, ˆın ciuda eforturilor noastre) sau au sugestii de ˆımbun˘at˘at, ire s˘a ˆıi contacteze pe coordonatorii culegerii. De asemenea, le ur˘am mult succes elevilor ˆın preg˘atirea lor pentru examenul de ad- mitere s, i sper˘am s˘a-i ˆıntˆalnim pe mult, i dintre ei ˆın s˘alile Facult˘at, ii de Matematic˘a s, i Informatic˘a. Cluj-Napoca, februarie 2025 Coordonatorii
Subiect · pagina 4
Precizare: Problemele din subiectele de la concursurile Mate-Info sau examenele de Admitere nu se vor reg˘asi printre problemele din aceast˘a carte. Culegerea are ca scop preg˘atirea s, i ˆınt, elegerea tipurilor de probleme abordate. Problemele propuse ˆın subiecte la urm˘atoarele edit, ii de concurs/examen vor fi complet noi. Not˘a important˘a ˆIn lipsa altor preciz˘ari: • Toate operat, iile aritmetice se efectueaz˘a pe tipuri de date nelimitate (nu exist˘a overflow / underflow). • Numerotarea indicilor tuturor vectorilor, matricelor s, i s, irurilor de caractere ˆıncepe de la 1. • Toate restrict, iile se refer˘a la valorile parametrilor actuali ˆın momentul apelului init, ial. • O subsecvent, ˘a a unui vector este format˘a din elemente care ocup˘a pozit, ii consecu- tive ˆın vector. • Un subs, ir al unui vector/s, ir este format din elemente situate nu neap˘arat pe pozit, ii consecutive ˆın vectorul/s, irul respectiv, ˆın ordinea ˆın care acestea apar ˆın s, irul dat. • Dac˘a pe un acelas, i rˆand apar mai multe instruct, iuni de atribuire consecutive, acestea sunt delimitate prin ”; ”.
Subiect · pagina 5
Cuprins I Teorie s, i probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 Algoritmi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Tipuri de date. Operatori. . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3 Tipuri structurate de date . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4 Algoritmi elementari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5 Complexitatea algoritmilor . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 6 Subprograme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 7 Recursivitate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 8 Metodele Backtracking, Divide et Impera s, i Greedy . . . . . . . . . . . 114 9 Combinatoric˘a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 10 Grafuri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 II Teste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 11 Admitere 2021 - 2025 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 12 Concurs 2021 - 2025 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327 13 Antrenament . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389 III R˘aspunsuri s, i indicat, ii . . . . . . . . . . . . . . . . . . . . . . . . . . 490 14 R˘aspunsuri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491 15 Rezolv˘ari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498 16 Propun˘atori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 665 17 Erat˘a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 668
Subiect · pagina 6
Partea I Teorie s, i probleme
Subiect · pagina 7
1 Algoritmi Acest capitol acoper˘a • Not¸iunea de algoritm • Date, variabile, expresii, operat¸ii • Structuri de baz˘a (liniar˘a, alternativ˘a ¸si repetitiv˘a) 1.1 Teorie 1.1.1 Introducere Un algoritm reprezint˘a un set finit de pas, i bine definit, i, care descriu o secvent, ˘a logic˘a de act, iuni necesare pentru a rezolva o problem˘a sau pentru a obt, ine un rezultat specific. Acesta poate fi implementat ca: • Algoritm principal: cont, ine logica principal˘a a programului s, i poate include operat, ii de citire/scriere • Procedur˘a (subalgoritm): o secvent, ˘a de instruct, iuni care efectueaz˘a o sarcin˘a specific˘a, comunic˘a doar prin parametri s, i nu returneaz˘a valori • Funct, ie (subalgoritm): similar cu procedura, dar returneaz˘a ˆıntotdeauna o va- loare s, i nu ar trebui s˘a aib˘a efecte laterale (precum citire/scriere) Not˘a: Subalgoritmii (proceduri s, i funct, ii) nu ar trebui s˘a efectueze operat, ii de citire sau scriere direct. Acestea ar trebui realizate ˆın algoritmul principal sau ˆın subalgoritmi special dedicat, i pentru operat, ii I/O. Comunicarea ˆıntre subalgoritmi se face exclusiv prin parametri (pentru proceduri) s, i prin valoarea returnat˘a (pentru funct, ii). Datele sunt informat, iile procesate de c˘atre un algoritm s, i pot fi de diferite tipuri, precum numerice, logice, textuale, etc. O variabil˘a este un spat, iu de memorie care poate stoca o valoare ce poate fi modificat˘a pe parcursul execut, iei unui algoritm. Fiecare variabil˘a este identificat˘a printr-un nume s, i are un tip de date asociat. O operat, ie este compus˘a din operanzi s, i un operator. Operanzii reprezint˘a datele asupra c˘arora se aplic˘a operat, ia, iar operatorul este simbolul care indic˘a tipul de operat, ie efectuat˘a asupra acestora. ˆIn funct, ie de scopul acestora, operat, iile pot fi clasificate ˆın aritmetice, logice sau relat, ionale. Operanzii pot fi constante, variabile, literali, rezultatele unor funct, ii, rezultatele altor operat, ii. O expresie este o operat, ie care are ca operanzi alte operat, ii. Interact, iunea cu utilizatorul sau cu fis, ierele externe se face prin instruct, iuni de intrare (citire) s, i ies, ire (scriere). Aceste operat, ii asigur˘a comunicarea dintre program s, i mediul ˆınconjur˘ator. ˆIn cele ce urmeaz˘a, vom utiliza instruct, iunile Write s, i Return pentru a evident, ia valorile afis, ate sau returnate de algoritmul respectiv.
Subiect · pagina 8
Algoritmi Teorie 1.1.2 Structuri de baz˘a • Structura liniar˘a: expresiile care sunt evaluate secvent, ial pe o singur˘a linie de cod, precum declar˘ari, atribuiri s, i operat, ii similare. Structura liniar˘a a ← 3 b ← 5 Write a + b ▷ se afis, eaz˘a 8 • Structura alternativ˘a (condit, ional˘a): permite luarea unei decizii prin executa- rea unei ramuri de cod, ˆın funct, ie de ˆındeplinirea unei condit, ii. Structura condit, ional˘a If 1: If n MOD 2 = 0 then 2: Write ”par” 3: Else 4: Write ”impar” 5: EndIf ▷ se afies, az˘a ”par” dac˘a n este par sau ”impar” altfel • Structura repetitiv˘a: execut˘a un set de instruct, iuni de mai multe ori, de obicei ˆın funct, ie de o condit, ie specific˘a. Exemplu: Structura repetitiv˘a cu test init, ial For 1: For i ← 0, 9 execute 2: Write i, ’ ’ 3: EndFor ▷ se afis, eaz˘a toate cifrele separate de un spat, iu Exemplu: Structura repetitiv˘a cu test init, ial While 1: i ← 0 2: While i ≤ 9 execute 3: Write i, ’ ’ 4: i ← i + 1 5: EndWhile ▷ se afis, eaz˘a toate cifrele separate de un spat, iu Exemplu: Structura repetitiv˘a cu test final Do...While 1: i ← 0 2: Do 3: Write i, ’ ’ 4: i ← i + 1 5: While i ≤ 9 ▷ se afis, eaz˘a toate cifrele separate de un spat, iu 3
Subiect · pagina 9
Algoritmi Probleme 1.2 Probleme 1. ✓ ?Fie algoritmul ceFace(a, b), unde a s, i b sunt numere ˆıntregi: Algorithm ceFace(a, b) a ← a DIV b b ← a * b a ← b DIV a Write a, ’ ’, b EndAlgorithm Precizat, i valorile init, iale ale lui a s, i b astfel ˆıncˆat algoritmul s˘a afis, eze 10 20. A. a = 18, b = 20 B. a = 28, b = 10 C. a = 20, b = 10 D. a = 10, b = 20 2. ✓ ?Fie a s, i b dou˘a numere ˆıntregi (−104 ≤ a, b ≤ 104). Precizat, i care dintre urm˘atorii algoritmi realizeaz˘a corect interschimbarea valorilor a s, i b s, i afis, eaz˘a valorile acestora interschimbate. De exemplu: Pentru a = 12 s, i b = 6, algoritmul ar trebui s˘a afis, eze 6 12. A. Algorithm swap1(a, b) a ← b + a b ← a − b a ← b − a Write a, ’ ’, b EndAlgorithm B. Algorithm swap2(a, b) a ← a * b b ← a DIV b a ← a DIV b Write a, ’ ’, b EndAlgorithm C. Algorithm swap3(a, b) a ← a DIV b b ← a * b a ← b DIV a Write a, ’ ’, b EndAlgorithm D. Algorithm swap4(a, b) a ← a − b b ← a − b a ← b + a Write a, ’ ’, b EndAlgorithm 3. ✓ ?Fie algoritmul pink(a, b, k), unde a, b, k sunt numere naturale (1 ≤ a, b, k ≤ 104). Algorithm pink(a, b, k) If a > b then a ← a ˆ b b ← a ˆ b a ← a ˆ b EndIf While a ≤ b execute a ← a + k b ← b − k Write a, ’ ’ EndWhile EndAlgorithm Operatorulˆeste operatorul XOR pe bit, i; tabelul de adev˘ar este urm˘atorul: ˆ 0 1 0 0 1 1 1 0 Exemplu: 3ˆ5 convertit ˆın binar este 011ˆ101 = 110 = 6, iar 1ˆ4 convertit ˆın binar este 001ˆ100 = 101 = 5. Care dintre urm˘atoarele afirmat, ii de mai jos nu sunt adev˘arate? 4
Subiect · pagina 10
Algoritmi Probleme A. Num˘arul de valori afis, ate de algoritm este egal cu (b − a) DIV (k · 2) + 1, b > a. B. Pentru a = 12, b = 100 s, i k = 4, algoritmul afis, eaz˘a 11 valori. C. Pentru a = 70, b = 20 s, i k = 6, algoritmul afis, eaz˘a 26 32 38 44 50. D. Algoritmul afis, eaz˘a ˆıntotdeauna valori din intervalul [a, a+b 2 ], multiple de k. 4. ✓ ?Fie algoritmii good(a, b) s, i bad(a, b), unde a s, i b sunt numere ˆıntregi (−104 ≤ a, b ≤ 104). Algorithm good(a, b) a ← a * b b ← a DIV b a ← a DIV b Write a, ’ ’, b EndAlgorithm Algorithm bad(a, b) a ← a − b a ← b − a Write a, ’ ’, b EndAlgorithm Aleget, i variantele care completeaz˘a corect spat, iul subliniat de mai sus astfel ˆıncˆat cei doi algoritmi s˘a afis, eze mereu aceleas, i valori pentru a s, i b, indiferent de valorile init, iale ale acestora. A. b ← a + b B. b ← a − b C. b ← b − a D. b ← a * b DIV a + a 5. ✓ ?Fie algoritmul container(n), unde n este un num˘ar natural (1 ≤ n ≤ 104). Algorithm container(n) a ← 0 b ← 1 While n > 1 execute a ← a + 1 b ← b ∗ 2 n ← n − b EndWhile Return a EndAlgorithm Care dintre urm˘atoarele afirmat, ii de mai jos sunt adev˘arate? A. Pentru n = 1024, algoritmul retur- neaz˘a 9. B. Pentru n = 336, algoritmul returneaz˘a 8. C. Algoritmul returneaz˘a ˆıntotdeauna o putere a lui 2. D. Algoritmul container(n) returneaz˘a cel mai mare num˘ar k, cu proprietatea c˘a num˘arul 2k este mai mic sau egal decˆat n. 6. ✓ ?Fie expresia E = n DIV 100 + n MOD 100 DIV 10 + n MOD 10, unde n este un num˘ar natural nenul (1 ≤ n < 103). Precizat, i pentru cˆate valori ale lui n, care respect˘a specificat, iile din enunt, , expresia E are valoarea 9. A. 9 B. 10 C. 45 D. 55 5
Subiect · pagina 11
2 Tipuri de date. Operatori. Acest capitol acoper˘a • Care sunt principalele tipuri de date s, i cum se reprezint˘a? • Care sunt tipurile de operatori s, i cum sunt aces, tia utilizat, i? 2.1 Teorie 2.1.1 Not, iunea de tip de date Tipul de dat˘a defines, te domeniul de valori pe care le poate lua o variabil˘a s, i operat, iile permise asupra acesteia. ˆIn limbajele de programare, tipurile de date pot fi: numerice ˆıntregi, numerice cu virgul˘a mobil˘a (detaliat mai jos), caracter, logice sau structurate (tablou, structur˘a). 2.1.2 Definirea tipurilor de date Tipurile de date fundamentale pot fi descrise, din punct de vedere numeric, prin intervale ce deriv˘a din num˘arul de bit, i alocat, i fiec˘arui tip. De obicei, un tip de date reprezentat pe n bit, i (cu semn, folosind complementul lui 2 - se va detalia ˆın cadrul materiei Arhitectura Sistemelor de Calcul) poate reprezenta valori ˆın intervalul [−2n−1, 2n−1 − 1], iar acelas, i tip, f˘ar˘a semn, poate reprezenta valori ˆın [0, 2n − 1]. Totus, i, pentru tipurile uzuale de date avem: • char (8 bit, i): – signed char: [−27, 27 − 1]; – unsigned char: [0, 28 − 1]. • short (16 bit, i): – short: [−215, 215 − 1]; – unsigned short: [0, 216 − 1]. • int (Minim 16 bit, i, dar poate fi s, i mai mult, ˆın funct, ie de limbaj): – int: Minim [−215, 215 − 1]; – unsigned int: Minim [0, 216 − 1]. • long (Minim 32 bit, i, dar poate fi s, i mai mult, ˆın funct, ie de limbaj): – long: Minim [−231, 231 − 1]; – unsigned long: Minim [0, 232 − 1]. • long long (Minim 64 bit, i, dar poate fi s, i mai mult, ˆın funct, ie de limbaj): – long: Minim [−263, 263 − 1];
Subiect · pagina 12
Tipuri de date. Operatori. Teorie – unsigned long: Minim [0, 264 − 1]. • float s, i double: Acestea reprezint˘a numere reale ˆın format cu virgul˘a mobil˘a, codi- ficate conform standardului IEEE 754. Intervalele nu se exprim˘a simplu sub form˘a de puteri ale lui 2 pentru ˆıntregul domeniu numeric, deoarece reprezint˘a numere ˆın form˘a normalizat˘a (se va detalia ˆın cadrul materiei Logic˘a computat, ional˘a). Totus, i, precizia lor ˆın bit, i este: – float: 32 bit, i (aprox. 24 bit, i pentru mantis˘a); – double: 64 bit, i (aprox. 53 bit, i pentru mantis˘a). 2.1.3 Operatori Operatorii sunt de 3 tipuri: aritmetici, logici s, i relat, ionali. Cei pe care noi ˆıi vom folosi ˆın cele ce urmeaz˘a sunt: • Operatori aritmetici: +, -, *, /, %; • Operatori logici: AND, OR, NOT; • Operatori relat, ionali: <, >, ≤, ≥, =,̸ = Operatorii aritmetici sunt evaluat, i conform regulilor standard de prioritate: • Operatorii *, / s, i % au prioritate mai mare decˆat + s, i -; • Expresiile grupate prin paranteze au prioritate ˆın timpul evalu˘arii unei expresii; • Pentru operatorii de aceeas, i prioritate se aplic˘a evaluarea de la stˆanga la dreapta. Operatorii logici opereaz˘a pe valori de adev˘ar (True sau False) s, i se evalueaz˘a dup˘a urm˘atoarele principii: • AND: Returneaz˘a True doar dac˘a ambii operanzi sunt True; • OR: Returneaz˘a True dac˘a cel put, in unul dintre operanzi este True; • NOT: Inverseaz˘a valoarea operandului (adic˘a, NOT False = True s, i NOT True = False). A B A AND B A OR B False False False False False True False True True False False True True True True True Tabela 2.1 Tabela de adev˘ar pentru operatorii logici AND s, i OR. Operatorii relat, ionali compar˘a dou˘a valori s, i returneaz˘a un rezultat boolean, dup˘a cum urmeaz˘a: • <: Verific˘a dac˘a valoarea din stˆanga este mai mic˘a decˆat cea din dreapta. • >: Verific˘a dac˘a valoarea din stˆanga este mai mare decˆat cea din dreapta. 7
Subiect · pagina 13
Tipuri de date. Operatori. Probleme • ≤: Verific˘a dac˘a valoarea din stˆanga este mai mic˘a sau egal˘a cu cea din dreapta. • ≥: Verific˘a dac˘a valoarea din stˆanga este mai mare sau egal˘a cu cea din dreapta. • =: Verific˘a egalitatea dintre cele dou˘a valori. •̸ =: Verific˘a inegalitatea dintre cele dou˘a valori. Evaluarea expresiilor relat, ionale se efectueaz˘a dup˘a evaluarea expresiilor aritmetice, res- pectˆand regulile standard de comparare. 2.2 Probleme 7. ✓ ?Fie variabila n care memoreaz˘a un num˘ar natural. Care dintre expresiile de mai jos are valoarea True dac˘a s, i numai dac˘a n este divizibil cu 5 s, i cu 9? A. (n MOD 5̸ = 1) AND (n MOD 9 = 0) B. ((n DIV 10) MOD 5̸ = 1) AND (n DIV 9 = 0) C. (n MOD 5̸ = 1) OR (n MOD 9 = 0) D. (n MOD 5 = 0) AND (n MOD 9 = 0) 8. ✓ ?Fie variabila y care memoreaz˘a un num˘ar natural. Care dintre expresiile de mai jos are valoarea True dac˘a s, i numai dac˘a y este mai mare decˆat 10 s, i nu este divizibil cu 4? A. (y > 10) AND (y MOD 4̸ = 0) B. (y > 10) OR (y MOD 4 = 0) C. NOT(y ≤ 10) AND (y MOD 4 = 0) D. (y > 10) AND (y MOD 2̸ = 0) 9. ✓ ?Fie variabila k care memoreaz˘a un num˘ar natural. Care dintre expresiile de mai jos are valoarea True dac˘a s, i numai dac˘a k este un num˘ar par mai mic decˆat 20? A. (k MOD 2 = 0) AND (k < 20) B. (k MOD 2̸ = 0) AND (k ≥ 20) C. (k MOD 2 = 0) OR (k ≥ 20) D. (k MOD 2 = 0) AND (k ≤ 20) 10. ✓ ?Fie variabila m care memoreaz˘a un num˘ar ˆıntreg. Care dintre expresiile de mai jos este True dac˘a s, i numai dac˘a m este un num˘ar negativ divizibil cu 8? A. (m > 0) AND (m MOD 8̸ = 0) B. (m < 0) OR (m MOD 8̸ = 0) C. (m < 0) AND (m MOD 8 = 0) D. (m MOD 8 = 0) AND (m > 0) 11. ✓ ?Fie variabilele a = 16, b = 4 ¸si c = 2. Ce valoare va avea expresia urm˘atoare? (a MOD b + b ∗ c) DIV (a DIV b − c) + (a + 1) MOD (b − 1) 8
Subiect · pagina 14
Tipuri de date. Operatori. Probleme A. 4 B. 5 C. 6 D. 7 12. ✓ ?Fie variabilele x = 20, y = 7 ¸si z = 3. Ce valoare va avea expresia urm˘atoare? (x + 1) MOD y + z ∗ (x − 1) DIV z − y MOD (z − 1) A. 18 B. 17 C. 21 D. 23 13. ✓ ?Fie variabilele a = 10, b = 5 ¸si c = 8. Ce valoare va avea a dup˘a executarea urm˘atoarei instruct¸iuni? a = a + (b ∗ c) DIV (c MOD (b + 2)) − ((c − 1) ∗ (b + 2)) A. 1 B. 8 C. 9 D. 10 14. ✓ ?Fie variabilele x = 8, y = 15 ¸si z = 5. Ce valoare va avea urm˘atoarea expresie? (x MOD (y − 1)) + (z ∗ (x + 1)) DIV ((y − 1) MOD (z − 1)) A. 25 B. 26 C. 27 D. 28 15. ✓ ?Se consider˘a urm˘atoarea expresie logic˘a: (A OR B) AND ( NOT A OR C) OR (B AND ( NOT C OR A)) Precizat, i pentru ce valori ale lui A, B, C, expresia are valoarea True. A. A = True, B = False, C = True B. A = False, B = True, C = False C. A = True, B = True, C = False D. A = False, B = False, C = True 16. ✓ ?Se consider˘a urm˘atoarea expresie logic˘a: ( NOT C AND B) OR (A AND NOT B) AND ( NOT A OR C) Precizat, i pentru ce valori ale lui A, B, C, expresia are valoarea True. A. A = True, B = False, C = False B. A = False, B = True, C = False C. A = True, B = True, C = False D. A = False, B = False, C = True 17. ✓ ?Se consider˘a urm˘atoarea expresie logic˘a: ((A AND ( NOT B OR C)) OR (( NOT A AND B) AND ( NOT C OR A))) AND (B OR NOT C) Precizat, i pentru ce valori ale lui A, B, C, expresia are valoarea True. 9
Subiect · pagina 15
Tipuri de date. Operatori. Probleme A. A = True, B = False, C = False B. A = False, B = True, C = False C. A = True, B = True, C = False D. A = True, B = False, C = True 18. ✓ ?Se consider˘a urm˘atoarea expresie logic˘a: ( NOT ((A OR B) AND C) OR ((B AND NO C) OR (NOTA AND (C OR NOT B)))) AND A Precizat, i pentru ce valori ale lui A, B, C, expresia are valoarea True. A. A = True, B = True, C = False B. A = False, B = False, C = True C. A = True, B = False, C = False D. A = True, B = False, C = True 19. ✓ ?Se consider˘a urm˘atoarea expresie logic˘a: (((A AND B) OR (NOT C AND A)) AND (B OR NOT A)) OR (( NOT B AND C) AND ( NOT A OR B)) Precizat, i pentru ce valori ale lui A, B, C, expresia are valoarea True. A. A = True, B = False, C = False B. A = False, B = False, C = True C. A = True, B = False, C = True D. A = True, B = True, C = False 20. ✓ ?Se consider˘a urm˘atoarea expresie logic˘a: (((A OR (NOT B AND C)) AND (NOT A OR B)) OR (( NOT C OR A) AND ( NOT B OR NOT A))) AND C Precizat, i pentru ce valori ale lui A, B, C, expresia are valoarea False. A. A = True, B = True, C = False B. A = True, B = False, C = True C. A = False, B = True, C = False D. A = False, B = False, C = True 21. ✓ ?Fie variabilele p = 12, q = 3 ¸si r = 4. Ce valoare va avea expresia urm˘atoare? ((p + 1) MOD q) + (r ∗ (p + 1)) − q MOD (r − 1) + (p + 1) DIV (q + 2) A. 50; B. 52; C. 55; D. 56. 22. ✓ ?Fie variabilele a = 9, b = 2 ¸si c = 5. Ce valoare va avea expresia urm˘atoare? (a − 1) MOD b + b ∗ (c + 1) − (a − 1) DIV b A. 7; B. 8; C. 9; D. 10. 23. ✓ ?Fie variabilele x = 25, y = 4 ¸si z = 2. Ce valoare va avea urm˘atoarea expresie? (x MOD y) + (y + 1) ∗ z − x DIV (y + 1) 10
Subiect · pagina 16
Tipuri de date. Operatori. Probleme A. 4; B. 6; C. 8; D. 10. 24. ✓ ?Fie variabilele a = 30, b = 6, c = 2. Ce valoare va avea expresia urm˘atoare? a DIV b − c + (b − 1) MOD (c + 1) + a MOD (b − 1) A. 3; B. 4; C. 5; D. 6. 25. ✓ ?Fie variabilele m = 10, n = 3 ¸si p = 3. Ce valoare va avea m dup˘a instruct¸iunea: m = ((m + 1) MOD n) + (n − 1) ∗ p − (m + 1) DIV (p + 0) A. 3; B. 4; C. 5; D. 6. 26. ✓ ?Fie variabilele a = 14, b = 7 ¸si c = 2. Ce valoare va avea expresia urm˘atoare? a MOD (b − 1) + (a + 1) DIV (b − 1) + c ∗ 2 MOD (b − 1) A. 10; B. 16; C. 18; D. 20. 27. ✓ ?Fie variabilele x = 4, y = 2 ¸si z = 1. Ce valoare va avea x dup˘a executarea acestei instruct, iuni? x = (x ∗ (y + 1)) − (y + 1) DIV (z + 1) + (x + 1) MOD y A. 10; B. 11; C. 12; D. 13. 28. ✓ ?Fie variabilele a = 6, b = 3, c = 2. Ce valoare va avea urm˘atoarea expresie? a DIV (b − 1) + (b − 1) ∗ (c MOD (a + 1)) − a MOD (c + 1) A. 5; B. 6; C. 7; D. 8. 29. ✓ ?Fie variabilele u = 12, v = 4, w = 3. Ce valoare va avea expresia? (u − 1) ∗ v DIV (u − 1) MOD w + (v − 1) MOD (w − 1) A. 20; B. 21; C. 22; D. 23. 30. ✓ ?Fie variabilele x = 5, y = 3, z = 10. Ce valoare va avea expresia urm˘atoare? x MOD y + z DIV (y + 1) − (z − 1) MOD (x − 1) 11
Subiect · pagina 17
Tipuri de date. Operatori. Probleme A. 2; B. 3; C. 4; D. 5. 31. ✓ ?Fie variabilele x = 7, y = 4, z = 2. Care este valoarea urm˘atoarei expresii? (x MOD (y − 1)) + (z ∗ (x + 2)) − (x + 2) DIV z A. 15; B. 16; C. 17; D. 18. 32. ✓ ?Fie variabilele a = 12, b = 5, c = 3. Care este valoarea returnat˘a de expresia urm˘atoare? (a DIV b) > c AND (b − 1) < c OR a MOD (b − 1) = 2 A. True; B. False; C. Eroare de compilare; D. Niciuna dintre variante. 33. ✓ ?Fie tipul de date signed char, reprezentat pe 8 bit, i cu semn. Care este domeniul de valori care se pot reprezenta pe acest tip de date? A. [−128, 127]; B. [−127, 128]; C. [0, 255]; D. [−256, 255]. 34. ✓ ?Fie variabila k = 3. Ce valoare va avea k dup˘a executarea acestei instruct, iuni? k = k + (k + 2) MOD (k + 2) + (k + 1) DIV 2 A. 1; B. 2; C. 3; D. 5. 35. ✓ ?Fie tipul de date unsigned long, reprezentat pe 32 de bit, i. Care dintre urm˘atoarele intervale este valabil pentru valorile reprezentabile pe acest tip de date? A. [0, 231 − 1]; B. [0, 232 − 1]; C. [0, 263 − 1]; D. [0, 264 − 1]. 36. ✓ ?Fie variabilele x = 10, y = 5. Ce valoarea va returna expresia urm˘atoare? x > 5 AND (x + y) < 20 OR y MOD 2 = 1 A. True; B. False; C. Eroare de compilare; D. Niciuna dintre variante. 37. ✓ ?Fie variabila n = 255 de tipul short. Poate valoarea lui n s˘a fie stocat˘a f˘ar˘a dep˘a¸sire ˆıntr-o alt˘a variabil˘a de tipul signed char? 12
Subiect · pagina 18
Tipuri de date. Operatori. Probleme A. Da; B. Nu; C. Depinde de limbajul de programare; D. Depinde de implementare. 38. ✓ ?Fie variabilele a = 8, b = 3, c = 1. Ce valoare va returna expresia urm˘atoare? (a + 1) DIV b − b MOD c + (a + 1) MOD b A. 1; B. 6; C. 2; D. 3. 39. ✓ ?Fie variabila x de tipul signed short. Init, ializarea x = 200 este: A. Incorect˘a, deoarece dep˘as, es, te inter- valul lui signed short; B. Corect˘a, deoarece signed short stocheaz˘a valori pˆan˘a la 127; C. Corect˘a, deoarece signed short ac- cept˘a valori din [-32768, 32767]; D. Depinde de implementare. 40. ✓ ?Fie variabilele m = 15, n = 4, p = 2. Care e valoarea final˘a a lui m dup˘a instruct¸iunea urm˘atoare? m = m MOD (n + p) + n DIV p A. 1; B. 3; C. 5; D. 7. 41. ✓ ?Care este limita inferioar˘a garantat˘a pentru tipul de dat˘a long long reprezentat pe minim 64 de bit, i cu semn? A. −263; B. −264; C. 0; D. Depinde. 42. ✓ ?Fie variabilele x = 13, y = 3, z = 5. Ce valoare va returna expresia urm˘atoare? (x MOD y) = 1 AND (z ∗ y) > x OR x < (z + y) A. True; B. False; C. Eroare de compilare; D. Niciuna dintre variante. 43. ✓ ?Fie variabilele a = 1, b = 2, c = 3. Ce valoare va returna expresia urm˘atoare? (b DIV a) > 0 OR (c − 1) < (b + 1) AND a == 2 A. True; B. False; C. Eroare de compilare; D. Niciuna dintre variante. 44. ✓ ?Fie variabilele x = 6 s, i y = 10. Ce valoarea va returna urm˘atoarea expresie? (x + y) ≤ 15 AND (y − x) ≥ 4 OR (x ∗ y) MOD 2 = 0 13
Subiect · pagina 19
Tipuri de date. Operatori. Probleme A. True; B. False; C. Eroare de compilare; D. Niciuna dintre variante. 45. ✓ ?Care dintre urm˘atoarele expresii logice sunt adev˘arate dac˘a s, i numai dac˘a valoarea natural˘a memorat˘a ˆın variabila x este multiplu de 5 s, i apart, ine intervalului (a, b]? A. NOT(x MOD 5̸ = 0 OR x ≤ a) AND (x ≤ b) B. x MOD 5̸ = 1 AND x > a AND x ≤ b C. x MOD 5 = 0 AND NOT(x < a AND x > b) D. NOT(x MOD 5̸ = 0 AND x ≤ a AND x > b) 14
Subiect · pagina 20
3 Tipuri structurate de date Acest capitol acoper˘a • Care este important, a tipurilor structurate de date? • Care sunt tipurilor de date structurate studiate s, i cum le folosim? 3.1 Teorie 3.1.1 Introducere Tipurile structurate de date reprezint˘a un concept fundamental ˆın informatic˘a, acestea permit, ˆand organizarea eficient˘a a informat, iilor ˆın programe s, i aplicat, ii, facilitˆand atˆat manipularea, cˆat s, i accesarea rapid˘a a datelor. Ele sunt utilizate pentru a gestiona vo- lume mari de date s, i pentru a rezolva probleme complexe, cum ar fi c˘autarea, sortarea sau determinarea celui mai scurt drum ˆıntre dou˘a puncte ˆıntr-o ret, ea. Analogic, putem compara acest concept cu o list˘a de cump˘ar˘aturi: ˆın loc s˘a ai obiec- tele ˆımpr˘as, tiate peste tot, le organizezi ˆıntr-o list˘a bine structurat˘a, unde s, tii exact ce trebuie s˘a cumperi s, i ˆın ce ordine. Similar, ˆın programare, structurile de date sunt utilizate pentru a organiza informat, ia ˆıntr-un mod eficient, permit, ˆand accesarea s, i manipularea rapid˘a s, i corect˘a a datelor. Tipuri structurate de date: • Tipul tablou; • Tipul s, ir de caractere; • Tipul ˆınregistrare. 3.1.2 Tipul tablou: tablouri ˆın memorie Un tablou este o structur˘a de date compus˘a dintr-un num˘ar fix de elemente, toate avˆand acelas, i tip de baz˘a. Acesta reprezint˘a o zon˘a de memorie identificat˘a printr-un nume specific, permit, ˆand stocarea mai multor valori de acelas, i tip. Datele dintr-un tablou pot fi gestionate fie ca un tot unitar, fie ca elemente independente, facilitˆand accesul rapid s, i organizat la fiecare valoare. Tablourile de memorie studiate sunt: • Tablouri de memorie unidimensionale; • Tablouri de memorie bidimensionale.
Subiect · pagina 21
Tipuri structurate de date Teorie 3.1.3 Tablouri de memorie unidimensionale Tablourile unidimensionale, cunoscute s, i sub denumirea de vectori, sunt structuri de date caracterizate prin un singur indice, fiecare element fiind accesibil prin intermediul acestuia. Dac˘a un tablou cont, ine un num˘ar de elemente, indicii acestor elemente sunt valori ˆıntregi cuprinse ˆın intervalul [1, num˘arul de elemente]. Astfel, vectorii permit organizarea eficient˘a a datelor ˆın memorie s, i faciliteaz˘a efectuarea de operat, ii asupra fiec˘arui element ˆın parte, eliminˆand necesitatea stoc˘arii individuale a fiec˘arei variabile. De exemplu, vectorul v cu un num˘ar de n elemente poate fi reprezentat astfel: v[1] v[2] ... ... v[n] Operat, ii cu vectori: Citirea elementelor unui vector: Algorithm Citire(v,n) For i ← 1, n execute Read v[i] EndFor EndAlgorithm Afis, area elementelor unui vector: Algorithm Afis, are(v,n) For i ← 1, n execute Write v[i] EndFor EndAlgorithm Afis, area elementelor unui vector ˆın ordine invers˘a: Algorithm Afis, areR(v,n) For i ← n, 1, −1 execute Write v[i] EndFor EndAlgorithm Cele mai ˆıntˆalnite probleme cu vectori sunt: • Inversarea unui vector • Suma elementelor unui vector • Determinarea valorii minime/maxime • Inserarea sau eliminarea unui element • C˘autarea unui element 16
Subiect · pagina 22
Tipuri structurate de date Teorie • Secvent, e, interclasare, sortare • Vectori de frecvent, ˘a Elementele unui tablou pot fi de orice tip de date disponibil ˆın limbajul de programare utilizat. Astfel, ele pot fi chiar s, i alte tablouri, ceea ce permite crearea de tablouri bidi- mensionale, cunoscute s, i sub numele de matrice. 3.1.4 Tablouri de memorie bidimensionale Un tablou bidimensional este o structur˘a de date cu dou˘a dimensiuni: una cores- punz˘atoare liniilor s, i alta coloanelor. Fiecare element este accesibil folosind doi in- dici, unul pentru linia pe care se afl˘a s, i altul pentru coloana respectiv˘a. De exemplu, matrice[i][j] reprezint˘a elementul aflat la intersect, ia liniei i s, i a coloanei j. O matrice cu num˘arul de linii egal cu num˘arul de coloane se numes, te o matrice p˘atratic˘a. Tablourile bidimensionale sunt utilizate pentru a reprezenta date sub form˘a de gril˘a sau tabel, cum ar fi matrice matematice, tabele de scoruri, imagini sau h˘art, i. Acestea ofer˘a un mod eficient de a organiza s, i accesa date structurale complexe s, i sunt esent, iale ˆın diverse domenii, cum ar fi calculul numeric, grafica computerizat˘a s, i s, tiint, a datelor. De exemplu, matricea mat cu n linii s, i m coloane poate fi reprezentat˘a ˆın urm˘atorul mod: mat[1][1] mat[1][2] ... mat[1][m] mat[2][1] mat[2][2] ... mat[2][m] ... ... ... ... mat[n][1] mat[n][2] ... mat[n][m] Operat, ii cu matrice: Citirea elementelor unei matrice: Algorithm Citire(mat,n,m) For i ← 1, n execute For j ← 1, m execute Read mat[i][j] EndFor EndFor EndAlgorithm 17
Subiect · pagina 23
Tipuri structurate de date Teorie Afis, area elementelor unei matrice: Algorithm Afis, are(mat,n,m) For i ← 1, n execute For j ← 1, m execute Write mat[i][j] EndFor EndFor EndAlgorithm 3.1.5 Matrici p˘atratice Not˘am cu n num˘arul de linii s, i coloane ale matricei, i reprezentˆand indicele liniei, iar j indicele coloanei. Relat, iile dintre indicii unei matrice p˘atratice: - Diagonala principal˘a: Elementele de pe diagonala principal˘a sunt cele pentru care indicele liniei este egal cu indicele coloanei, adic˘a i = j. Deasupra diagonalei principale, se respect˘a relat, ia i < j, iar sub diagonala principal˘a i > j. - Diagonala secundar˘a: Elementele de pe diagonala secundar˘a sunt cele pentru care suma indicilor liniei s, i coloanei este egal˘a cu n−1, adic˘a i+j = n+1. Deasupra diagonalei secundare, se respect˘a relat, ia i + j < n + 1, iar sub diagonala secundar˘a i + j > n + 1. Prin trasarea ambelor diagonale, se delimiteaz˘a patru zone diferite ale matricei: Nord, Sud, Est s, i Vest Nord Sud EstVest • Nord: Elemente situate deasupra di- agonalei principale s, i a diagonalei se- cundare, unde i < j s, i i + j < n + 1. • Sud: Elemente situate sub diagonala principal˘a s, i sub diagonala secundar˘a, unde i > j s, i i + j > n + 1. • Vest: Elemente situate sub diago- nala secundar˘a, dar deasupra diagona- lei principale, unde i > j s, i i + j < n + 1. • Est: Elemente situate deasupra dia- gonalei secundare, dar sub diagonala principal˘a, unde i < j s, i i + j > n + 1. Cele mai ˆıntˆalnite probleme cu matrice sunt: • Interschimbarea a dou˘a linii sau coloane • Rotirea unei matrice • Labirint 3.1.6 Tipul s, ir de caractere Un s, ir de caractere este o structur˘a de date utilizat˘a pentru a stoca s, i manipula secvent, e de caractere. Acesta poate reprezenta cuvinte, propozit, ii sau alte combinat, ii de caractere, 18
Subiect · pagina 24
Tipuri structurate de date Probleme fiind unul dintre cele mai utilizate tipuri de date ˆın programare. ˆIn majoritatea limbajelor de programare, un s, ir este tratat ca un tablou unidimensional de caractere. Reprezentarea s, irurilor de caractere s, i codurile ASCII: Fiecare caracter dintr-un s, ir este reprezentat intern printr-un cod numeric, conform stan- dardului ASCII (American Standard Code for Information Interchange). De exemplu: -’A’ are codul ASCII 65. -’a’ are codul ASCII 97. -’0’ are codul ASCII 48. Aceast˘a reprezentare permite manipularea direct˘a a caracterelor folosind operat, ii pe co- durile lor. ˆIn memorie, un s, ir de caractere este stocat sub forma unui tablou de caractere, fiecare celul˘a cont, inˆand codul ASCII al unui caracter. S, irul este terminat de caracterul special ’\0’ (null) pentru a marca sfˆars, itul. Accesarea unui caracter dintr-un s, ir: Fiecare caracter al unui s, ir poate fi accesat folosind un indice (ˆıncepˆand de la 1). De exemplu, pentru s, irul de caractere s = ”admitere UBB”, s[1] = ’a’, s[5] = ’t’, s[8] = ’ ’, s[12] = ’B’ s, i s[13] = ’\0’. 3.2 Probleme 46. ✓ ?Se consider˘a algoritmul Verifica(n, a), unde n este un num˘ar natural (1 ≤ n ≤ 103) s, i a este un vector cu n elemente numere ˆıntregi (a[1], a[2], ..., a[n]), unde −100 ≤ a[i] ≤ 100, pentru i = 1, 2, ..., n: Algorithm Verifica(n, a) m ← n DIV 2 For i ← 1,m execute If n MOD 2 = 0 then aux ← a[m + i] a[m + i] ← a[n − i + 1] a[n − i + 1] ← aux Else aux ← a[m + i + 1] a[m + i + 1] ← a[n − i + 1] a[n − i + 1] ← aux EndIf EndFor For i ← 1,m execute If a[i]̸ = a[n − i + 1] then Return False EndIf EndFor Return True EndAlgorithm Se cere s˘a se determine pentru ce valori ale vectorului a, apelul Verifica(n, a) retur- neaz˘a True. A. a = [1, 2, 3, 4, 3, 2, 1]; B. a = [1, 2, 3, 3, 3, 1, 2, 1]; C. a = [1, 2, 1, 2]; D. a = [−200, 10, −200]. 47. ✓ ?Se consider˘a algoritmul Alg(x, m), unde m este un num˘ar natural (1 ≤ m ≤ 103) s, i x este un vector cu m elemente numere ˆıntregi (x[1], x[2], ..., x[m]), unde −100 ≤ x[i] ≤ 100, pentru i = 1, 2, ..., m: 19
Subiect · pagina 25
Tipuri structurate de date Probleme Algorithm Alg(x, m) f x ← 0 For p ← 1,m execute a ← 0 For q ← p,m execute a ← a + x[q] If a = 0 then w ← q − p + 1 If w > f x then f x ← w EndIf EndIf EndFor EndFor Return f x EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt false? A. Algoritmul are o complexitate de timp O(m3); B. Variabila a este folosit˘a pentru a cal- cula lungimea unei subsecvent, e; C. Pentru x = [2, 2, 2], rezultatul retur- nat este 0; D. Pentru x = [0, 2, −2, 1, 1, −1, 1, 6, 0, −1], re- zultatul returnat este 4. 48. ✓ ?Se consider˘a algoritmul Contor(x,n), unde n este un num˘ar natural (1 ≤ n ≤ 103) s, i x este un vector cu n elemente numere ˆıntregi (x[1], x[2], ..., x[n]), unde 0 ≤ x[i] ≤ 105, s, i algoritmul Alg(numar), unde numar este un num˘ar natural (0 ≤ numar): Algorithm Alg(numar) If numar < 2 then Return False EndIf For d ← 2,√numar execute If numar MOD d = 0 then Return False EndIf EndForReturn True EndAlgorithm Algorithm Contor(x, n) count ← 0 For i ← 1,n − 1 execute For j ← i + 1 to n execute v ← x[i] asc ← True ok ← 1 For k ← i,j − 1 execute If x[k] ≥ x[k + 1] then asc ← False ok ← 0 EndIf If ok = 1 then v ← v + x[k + 1] EndIf EndFor If asc AND Alg(v) then count ← count + 1 EndIf EndFor EndFor Return count EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Pentru x = [7, 7, 7, 7, 7, 7, 7], rezulta- tul returnat de Contor(x,7) este 7; B. Pentru x = [2, 3, 5, 7], rezultatul re- turnat de Contor(x,4) este 2; C. Pentru x = [7, 5, 3, 2], rezultatul re- turnat de Contor(x,4) este 2; D. Pentru x = [7, 2, 2, 9, 6], rezultatul re- turnat de Contor(x,5) este 1. 20
Subiect · pagina 26
Tipuri structurate de date Probleme 49. ✓ ?Se consider˘a 2 algoritmi: A(x,n,k) s, i B(x,n,k), unde n este un num˘ar natural (1 ≤ n ≤ 103) s, i x este un vector cu n elemente numere ˆıntregi (x[1], x[2], ..., x[n]), unde 0 ≤ x[i] ≤ 105, pentru i = 1, 2, ..., n, k num˘ar natural. Algorithm A(x, n, k) k ← k MOD n For i ← 1, k execute temp[i] ← x[i] EndFor For i ← k + 1, n execute x[i − k] ← x[i] EndFor For i ← 1, k execute x[n − k + i] ← temp[i] EndFor EndAlgorithm Algorithm Helper(x, n) primul ← x[1] For i ← 1, n − 1 execute x[i] ← x[i + 1] EndFor x[n] ← primul EndAlgorithm Algorithm B(x, n, k) For i ← 1, k execute Helper(x, n) EndFor EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Algoritmul A face acelas, i lucru ca algoritmul B, dar algoritmul A este mai eficient; B. Algoritmul A nu face acelas, i lucru ca algoritmul B; C. Algoritmul A face acelas, i lucru ca algoritmul B, dar algoritmul B este mai eficient; D. Algoritmul A face acelas, i lucru ca algoritmul B doar dac˘a k = n. 50. ✓ ?Se consider˘a algoritmul Calculeaza(x,n), unde n este un num˘ar natural (1 ≤ n ≤ 103) s, i x este un vector cu n elemente numere ˆıntregi (x[1], x[2], ..., x[n]), unde −104 ≤ x[i] ≤ 104, pentru i = 1, 2, ..., n: Algorithm Calculeaza(x, n) s ← x[1] a ← x[1] For i ← 2, n execute If a + x[i] > x[i] then a ← a + x[i] Else a ← x[i] EndIf If a > s then s ← a EndIf EndFor Return s EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Pentru x = [−2, 1, −3, 4, −1, 2, 1, −5, 4], rezul- tatul returnat de Calculeaza(x,9) este 6; B. Pentru x = [1, −2, 3, 5, −1], rezultatul returnat de Calculeaza(x,5) este 8; C. Pentru x = [−1, −2, −3, −4], rezulta- tul returnat de Calculeaza(x,4) este −1; D. Pentru x = [2, 4, −1, 3], rezultatul re- turnat de Calculeaza(x,4) este 6. Problemele 51. s, i 52. se refer˘a la urm˘atorii 2 algoritmi: Se consider˘a algoritmul Afiseaza(x,n,k), unde n este un num˘ar natural (1 ≤ n ≤ 103), x este un vector cu n elemente numere ˆıntregi (x[1], x[2], ..., x[n]), unde −104 ≤ x[i] ≤ 104, pentru i = 1, 2, ..., n, s, i k este un num˘ar natural (1 ≤ k ≤ n), s, i algoritmul A(x,n), unde n, x au aceleas, i restrict, ii ca pentru algoritmul Afiseaza(x,n,k): 21
Subiect · pagina 27
Tipuri structurate de date Probleme Algorithm A(x, n) For i ← 1,n − 1 execute For j ← i + 1,n execute If x[i] > x[j] then a ← x[i] x[i] ← x[j] x[j] ← a EndIf EndFor EndFor EndAlgorithm Algorithm Afiseaza(x, n, k) A(x, n) i ← 1 While i ≤ n execute count ← 1 While i + count ≤ n AND x[i] = x[i + count] execute count ← count + 1 EndWhile If count MOD k̸ = 0 then scrie x[i] EndIf i ← i + count EndWhile EndAlgorithm 51. ✓ ?Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Apelul algoritmului A(x,n) nu afecteaz˘a rezultatul afis, at de algoritmul Afiseaza(x,n,k), indiferent de parametri; B. Apelul algoritmului A(x,n) nu afecteaz˘a rezultatul afis, at de algoritmul Afiseaza(x,n,k), dac˘a s, i numai dac˘a s, irul x este ordonat cresc˘ator; C. Algoritmul A(x,n) sorteaz˘a cresc˘ator s, irul x; D. Algoritmul A(x,n) sorteaz˘a descresc˘ator s, irul x. 52. ✓ ?Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Pentru x = [1, 4, 1, 2, 3, 3, 2] s, i k = 2, rezultatul afis, at de Afiseaza(x,7,2) este 4; B. Pentru x = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4] s, i k = 3, rezultatul afis, at de Afiseaza(x,10,3) este 1, 2, 4; C. Pentru x = [5, 6, 5, 7, 6, 6, 7] s, i k = 2, rezultatul afis, at de Afiseaza(x,7,2) este 5, 7; D. Pentru x = [2, 2, 4, 4, 4, 6, 4, 5] s, i k = 2, rezultatul afis, at de Afiseaza(x,8,2) este 4, 6. 53. ✓ ?Se consider˘a algoritmul Peak(x,n), unde n este un num˘ar natural (3 ≤ n ≤ 103), x este un vector cu n elemente numere ˆıntregi (x[1], x[2], ..., x[n]), unde −104 ≤ x[i] ≤ 104, pentru i = 1, 2, ..., n: Algorithm Peak(x, n) i ← 1 While i < n and x[i] < x[i + 1] execute i ← i + 1 EndWhile If i = 1 or i = n then Return False EndIf While i < n and x[i] > x[i + 1] execute i ← i + 1 EndWhile 22
Subiect · pagina 28
Tipuri structurate de date Probleme Return i = n EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Pentru x = [1, 2], rezultatul returnat de Peak(x,2) este True; B. Pentru x = [1, 4, 3, 2, 1], rezultatul returnat de Peak(x,5) este True; C. Pentru x = [1, 3, 3, 2, 1], rezultatul returnat de Peak(x,5) este False; D. Pentru x = [1, 2, 3, 4], rezultatul returnat de Peak(x,3) este True. 54. ✓ ?Se consider˘a algoritmul Down(x,n), unde n este un num˘ar natural (3 ≤ n ≤ 103), x este un vector cu n elemente numere ˆıntregi (x[1], x[2], ..., x[n]), unde −104 ≤ x[i] ≤ 104, pentru i = 1, 2, ..., n: Algorithm Down(x, n) i ← 1 While i < n and x[i] > x[i + 1] execute i ← i + 1 EndWhile If i = 1 or i = n then Return False EndIf While i < n and x[i] < x[i + 1] execute i ← i + 1 EndWhile If i = n then Return True Else Return False EndIf EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Pentru x = [4, 2, 3, 5], rezultatul returnat de Down(x,4) este True; B. Pentru x = [4, 3, 2, 1], rezultatul returnat de Down(x,4) este True; C. Pentru x = [1, 2, 3, 4], rezultatul returnat de Down(x,4) este False; D. Pentru x = [4, 3, 3, 2, 1], rezultatul returnat de Down(x,5) este True. 55. ✓ ?Se consider˘a algoritmul Get(a,b,n,m), unde n s, i m sunt lungimile sirurilor de ca- ractere a s, i b, respectiv, iar a s, i b sunt dou˘a s, iruri de caractere formate din litere mici ale alfabetului englez (a[1], a[2], ..., a[n]) s, i (b[1], b[2], ..., b[m]): Presupunem c˘a avem definit urm˘atorul subalgoritm: ascii(c) - returneaz˘a codul ASCII al caracterului c. Presupunem c˘a operat, iile aritmetice nu produc dep˘as, ire pe mult, imea numerelor ˆıntregi. Algorithm Get(a, b, n, m) i ← 1 While i ≤ n and i ≤ m and a[i] = b[i] execute i ← i + 1 EndWhile Return i − 1 EndAlgorithm 23
Subiect · pagina 29
Tipuri structurate de date Probleme Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Pentru a = abcdef, b = abcxyz, rezultatul returnat de Get(a,b,6,6) este 3; B. Pentru a = hello, b = world, rezultatul returnat de Get(a,b,5,5) este 1; C. Pentru a = test, b = testcase, rezultatul returnat de Get(a,b,4,8) este 4; D. Pentru a = abcd, b = abef, rezultatul returnat de Get(a,b,4,4) este 2. 56. ✓ ?Se d˘a un s, ir a de n caractere din alfabetul englez, (a[1], a[2], ..., a[n]). Dorim s˘a afl˘am cea mai lung˘a subsecvent, ˘a a sa care este palindrom. Care dintre urm˘atoarele imple- ment˘ari returneaz˘a lungimea acestei subsecvent, e la apelul LongestPalindrome(a,n)? A. Algorithm LongestPalindrome(a, n) maxLength ← 1 For i ← 1,n execute len1 ← ExpandAroundCenter(a, n, i, i) len2 ← ExpandAroundCenter(a, n, i, i+1) If len1 > maxLength then maxLength ← len1 EndIf If len2 > maxLength then maxLength ← len2 EndIf EndFor Return maxLength EndAlgorithm Algorithm ExpandAroundCenter(a, n, l, r) While l ≥ 1 and r ≤ n and a[l] = a[r] execute l ← l − 1 r ← r + 1 EndWhile Return r − l − 1 EndAlgorithm B. Algorithm LongestPalindrome(a, n) maxLength ← 0 For i ← 1 to n execute For j ← i + 1 to n execute If a[i] = a[j] then If j − i + 1 > maxLength then maxLength ← j − i + 1 EndIf EndIf EndFor EndFor Return maxLength EndAlgorithm C. Algorithm LongestPalindrome(a, n) maxLength ← 1 start ← 1 For i ← 1,n execute 24
Subiect · pagina 30
Tipuri structurate de date Probleme dp[i][i] ← True EndFor For i ← 1,n − 1 execute If a[i] = a[i + 1] then dp[i][i + 1] ← True start ← i maxLength ← 2 EndIf EndFor For len ← 3,n execute For i ← 1,n − len + 1 execute j ← i + len − 1 If a[i] = a[j] and dp[i + 1][j − 1] = True then dp[i][j] ← True If len > maxLength then maxLength ← len start ← i EndIf EndIf EndFor EndFor Return maxLength EndAlgorithm D. Niciuna dintre variante. 57. ✓ ?Se consider˘a algoritmul Compute(m,n), unde n este dimensiunea unei matrici p˘atratice m de dimensiune n x n, iar m este o matrice cu elemente ˆıntregi (m[1][1], m[1][2], ..., m[n][n]): Algorithm Compute(m, n) p1 ← 1 p2 ← 1 For i ← 1 to n execute p1 ← p1 · m[i][i] p2 ← p2 · m[i][n − i + 1] EndFor Return p1 · p2 EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Pentru m = 1 2 3 4 , rezultatul returnat de Compute(m,2) este 11; B. Pentru m = 2 3 4 5 6 7 8 9 10 , rezultatul returnat de Compute(m,3) este 23040; C. Pentru m = 1 0 0 0 1 0 0 0 1 , rezultatul returnat de Compute(m,3) este 1; D. Pentru m = 3 1 2 4 5 6 7 8 9 , rezultatul returnat de Compute(m,3) este 11430. 25
Subiect · pagina 31
Tipuri structurate de date Probleme Problemele 58. s, i 59. se refer˘a la urm˘atorii 2 algoritmi: Se consider˘a algoritmul algoritmul B(m,n), unde n este dimensiunea unei matrici p˘atratice m de dimensiune n x n, iar m este o matrice cu elemente ˆıntregi (m[1][1], m[1][2], ..., m[n][n]), s, i algoritmul A(m,n,i,s1,s2), unde m, n au aceleas, i restrict, ii ca pentru algoritmul B(m,n), iar i,s1,s2 sunt numere ˆıntregi. Algorithm A(m, n, i, s1, s2) If i = n + 1 then Return s1 − s2 EndIf x ← 0 For j ← 1,n execute x ← x + m[i][j] EndFor If i MOD 2 = 0 then s1 ← s1 + x Else s2 ← s2 + x EndIf Return A(m, n, i + 1, s1, s2) EndAlgorithm Algorithm B(m, n) Return A(m, n, 1, 0, 0) EndAlgorithm 58. ✓ ?Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Pentru m = 1 2 3 4 , rezultatul returnat de B(m,2) este 4; B. Pentru m = 2 3 4 5 6 7 8 9 10 , rezultatul returnat de B(m,3) este −18; C. Pentru m = 1 1 1 1 1 1 1 1 1 , rezultatul returnat de B(m,3) este 0; D. Pentru m = 10 20 30 5 15 25 40 50 60 , rezultatul returnat de B(m,3) este 65. 59. ✓ ?Dac˘a ˆın subalgoritmul A(m,n,i,s1,s2), ˆınlocuim apelul Return A(m, n, i + 1, s1, s2) cu Return A(m, n, i − 1, s1, s2), ce ar trebui modificat ˆın subalgoritmul B(m,n) pentru a oferi acelas, i rezultat? A. ˆInlocuim Return A(m, n, 1, 0, 0) cu Return A(m, n, 0, n, 0); B. ˆInlocuim Return A(m, n, 1, 0, 0) cu Return A(m, n, 0, n, n − 1); C. ˆInlocuim Return A(m, n, 1, 0, 0) cu Return A(m, n, 0, 0, n); D. ˆInlocuim Return A(m, n, 1, 0, 0) cu Return A(m, n, n, 0, 0); 60. ✓ ?Se consider˘a algoritmii H(m,mx,nx) s, i G(m,mx,nx), unde m este o matrice cu mx linii s, i nx coloane (m[1][1], m[1][2], ..., m[mx][nx]), mx s, i nx sunt numere naturale mai 26
Subiect · pagina 32
Tipuri structurate de date Probleme mari decˆat 2: Algorithm H(m, mx, nx) For j ← 1,nx execute temp ← m[mx − 2][j] m[mx − 2][j] ← m[mx − 1][j] m[mx − 1][j] ← temp EndFor For i ← 1,mx execute temp ← m[i][nx − 2] m[i][nx − 2] ← m[i][nx − 1] m[i][nx − 1] ← temp EndFor Return m EndAlgorithm Algorithm G(m, mx, nx) For i ← 1,mx execute temp ← m[i][nx − 2] m[i][nx − 2] ← m[i][nx − 1] m[i][nx − 1] ← temp EndFor For j ← 1,nx execute temp ← m[mx − 2][j] m[mx − 2][j] ← m[mx − 1][j] m[mx − 1][j] ← temp EndFor Return m EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Ambii algoritmi au acelas, i efect asupra unei matrici m; B. Pentru m = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 , rezultatul returnat de H(m,4,4) este 1 2 4 3 5 6 8 7 13 14 16 15 9 10 12 11 ; C. Algoritmul H(m,mx,nx) returneaz˘a un rezultat diferit fat, ˘a de rezultatul returnat de algoritmul G(m,mx,nx); D. Pentru m = 1 2 3 4 5 6 7 8 9 , rezultatul returnat de G(m,3,3) este 1 2 3 7 8 9 4 5 6 . 61. ✓ ?Se consider˘a algoritmul Cauta(a, n , i, j), unde s este un vector cu n elemente, init, ial egale cu 0, iar a un s, ir de numere ˆıntregi (a[1], a[2], ..., a[n]) cu n elemente, 1 ≤ i ≤ j < n + 1: Algorithm Cauta(a, n, i, j) s ← Construieste(a, n) If i = 1 then Return s[j] Else Return s[j] − s[i − 1] EndIf EndAlgorithm Algorithm Construieste(a, n) s[1] ← a[1] For k ← 2,n execute s[k] ← s[k − 1] + a[k] EndFor Return s EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? 27
Subiect · pagina 33
Tipuri structurate de date Probleme A. Pentru a = [1, 2, 3, 4, 5] s, i i = 2, j = 4, rezultatul returnat de Cauta(a,5,2,4) este 9; B. Pentru a = [1, 1, 1, 1, 1] s, i i = 1, j = 4, rezultatul returnat de Cauta(a,5,1,4) este 5; C. Algoritmul returneaz˘a suma elementelor dintre indicii i s, i j, inclusiv, ai vectorului a; D. Algoritmul returneaz˘a suma elementelor dintre indicii i s, i j, f˘ar˘a a[i], a[j], ai vectorului a. 62. ✓ ?Se consider˘a algoritmul Find(m, n), unde n este dimensiunea unei matrici p˘atratice m de dimensiune n x n. Algorithm Find(m, n) For i ← 1, n execute For j ← i + 1, n execute If m[i][j]̸ = m[j][i] then Return False EndIf EndFor EndFor Return True EndAlgorithm Ce face algoritmul? A. Verific˘a dac˘a toate elementele de pe marginea matricei sunt egale; B. Verific˘a dac˘a toate elementele de pe diagonala principal˘a sunt egale; C. Verific˘a dac˘a matricea este simetric˘a fat, ˘a de diagonala secundar˘a; D. Verific˘a dac˘a matricea este simetric˘a fat, ˘a de diagonala principal˘a. 63. ✓ ?Se consider˘a algoritmul bin(arr, n), unde n este un num˘ar natural nenul (1 ≤ n ≤ 104) s, i arr este un s, ir binar de n elemente. Algorithm bin(arr, n) cont ← 0 For i ← 1, n − 1 execute cont ← cont + arr[i] * arr[i + 1] EndFor Return cont EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Pentru apelul bin([0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1], 20), algoritmul returneaz˘a 6. B. Pentru n = 11, exist˘a exact 233 s, iruri binare arr cu proprietatea c˘a apelul bin(arr, n) returneaz˘a 0. C. Pentru n = 6, exist˘a exact 20 s, iruri binare arr cu proprietatea c˘a apelul bin(arr, n) returneaz˘a 0. D. Pentru n = 8, exist˘a exact 201 s, iruri binare arr cu proprietatea c˘a apelul bin(arr, n) returneaz˘a o valoare diferit˘a de 0. 28
Subiect · pagina 34
Tipuri structurate de date Probleme 64. ✓ ?Fie vectorul v = [3, 5, 2, 2, 7, 9, 1, 1, 4, 6]. Primul element este situat pe pozit, ia 0. Care este valoarea expresiei urm˘atoare? v[2 ∗ v[2 ∗ v[3] − 1] + 1] + v[2 ∗ v[7 − 5] − 1] + v[3 − v[2 ∗ v[2] − 3] + 6] A. 11 B. 24 C. 18 D. Niciuna din variantele de mai sus. 65. ✓ ?Se consider˘a algoritmul Algo(a, n, m, k), unde a este un tablou bidimensional cu dimensiunea n × m (1 ≤ n, m ≤ 103), unde n s, i m sunt numere naturale iar fiecare element din a este un num˘ar natural. Parametrul k este un num˘ar natural (1 ≤ k ≤ min(n, m)). Fie x o matrice de dimenisune n × m, unde fiecare element este init, ializat cu 0. Algorithm Algo(a, n, m, k) max ← 0 For i ← 1, n execute For j ← 1, m execute If Check(a[i][j]) then x[i][j] ← a[i][j] EndIf EndFor EndFor For i ← 1, n − k + 1 execute For j ← 1, m − k + 1 execute sum ← 0 For p ← 0, k − 1 execute For q ← 0, k −1 execute sum ← sum + x[i + p][j + q] EndFor EndFor If sum > max then max ← sum EndIf EndFor EndFor Return max EndAlgorithm Algorithm Check(num) If num ≤ 1 then Return False EndIf For i ← 2, √num execute If num MOD i = 0 then Return False EndIf EndFor Return True EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Complexitatea algoritmului este O(n · m · k2). B. Algoritmul Algo determin˘a suma maxim˘a a elementelor prime dintr-o submatrice k × k din a. C. Pentru apelul f(a, 5, 5, 3) s, i matricea a = 2 3 4 5 6 3 5 7 9 11 4 5 7 10 13 5 9 13 17 4 6 11 16 4 9 algoritmul va returna valoarea 62. 29
Subiect · pagina 35
Tipuri structurate de date Probleme D. Algoritmul verific˘a dac˘a exist˘a o submatrice k × k ˆın care toate elementele sunt numere prime s, i returneaz˘a suma acestora. 66. ✓ ?Fie vectorul v = [4, 7, 1, 9, 6, 3, 8, 5, 5, 2]. Primul element este situat pe pozit, ia 0. Care este valoarea expresiei urm˘atoare? v[2 ∗ v[4] MOD 3] + v[v[7] DIV 2 − 1] ∗ v[3 − v[2] + 1] A. 42 B. 67 C. Acelas, i rezultat ca al expresiei v[v[9] ∗ v[4] MOD v[5]] + v[v[8] DIV v[9] − v[2]] ∗ v[3 − v[2] + v[2]]. D. Acelas, i rezultat ca al expresiei v[v[8] MOD v[5]∗3]∗v[3]−v[v[9]]−v[0]−v[v[2] DIV 3]∗ v[4 − v[5]]. 30
Subiect · pagina 36
4 Algoritmi elementari Acest capitol acoper˘a • Baze de numerat, ie • Divizibilitate • Determinare minim/maxim • C˘aut˘ari secvent, iale/binare pe s, iruri de numere • Interclasare • Metode de sortare 4.1 Teorie 4.1.1 Baze de numerat, ie Cu except, ia bazei 10, alte baze de numerat, ie utilizate frecvent sunt: • Baza 2 (binar): cifrele 0 s, i 1, utilizat˘a ˆın computere. • Baza 8 (octal): cifrele 0-7, folosit˘a pentru simplificarea reprezent˘arii binare. • Baza 16 (hexazecimal): cifrele 0-9 s, i literele A − F (A = 10, B = 11, ..., F = 15). • Baza b (caz general): cifrele 0, 1, ..., b − 1 Transformarea din baza 10 ˆın baza b Transformarea unui num˘ar n din baza 10 ˆın baza b, se realizeaz˘a utilizˆand metoda ˆımp˘art, irii repetate, conform urm˘atorilor pas, i: • ˆImparte cu rest num˘arul n la baza b. • Noteaz˘a restul (care va deveni o cifr˘a ˆın baza b). • ˆImparte cˆatul obt, inut anterior la baza b. • Repet˘a pˆan˘a cˆand cˆatul devine 0. • Resturile obt, inute, scrise ˆın ordinea invers˘a obt, inerii, reprezint˘a scrierea ˆın baza b a lui n.
Subiect · pagina 37
Algoritmi elementari Teorie Pasul 1: 46 ÷ 3 = 15 Rest: 1 Pasul 2: 15 ÷ 3 = 5 Rest: 0 Pasul 3: 5 ÷ 3 = 1 Rest: 2 Pasul 4: 1 ÷ 3 = 0 Rest: 1 Rezultat final: 46(10) = 1201(3) Transformare iterativ˘a din baza 10 ˆın baza b: 1: Algorithm iterativ(n, b) 2: poz ← 0 3: While n > 0 execute 4: poz ← poz + 1 5: cif re[poz] ← n MOD b 6: n ← n DIV b 7: EndWhile 8: For i ← poz, 1, −1 execute 9: Write cif re[i] 10: EndFor 11: EndAlgorithm Complexitate: O(log(n)) Transformare recursiv˘a din baza 10 ˆın baza b: 1: Algorithm recursiv(n, b) 2: If n > 0 then 3: recursiv(n DIV b, b) 4: Write n MOD b 5: EndIf 6: EndAlgorithm Complexitate: O(log(n)) Transformarea din baza b ˆın baza 10 Pentru a converti un num˘ar din baza b ˆın baza 10, folosim o formul˘a care exprim˘a num˘arul ca o sum˘a de puteri ale bazei b. Fie un num˘ar ckck−1 . . . c1c0(b), atunci conversia acestuia ˆın baza 10 se face conform formulei: ckck−1 . . . c1c0(b) = ck · bk + ck−1 · bk−1 + · · · + c1 · b1 + c0 · b0 Exemplu: 11010001(2) = 1 · 27 + 1 · 26 + 0 · 25 + 1 · 24 + 0 · 23 + 0 · 22 + 0 · 21 + 1 · 20 = 1 · 128 + 1 · 64 + 0 · 32 + 1 · 16 + 0 · 8 + 0 · 4 + 0 · 2 + 1 · 1 = 128 + 64 + 0 + 16 + 0 + 0 + 0 + 1 = 128 + 64 + 16 + 1 32
Subiect · pagina 38
Algoritmi elementari Teorie = 209 Astfel, rezultatul este: 11010001(2) = 209(10) Transformare iterativ˘a din baza b ˆın baza 10: 1: Algorithm iterativ(n, b) 2: result ← 0 3: p ← 1 4: While n > 0 execute 5: result ← result + (n MOD 10) ∗ p 6: p ← p ∗ b 7: n ← n DIV 10 8: EndWhile 9: Return result 10: EndAlgorithm Transformare recursiv˘a din baza b ˆın baza 10: 1: Algorithm recursiv(n, b) 2: If n = 0 then 3: Return 0 4: EndIf 5: Return (n MOD 10) + recursiv(n DIV 10, b) ∗ b 6: EndAlgorithm Transformarea din baza b ˆın baza d Pentru transformarea unui num˘ar din baza b ˆın baza d, procesul poate fi realizat ˆın dou˘a etape principale: • 1. Conversia num˘arului din baza b ˆın baza 10. • 2. Conversia rezultatului din baza 10 ˆın baza d. 4.1.2 Conversii rapide Transform˘arile rapide ˆıntre baze care sunt puteri ale lui 2 (cum ar fi 2, 4, 8 sau 16) se bazeaz˘a pe gruparea cifrelor binare ˆın subgrupuri specifice. Aceast˘a abordare permite conversia direct˘a a unui num˘ar din baza 2 ˆın alte baze f˘ar˘a a trece prin baza 10. 1. Conversia din baza 2 ˆın baza 4, 8, sau 16 se realizeaz˘a ˆın urm˘atorul mod: • Grupare: ˆImp˘art, im num˘arul binar ˆın grupuri de cˆate 2 cifre (pentru baza 4), 3 cifre (pentru baza 8) sau 4 cifre (pentru baza 16) cifre. Dac˘a num˘arul de cifre binare nu este multiplu al dimensiunii grupului, se completeaz˘a cu zerouri ˆın partea stˆang˘a. • Conversie: Fiecare grup de cifre binare se transform˘a direct ˆın cifra corespunz˘atoare din baza dorit˘a. Exemplu: 33
Subiect · pagina 39
Algoritmi elementari Teorie a. Din baza 2 ˆın baza 4: • Num˘ar: 110101110(2) • Grupare: 4 = 22: (01)(10)(10)(11)(10) • Conversie: 1, 2, 2, 3, 2 • Rezultatul: 12232(4) b. Din baza 2 ˆın baza 8: • Num˘ar: 110101110(2) • Grupare: 8 = 23: (110)(101)(110) • Conversie: 6, 5, 6 • Rezultatul: 656(8) c. Din baza 2 ˆın baza 16: • Num˘ar: 110101110(2) • Grupare: 16 = 24: (0001)(1010)(1110) • Conversie: 1, A, E • Rezultatul: 1AE(16) 2. Conversia din baza 4, 8, sau 16 ˆın baza 2: • Fiecare cifr˘a din baza respectiv˘a se transform˘a ˆın echivalentul s˘au binar, folosind 2 (pentru baza 4), 3 (pentru baza 8) sau 4 (pentru baza 16) cifre binare pentru fiecare cifr˘a din baza respectiv˘a. Exemplu: a. Din baza 4 ˆın baza 2: • Num˘ar: 10313(4) • Grupare: 1, 0, 3, 1, 3 • Conversie: (01)(00)(11)(01)(11) • Rezultatul: 100110111(2) b. Din baza 8 ˆın baza 2: • Num˘ar: 467(8) • Grupare: 4, 6, 7 • Conversie: (100)(110)(111) • Rezultatul: 100110111(2) c. Din baza 16 ˆın baza 2: • Num˘ar: 137(16) • Grupare: 1, 3, 7 • Conversie: (0001)(0011)(0111) • Rezultatul: 100110111(2) 4.1.3 Divizibilitate Divizibilitatea se refer˘a la proprietatea unui num˘ar a de a fi ˆımp˘art, it exact la un alt num˘ar b (notat b | a). 34
Subiect · pagina 40
Algoritmi elementari Teorie • Divizor: Un num˘ar care ˆımparte exact alt num˘ar, adic˘a restul ˆımp˘art, irii ˆıntregi este 0. De exemplu, 2 este divizor al lui 8. • Multiplu: Rezultatul obt, inut prin ˆınmult, irea unui num˘ar ˆıntreg cu alt num˘ar. De exemplu, 12 este multiplu al lui 3. • Rest: Num˘arul r˘amas dup˘a ˆımp˘art, ire. De exemplu, restul ˆımp˘art, irii lui 10 la 3 este 1. Divizorii unui num˘ar Un num˘ar d este divizor al lui n dac˘a n : d = k, unde k este un num˘ar ˆıntreg. Exemplu: Pentru n = 12, divizorii sunt 1, 2, 3, 4, 6, 12. Exemplu 1: Afis, area divizorilor unui num˘ar 1: Algorithm afisare(n) 2: For d ← 1, n execute 3: If n MOD d = 0 then 4: Write d, ’ ’ 5: EndIf 6: EndFor 7: EndAlgorithm Complexitate: O(n) Exemplu 2: Afis, area divizorilor unui num˘ar 1: Algorithm afisare(n) 2: For d ← 1, d ∗ d ≤ n execute 3: If n MOD d = 0 AND d ∗ d < n then 4: Write d, ’ ’, n DIV d, ’ ’ 5: Else 6: If d ∗ d = n then 7: Write d 8: EndIf 9: EndIf 10: EndFor 11: EndAlgorithm Complexitate: O(√n) Observat, ii importante • Divizorii unui num˘ar sunt simetrici: dac˘a d este un divizor al lui n, atunci n DIV d este de asemenea un divizor. • Numerele care nu sunt p˘atrate perfecte au num˘ar par de divizori. • Singurele numere cu num˘ar impar de divizori sunt p˘atratele perfecte. • Cel mai mic divizor propriu al unui num˘ar natural (diferit de 1 s, i de num˘arul ˆınsus, i) este ˆıntotdeauna un num˘ar prim. CMMDC (Cel Mai Mare Divizor Comun) Cel mai mare divizor comun (CMMDC) al dou˘a numere naturale a s, i b este cel mai mare num˘ar natural care divide atˆat pe a, cˆat s, i pe b. CMMDC al numerelor a s, i b se noteaz˘a (a, b). Dac˘a (a, b) = 1, spunem c˘a a s, i b sunt prime ˆıntre ele. Descompunerea ˆın factori primi sau Algoritmul lui Euclid reprezint˘a metode prin care putem calcula CMMDC. 35
Subiect · pagina 41
Algoritmi elementari Teorie Algoritmul lui Euclid prin sc˘aderi: Cel mai mare divizor a dou˘a numere divide s, i diferent, a acestora. • Dac˘a a = b, CMMDC este a sau b. • Dac˘a a > b, se ˆınlocuies, te a cu a − b. • Dac˘a a < b, se ˆınlocuies, te b cu b − a. • Se repet˘a pas, ii 2 s, i 3 cˆat timp a̸ = b. Rezultatul final va fi CMMDC. Algoritmul lui Euclid prin sc˘aderi, itera- tiv Algorithm iterativ(a, b) While a̸ = b execute If a > b then a ← a − b Else b ← b − a EndIf EndWhile Return a EndAlgorithm Complexitate: O(min(a, b)) Algoritmul lui Euclid prin sc˘aderi, recur- siv Algorithm recursiv(a, b) If a = b then Return a Else If a > b then Return recursiv(a − b, b) Else Return recursiv(a, b − a) EndIf EndIf EndAlgorithm Complexitate: O(min(a, b)) Algoritmul lui Euclid prin ˆımp˘art, iri (cu resturi): Cel mai mare divizor a dou˘a numere divide s, i restul ˆımp˘art, irii acestora, conform teoremei ˆımp˘art, irii cu rest. • Dac˘a b = 0, CMMDC este a. • Dac˘a b̸ = 0, calculeaz˘a r = a mod b. • ˆInlocuies, te a cu b s, i b cu r. • Repet˘a pas, ii 2-3 cˆat timp b̸ = 0. CMMDC este valoarea final˘a a lui a. Exemplu: Algoritmul lui Euclid pentru a = 56 s, i b = 42: Algoritmul lui Euclid prin ˆımp˘art, iri, ite- rativ Algorithm iterativ(a, b) While b > 0 execute r ← a MOD b a ← b b ← r EndWhile Return a EndAlgorithm Complexitate: O(log(min(a, b))) Algoritmul lui Euclid prin ˆımp˘art, iri, re- cursiv Algorithm recursiv(a, b) If b = 0 then Return a Else Return recursiv(b, a MOD b) EndIf EndAlgorithm Complexitate: O(log(min(a, b))) 36
Subiect · pagina 42
Algoritmi elementari Teorie CMMMC (Cel Mai Mic Multiplu Comun) Cel mai mic multiplu comun (CMMMC) al dou˘a sau mai multe numere ˆıntregi este cel mai mic num˘ar ˆıntreg pozitiv care este divizibil cu toate numerele respective. Pentru dou˘a numere a s, i b, CMMMC se calculeaz˘a folosind formula: CMMMC(a, b) = a · b CMMDC(a, b) , unde CMMDC este cel mai mare divizor comun. Primalitate Un num˘ar prim este un num˘ar ˆıntreg pozitiv mai mare decˆat 1 care are exact doi divizori: 1 s, i el ˆınsus, i. Pentru a verifica algoritmic dac˘a un num˘ar n este prim: • Presupunem c˘a n este prim. • Dac˘a n ≤ 1, atunci nu este prim. • C˘aut˘am un divizor ˆıntre 2 s, i √n. • Dac˘a n nu este divizibil cu niciunul dintre aceste numere, atunci este prim. • Dac˘a g˘asim un divizor d, atunci n nu este prim. Metoda 1: Verificare dac˘a un num˘ar este prim 1: Algorithm primalitate(n) 2: If n ≤ 1 then 3: Return False 4: EndIf 5: For d ← 2, n − 1 execute 6: If n MOD d = 0 then 7: Return False 8: EndIf 9: EndFor 10: Return True 11: EndAlgorithm Complexitate: O(n) Metoda 2: Verificare dac˘a un num˘ar este prim 1: Algorithm primalitate(n) 2: If n ≤ 1 then 3: Return False 4: EndIf 5: If n MOD 2 = 0 AND n > 2 then 6: Return False 7: EndIf 8: For d ← 3, d ∗ d ≤ n, 2 execute 9: If n MOD d = 0 then 10: Return False 11: EndIf 12: EndFor 13: Return True 14: EndAlgorithm Complexitate: O(√n) 37
Subiect · pagina 43
Algoritmi elementari Teorie Observat, ie important˘a • Putem stabili dac˘a un num˘ar n este prim s, i prin urm˘atoarele feluri: – Num˘ar˘am divizorii lui n. Dac˘a are exact 2 divizori, atunci n este prim. – Determin˘am suma divizorilor lui n. Dac˘a suma este egal˘a cu n + 1, num˘arul este prim. Descompunerea ˆın factori primi Descompunerea ˆın factori primi este procesul prin care un num˘ar ˆıntreg pozitiv este exprimat ca produs de numere prime, posibil ridicate la o putere. De exemplu, num˘arul 60 poate fi descompus ˆın factori primi astfel: 60 = 22 · 31 · 51 Pentru a descompune un num˘ar ˆıntreg pozitiv n ˆın factori primi, se urmeaz˘a pas, ii urm˘atori: • ˆIncepem cu cel mai mic num˘ar prim, 2. • ˆImp˘art, im n la 2. Dac˘a n este divizibil cu 2, not˘am 2 ca factor s, i ˆımp˘art, im n cu 2. • Continu˘am ˆımp˘art, irea lui n la 2 pˆan˘a cˆand n nu mai este divizibil cu 2. • Trecem la urm˘atorul num˘ar prim (3, 5, 7, etc.) s, i repet˘am procesul pˆan˘a cˆand n devine egal cu 1. Descompunerea ˆın factori primi 1: Algorithm factorizare(n) 2: d ← 2 3: While n > 1 execute 4: putere ← 0 5: While n MOD d = 0 execute 6: putere ← putere + 1 7: n ← n DIV d 8: EndWhile 9: If putere > 0 then 10: Write d, ^, putere 11: Write new line 12: EndIf 13: d ← d + 1 14: If d ∗ d > n then 15: d ← n 16: EndIf 17: EndWhile 18: EndAlgorithm Complexitate: O(√n) 38
Subiect · pagina 44
Algoritmi elementari Teorie 4.1.4 S¸irul lui Fibonacci S, irurile cu termen general sunt frecvent ˆıntˆalnite ˆın matematic˘a, ˆıns˘a ˆın informatic˘a ele sunt adesea utilizate pentru implementarea structurilor repetitive sau a programelor re- cursive. Cu toate acestea, S, irul lui Fibonacci nu este un s, ir oarecare cu termen general, deoarece al n-lea termen al s˘au este dependent de termenii n − 1 s, i n − 2. Astfel, pentru S, irul lui Fibonacci, sunt valabile urm˘atoarele preciz˘ari: fiecare termen n este suma terme- nilor n − 1 s, i n − 2, iar s, irul ˆıncepe cu termenii 0 s, i 1 (unii programatori consider˘a primii termeni ca fiind 1 s, i 1, dar ambele convent, ii sunt acceptate). ˆIn cele ce urmeaz˘a, vom considera primul termen al s, irului f0 = 0. Deci, dac˘a fn, n ∈ N este s, irul lui Fibonacci, avem: fn = 0, dac˘a n = 0; 1, dac˘a n = 1; fn−1 + fn−2, dac˘a n ≥ 2. Astfel, un posibil program care afis, eaz˘a primii n termeni din s, irul lui Fibonacci s, i care foloses, te un vector este: S, irul lui Fibonacci folosind un array: 1: Algorithm Fibo(n) 2: f [0] ← 1 3: f [1] ← 1 4: For i ← 2, n − 1 execute 5: f [i] = f [i − 1] + f [i − 2] 6: EndFor 7: For i ← 0, n − 1 execute 8: afis, eaz˘a f [i] 9: EndFor 10: EndAlgorithm Aceast˘a implementare este una simpl˘a s, i intuitiv˘a, dar nu este cea mai optim˘a din punct de vedere al complexit˘at, ii spat, iale, deoarece foloses, te un vector de dimensiune n(complexitatea spat, iu este O(n)). Un algoritm care afis, eaz˘a primii n termeni din s, irul lui Fibonacci ˆın complexitate spat, iu O(1) ar fi urm˘atorul, care foloses, te doar 3 variabile, numere naturale: S, irul lui Fibonacci folosind trei variabile: 1: Algorithm Fibo(n) 2: a ← 1 3: b ← 1 4: Write a, Write b 5: For i ← 2, n − 1 execute 6: aux ← a + b 7: a ← b 8: b ← aux 9: Write aux 10: EndFor 11: EndAlgorithm 39
Subiect · pagina 45
Algoritmi elementari Teorie Complexitatea de timp pentru afis, area primelor n numere din s, irul lui Fibonacci este O(n). ˆIns˘a, verificarea dac˘a un num˘ar x este ˆın S, irul lui Fibonacci se poate implementa ˆın complexitatea de timp O(1), folosind urm˘atoarea proprietate: x face parte din s, irul Fibonacci ⇔ ⇔ 5x2 + 4 este p˘atrat perfect sau 5x2 − 4 este p˘atrat perfect . 4.1.5 Determinare minim/maxim Determinarea maximului s, i minimului reprezint˘a procesul de identificare a valorii celei mai mari (maxim) sau celei mai mici (minim) dintr-un set de valori. Maximul s, i minimul a dou˘a valori Determinarea minimului unei valori Algorithm minim(a, b) If a < b then Return a Else Return b EndIf EndAlgorithm Complexitate: O(1) Determinarea maximului unei valori Algorithm maxim(a, b) If a > b then Return a Else Return b EndIf EndAlgorithm Complexitate: O(1) Determinarea minimului pentru un num˘ar oarecare de valori Algoritmul primaValoare va p˘astra ˆın variabila min cu cea mai mic˘a valoare citit˘a (init, ia, prima valoarea citit˘a), ˆın timp ce valoareMare init, ializeaz˘a variabila min cu o valoare su- ficient de mare pentru a permite g˘asirea minimului, ambii algoritmi terminˆandu-se cˆand se introduce valoarea 0. Variabila min init, ializat˘a cu prima va- loare citit˘a 1: Algorithm primaValoare 2: Read nr 3: min ← nr 4: Read nr 5: While nr̸ = 0 execute 6: If nr < min then 7: min ← nr 8: EndIf 9: Read nr 10: EndWhile 11: Write min 12: EndAlgorithm Complexitate: O(n) Variabila M in init, ializat˘a cu o valoare mare 1: Algorithm valoareMare 2: min ← ∞ 3: Read nr 4: While nr̸ = 0 execute 5: If nr < min then 6: min ← nr 7: EndIf 8: Read nr 9: EndWhile 10: Write min 11: EndAlgorithm Complexitate: O(n) 40
Subiect · pagina 46
Algoritmi elementari Teorie Determinarea maximului pentru un num˘ar oarecare de valori Algoritmul primaValoare actualizeaz˘a variabila max cu prima valoare citit˘a, ˆın timp ce valoareMica init, ializeaz˘a variabila max cu o valoare suficient de mic˘a pentru a permite g˘asirea maximului, ambii algoritmi terminˆandu-se cˆand se introduce 0. Variabila M ax init, ializat˘a cu cea mai mare valoarea citit˘a 1: Algorithm primaValoare 2: Read nr 3: max ← nr 4: Read nr 5: While nr̸ = 0 execute 6: If nr > max then 7: max ← nr 8: EndIf 9: Read nr 10: EndWhile 11: Write max 12: EndAlgorithm Complexitate: O(n) Variabila M ax init, ializat˘a cu o valoarea mic˘a 1: Algorithm valoareMica 2: max ← −999999 3: Read nr 4: While nr̸ = 0 execute 5: If nr > max then 6: max ← nr 7: EndIf 8: Read nr 9: EndWhile 10: Write max 11: EndAlgorithm Complexitate: O(n) 4.1.6 C˘aut˘ari pe s, iruri de numere C˘autarea Secvent¸ial˘a C˘autarea secvent¸ial˘a (numit˘a s, i c˘autare liniar˘a) presupune parcurgerea element cu ele- ment a ¸sirului pˆan˘a cˆand fie se g˘ase¸ste elementul c˘autat, fie se ajunge la finalul ¸sirului f˘ar˘a a g˘asi elementul respectiv. Din punct de vedere al complexit˘at¸ii timp, ˆın cel mai bun caz (cˆand elementul se afl˘a la ˆınceputul ¸sirului), complexitatea c˘aut˘arii este O(1), ˆıns˘a ˆın medie ¸si ˆın cel mai r˘au caz, complexitatea va fi O(n), unde n este lungimea ¸sirului. Exemplu: Presupunem c˘a avem ¸sirul A = [2, 5, 7, 10, 14, 20], iar elementul c˘autat este 10. C˘autarea secvent¸ial˘a va compara ˆın ordine elementele: 2, 5, 7, 10, iar la al patrulea element g˘ase¸ste valoarea c˘autat˘a. Ilustrarea grafic˘a a c˘aut˘arii lui 10 ˆın A este aceasta: 2 5 7 10 14 20 10̸ = 2 10̸ = 5 10̸ = 7 10 = 10 Consider˘am A - ¸sir de numere, n - dimensiunea ¸sirului s, i x - elementul c˘autat. O imple- mentare ˆın pseudocod a c˘aut˘arii secvent, iale arat˘a astfel: 41
Subiect · pagina 47
Algoritmi elementari Teorie C˘autare Secvent¸ial˘a 1: For i = 0, n − 1 execute 2: If A[i] = x then 3: Return i ▷ Return˘am pozit, ia lui x 4: EndIf 5: EndFor 6: Return −1 ▷ x nu a fost g˘asit C˘autarea Binar˘a Pentru a putea c˘auta un element ˆıntr-un s, ir folosind C˘autarea Binar˘a, s, irul trebuie s˘a fie sortat (vezi urm˘atorul capitol referitor la Metode de Sortare). Ideea de baz˘a este ˆımp˘art¸irea ¸sirului ˆın dou˘a subintervale de dimensiune aproximativ egal˘a. Astfel, la fiecare pas: • Se calculeaz˘a indicele mijlocului secvent, ei curente → m; • Dac˘a A[m] este elementul c˘autat, return˘am m. • Dac˘a A[m] > x, continu˘am c˘autarea ˆın subsecvent, a stˆang˘a [st, m − 1]. • Dac˘a A[m] < x, continu˘am c˘autarea ˆın subsecvent, a dreapt˘a [m + 1, dr]. C˘autarea binar˘a are o complexitate timp atˆat ˆın cazul mediu, cˆat ¸si ˆın cel mai r˘au caz de O(log n), unde n este lungimea ¸sirului. Observat, ie: Complexitatea C˘aut˘arii Binare nu include s, i complexitatea sort˘arii s, irului. Atunci cˆand ˆıncepem s˘a c˘aut˘am binar un anumit element, s, irul trebuie s˘a fie deja sortat. Exemplu: Consider˘am acela¸si ¸sir sortat: A = [2, 5, 7, 10, 14, 20], unde vom c˘auta elementul 10. Pa¸sii sunt urm˘atorii: • Interval init¸ial: st = 0, dr = 5, m = ⌊(0 + 5)/2⌋ = 2. Avem elementul A[2] = 7; • Cum 7 < 10, c˘aut˘am ˆın secvent, a [3, 5]; • Avem m = ⌊(3 + 5)/2⌋ = 4 s, i elementul A[4] = 14; • 14 > 10, deci c˘aut˘am ˆın secvent, a [3, 3]; • m = ⌊(3 + 3)/2⌋ = 3, A[3] = 10 s, i oprim c˘autarea. Ilustrarea grafic˘a a c˘aut˘arii lui 10 ˆın A este aceasta: 42
Subiect · pagina 48
Algoritmi elementari Teorie Pasul 1: 2 5 7 10 14 20 st drm 7 < 10 → st = m + 1 Pasul 2: 2 5 7 10 14 20 st drm 14 > 10 → dr = m − 1 Pasul 3: 2 5 7 10 14 20 st dr m 10 = 10 → stop Figura 4.1 C˘autare binar˘a pentru elementul 10 Consider˘am A - ¸sir de numere, n - dimensiunea ¸sirului s, i x - elementul c˘autat. O imple- mentare ˆın pseudocod a c˘aut˘arii secvent, iale arat˘a astfel: C˘autare Binara 1: While st ≤ dr execute 2: m ← (st + dr) DIV 2 3: If A[m] = x then 4: Return m 5: Else If A[m] > x then 6: dr ← m − 1 7: Else 8: st ← m + 1 9: EndIf 10: EndWhile 11: Return −1 4.1.7 Interclasarea Interclasarea este o tehnic˘a fundamental˘a utilizat˘a pentru combinarea a dou˘a secvent, e sortate ˆıntr-o singur˘a secvent, ˘a sortat˘a. Aceast˘a metod˘a este folosit˘a frecvent ˆın algoritmi precum sortarea prin interclasare (Merge Sort) sau pentru alte aplicat, ii care presupun manipularea datelor sortate. Principiile Interclas˘arii • Intr˘arile: – Dou˘a liste sortate (sau secvent, e sortate) • Ies, irea: 43
Subiect · pagina 49
Algoritmi elementari Teorie
– O singur˘a list˘a sortat˘a obt, inut˘a prin combinarea celor dou˘a liste
• Procesul:
– Compararea elementelor curente din cele dou˘a liste
– Inserarea elementului mai mic ˆın lista final˘a
– Repetarea procesului pˆan˘a la epuizarea ambelor liste
Modelul Matematic al Interclas˘arii
Consider˘am dou˘a liste sortate A = {a1, a2, . . . , am} s, i B = {b1, b2, . . . , bn}. Interclasarea
produce o list˘a C = {c1, c2, . . . , cm+n} astfel ˆıncˆat C este de asemenea sortat˘a:
C = Merge(A, B)
Algoritmul pentru Interclasare
Algoritmul de Interclasare
1: Algorithm Merge(A, B)
2: i ← 1, j ← 1, k ← 1
3: C ← list˘a goal˘a
4: While i ≤ |A| && j ≤ |B| execute ▷ S-a folosit |A| = lungimea s, irului A
5: If A[i] ≤ B[j] then
6: C[k] ← A[i]
7: i ← i + 1
8: Else
9: C[k] ← B[j]
10: j ← j + 1
11: EndIf
12: k ← k + 1
13: EndWhile
14: While i ≤ |A| execute
15: C[k] ← A[i]
16: i ← i + 1, k ← k + 1
17: EndWhile
18: While j ≤ |B| execute
19: C[k] ← B[j]
20: j ← j + 1, k ← k + 1
21: EndWhile
22: Return C
23: EndAlgorithm
Complexitatea Algoritmului
• Complexitatea temporal˘a: O(m + n), unde m s, i n sunt dimensiunile celor dou˘a
liste de intrare. Acest lucru rezult˘a din faptul c˘a fiecare element este comparat s, i
inserat o singur˘a dat˘a.
• Complexitatea spat, ial˘a: O(m + n) pentru stocarea listei rezultate.
44Subiect · pagina 50
Algoritmi elementari Teorie
Aplicat, ii
• Sortarea prin interclasare:
– Algoritmul Merge Sort utilizeaz˘a interclasarea pentru a combina subsecvent, e
sortate.
• ˆImbinarea datelor sortate:
– Utilizat ˆın baze de date s, i fluxuri de date mari pentru a uni seturi sortate.
4.1.8 Metode de sortare
Ce sunt metodele de sortare?
Metodele de sortare ne ajut˘a s˘a aducem elementele unui tablou unidimensional (vector)
ˆıntr-o ordine cresc˘atoare sau descresc˘atoare. Exist˘a mai multe metode de a realiza
acest lucru, iar diferent, a major˘a care ne va determina s˘a alegem o anumit˘a metod˘a va
fi cu sigurant, ˘a complexitatea timp a metodei. Atunci cˆand proces˘am un s, ir cu o
lungime imens˘a, suntem interesat, i ca operat, ia de sortare s˘a fie f˘acut˘a cˆat mai eficient
din punct de vedere al timpului de execut, ie. ˆIn cele ce urmeaz˘a, vom prezenta cele mai
ˆıntˆalnite metode de sortare ˆın Informatica de liceu, iar la finalul prezent˘arii vom face o
scurt˘a comparat, ie ˆıntre eficient, a acestora.
Metoda Bubble Sort
Bubble Sort este un algoritm de sortare care parcurge ˆın mod repetat un s, ir de numere,
comparˆand perechi de elemente adiacente s, i interschimbˆandu-le dac˘a sunt ˆın ordinea
gres, it˘a fat, ˘a de cum ne dorim s˘a sort˘am s, irul (cresc˘ator/descresc˘ator). Procesul continu˘a
pˆan˘a cˆand s, irul este complet ordonat, adic˘a nu mai sunt necesare interschimb˘ari.
Exemplu: Vom sorta s, irul [5, 1, 4, 2, 8] cresc˘ator, folosind metoda Bubble Sort:
• Iterat, ia 1:
– Compar˘am 5 s, i 1: 5 > 1, interschimb˘am → {1, 5, 4, 2, 8}
– Compar˘am 5 s, i 4: 5 > 4, interschimb˘am → {1, 4, 5, 2, 8}
– Compar˘am 5 s, i 2: 5 > 2, interschimb˘am → {1, 4, 2, 5, 8}
– Compar˘am 5 s, i 8: 5 < 8, nu interschimb˘am.
• Iterat, ia 2:
– Compar˘am 1 s, i 4: 1 < 4, nu interschimb˘am.
– Compar˘am 4 s, i 2: 4 > 2, interschimb˘am → {1, 2, 4, 5, 8}
– Compar˘am 4 s, i 5: 4 < 5, nu interschimb˘am.
– Compar˘am 5 s, i 8: 5 < 8, nu interschimb˘am.
• Iterat, ia 3:
– Compar˘am 1 s, i 2: 1 < 2, nu interschimb˘am.
– Compar˘am 2 s, i 4: 2 < 4, nu interschimb˘am.
– Compar˘am 4 s, i 5: 4 < 5, nu interschimb˘am.
45Subiect · pagina 51
Algoritmi elementari Teorie
La finalul execut, iei, obt, inem s, irul sortat cresc˘ator: {1, 2, 4, 5, 8}. O ilustrare grafic˘a a
rezultatelor ˆın urma celor 3 iterat, ii se reg˘ases, te mai jos:
5 1 4 2 8
1 5 4 2 8
1 4 5 2 8
1 2 4 5 8
Iterat, ia 1:
Iterat, ia 2:
Iterat, ia 3:
Final:
Figura 4.2 Sortare cu metoda Bubble Sort
O implementare a algoritmului ˆın pseudocod arat˘a astfel:
Bubble Sort
1: Do
2: ok ← True
3: For i ← 1, n − 1 execute
4: If A[i] > A[i + 1] then
5: Swap(A[i], A[i + 1])
6: ok ← False
7: EndIf
8: EndFor
9: While NOT ok
Complexitate timp: O(n2) ˆın cel mai r˘au caz, O(n) ˆın cel mai bun caz.
Metoda Selection Sort
Sortarea prin metoda Selection Sort funct, ioneaz˘a prin g˘asirea ˆın mod repetat a elemen-
tului minim din vectorul nesortat s, i mutarea lui pe pozit, ia corespunz˘atoare ˆın vectorul
sortat.
Exemplu: Vom sorta s, irul {29, 10, 14, 37, 13} folosind Selection Sort:
• Iterat, ia 1:
– G˘asim minimul ˆın {29, 10, 14, 37, 13}, care este 10.
– Interschimb˘am 29 cu 10 → {10, 29, 14, 37, 13}.
• Iterat, ia 2:
– G˘asim minimul ˆın {29, 14, 37, 13}, care este 13.
– Interschimb˘am 29 cu 13 → {10, 13, 14, 37, 29}.
46Subiect · pagina 52
Algoritmi elementari Teorie
• Iterat, ia 3:
– G˘asim minimul ˆın {14, 37, 29}, care este 14.
– Cum 14 este deja la locul s˘au, nu interschimb˘am.
• Iterat, ia 4:
– G˘asim minimul ˆın {37, 29}, care este 29.
– Interschimb˘am 37 cu 29 → {10, 13, 14, 29, 37}.
Cum s, irul este sortat, algoritmul se opres, te ˆın acest punct. O reprezentare grafic˘a a
pas, ilor se reg˘ases, te mai jos:
29 10 14 37 13
10 29 14 37 13
10 13 14 37 29
10 13 14 37 29
10 13 14 29 37
Iterat, ia 1:
Iterat, ia 2:
Iterat, ia 3:
Iterat, ia 4:
Final:
Figura 4.3 Sortare cu metoda Selection Sort
O implementare a algoritmului ˆın pseudocod arat˘a astfel:
Selection Sort
1: For i ← 1, n − 1 execute
2: min ← i
3: For j ← i + 1, n execute
4: If A[j] < A[min] then
5: min ← j
6: EndIf
7: EndFor
8: If min̸ = i then
9: Swap(A[i], A[min])
10: EndIf
11: EndFor
Complexitate: O(n2), atˆat ˆın cel mai bun, cˆat s, i ˆın cel mai r˘au caz.
47Subiect · pagina 53
Algoritmi elementari Teorie
Metoda Insertion Sort
Insertion Sort este un algoritm de sortare simplu s, i eficient pentru seturi mici de date.
Funct, ioneaz˘a pe principiul construirii treptate a s, irului sortat, inserˆand fiecare element ˆın
pozit, ia corect˘a. Algoritmul parcurge s, irul de la stˆanga la dreapta s, i la fiecare pas, mut˘a
elementul curent ˆın pozit, ia corespunz˘atoare fat, ˘a de elementele deja sortate din partea
stˆang˘a a s, irului.
Exemplu: Vom sorta s, irul {12, 11, 13, 5, 6} folosind metoda Insertion Sort:
• Iterat, ia 1:
– Element curent: 11
– Compar˘am cu 12, deoarece 11 < 12, mut˘am 12 o pozit, ie la dreapta.
– Inser˘am 11 pe pozit, ia 1.
– S, irul devine: {11, 12, 13, 5, 6}
• Iterat, ia 2:
– Element curent: 13
– Compar˘am cu 12, deoarece 13 ≥ 12, nu facem modific˘ari.
– S, irul r˘amˆane: {11, 12, 13, 5, 6}
• Iterat, ia 3:
– Element curent: 5
– Compar˘am cu 13, 5 < 13, mut˘am 13 la dreapta.
– Compar˘am cu 12, 5 < 12, mut˘am 12 la dreapta.
– Compar˘am cu 11, 5 < 11, mut˘am 11 la dreapta.
– Inser˘am 5 pe pozit, ia 0.
– S, irul devine: {5, 11, 12, 13, 6}
• Iterat, ia 4:
– Element curent: 6
– Compar˘am cu 13, 6 < 13, mut˘am 13 la dreapta.
– Compar˘am cu 12, 6 < 12, mut˘am 12 la dreapta.
– Compar˘am cu 11, 6 < 11, mut˘am 11 la dreapta.
– Compar˘am cu 5, 6 ≥ 5, inser˘am 6 pe pozit, ia 1.
– S, irul devine: {5, 6, 11, 12, 13}
La finalul execut, iei, obt, inem s, irul sortat: {5, 6, 11, 12, 13}. O ilustrare grafic˘a a pas, ilor
algoritmului este prezentat˘a mai jos:
48Subiect · pagina 54
Algoritmi elementari Teorie
Iterat, ia 1: 12 11 13 5 6 → 11 12 13 5 6
Iterat, ia 2: 11 12 13 5 6 → 11 12 13 5 6
Iterat, ia 3: 11 12 13 5 6 → 5 11 12 13 6
Iterat, ia 4: 5 11 12 13 6 → 5 6 11 12 13
Figura 4.4 Sortare cu metoda Insertion Sort
O implementare a algoritmului ˆın pseudocod arat˘a astfel:
Insertion Sort
1: For i ← 1 to n − 1 execute
2: key ← A[i]
3: j ← i − 1
4: While j ≥ 0 and A[j] > key execute
5: A[j + 1] ← A[j]
6: j ← j − 1
7: EndWhile
8: A[j + 1] ← key
9: EndFor
Complexitate: O(n2), atˆat ˆın cel mai bun, cˆat s, i ˆın cel mai r˘au caz.
Metoda Quick Sort
Quick Sort este un algoritm de sortare care utilizeaz˘a strategia ”Divide et Impera”. Algo-
ritmul funct, ioneaz˘a prin selectarea unui element numit ”pivot” s, i divizarea s, irului astfel
ˆıncˆat toate elementele mai mici decˆat pivotul s˘a fie plasate ˆınaintea acestuia, iar cele mai
mari dup˘a el. Acest proces se repet˘a recursiv pentru subs, irurile rezultate pˆan˘a cˆand s, irul
este complet sortat.
Exemplu: Vom sorta s, irul {33, 10, 55, 71, 29, 3, 18} folosind metoda Quick Sort:
• Pasul 1:
– Alegem pivotul: 33.
– Diviz˘am s, irul ˆın funct, ie de pivot:
∗ Elemente mai mici decˆat 33: {10, 29, 3, 18}
∗ Pivot: {33}
∗ Elemente mai mari decˆat 33: {55, 71}
• Pasul 2: Aplic˘am recursiv Quick Sort pe subs, irurile rezultate.
49Subiect · pagina 55
Algoritmi elementari Teorie
– Sort˘am {10, 29, 3, 18}
∗ Pivot: 10
∗ Elemente mai mici: {3}
∗ Elemente mai mari: {29, 18}
– Sort˘am {3} (deja sortat)
– Sort˘am {29, 18}
∗ Pivot: 29
∗ Elemente mai mici: {18}
∗ Elemente mai mari: {}
• Pasul 3: Reunim subs, irurile sortate.
– Subs, irul stˆang sortat: {3, 10, 18, 29}
– Pivotul init, ial: {33}
– Sort˘am {55, 71}
∗ Pivot: 55
∗ Elemente mai mici: {}
∗ Elemente mai mari: {71}
– Subs, irul drept sortat: {55, 71}
La final, obt, inem s, irul sortat: {3, 10, 18, 29, 33, 55, 71}. O ilustrare grafic˘a a procesului
este prezentat˘a mai jos:
33
{33}
10
{3, 10, 18, 29}
3
{3}
29
{18, 29}
18
{18} ∅
55
{55, 71}
∅ 71
{71}
Figura 4.5 Sortare cu metoda Quick Sort
O implementare a algoritmului ˆın pseudocod arat˘a astfel:
50Subiect · pagina 56
Algoritmi elementari Teorie
Quick Sort
1: Algorithm QuickSort(A, low, high)
2: If low < high then
3: pivot index ← Partition(A, low, high)
4: QuickSort(A, low, pivot index − 1)
5: QuickSort(A, pivot index + 1, high)
6: EndIf
7: EndAlgorithm
8: Algorithm Partition(A, low, high)
9: pivot ← A[high]
10: i ← low − 1
11: For j ← low to high − 1 execute
12: If A[j] ≤ pivot then
13: i ← i + 1
14: Swap(A[i], A[j])
15: EndIf
16: EndFor
17: Swap(A[i + 1], A[high])
18: Return i + 1
19: EndAlgorithm
Complexitate timp:
• Caz mediu: O(n log n)
• Cazul cel mai r˘au: O(n2) (dac˘a s, irul este deja sortat invers sau pivotul ales este
mereu cel mai mic/mare element)
Metoda Merge Sort
Merge Sort este, de asemenea, un algoritm care utilizeaz˘a ”Divide et Impera”. Spre
deosebire de Quick Sort, Merge Sort ˆımparte ˆın mod recursiv s, irul ˆın jum˘at˘at, i pˆan˘a cˆand
ajunge la subs, iruri de un singur element, apoi le ˆımbin˘a (merge) ˆıntr-un mod ordonat
pentru a obt, ine s, irul sortat final.
Exemplu: Vom sorta s, irul {38, 27, 43, 3, 9, 82, 10} folosind metoda Merge Sort:
• Pasul 1: Diviz˘am recursiv s, irul pˆan˘a la subs, iruri de un element:
– S, irul init, ial: {38, 27, 43, 3, 9, 82, 10};
– ˆImp˘art, im ˆın dou˘a: {38, 27, 43} s, i {3, 9, 82, 10};
– Continu˘am ˆımp˘art, irea:
∗ {38, 27, 43} → {38}, {27, 43} → {27}, {43};
∗ {3, 9, 82, 10} → {3, 9}, {82, 10} → {3}, {9}, {82}, {10}.
• Pasul 2: ˆImbin˘am subs, irurile ˆıntr-un mod ordonat:
– ˆImbin˘am {27} s, i {43} → {27, 43};
– ˆImbin˘am {38} s, i {27, 43} → {27, 38, 43};
– ˆImbin˘am {3} s, i {9} → {3, 9};
51Subiect · pagina 57
Algoritmi elementari Teorie
– ˆImbin˘am {82} s, i {10} → {10, 82};
– ˆImbin˘am {3, 9} s, i {10, 82} → {3, 9, 10, 82}.
• Pasul 3: ˆImbin˘am cele dou˘a subs, iruri sortate:
– ˆImbin˘am {27, 38, 43} s, i {3, 9, 10, 82} → {3, 9, 10, 27, 38, 43, 82}.
La final, obt, inem s, irul sortat: {3, 9, 10, 27, 38, 43, 82}. Diagrama de mai jos ilustreaz˘a
procesul:
{38, 27, 43, 3, 9, 82, 10}
{38, 27, 43}
{38} {27, 43}
{27} {43}
{3, 9, 82, 10}
{3, 9}
{3} {9}
{82, 10}
{82} {10}
Figura 4.6 Divizarea s, irului ˆın Merge Sort
{3, 9, 10, 27, 38, 43, 82}
{27, 38, 43}
{38} {27, 43}
{27} {43}
{3, 9, 10, 82}
{3, 9}
{3} {9}
{10, 82}
{10} {82}
Figura 4.7 ˆImbinarea subs, irurilor ˆın Merge Sort
O implementare a algoritmului ˆın pseudocod arat˘a astfel:
Merge Sort
1: Algorithm MergeSort(A, lef t, right)
2: If lef t < right then
3: mid ← ⌊(lef t + right)/2⌋
4: MergeSort(A, lef t, mid)
5: MergeSort(A, mid + 1, right)
6: Merge(A, lef t, mid, right) ▷ Definit˘a la capitolul interclasare
7: EndIf
8: EndAlgorithm
Complexitate timp: O(n log n) ˆın toate cazurile, datorit˘a diviz˘arii s, i ˆımbin˘arii constante
a subs, irurilor.
52Subiect · pagina 58
Algoritmi elementari Probleme Comparat, ie ˆıntre metodele de sortare Pˆan˘a acum am prezentat multiple metode de sortare, iar acum a venit timpul s˘a punem urm˘atoarea problem˘a: Pe care dintre ele este cel mai bine s˘a o utiliz˘am? R˘aspunsul se bazeaz˘a foarte mult pe analiza complexit˘at, ilor acestora, explicate ˆın urm˘atorul capitol. Pe scurt, complexit˘at, ile sort˘arilor arat˘a astfel: Algoritm Cazul mediu Cazul cel mai r˘au Bubble Sort O(n2) O(n2) Selection Sort O(n2) O(n2) Insertion Sort O(n2) O(n2) Quick Sort O(n log n) O(n2) Merge Sort O(n log n) O(n log n) Tabela 4.1 Comparat, ie algoritmi de sortare Avˆand ˆın vedere comparat, ia de mai sus, observ˘am c˘a algoritmul Merge Sort este cel mai stabil s, i eficient din punct de vedere al complexit˘at, ii. As, adar, atunci cˆand ne dorim s˘a sort˘am un s, ir de numere cˆat mai eficient, putem folosi cu certitudine Merge Sort. 4.2 Probleme 67. ✓ ?Care este rezultatul conversiei num˘arului binar 1010101100 ˆın baza 8? A. 684 B. 1254 C. 1002 D. Niciunul din r˘aspunsurile A., B., C. 68. ✓ ?Care este rezultatul conversiei num˘arului zecimal 24 + 26 + 210 − 3 ˆın baza 2? A. 10001001101 B. 1101 C. 10001010000 D. Niciunul dintre r˘aspunsurile A., B., C. 69. ✓ ?Fie expresia E = 10(16) − 10(15) + 10(14) − 10(13) + · · · + 10(2), unde notat, ia x(b) semnific˘a num˘arul x scris ˆın baza b. Care valoare corespunde expresiei E? A. 0 B. 1001(2) C. 11(8) D. 9(16) 70. ✓ ?Se consider˘a algoritmul ceFace(arr, n), unde n este un num˘ar natural nenul (1 ≤ n ≤ 104) s, i arr este un s, ir de numere ˆıntregi cu n elemente (−106 ≤ arr[1], arr[2], . . . , arr[n] ≤ 106). 53
Subiect · pagina 59
Algoritmi elementari Probleme Algorithm ceFace(arr, n) c ← arr[1] For i ← 2, n execute dup ← false For j ← 1, i − 1 execute If arr[i] = arr[j] then dup ← true EndIf EndFor If NOT dup then If arr[i] < c then c ← arr[i] EndIf EndIf EndFor Return c EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Pentru apelul ceFace([7, 3, 3, 4, 8], 5) algoritmul returneaz˘a 4. B. Algoritmul ceFace(arr, n) deter- min˘a elementul minim din vectorul arr. C. Algoritmul ceFace(arr, n) deter- min˘a elementul maxim din vectorul arr. D. Dac˘a toate elementele din s, irul arr sunt egale, algoritmul ceFace(arr, n) returneaz˘a oricare dintre aceste ele- mente. 71. ✓ ?Se consider˘a algoritmii ceFace1(x) s, i ceFace2(x) definit, i al˘aturat, unde x este un num˘ar ˆıntreg, cel mult 109. Algorithm ceFace1(x) While x > 9 execute s ← 0 While x > 0 execute s ← s + x MOD 10 x ← [x DIV 10] EndWhile x ← s EndWhile Return x EndAlgorithm Algorithm ceFace2(x) If x = 0 OR x MOD 9 = 0 then Return 0 Else Return x MOD 9 EndIf EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Algoritmul ceFace1(x) returneaz˘a suma cifrelor lui x; B. Algoritmul ceFace2(x) returneaz˘a ˆıntotdeauna restul ˆımp˘art, irii lui x la 9; C. Algoritmii ceFace1(x) s, i ceFace2(x) vor returna mereu aceeas, i valoare ∀x; D. Algoritmul ceFace1(x) returneaz˘a cifra de control a num˘arului x. 72. ✓ ?Precizat, i care dintre urm˘atoarele afirmat, ii referitoare la egalitatea unor valori ˆın diferite baze de numerat, ie sunt adev˘arate, unde x(b) semnific˘a num˘arul x scris ˆın baza b. A. 1010101(2) = 85(10) B. 11100100011011111010(2) = E46F A(16) C. 21030010121110(3) = 7203543(9) D. 1234(8) = 1010011100(2) 54
Subiect · pagina 60
Algoritmi elementari Probleme 73. ✓ ?Se consider˘a algoritmul ceFace(n), unde n este un num˘ar natural (0 ≤ n ≤ 104). Algorithm ceFace(n) If n = 1 then Return False EndIf If n = 2 then Return True EndIf If n MOD 2 = 0 AND n ≥ 4 then Return False EndIf For index ← 3, index * index ≤ n execute If n MOD index = 0 then Return False EndIf EndFor Return True EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. ˆIn cazul apelului ceFace(21), algorit- mul returneaz˘a True. B. Algoritmul returneaz˘a False pentru toate valorile pare diferite de 2. C. Algoritmul returneaz˘a True dac˘a s, i numai dac˘a num˘arul n este prim, False altfel. D. Exist˘a exact 5 numere cu proprieta- tea c˘a n ≤ 10, pentru care apelul ceFace(n) returneaz˘a True. 74. ✓ ?Se consider˘a algoritmul ceFace(n), unde n este un num˘ar natural nenul (1 ≤ n ≤ 109): Algorithm ceFace(n) top ← 0 While n > 0 execute If n MOD 6 = 0 then top ← top + 1 EndIf n ← n DIV 6 EndWhile Return top EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Pentru n = 1302, algoritmul retur- neaz˘a valoarea 3. B. Pentru n = 216, algoritmul returneaz˘a valoarea 2. C. Dac˘a n este un num˘ar par, algoritmul returneaz˘a o valoare impar˘a. D. Algoritmul returneaz˘a num˘arul de ci- fre de 0 din reprezentarea ˆın baza 6 a num˘arului n. 75. ✓ ?Se consider˘a 3 numere ˆın diferite baze de numerat, ie: x = 429 ˆın baza 10, y = 1AD ˆın baza 16 s, i z = 110101100 ˆın baza 2. Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. x = y s, i y̸ = z. B. x = y = z. C. x̸ = y s, i y̸ = z. D. x̸ = y s, i y = z. 76. ✓ ?Se consider˘a subalgoritmul ceFace() definit al˘aturat. S¸irul a de lungime n este citit de la tastatur˘a, iar ¸sirul sp este init¸ializat cu 0. Funct¸ia max(a, b) returneaz˘a maximul dintre numerele a ¸si b. Vectorii sunt indexat, i de la 0. 55
Subiect · pagina 61
Algoritmi elementari Probleme Algorithm ceFace() c ← a[0] sp[0] ← a[0] If c < 0 then c ← 0 EndIf For i ← 1, n − 1 execute c ← c + a[i] sp[i] ← max(sp[i − 1], c) If c < 0 then c ← 0 EndIf EndFor c ← a[n − 1] b ← a[n − 1] If c < 0 then c ← 0 EndIf d ← b + sp[n − 2] For i ← n − 2 to 1, −1 execute c ← c + a[i] If b < c then b ← c EndIf If c < 0 then c ← 0 EndIf d ← max(d, b + sp[i − 1]) EndFor Output d EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Subalgoritmul ceFace determin˘a suma maxim˘a posibil˘a care se poate obt, ine din dou˘a secvent, e oarecare din ¸sirul a. B. Subalgoritmul ceFace determin˘a suma maxim˘a posibil˘a care se poate obt, ine din dou˘a secvent, e care nu au niciun element comun din ¸sirul a. C. Subalgoritmul ceFace determin˘a secvent, a de lungime maxim˘a s, i sum˘a maxim˘a din ¸sirul a. D. Subalgoritmul ceFace determin˘a num˘arul de secvent, e cu sum˘a s, i lungimea maxim˘a din ¸sirul a. 77. ✓ ?Se consider˘a algoritmul ceFace(arr, n, i), unde n s, i i sunt numere naturale nenule (1 ≤ n ≤ 104, 1 ≤ i ≤ n) s, i arr este un s, ir de numere ˆıntregi cu n elemente (−106 ≤ arr[1], arr[2], . . . , arr[n] ≤ 106). Algorithm ceFace(arr, n, i) If i = n then Return arr[i] EndIf m ← ceFace(arr, n, i + 1) If arr[i] > m then m ← arr[i] EndIf Return m EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate referitoare la algoritmul ceFace(arr, n, i)? A. Pentru apelul ceFace([10, -3, 7, 5, -11, 12, 6, 0], 8, 1) algoritmul re- turneaz˘a -11. B. Pentru apelul ceFace([10, -3, 7, 5, -11, 12, 6, 0], 8, 1) algoritmul re- turneaz˘a 12. 56
Subiect · pagina 62
Algoritmi elementari Probleme C. Pentru apelul ceFace([5, -4, 3, -2, 1], 5, 2) algoritmul returneaz˘a 5. D. Algoritmul ceFace(arr, n, i) determin˘a maximul din ˆıntregul vector arr. 78. ✓ ?Se consider˘a algoritmul special(v, n, k), unde n s, i v sunt dou˘a numere naturale (1 ≤ n ≤ 104, 1 ≤ k ≤ 9), iar v este un s, ir de numere naturale cu n elemente (v[1], v[2], . . . , v[n]). Algorithm special(v, n, k) If n = 0 then Return 0 EndIf Return ((v[n] DIV 10 − v[n] MOD 10 ∗ 2) MOD k = 0) + special(v, n − 1, k) EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Pentru apelul special([11, 33, 36, 44, 66, 67], 6, 3) algoritmul returneaz˘a 3. B. Pentru apelul special([28, 70, 30, 35], 4, 7) algoritmul returneaz˘a 3. C. Algoritmul special(v, n, k) calculeaz˘a s, i returneaz˘a cˆate numere sunt divizibile cu k ˆın vectorul v. D. Pentru apelurile special([21, 15, 6, 8, 49], 5, 7) s, i special([77, 147, 5, 16, 25], 5, 7) algoritmul returneaz˘a ˆın ambele cazuri o valoare par˘a. 79. ✓ ?Se consider˘a algoritmul taste(arr, n), unde n este un num˘ar natural nenul (1 ≤ n ≤ 104), iar arr este un s, ir de numere naturale cu n elemente (1 ≤ arr[1], arr[2], . . . , arr[n] ≤ 106). Algorithm taste(arr, n) If n = 0 then Return 0 EndIf p ← true If arr[n] ≤ 1 then p ← false EndIf For j ← 2 to j * j ≤ arr[n] execute If arr[n] MOD j = 0 then p ← false EndIf EndFor If p then Return taste(arr, n - 1) EndIf Return arr[n] + taste(arr, n - 1) EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Algoritmul taste(arr, n) retur- neaz˘a suma numerelor prime din vectorul arr. B. Pentru apelul taste([3, 8, 9, 13, 15, 21, 23, 24], 8) algo- ritmul returneaz˘a 39. C. Pentru apelul taste([1, 5, 6, 9, 11, 16, 17, 19, 20], 9) algoritmul returneaz˘a 52. D. Algoritmul taste(arr, n) retur- neaz˘a 0 dac˘a niciun element din vectorul arr nu este prim. 80. ✓ ?Se consider˘a algoritmul extra(n), unde n este un num˘ar natural nenul (1 ≤ n ≤ 109). 57
Subiect · pagina 63
Algoritmi elementari Probleme Algorithm extra(n) If n > 0 then Write n MOD 2 extra(n DIV 2) EndIf EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Pentru n = 73, algoritmul afis, eaz˘a 1001001. B. Pentru n = 21, algoritmul afis, eaz˘a 10101. C. Algoritmul afis, eaz˘a reprezentarea num˘arului n ˆın baza 2. D. Algoritmul are complexitate logaritmic˘a. 81. ✓ ?Se consider˘a algoritmul ceFace(arr, n), unde n este un num˘ar natural nenul (2 ≤ n ≤ 104), iar arr este un s, ir de numere ˆıntregi cu n elemente (−104 ≤ arr[1], arr[2], . . . , arr[n] ≤ 104). Algorithm ceFace(arr, n) a ← 10001 b ← −10001 For i ← 2 to n execute If arr[i] > arr[1] AND arr[i] < a then a ← arr[i] EndIf If arr[i] < arr[1] AND arr[i] > b then b ← arr[i] EndIf EndFor If a = 10001 OR b = −10001 then Return arr[1] Else Return a + b EndIf EndAlgorithm Pentru care dintre urm˘atoarele ape- luri ale algoritmului ceFace(arr, n) algoritmul returneaz˘a valoarea 31? A. ceFace([31, 31, 31, 31, 31], 5) B. ceFace([31, -21, -11, -1, 32, -5, 49], 7) C. ceFace([18, 20, 5, 6], 4) D. ceFace([15, 17, 5, 49, 37, 14], 6) 82. ✓ ?Se consider˘a algoritmul ceFace(a, b), unde a s, i b sunt numere naturale pozitive (1 ≤ a ≤ b ≤ 109). 58
Subiect · pagina 64
Algoritmi elementari Probleme Algorithm ceFace(a, b) k ← 0 m ← 109 M ← 0 For i ← a, b execute x ← 1 nr ← 0 d ← 2 cn ← i While cn > 1 AND d * d ≤ cn execute nr ← 0 If cn MOD d = 0 then While cn MOD d = 0 execute cn ← cn DIV d nr ← nr + 1 EndWhile x ← x * (nr + 1) EndIf d ← d + 1 EndWhile If cn > 1 then x ← x * 2 EndIf If x > M then M ← x m ← i k ← 1 Else If x = M then k ← k + 1 EndIf EndIf EndFor Write m, M , k EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Pentru apelul ceFace(200, 200), algoritmul afi¸seaz˘a va- lorile 200 10 1. B. Pentru apelul ceFace(2, 10), algoritmul afi¸seaz˘a valorile 6 4 3. C. Algoritmul ceFace(a, b) determin˘a s, i afi¸seaz˘a cel mai mic num˘ar din intervalul [a, b] cu num˘ar maxim de divizori, num˘arul de divizori al acestuia s, i num˘arul de nu- mere cu aceast˘a proprietate. D. Algoritmul ceFace(a, b) determin˘a s, i afi¸seaz˘a cel mai mic num˘ar din interva- lul [a, b] cu num˘ar maxim de factori primi distinct, i, num˘arul acestora s, i num˘arul de numere care au aceast˘a proprietate. 83. ✓ ?Care ar putea fi elementele unui vector astfel ˆıncˆat, aplicˆand metoda c˘aut˘arii binare pentru valoarea 64, aceasta s˘a fie comparat˘a succesiv cu valorile 36, 45, 64? A. [4, 7, 9, 15, 36, 40, 42, 45, 64, 67] B. [2, 4, 7, 12, 24, 36, 50] C. [12, 24, 36, 42, 54, 66] D. [4, 8, 9, 36, 16, 45, 64] 84. ✓ ?Fie expresia E = AB(16) + 120(3) − 120(4), unde notat, ia x(b) semnific˘a num˘arul x scris ˆın baza b. Care valoare corespunde expresiei E? A. 162(10); B. 278(8); C. 1000101(2); D. 242(8). 85. ✓ ?Se consider˘a algoritmul dificil(n), unde n este un num˘ar natural nenul (1 ≤ n ≤ 106). 59
Subiect · pagina 65
Algoritmi elementari Probleme Algorithm dificil(n) k ← 0 nr ← 0 For index ← 1 to n execute nr ← index While nr > 0 execute k ← k + (nr MOD 2) nr ← nr DIV 2 EndWhile EndFor Return k EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Pentru n = 509, algoritmul returneaz˘a 2287. B. Pentru n = 1025, algoritmul retur- neaz˘a 5123. C. Pentru n = 120, algoritmul returneaz˘a 406. D. Algoritmul dificil(n) calculeaz˘a s, i returneaz˘a num˘arul total de cifre de 1 din reprezentarea binar˘a a tuturor numerelor de la 1 pˆan˘a la n. 86. ✓ ?Se consider˘a algoritmul indigo(n), unde n este un num˘ar natural (1 ≤ n ≤ 106). Algorithm indigo(n) cnt ← 0 For i ← 2, i * i ≤ n execute If n MOD i = 0 then cnt ← cnt + 1 While n MOD i = 0 execute n ← n DIV i EndWhile EndIf EndFor If n > 1 then cnt ← cnt + 1 EndIf Return cnt EndAlgorithm Care dintre urm˘atoarele apeluri ale al- goritmului indigo(n) returneaz˘a va- loarea 3? A. indigo(120) B. indigo(9016) C. indigo(630) D. indigo(8064) 87. ✓ ?Se consider˘a algoritmul lambda(n), unde n este un num˘ar natural nenul (1 ≤ n ≤ 109). Algorithm lambda(n) If n < 10 then Return n EndIf b ← lambda(n DIV 10) a ← n MOD 10 If a MOD 4 > b MOD 4 then Return a EndIf Return b EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate re- feritoare la algoritmul lambda(n)? A. Pentru apelul lambda(12569) algoritmul retur- neaz˘a 2. B. Pentru apelul lambda(783031) algoritmul re- turneaz˘a 8. C. Pentru apelurile lambda(2024) s, i lambda(2025) algoritmul returneaz˘a aceeas, i valoare. D. Algoritmul lambda(n) returneaz˘a prima cifr˘a divizibil˘a cu 4 din reprezentarea num˘arului n. 88. ✓ ?Se consider˘a algoritmul book(n), unde n este un num˘ar natural nenul (1 ≤ n ≤ 109). 60
Subiect · pagina 66
Algoritmi elementari Probleme
Algorithm book(n)
If n < 10 then
x ← n MOD 3
y ← n MOD 2
If x = 0 AND y̸ = 0 then
Return n
Else
Return -1
EndIf
EndIf
u ← n MOD 10
v ← n DIV 10
p ← book(v)
t ← u MOD 3
q ← u MOD 2
z ← p
If t = 0 AND q̸ = 0 AND u > z then
w ← u
Else
w ← z
EndIf
r ← w * 2 − w
Return r
EndAlgorithm
Care dintre urm˘atoarele afirmat, ii sunt false
referitoare la algoritmul book(n)?
A. Pentru apelul book(3063528) algorit-
mul returneaz˘a 3.
B. Pentru apelul book(24680) algorit-
mul returneaz˘a -1.
C. Pentru apelul book(5792041) algorit-
mul returneaz˘a 9.
D. Algoritmul book(n) returneaz˘a -1
dac˘a num˘arul n cont, ine doar cifre din
mult, imea {3, 4, 5, 6, 7, 8}.
89. ✓ ?Se consider˘a algoritmii switch(a, b) s, i case(a, b), unde a s, i b sunt numere natu-
rale (1 ≤ a, b ≤ 106).
Algorithm switch(a, b)
If a = b then
Return a
EndIf
If a < b then
Return switch(a, b - a)
EndIf
Return switch(a - b, b)
EndAlgorithm
Algorithm case(a, b)
Return a * b DIV switch(a, b)
EndAlgorithm
Care dintre urm˘atoarele afirmat, ii sunt adev˘arate?
A. Dac˘a a = 2024 s, i b = 32, atunci apelul switch(a, b) returneaz˘a 8.
B. Dac˘a a = 48 s, i b = 22, atunci apelul case(a, b) returneaz˘a 528.
C. Algoritmul switch(a, b) returneaz˘a cel mai mic multiplu comun al lui a s, i b.
D. Algoritmul case(a, b) returneaz˘a produsul celor dou˘a numere, dac˘a acestea
sunt prime ˆıntre ele.
90. ✓ ?Se consider˘a algoritmul red(arr, n), unde n este un num˘ar natural nenul (1 ≤ n ≤
104) s, i arr este un s, ir de numere ˆıntregi cu n elemente (0 ≤ arr[1], arr[2], . . . , arr[n] ≤
106).
61Subiect · pagina 67
Algoritmi elementari Probleme Algorithm red(arr, n) For i ← n − 1, 1, −1 execute If arr[i] < arr[i + 1] then arr[i] ← arr[i] − arr[i + 1] arr[i + 1] ← arr[i + 1] + arr[i] arr[i] ← arr[i + 1] − arr[i] EndIf EndFor Return arr[1] EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Pentru apelul red([15, 23, 7, 12, 81, 49, 35, 31], 8) algoritmul re- turneaz˘a 7. B. Pentru apelul red([23, 10, 44, 52, 19, 81, 3, 72, 22], 9) algo- ritmul returneaz˘a 81. C. Algoritmul red(arr, n) sorteaz˘a des- cresc˘ator vectorul arr. D. Algoritmul red(arr, n) determin˘a elementul minim din vectorul arr. 91. ✓ ?Se consider˘a algoritmul great(arr, n, i), unde n s, i i sunt numere naturale ne- nule (1 ≤ n, i ≤ 104), iar arr este un s, ir de numere naturale cu n elemente (1 ≤ arr[1], arr[2], . . . , arr[n] ≤ 106). Algorithm great(arr, n, i) If i = n then Return arr[i] EndIf g ← great(arr, n, i + 1) While g̸ = 0 execute If arr[i] > g then arr[i] ← arr[i] MOD g Else temp ← arr[i] arr[i] ← g g ← temp MOD g EndIf EndWhile Return arr[i] EndAlgorithm Precizat, i care dintre urm˘atoarele afirmat, ii sunt adev˘arate referitoare la algoritmul great(arr, n, i). A. Pentru apelul great([30, 60, 12, 48, 72], 5, 1) algoritmul returneaz˘a 3. B. Pentru apelul great([21, 14, 42], 3, 2) algoritmul returneaz˘a 7. C. Pentru apelul great([45, 35, 20, 80, 50], 5, 3) algoritmul returneaz˘a 10. D. Algoritmul are complexitate liniar˘a O(n). 92. ✓ ?Se consider˘a algoritmul Algo(v, n), unde v este un vector cu n numere naturale (v[1], v[2], . . . , v[n]) (1 ≤ n ≤ 105): Algorithm Algo(v, n) s ← 0 For i ← 1, n execute v[i] ← n + 1 − i EndFor For i ← 1, n execute If i MOD 2̸ = 0 then s ← s + v[i] EndIf EndFor Write s EndAlgorithm Ce valoare afis, eaz˘a algoritmul ˆın urma ape- lului Algo(v, 10)? A. 25 B. 35 C. 50 D. 30 62
Subiect · pagina 68
Algoritmi elementari Probleme 93. ✓ ?Se consider˘a algoritmii ceFace1(v, n) s, i ceFace2(v, n, i, fl, sl), unde n s, i i sunt numere naturale (1 ≤ n ≤ 104, 0 ≤ i ≤ n), iar v este un s, ir de numere ˆıntregi cu n + 1 elemente (0 ≤ v[0], v[1], v[2], . . . , v[n] ≤ 106). f l si sl sunt 2 numere naturale (0 ≤ f l, sl ≤ 106). Algorithm ceFace2(v, n, i, fl, sl) If i ≤ n then If v[i] > f l then ceFace2(v, n, i + 1, v[i], fl) Else If v[i] > sl AND v[i]̸ = f l then ceFace2(v, n, i + 1, fl, v[i]) Else ceFace2(v, n, i + 1, fl, sl) EndIf EndIf Else Write ‘(‘, fl, ‘,‘, sl, ‘)‘, ‘ ’ EndIf EndAlgorithm Algorithm ceFace1(v, n) For k ← 0, n execute ceFace2(v, n, k, 0, 0) EndFor EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate referitoare la algoritmii ceFace1(v, n) s, i ceFace2(v, n, i, fl, sl)? A. Pentru apelul ceFace2([9, 8, 6, 3, 7, 2, 4], 6, 1, 0, 0), algoritmul afis, eaz˘a (8, 7). B. Pentru apelul ceFace1([7, 9, 1, 4, 5, 3], 5), algoritmul afis, eaz˘a (9, 7) (9, 5) (5, 4) (5, 4) (5, 3). C. Algoritmul ceFace1(v, n) afis, eaz˘a n + 1 perechi de numere din vectorul v, de forma (a, b), unde a > b s, i a este cel mai mare element din vectorul v. D. Pentru apelul ceFace2([5, 5, 4, 2, 1, 3, 1], 6, 3, 0, 0), algoritmul afis, eaz˘a (3, 2). 94. ✓ ?Se consider˘a algoritmul ceFace(n), unde n este un num˘ar natural nenul (1 ≤ n ≤ 109). Algorithm ceFace(n) While n̸ = 0 execute If n MOD 4 > 1 then Return False EndIf n ← n DIV 4 EndWhile Return True EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt false? A. Algoritmul returneaz˘a True dac˘a s, i numai dac˘a n cont, ine doar cifrele 0 s, i 1 ˆın reprezentarea sa ˆın baza 4. B. Algoritmul verific˘a dac˘a num˘arul n poate fi scris ca suma de puteri dis- tincte ale lui 4. C. Pentru n = 806, algoritmul returneaz˘a False. D. Algoritmul returneaz˘a False pentru orice num˘ar care nu este multiplu de 4. 63
Subiect · pagina 69
Algoritmi elementari Probleme 95. ✓ ?Se consider˘a algoritmul Algo(v), unde v este un vector cu n = 8 elemente (v[1], v[2], . . . , v[8]): Algorithm Algo(v) For i ← 8, 1, −1 execute If i MOD 2̸ = 0 then v[i] ← i + 1 Else v[i] ← i − i/2 EndIf EndFor EndAlgorithm Cum va ar˘ata vectorul v ˆın urma execut, iei instruct, iunilor algoritmului Algo(v)? A. 3 1 5 3 7 5 9 7 B. 2 1 4 3 6 5 8 7 C. 2 1 4 2 6 3 8 4 D. 3 1 5 3 5 7 7 9 96. ✓ ?Se consider˘a algoritmul Algo(v, n, e), unde v este un vector cu n elemente ˆıntregi distincte (v[1], v[2], . . . , v[n]), 1 ≤ n ≤ 104 s, i v[i]̸ = v[j], pentru 1 ≤ i ≤ j ≤ n), iar e este un num˘ar ˆıntreg. Algoritmul caut˘a elementul e ˆın vectorul v s, i, dac˘a ˆıl g˘ases, te, mut˘a toate elementele de dup˘a elementul e la ˆınceputul vectorului s, i returneaz˘a True, nemodificˆand ordinea celorlalte elemente. Dac˘a elementul e nu se g˘ases, te ˆın v, al- goritmul returneaz˘a False s, i nu modific˘a nimic. De exemplu, pentru vectorul v cu elementele [3, 5, 7, 9, 11] s, i e = 5, algoritmul va returna True s, i vectorul v va deveni [7, 9, 11, 3, 5]. Care dintre urm˘atoarele implement˘ari de mai jos este o variant˘a corect˘a pentru algoritmul descris? A. Algorithm algo(v, n, e) i ← 0 While i < n execute If v[i] = e then Break EndIf i ← i + 1 EndWhile If i = n then Return False EndIf j ← i While j < n execute v[j − i] ← v[j] j ← j + 1 EndWhile k ← 0 While k < i execute v[n − i + k] ← v[n − k − 1] k ← k + 1 EndWhile Return True EndAlgorithm B. Algorithm algo(v, n, e) i ← 0 f ound ← False While i < n execute If v[i] = e then f ound ← True Break EndIf i ← i + 1 EndWhile If NOT f ound then Return False EndIf j ← i While j < n execute v[j − i] ← v[j] j ← j + 1 EndWhile k ← 0 While k < i execute v[k] ← v[n − i + k] k ← k + 1 EndWhile Return True EndAlgorithm 64
Subiect · pagina 70
Algoritmi elementari Probleme C. Algorithm algo(v, n, e) i ← 1 f ound ← False While i ≤ n execute If v[i] = e then f ound ← True Break EndIf i ← i + 1 EndWhile If NOT f ound then Return False EndIf elements ← n − i temp ← [] ▷ vector vid For j ← 1, elements execute temp[j] ← v[i + j] EndFor For j ← i, 1, −1 execute v[j + elements] ← v[j] EndFor For j ← 1, elements execute v[j] ← temp[j] EndFor Return True EndAlgorithm D. Algorithm algo(v, n, e) i ← 0 f ound ← False While i < n execute If v[i] = e then f ound ← True Break EndIf i ← i + 1 EndWhile If NOT f ound then Return False EndIf temp ← [0] ∗ i k ← 0 tempIndex ← 0 While k ≤ i execute temp[tempIndex] ← v[k] tempIndex ← tempIndex + 1 k ← k + 1 EndWhile j ← i While j < n execute v[j − i] ← v[j] j ← j + 1 EndWhile k ← 0 While k < i execute v[n − i + k] ← temp[k] k ← k + 1 EndWhile Return True EndAlgorithm 97. ✓ ?Se consider˘a algoritmul algo(v, n, k), unde n este un num˘ar natural (1 ≤ n ≤ 104), v este un vector cu n elemente numere ˆıntregi (v[1], v[2], . . . , v[n]), iar k este un num˘ar natural: Algorithm algo(v, n, k) If n MOD k̸ = 0 then Return False EndIf s ← n DIV k For i ← 1, k execute start ← (i − 1) ∗ s + 1 end ← i ∗ s For j ← start, end − 1 execute If v[j] ≥ v[j + 1] then Return False EndIf EndFor EndFor 65
Subiect · pagina 71
Algoritmi elementari Probleme Return True EndAlgorithm Precizat, i care dintre afirmat, iile de mai jos sunt adev˘arate: A. Algoritmul verific˘a dac˘a un vector poate fi ˆımp˘art, it ˆın k subsecvent, e egale, fiecare fiind strict cresc˘ator. B. Algoritmul verific˘a dac˘a un vector poate fi ˆımp˘art, it ˆın k subsecvent, e, fiecare fiind ordonat cresc˘ator. C. Apelul algo([1, 2, 1, 2, 1, 2, 1, 2], 8, 4) returneaz˘a valoarea True. D. Apelul algo([1, 2, 3, 4, 3, 4], 6, 2) returneaz˘a valoarea True. 98. ✓ ?Se consider˘a algoritmul algo(n, k), unde n s, i k sunt numere naturale (1 ≤ n, k ≤ 106): Algorithm algo(n, k) nr ← 0 p ← 1 While (n̸ = 0) AND (k̸ = 0) execute a ← n MOD 10 b ← (n DIV 10) MOD 10 If (a + b) MOD 3 = 0 then nr ← nr + (a ∗ b) ∗ p p ← p ∗ 10 Else k ← k − 1 EndIf n ← n DIV 10 EndWhile Return nr EndAlgorithm Care dintre urm˘atoarele perechi de apeluri returneaz˘a valori identice? A. algo(676458, 3) s, i algo(655413, 3) B. ceFace(2314587, 4) s, i ceFace(1314579, 5) C. algo(321458, 7) s, i algo(120459, 6) D. ceFace(227459, 6) s, i algo(227454, 4) 99. ✓ ?Se consider˘a algoritmul transform(secv, n, m), unde n este un num˘ar natural (1 ≤ n ≤ 104), secv este un vector cu n elemente numere naturale (secv[1], secv[2], . . . , secv[n]), iar m este un num˘ar ˆıntreg. Se consider˘a |m| ca fiind valoarea absolut˘a a num˘arului. Algorithm transform(secv, n, m) For i ← 1, n execute rez[i] ← 1 EndFor For i ← 1, n execute If m = 0 then rez[i] ← 1 Else If m > 0 then prod ← 1 For j ← 1, m execute prod ← prod ∗ secv[(i + j − 1) MOD n + 1] EndFor rez[i] ← prod Else prod ← 1 66
Subiect · pagina 72
Algoritmi elementari Probleme For j ← 1, |m| execute prod ← prod ∗ secv[(i − j + n − 1) MOD n + 1] EndFor rez[i] ← prod EndIf EndFor Return rez EndAlgorithm Precizat, i care dintre urm˘atoarele afirmat, ii sunt adev˘arate: A. Pentru apelul transform([1, 3, 8, 5, 9], 5, 2) algoritmul va returna [25, 40, 45, 30, 9]. B. Pentru apelul transform([1, 3, 2, 7], 4, -3) algoritmul va returna [42, 14, 21, 6]. C. Pentru apelul transform([2, 3, 4, 5, 6], 5, 3) algoritmul va returna [60, 120, 60, 36, 24]. D. Pentru apelul transform([1, 3, 7, 5, 9], 5, -2) algoritmul va returna [45, 9, 3, 21, 35]. 100. ✓ ?Se consider˘a algoritmii g(v, n), s, i f(v, n, t),unde n este un num˘ar natural (1 ≤ n ≤ 104), v este un vector cu n elemente numere naturale (v[1], v[2], . . . , v[n]), iar t este un num˘ar natural (1 ≤ n ≤ 104). Valoarea IN F reprezint˘a valoarea cea mai mare valoarea posibil˘a. Algorithm f(v, n, t) g(v, n) c ← INF aux ← [ ] For i ← 1, 3 execute aux[i] ← 0 EndFor For i ← 1, n − 2 execute l ← i + 1 r ← n − 1 While l < r execute s ← v[i] + v[l] + v[r] If |s − t| < |c − t| then c ← s aux ← [v[i], v[l], v[r]] EndIf If s < t then l ← l + 1 Else If s > t then r ← r − 1 Else Return aux EndIf EndWhile EndFor Return aux EndAlgorithm Algorithm g(v, n) For i ← 1, n − 1 execute For j ← 1, n − i execute If v[j] > v[j + 1] then temp ← v[j] v[j] ← v[j + 1] v[j + 1] ← temp EndIf EndFor EndFor EndAlgorithm 67
Subiect · pagina 73
Algoritmi elementari Probleme Precizat, i care dintre afirmat, iile de mai jos sunt adev˘arate: A. Algoritmul indic˘a tripletul de elemente din vector, a c˘arui sum˘a reprezint˘a cea mai apropiat˘a valoare de o valoare dat˘a. B. Algoritmul indic˘a tripletul de elemente din vector, a c˘arui sum˘a reprezint˘a ele- mentul strict mai mic al unei valori date. C. Pentru apelul f([-1, 2, 1, -3, 5, -4], 6, 1) algoritmul returneaz˘a [−3, −1, 5]. D. Pentru apelul f([-1, 7, 1, 5, -8], 5, 6) algoritmul returneaz˘a [−1, 1, 5]. 101. ✓ ?Se consider˘a algoritmul one(nr), unde nr este un num˘ar natural nenul (1 ≤ nr ≤ 106) s, i algoritmul two(v, n), unde n este un num˘ar natural nenul (1 ≤ n ≤ 10000) s, i v un vector cu n numere naturale pozitive (1 ≤ v[1], v[2], . . . , v[n] ≤ 106). 1: Algorithm two(v, n) 2: cnt ← 0 3: p ← 1 4: For i ← 1, n − 1 execute 5: For j ← n, i + 1, −1 execute 6: p ← p + 1 7: If (one(v[i]) MOD 2 = one(v[j]) MOD 2) AND (one(v[i]) MOD 2) then 8: cnt ← cnt + 1 9: EndIf 10: EndFor 11: EndFor 12: Return p − cnt − 1 13: EndAlgorithm Algorithm one(nr) c ← 0 For d ← 1, d * d ≤ nr execute If nr MOD d = 0 then c ← c + 1 If d * d < nr then c ← c + 1 EndIf EndIf EndFor Return c EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt false? A. Pentru apelul one(2027), se retur- neaz˘a 2. B. Pentru apelul two([144, 12, 24, 1024, 4, 36], 6), se returneaz˘a 6. C. Algoritmul two(v, n) returneaz˘a num˘arul de perechi (a, b) de elemente din vector, cu num˘ar par de divizori. D. Dac˘a linia 12 ar fi schimbat˘a cu “Return cnt”, algoritmul two(v, n) ar returna num˘arul de perechi de elemente din vector, cu proprietatea c˘a cele 2 numere sunt p˘atrate per- fecte. 102. ✓ ?Se consider˘a algoritmul poate(n, b), unde n s, i b sunt numere naturale nenule (1 ≤ n ≤ 109, 2 ≤ b ≤ 10). Algorithm poate(n, b) If n = 0 then Return 1 EndIf 68
Subiect · pagina 74
Algoritmi elementari Probleme Return n MOD b MOD 2 * poate(n DIV b, b) EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Pentru n = 42 s, i b = 4, algoritmul returneaz˘a 1. B. Pentru n = 502 s, i b = 7, algoritmul returneaz˘a 1. C. Algoritmul poate(n, b) returneaz˘a produsul cifrelor pare ale lui n din reprezen- tarea ˆın baza b. D. Algoritmul poate(n, b) returneaz˘a 1 dac˘a s, i numai dac˘a toate cifrele lui n din reprezentarea ˆın baza b sunt impare. 103. ✓ ?Fie nr un num˘ar ˆıntreg (0 < nr ≤ 109) s, i b o baz˘a ˆıntreag˘a (1 < b < 11). Precizat, i care dintre urm˘atorii algoritmi transform˘a corect num˘arul nr din baza b ˆın baza 10 s, i returneaz˘a acest num˘ar. A. Algorithm alg1(nr, b) rez ← 0 k ← 1 ax ← 1 While nr > 0 execute ax ← (nr MOD 10) ∗ k rez ← rez + ax nr ← nr DIV 10 k ← k ∗ b EndWhile Return rez EndAlgorithm B. Algorithm alg2(nr, b) rez ← 0 k ← 1 While nr > 0 execute k ← k ∗ b rez ← rez + (nr MOD 10) ∗ k nr ← nr DIV 10 EndWhile Return rez EndAlgorithm C. Algorithm alg3(nr, b) If nr = 0 then Return 0 EndIf Return nr MOD 10+alg3(nr DIV 10, b∗ b) EndAlgorithm D. Algorithm alg4(nr, b) If nr = 0 then Return 0 EndIf ax ← nr ax ← ax MOD 10 nr1 ← nr DIV 10 Return ax + alg4(nr1, b) ∗ b EndAlgorithm 104. ✓ ?Se consider˘a algoritmul clock(n), unde n este un num˘ar natural (1 ≤ n ≤ 104). Algorithm clock(n) nd ← 0 For i ← 1, n execute If n MOD i = 0 then If i MOD 2 = 0 then nd ← nd + 1 Else nd ← nd − 1 EndIf 69
Subiect · pagina 75
Algoritmi elementari Probleme
EndIf
EndFor
Return nd
EndAlgorithm
Care dintre urm˘atoarele afirmat, ii sunt adev˘arate?
A. Dac˘a n = 12, algoritmul returneaz˘a 2.
B. Algoritmul calculeaz˘a s, i returneaz˘a diferent, a dintre num˘arul de divizori pari s, i
num˘arul de divizori impari ai lui n.
C. Dac˘a n este un num˘ar prim, algoritmul clock(n) returneaz˘a ˆıntotdeauna -2.
D. Algoritmul clock(n) returneaz˘a 0 pentru toate numerele din mult, imea
{2, 6, 18, 30, 72}.
105. ✓ ?Se consider˘a algoritmul algo(n, x, p), unde n este un num˘ar natural (1 ≤ n ≤
105), x este un vector cu n elemente numere ˆıntregi (x[1], x[2], . . . , x[n]), iar p este un
num˘ar natural:
Algorithm algo(n, x, p)
If n MOD p̸ = 0 then
Return False
EndIf
i ← 1
While i ≤ n − p execute
If x[i]̸ = x[i + p] then
Return False
EndIf
i ← i + 1
EndWhile
Return True
EndAlgorithm
Pentru care dintre urm˘atoarele condit, ii al-
goritmul returneaz˘a True?
A. Dac˘a vectorul x este periodic de peri-
oad˘a p, iar lungimea n este un multi-
plu al perioadei p.
B. Dac˘a ˆın vectorul x toate elementele au
aceeas, i valoare, indiferent de valoarea
lui p.
C. Dac˘a x[i] este egal cu x[i+p] pen-
tru i = 1, n, iar lungimea n nu este
multiplu al lui p.
D. Dac˘a vectorul x este periodic cu peri-
oada p, iar n mod p = 0.
106. ✓ ?Se consider˘a algoritmul algo(n, d), unde n este un num˘ar natural pozitiv (1 ≤
n ≤ 104), iar d este o cifr˘a (0 ≤ d ≤ 9).
Algorithm algo(n, d)
count ← 0
total ← 0
While n > 0 execute
r ← n MOD 10
If r = d then
count ← count + 1
EndIf
total ← total + 1
n ← n DIV 10
EndWhile
Return count > total DIV 2
EndAlgorithm
Precizat, i care dintre urm˘atoarele afirmat, ii
sunt adev˘arate:
A. Pentru n = 1223333 s, i d = 3, algorit-
mul returneaz˘a True.
B. Pentru n = 444555 s, i d = 4, algorit-
mul returneaz˘a True.
C. Algoritmul verific˘a dac˘a cifra d apare
de mai multe ori decˆat jum˘atate din
num˘arul total de cifre ale lui n.
D. Pentru n = 77431 s, i d = 7, algoritmul
returneaz˘a True.
70Subiect · pagina 76
Algoritmi elementari Probleme 107. ✓ ?Se consider˘a algoritmul algo(n, b), unde n este un num˘ar natural pozitiv (1 ≤ n ≤ 106) s, i b este un num˘ar natural. Algorithm algo(n, b) count ← 0 While n > 0 execute r ← n MOD b If r MOD (b − 1) = 0 then count ← count + 1 EndIf n ← n DIV b EndWhile Return count EndAlgorithm Precizat, i care dintre urm˘atoarele afirmat, ii sunt adev˘arate: A. Pentru n = 31 s, i b = 4, algoritmul returneaz˘a 2. B. Pentru n = 255 s, i b = 16, algoritmul returneaz˘a 2. C. Algoritmul determin˘a cˆate cifre din reprezentarea num˘arului n ˆın baza b sunt divizibile cu b − 1. D. Algoritmul determin˘a suma cifrelor din reprezentarea num˘arului n ˆın baza b care sunt divizibile cu b − 1. 108. ✓ ?Se consider˘a algoritmul algo(n, x), unde n este un num˘ar natural (1 ≤ n ≤ 104), iar x este un vector cu n elemente numere ˆıntregi (x[1], x[2], . . . , x[n]). Algorithm algo(n, x) For i ← 1, n − 1 execute nr ← 0 a ← x[i] b ← x[i + 1] While a > 0 OR b > 0 execute If a > 0 then cif a ← a MOD 10 Else cif a ← 0 EndIf If b > 0 then cif b ← b MOD 10 Else cif b ← 0 EndIf If cif a > cif b then nr ← nr + (cif a − cif b) Else If cif a < cif b then nr ← nr − (cif b − cif a) Else nr ← nr + 1 EndIf a ← a DIV 10 b ← b DIV 10 EndWhile x[i] ← (x[i] + nr) MOD (i + 1) EndFor s ← 0 For i ← 1, n execute s ← s + x[i] EndFor 71
Subiect · pagina 77
Algoritmi elementari Probleme x[n] ← s MOD 10 Return x EndAlgorithm Care va fi noul cont, inut al vectorului x dup˘a executarea algoritmului dat dac˘a n = 6 s, i x = [134, 214, 789, 578, 636, 543]? A. [0, 2, 1, 2, 3, 2] B. [0, 2, 1, 3, 3, 3] C. [0, 2, 1, 3, 3, 2] D. [1, 2, 1, 3, 3, 2] 109. ✓ ?Se consider˘a algoritmul algo(n), unde n este un num˘ar natural (1 ≤ n ≤ 105). Algorithm algo(n) a ← 0 b ← False While n > 0 execute c ← n MOD 10 If c MOD 2 = 0 then a ← a + c b ← True EndIf n ← n DIV 10 EndWhile If NOT b then Return −1 Else Return a EndIf EndAlgorithm Ce va returna apelul algo(6356)? A. 13 B. 50 C. 0 D. 12 110. ✓ ?Se consider˘a algoritmul algo(a, b), unde a s, i b sunt numere naturale (1 ≤ a, b ≤ 105). Algorithm algo(a, b) c ← 0 d ← 1 p ← 1 While a + b > 0 execute If (a MOD 10 + b MOD 10) MOD 2 = 0 then c ← (a MOD 10 + b MOD 10) ∗ p Else If a MOD 10 > b MOD 10 then c ← (a MOD 10 − b MOD 10) ∗ p Else c ← (b MOD 10 − a MOD 10) ∗ p EndIf EndIf If c < 0 then c ← c ∗ (−1) EndIf d ← d + c p ← p + 2 a ← a DIV 10 b ← b DIV 10 72
Subiect · pagina 78
Algoritmi elementari Probleme EndWhile Return d EndAlgorithm Care va fi rezultatul apelului algo(387, 2349)? A. 23 B. 145 C. 97 D. 278 111. ✓ ?Se consider˘a algoritmul f(v, n), unde n este un num˘ar natural (1 ≤ n ≤ 104), iar v este un vector cu n elemente numere naturale (v[1], v[2], . . . , v[n]). Algorithm f(v, n) If n = 0 then Return 0 EndIf If n = 1 then Return v[1] EndIf p2 ← 0 p1 ← v[1] For i ← 2, n execute If p1 > p2 + v[i] then c ← p1 Else c ← p2 + v[i] EndIf p2 ← p1 p1 ← c EndFor Return p1 EndAlgorithm A. Apelul f([2, 7, 9, 3, 1], 5) va returna valoarea 12. B. Apelul f([2, 1, 1, 2], 4) va re- turna valoarea 3. C. Apelul f([9, 7, 8, 4, 1, 9], 6) va returna valoarea 26. D. Apelul f([9, 7, 8, 4, 1, 6, 9, 2], 8) va returna valoarea 32. 112. ✓ ?Se consider˘a algoritmul ceFace(n, arr), unde n este un num˘ar natural nenul (1 ≤ n ≤ 104) s, i arr este un vector de n numere ˆıntregi (−100 ≤ arr[1], arr[2], . . . , arr[n] ≤ 100). Algorithm ceFace(n, arr) b ← True i ← 1 While i ≤ n and b execute b ← arr[i] mod 2 = 0 i ← i + 1 EndWhile Return b EndAlgorithm Pentru care din urm˘atoarele situat, ii algorit- mul returneaz˘a True? A. Dac˘a vectorul arr este format din va- lorile 2, 0, 4, −2, 8, −6. B. Dac˘a vectorul arr este format din va- lorile 4, 10, −1, 8, 6, 2. C. Dac˘a vectorul arr are doar elemente impare. D. Dac˘a vectorul arr are cel put, in un ele- ment par. 113. ✓ ?Se consider˘a algoritmul X(arr, n, y), unde n s, i y sunt numere naturale (4 ≤ n ≤ 104, 1 ≤ y ≤ 104) s, i arr este un vector de n numere naturale nenule (1 ≤ arr[1], arr[2], . . . , arr[n] ≤ 104). 73
Subiect · pagina 79
Algoritmi elementari Probleme Algorithm X(arr, n, y) If y > n then Return 0 EndIf For i ← 1, n − 2 execute arr[i+1] ← arr[i]+2 * arr[i+2]−arr[i+1] EndFor Return arr[y] EndAlgorithm Pentru care din urm˘atoarele ape- luri returneaz˘a valoarea 16? A. X([7, 4, 3, 5, 12], 5, 3) B. X([2, 5, 7, 9, 4], 5, 4) C. X([1, 4, 7, 8, 10, 16], 6, 6) D. X([7, 5, 2, 3, 4, 9, 2], 7, 5) Problemele 114., 115. se refer˘a la urm˘atorul algoritm ceFace(n, k, r), unde n, k, s, i r sunt numere naturale nenule (1 ≤ n, k, r ≤ 103). Algorithm ceFace(n, k, r) If k * k > n then If n > 1 then r ← r * (n + 1) EndIf Return r EndIf p ← 0 sF ← 1 While n MOD k = 0 execute p ← p + 1 n ← n DIV k sF ← sF * k EndWhile If p > 0 then r ← r * (sF * k − 1) DIV (k − 1) EndIf Return ceFace(n, k + 1, r) EndAlgorithm 114. ✓ ?Pentru care din urm˘atoarele afirmat, ii sunt adev˘arate referitoare la apelul ceFace(n, 2, 1)? A. Algoritmul returneaz˘a num˘arul de divizori impari ai num˘arului n. B. Algoritmul returneaz˘a num˘arul de divizori ai num˘arului n. C. Algoritmul returneaz˘a suma divizorilor num˘arului n. D. Algoritmul are complexitatea de timp O(log n). 115. ✓ ?Care dintre urm˘atoarele afirmat, ii sunt false referitoare la algoritmul ceFace(n, k, r)? A. Pentru apelul ceFace(12, 2, 1) algoritmul returneaz˘a 28. B. Pentru apelurile ceFace(16, 2, 1) s, i ceFace(30, 2, 2) algoritmul returneaz˘a 31. C. Pentru apelul ceFace(360, 2, 1) algoritmul returneaz˘a 1160. D. Pentru apelurile ceFace(100, 2, 1) s, i ceFace(100, 2, 2) algoritmul retur- neaz˘a aceeas, i valoare. 116. ✓ ?Se consider˘a algoritmul ceFacea(n, l, h), unde n, l s, i h sunt numere naturale nenule (1 ≤ n, l, h ≤ 109). 74
Subiect · pagina 80
Algoritmi elementari Probleme Algorithm ceFacea(n, l, h) If l > h then Return False EndIf m ← l + (h − l) DIV 2 If m * m * m = n then Return True Else If m * m * m < n then Return ceFacea(n, m + 1, h) Else Return ceFacea(n, l, m - 1) EndIf EndIf EndAlgorithm Precizat, i care afirmat, ii de mai jos sunt adev˘arate referitor la algorit- mul ceFacea(n, 1, n). A. Algoritmul returneaz˘a False pentru n = 8. B. Algoritmul returneaz˘a True pentru n = 5832. C. Exist˘a cel put, in 27 valori ˆın intervalul (1, 30] pentru care algoritmul returneaz˘a False. D. Algoritmul returneaz˘a True pentru exact 6 valori din in- tervalul [9, 513). 117. ✓ ?Se consider˘a algoritmul Magic(n), unde n este un num˘ar natural (1 ≤ n ≤ 105) Algorithm Magic(n) s ← 0 p ← 1 While n > 0 execute c ← n MOD 10 If c MOD 2 = 0 then s ← s + c ∗ p p ← p ∗ 10 Else s ← c + s ∗ 10 EndIf n ← n DIV 10 EndWhile Return s EndAlgorithm Precizat, i care dintre afirmat, iile urm˘atoare sunt adev˘arate: A. Pentru apelul Magic(23456) valoarea returnat˘a de algoritm este 1255 B. Pentru apelul Magic(987654) valoa- rea returnat˘a de algoritm este 18579 C. Algoritmul Magic(n) returneaz˘a un num˘ar construit prin rearanjarea ci- frelor lui n, astfel ˆıncˆat cifrele impare sunt p˘astrate ˆın ordine direct˘a, iar ci- frele pare ˆın ordine invers˘a, ment, inˆand pozit, iile relative ale acestora. D. Algoritmul Magic(n) inverseaz˘a ordi- nea tuturor cifrelor lui n. 118. ✓ ?Se consider˘a algoritmul Algo(x, y), unde x s, i y sunt numere naturale: Algorithm Algo(x, y) a ← x b ← y If a = 0 OR b = 0 then a ← a ∗ b Else While a̸ = b execute If a < b then a ← a + x Else b ← b + y EndIf EndWhile EndIf 75
Subiect · pagina 81
Algoritmi elementari Probleme Write a EndAlgorithm Precizat, i care dintre urm˘atoarele afirmat, ii sunt corecte: A. Algoritmul determin˘a cel mai mare divizor comun al numerelor x s, i y. B. Algoritmul calculeaz˘a cel mai mare multiplu al numerelor x sau y. C. Algoritmul calculeaz˘a cel mai mic multiplu comun a numerelor x s, i y. D. Algoritmul determin˘a cel mai mic num˘ar divizibil fie cu x, fie cu y. 119. ✓ ?Se consider˘a algoritmul ceFace(n), unde n este un num˘ar natural (1 ≤ n ≤ 106). Algorithm ceFace(n) s ← 0 p ← 1 While n > 0 execute c ← n MOD 10 p ← 1 x ← c ok ← True For i ← 1, c − 1 execute x ← x ∗ 10 + c p ← p ∗ 10 EndFor t ← x inv ← 0 While t > 0 execute inv ← inv ∗ 10 + t MOD 10 t ← t DIV 10 EndWhile If x = inv AND x > 0 then s ← s + x p ← p ∗ c EndIf n ← n DIV 10 EndWhile Return s MOD p EndAlgorithm Precizat, i care dintre afirmat, iile urm˘atoare sunt adev˘arate: A. Algoritmul ceFace(n) calculeaz˘a suma numerelor formate din cifrele lui n, repetate s, i verificate dac˘a sunt palindromuri, s, i returneaz˘a restul ˆımp˘art, irii la produsul cifrelor speciale. B. Pentru apelul ceFace(789), valoarea returnat˘a de algoritm este 464. C. Algoritmul returneaz˘a 0 dac˘a n cont, ine cel put, in o cifr˘a 0 D. Pentru apelul ceFace(123), algorit- mul returneaz˘a 3 deoarece doar cifrele care genereaz˘a palindromuri de lun- gime impar˘a contribuie la suma final˘a. 120. ✓ ?Se consider˘a algoritmul ceFace(n, p), unde n s, i p sunt numere naturale nenule (2 ≤ n ≤ 20, 1 ≤ p ≤ n). Algorithm ceFace(n, p) nrF ← 0 pr ← p While n ≥ pr execute nrF ← nrF + n DIV pr pr ← pr ∗ p EndWhile Return nrF EndAlgorithm Precizat, i care afirmat, ii de mai jos sunt adev˘arate: A. Algoritmul are complexitatea O(log n). 76
Subiect · pagina 82
Algoritmi elementari Probleme B. Algoritmul returneaz˘a suma numerelor mai mici ca n care sunt divizibile cu p. C. Algoritmul returneaz˘a num˘arul de factori p din n!. D. Algoritmul returneaz˘a num˘arul de numere divizibile cu p din intervalul [1, n]. 121. ✓ ?Se consider˘a algoritmii Cifra(n) s, i Check(x), unde n s, i x sunt numere naturale (1 ≤ n, x ≤ 106). f recv este un s, ir de 10 elemente, init, ializate cu 0. Algorithm Cifra(n) temp ← n While temp > 0 execute cif ra ← temp MOD 10 f recv[cif ra] ← f recv[cif ra] + 1 If f recv[cif ra] > 1 then Return 0 EndIf temp ← temp DIV 10 EndWhile s ← Check(n) If s = n then Return 1 EndIf While s > 9 execute aux ← s s ← 0 While aux > 0 execute s ← s + aux MOD 10 aux ← aux DIV 10 EndWhile EndWhile Return s EndAlgorithm Algorithm Check(x) s ← 0 For d ← 1, √x execute If x MOD d = 0 then s ← s + d If d ∗ d̸ = x then s ← s + x DIV d EndIf EndIf EndFor Return s EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Funct, ia Cifra(n) returneaz˘a 1 dac˘a n este un num˘ar perfect s, i toate cifrele sale sunt distincte. B. Pentru apelul Cifra(7654), valoarea returnat˘a de algoritm este 9. C. Funct, ia Cifra(n) returneaz˘a restul sumei divizorilor lui n redus la o singur˘a cifr˘a, dac˘a toate cifrele lui n sunt distincte. D. Pentru apelul Cifra(452), valoarea returnat˘a de algoritm este 6. 122. ✓ ?Se consider˘a algoritmii ceFace(n) s, i Algo(n), unde n este un num˘ar natural nenul (1 ≤ n ≤ 106). Simbolul & reprezint˘a operat, ia de AND pe bit, i (1012&1102 = 1002). 77
Subiect · pagina 83
Algoritmi elementari Probleme
Algorithm Algo(n)
For i ← 1, n execute
v[i] ← i − 1
EndFor
For i ← n, 2 execute
j ← (i − 1) & ((i − 1) − 1)
aux ← v[i]
v[i] ← v[j + 1]
v[j + 1] ← aux
EndFor
Return v
EndAlgorithm
Algorithm ceFace(n)
p ← Algo(n)
suma ← 0
For i ← 1, n execute
If (p[i] & (i − 1)) = (i − 1) then
suma ← suma + 1
EndIf
EndFor
Return suma
EndAlgorithm
Care dintre urm˘atoarele afirmat, ii sunt adev˘arate?
A. Pentru apelul ceFace(2345), valoarea returnat˘a de algoritm este 587.
B. Algoritmul determin˘a suma palindromurilor formate din fiecare cifr˘a repetat˘a
un num˘ar egal cu valoarea sa, modulat˘a de produsul cifrelor din num˘ar care
genereaz˘a palindromurilor valide.
C. Pentru apelul ceFace(7546), valoarea returnat˘a de algoritm este 1887.
D. Algoritmul calculeaz˘a r˘ad˘acina produsului dintre palindromurilor formate din
fiecare cifr˘a repetat˘a de atˆatea ori cˆat reprezint˘a valoarea cifrei.
123. ✓ ?Se consider˘a algoritmul S(n, s, d), unde n, s s, i d sunt numere naturale nenule
(1 ≤ n, s, d ≤ 104).
Algorithm S(n, s, d)
If s > n then
Return False
EndIf
If s = n then
Return True
EndIf
Return S(n, s + d, d + 2)
EndAlgorithm
Precizat, i care afirmat, ii sunt adev˘arate referitor la apelul algoritmului S(n, 0, 1):
A. Algoritmul verific˘a dac˘a n este p˘atrat perfect.
B. Algoritmul verific˘a dac˘a n poate fi scris ca sum˘a de numere naturale consecutive
impare ˆıncepˆand de la 1.
C. Exist˘a exact 19 valori ˆın intervalul [71, 734] pentru care algoritmul returneaz˘a
True.
D. Algoritmul returneaz˘a False pentru exact 2 numere din mult, imea {73, 9, 442, 841,
576, 962}.
124. ✓ ?Se consider˘a algoritmul ceFace(n, k), unde n s, i k reprezint˘a numere naturale:
78Subiect · pagina 84
Algoritmi elementari Probleme Algorithm ceFace(n, k) c ← 0 While n > 0 execute x ← n y ← 0 len ← 0 For i ← 1, k execute If x = 0 then Return c EndIf y ← y ∗ 10 + (x MOD 10) x ← x DIV 10 len ← len + 1 EndFor If len < k then Return c EndIf unique ← True temp ← y While temp > 0 execute d ← (temp MOD 10) f recv[d] ← f recv[d] + 1 If f recv[d] > 1 then unique ← False Break EndIf temp ← temp DIV 10 EndWhile If unique then c ← c + 1 EndIf n ← n DIV 10 EndWhile Return c EndAlgorithm Precizat, i care dintre urm˘atoarele afirmat, ii sunt adev˘arate: A. Secvent, ele verificate sunt reordonate s, i comparate ˆın ordine descresc˘atoare pentru a determina unicitatea cifrelor. B. Algoritmul determin˘a num˘arul de subsecvent, e de k cifre consecutive ˆın n, unde toate cifrele din subsecvent, ˘a sunt distincte C. Dac˘a lungimea r˘amas˘a a num˘arului n este mai mic˘a decˆat k, algoritmul returneaz˘a 0 f˘ar˘a a mai verifica alte secvent, e. D. Algoritmul calculeaz˘a suma cifrelor distincte din secvent, ele de lungime k ˆın loc s˘a returneze num˘arul lor. 125. ✓ ?Se consider˘a algoritmul SpecialBits(n), unde n reprezint˘a un num˘ar natural (1 ≤ n ≤ 105). Operat, ia SHL (Shift Left) este definit˘a ca o operat, ie de deplasare pe bit, i (bitwise shift left), care deplaseaz˘a bit, ii unui num˘ar spre stˆanga cu un anumit num˘ar de pozit, ii. Algorithm SpecialBits(n) If n = 0 then Return 0 EndIf count ← 0 mask ← 1 While mask ≤ n execute temp ← n AND ((mask SHL 1) − 1) next ← temp OR mask If next ≤ n then count ← count + 1 aux ← next While aux > 0 execute 79
Subiect · pagina 85
Algoritmi elementari Probleme If (aux AND mask)̸ = 0 then test ← aux AND (aux −1) If test ≤ n then count ← count + 1 aux ← test Else aux ← aux AND (aux − 1) EndIf Else aux ← aux AND (aux − 1) EndIf EndWhile EndIf mask ← mask SHL 1 EndWhile Return count EndAlgorithm Precizat, i care dintre urm˘atoarele afirmat, ii sunt adev˘arate: A. Algoritmul returneaz˘a num˘arul de operat, ii posibile asupra n, care respect˘a con- strˆangerile impuse de mask s, i bit-shifting. B. Dac˘a n este o putere a lui 2, algoritmul va returna ˆıntotdeauna n − 1. C. Algoritmul verific˘a toate submask-urile posibile ale lui n, indiferent de con- strˆangeri. D. Pentru apelul SpecialBits(12), algoritmul va returna valoarea 9. 126. ✓ ?Se consider˘a algoritmul ceFace(a, b), unde a s, i b sunt numere naturale (1 ≤ a, b ≤ 104). 1: Algorithm ceFace(a, b) 2: x ← a 3: y ← b 4: While x̸ = y execute 5: If x < y then 6: x ← x + a 7: Else 8: y ← y + b 9: EndIf 10: EndWhile 11: Return x 12: EndAlgorithm Precizat, i care dintre urm˘atoarele afirmat, ii sunt adev˘arate: A. Pentru apelul ceFace(24, 36), algo- ritmul returneaz˘a 72. B. Pentru apelul ceFace(52, 14), algo- ritmul returneaz˘a 728. C. Algoritmul returneaz˘a cel mai mare divizor comun al lui a s, i b. D. Dac˘a Linia 11 ar fi schimbat˘a cu Return a * b DIV y, algoritmul ar returna cel mai mare divizor comun al lui a s, i b. 80
Subiect · pagina 86
5 Complexitatea algoritmilor Acest capitol acoper˘a • De ce sunt importante complexit˘at, ile ˆın analiza algoritmilor; • Cum se determin˘a complexitatea unui algoritm; • Exemple de complexit˘at, i comune s, i implement˘arile lor; • Diferent, a ˆıntre complexit˘at, i aditive s, i multiplicative. 5.1 Teorie Complexit˘at, ile algoritmilor reprezint˘a un concept fundamental care se afl˘a la intersect, ia dintre informatic˘a s, i matematic˘a. Acestea ne permit s˘a estim˘am num˘arul aproximativ de pas, i necesari pentru ca un algoritm s˘a rezolve o problem˘a, constituind un instrument esent, ial ˆın alegerea algoritmului optim ˆın funct, ie de cerint, ele de eficient, ˘a. Des, i comple- xitatea poate fi analizat˘a atˆat din perspectiva temporal˘a, cˆat s, i spat, ial˘a, ˆın acest capitol ne vom concentra pe analiza temporal˘a a algoritmilor. 5.1.1 Elementele Fundamentale ale Complexit˘at, ilor • Complexitate constant˘a O(1): – Timpul de execut, ie este independent de dimensiunea datelor de intrare – Operat, iile elementare (atribuiri, operat, ii aritmetice simple, comparat, ii) au complexitate constant˘a • Complexitate liniar˘a O(n): – Num˘arul de pas, i este direct proport, ional cu dimensiunea datelor de intrare • Complexitate logaritmic˘a O(log n): – Num˘arul de pas, i cres, te lent pe m˘asur˘a ce dimensiunea datelor de intrare devine mai mare • Complexitate radical O(√n): – La fel ca ˆın cazul complexit˘at, ii logaritmice, num˘arul de pas, i cres, te lent pe m˘asur˘a ce dimensiunea intr˘arii devine mai mare • Complexitate p˘atratic˘a O(n2): – Num˘arul de pas, i cres, te proport, ional cu p˘atratul dimensiunii datelor de intrare ˆın cazul buclelor imbricate • Complexitate exponent, ial˘a O(2n):
Subiect · pagina 87
Complexitatea algoritmilor Teorie – Timpul de execut, ie cres, te rapid, fiind adesea ineficient pentru valori mari ale intr˘arii • Teorema Master (pentru algoritmi Divide and Conquer): – Fie un algoritm recursiv de tipul Divide and Conquer. Complexitatea sa poate fi scris˘a sub forma T (n) = a · T (n/b) + Θ(nk · logp(n)). – Clasa de complexitate a algoritmului poate fi determinat˘a astfel: ∗ Cazul 1: Dac˘a a > bk ⇒ T (n) = Θ(nlogb(a)) ∗ Cazul 2: Dac˘a a = bk: · Pentru p > −1 ⇒ T (n) = Θ(nlogb(a) · logp+1(n)) · Pentru p = −1 ⇒ T (n) = Θ(nlogb(a) · log(log(n))) · Pentru p < −1 ⇒ T (n) = Θ(nlogb(a)) ∗ Cazul 3: Dac˘a a < bk: · Pentru p ≥ 0 ⇒ T (n) = Θ(nk · logp(n)) · Pentru p < 0 ⇒ T (n) = O(nk) 5.1.2 Exemple de implementare Exemplu de Complexitate Liniar˘a O(n) 1: For i ← 1, n execute 2: Write i 3: EndFor Exemplu de Complexitate Logaritmic˘a O(log n) 1: i ← 1 2: While i ≤ n execute 3: Write i 4: i ← i × 2 5: EndWhile Exemplu de Complexitate O(√n) 1: i ← 1 2: While i ∗ i ≤ n execute 3: Write i 4: i ← i + 1 5: EndWhile Exemplu de Complexitate P˘atratic˘a O(n2) 1: For i ← 1, n execute 2: For j ← 1, n execute 3: Write i, j 4: EndFor 5: EndFor 82
Subiect · pagina 88
Complexitatea algoritmilor Probleme Exemplu de Complexitate Exponent, ial˘a O(2n) 1: Algorithm Fibonacci(n) 2: If n ≤ 1 then 3: Return 1 4: Else 5: Return Fibonacci(n − 1) + Fibonacci(n − 2) 6: EndIf 7: EndAlgorithm 5.1.3 Analiza Complexit˘at, ii • Complexitate temporal˘a: Analiza unui algoritm ˆın funct, ie de num˘arul de operat, ii efectuate ˆın timpul execut, iei. • Complexitate spat, ial˘a: Analiza resurselor de memorie utilizate de algoritm ˆın timpul execut, iei. Observat, ie important˘a: Constantele sunt ignorate ˆın analiza Big-O, deoarece nu influent, eaz˘a cres, terea pe termen lung a complexit˘at, ii. De exemplu, un algoritm de com- plexitate O(2n) este considerat echivalent cu unul de complexitate O(n). 5.2 Probleme 127. ✓ ?Se consider˘a algoritmul ceFace(n), unde n este un num˘ar natural nenul (1 ≤ n ≤ 104). Algorithm ceFace(n) k ← 0 For i ← n, n DIV 3, −1 execute For j ← 3, n, j ← j * 3 execute k ← k + n DIV 3 EndFor EndFor Return k EndAlgorithm Care este complexitatea de timp a algoritmului ceFace(n)? A. O(n2) B. O(n2 · log3(n)) C. O(n) D. O(n · log3(n)) 128. ✓ ?Se consider˘a algoritmul ceFace(n, v), unde v este un tablou unidimensional cu cel mult 106 elemente (v[1], v[2], . . . , v[n]) s, i n reprezint˘a num˘arul elementelor din v. Subalgoritmul A(n, v) produce o schimbare asupra tabloului v, sortˆand elementele cresc˘ator folosind metoda Selection Sort. Algorithm ceFace(n, v) A(n, v) For i ← 1, n − 2 execute For j ← i + 1, n − 1 execute st ← j + 1 dr ← n k ← n While st ≤ dr execute k ← (st + dr)/2 If v[i] + v[j] > v[k] then 83
Subiect · pagina 89
Complexitatea algoritmilor Probleme st ← k + 1 Else dr ← k − 1 EndIf EndWhile cnt ← cnt + (dr − j) EndFor EndFor Return cnt EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Algoritmul ceFace are complexitatea O(n); B. Algoritmul ceFace are complexitatea O(n2 log(n)) s, i calculeaz˘a num˘arul triple- telor (i, j, k) din tabloul v cu proprietatea c˘a v[i] − v[j] + v[k] > 0. C. Algoritmul ceFace are complexitatea O(n3) s, i calculeaz˘a num˘arul tripletelor (i, j, k) din tabloul v cu proprietatea c˘a v[i] + v[j] > 0. D. Algoritmul ceFace calculeaz˘a num˘arul triunghiurilor distincte care au lungimile laturilor ˆın tabloul v. 129. ✓ ?Se consider˘a algoritmul ceFace(n), unde n este un num˘ar natural nenul (1 ≤ n ≤ 104). Algorithm ceFace(n) k ← 0 m ← 1 While k ≤ n execute ind ← 1 While ind ≤ m execute Write j ind ← ind + 1 EndWhile k ← k + 1 m ← m * 3 EndWhile EndAlgorithm Care este complexitatea de timp a algorit- mului ceFace(n)? A. O(n · log3(n)) B. O(n2) C. O(3n) D. O(n · m) 130. ✓ ?Se consider˘a algoritmul Ack(n), unde n este un num˘ar natural nenul (1 ≤ n ≤ 104). Algorithm Ack(n) If n̸ = 1 then Ack(n - 1) Write n Ack(n - 1) Write n − 1 EndIf EndAlgorithm Care dintre urm˘atoarele afirmat, ii referitoare la algo- ritmul Ack(n) sunt false? A. Complexitatea de timp a algoritmului Ack(n) este O(n). B. Complexitatea de timp a algoritmului Ack(n) este O(2n). C. Complexitatea de timp a algoritmului Ack(n) este O(n2). D. Niciuna dintre afirmat, iile de mai sus. 84
Subiect · pagina 90
Complexitatea algoritmilor Probleme
131. ✓ ?Se consider˘a algoritmul ceFace(n, i), unde n s, i i sunt numere naturale nenule
(1 ≤ n, i ≤ 104).
Algorithm ceFace(n, i)
If n = 1 then
Return 1
Else
m ← n DIV 2
If i MOD 2 = 0 then
Return ceFace(m, i)−i
Else
Return ceFace(m, i)+i
EndIf
EndIf
EndAlgorithm
Care dintre urm˘atoarele afirmat, ii referitoare la
algoritmul ceFace(n, i) sunt adev˘arate?
A. Complexitatea de timp a algoritmului
ceFace(n, i) este O(log2(n)).
B. Complexitatea de timp a algoritmului
ceFace(n, i) este O(n).
C. Complexitatea de timp a algoritmului
ceFace(n, i) este O(n2).
D. Apelul ceFace(17, 5) returneaz˘a valoa-
rea 21.
132. ✓ ?Se consider˘a algoritmul X(n), unde n este un num˘ar natural nenul (1 ≤ n ≤ 104).
Algorithm X(n)
s ← 0
ind ← n
While ind > 0 execute
j ← 1
While j ≤ ind execute
s ← s + j + 5
j ← j * 5
ind ← ind DIV 5
EndWhile
EndWhile
Return s
EndAlgorithm
Care este complexitatea de timp a
algoritmului X(n)?
A. O(n2)
B. O(n · log5 n)
C. O(5n)
D. O(log5 n)
133. ✓ ?Care dintre urm˘atorii algoritmi sorteaz˘a ˆın cel mai eficient mod elementele unui
vector de n elemente cu valori din mult, imea {0, 1, 3, 5, 8, 9}?
A. QuickSort B. MergeSort C. CountSort D. BubbleSort
134. ✓ ?Se consider˘a vectorul ordonat cresc˘ator a cu n elemente numere naturale (1 ≤ n ≤
104) s, i un num˘ar natural q (1 ≤ n ≤ 109). Fie T interog˘ari de tipul: ”care este
num˘arul maxim de elemente din a ale c˘aror sum˘a nu dep˘as, es, te valoarea num˘arului
q?”. Care este complexitatea celui mai eficient subprogram care rezolv˘a o interogare?
(excluzˆand orice alte operat, ii ˆınaintea proces˘arii interog˘arilor)
A. O(log n); B. O(n log n); C. O(n); D. O(n2 log n).
85Subiect · pagina 91
6 Subprograme Acest capitol acoper˘a • Ce sunt subprogramele s, i de ce sunt utile? • Cum definim s, i folosim subprograme? • Tipurile de subprograme: funct, ii s, i proceduri. • Reutilizarea subprogramelor pentru organizarea codului. 6.1 Teorie Introducere ˆIn acest subcapitol discut˘am despre subprograme, un concept foarte important ˆın progra- mare. Subprogramele reprezint˘a un mod de a ˆımp˘art, i un program mai mare ˆın sect, iuni mai mici s, i reutilizabile, facilitˆand organizarea s, i gestionarea codului. Elementele Fundamentale ale Subprogramelor • Funct, ii: – Subprograme care returneaz˘a o valoare. • Proceduri: – Subprograme care nu returneaz˘a o valoare. Definirea Subprogramelor Un subprogram este definit o singur˘a dat˘a, dar poate fi apelat de oricˆate ori este necesar ˆın contextul unui program. Definirea unui subprogram implic˘a specificarea unui nume s, i a unei liste de parametri. ˆIn cazul funct, iilor, este necesar˘a utilizarea s, i a unei instruct, iuni return pentru a returna o valoare. Funct, ia suma 1: Algorithm suma(a, b) 2: Return a + b 3: EndAlgorithm Exemplul prezentat mai jos ilustreaz˘a o funct, ie simpl˘a care primes, te doi parametri, a s, i b, s, i returneaz˘a suma acestora. Funct, ia poate fi apelat˘a de mai multe ori: Apelarea funct, iei suma 1: result ← suma(3, 5) 2: Write result
Subiect · pagina 92
Subprograme Probleme Parametrii Subprogramelor Subprogramele pot include parametri, care reprezint˘a variabilele de intrare necesare pen- tru a executa operat, iile definite. Aces, ti parametri pot fi de mai multe tipuri, iar atˆat num˘arul, cˆat s, i tipul lor trebuie specificate la momentul apel˘arii subprogramului. Funct, ia inmultire 1: Algorithm inmultire(a, b) 2: Return a ∗ b 3: EndAlgorithm ˆIn cazul ˆın care un subprogram nu primes, te parametri, lista de parametri este omis˘a: Funct, ia hello 1: Algorithm hello 2: Write ”Salutare viitor student UBB Info!” 3: EndAlgorithm Reutilizarea Subprogramelor Unul dintre cele mai mari avantaje ale subprogramelor este reutilizarea. Odat˘a definit, un subprogram poate fi apelat de oricˆate ori este nevoie, ceea ce faciliteaz˘a modularitatea s, i reduce totodat˘a redundant, a codului: Apelarea funct, iei suma pentru reutilizare 1: result1 ← suma(10, 20) 2: result2 ← suma(15, 25) Concluzie Subprogramele sunt un instrument esent, ial pentru organizarea codului ˆın sect, iuni re- utilizabile. Acestea simplific˘a dezvoltarea aplicat, iilor, reduc volumul de cod scris de programatori s, i contribuie la cres, terea clarit˘at, ii s, i modularit˘at, ii codului. 6.2 Probleme 135. ✓ ?Se consider˘a algoritmul ceFace(arr, n, y), unde n s, i y sunt numere naturale (1 ≤ n ≤ 104, 1 ≤ y ≤ 104) s, i arr este un vector de n numere naturale nenule (1 ≤ arr[1], arr[2], . . . , arr[n] ≤ 104). 87
Subiect · pagina 93
Subprograme Probleme Algorithm ceFace(arr, n, y) rezultat ← 0 For i ← 1, n execute If arr[i] > y then rezultat ← rezultat + 1 EndIf EndFor Return rezultat EndAlgorithm Care dintre urm˘atoarele afirmat, ii despre funct, ie sunt adev˘arate? A. Algoritmul are complexitate O(n); B. Funct, ia returneaz˘a num˘arul elemente- lor din arr care sunt mai mari decˆat y; C. Algoritmul returneaz˘a 0 dac˘a toate elementele din arr sunt mai mici decˆat y+1; D. Algoritmul poate fi optimizat pentru a reduce complexitatea la O(log n). 136. ✓ ?Se consider˘a algoritmul ceFace(v, n, k), unde n s, i k sunt numere naturale (1 ≤ n, k ≤ 106), iar v este un vector de n numere naturale nenule (1 ≤ v[1], v[2], . . . , v[n] ≤ 109). Algorithm ceFace(v, n, k) k ← k MOD n temp ← vector auxiliar de dimensiune n For i ← 1, n execute temp[(i + k − 1) MOD n + 1] ← v[i] EndFor For i ← 1, n execute v[i] ← temp[i] EndFor EndAlgorithm Care dintre urm˘atoarele afirmat, ii despre funct, ie sunt adev˘arate? A. Algoritmul are complexitate O(n); B. Realizeaz˘a o rotat, ie a vectorului la dreapta cu k pozit, ii; C. Algoritmul face ca in vectorul temp doar pozitiile pare sa fie ocupate; D. Modific˘a vectorul original. 137. ✓ ?Se consider˘a algoritmul ceFace(v, n), unde n este un num˘ar natural nenul (1 ≤ n ≤ 106), iar v este un vector de n numere ˆıntregi (−109 ≤ v[1], v[2], . . . , v[n] ≤ 109). Algorithm ceFace(v, n) count ← 0 For i ← 1, n − 1 execute If v[i] > v[i + 1] then temp ← v[i] v[i] ← v[i + 1] v[i + 1] ← temp count ← count + 1 EndIf EndFor Return count EndAlgorithm Care dintre urm˘atoarele afirmat, ii despre funct, ie sunt adev˘arate? A. Algoritmul implementeaz˘a o iterat, ie din bubble sort; B. Complexitatea este O(n); C. Num˘arul returnat reprezint˘a cˆate in- terschimb˘ari s-au f˘acut; D. Vectorul va fi complet sortat dup˘a execut, ie. 138. ✓ ?Se consider˘a algoritmul ceFace(v, n), unde n este un num˘ar natural nenul (1 ≤ n ≤ 106), iar v este un vector de n numere ˆıntregi (−109 ≤ v[1], v[2], . . . , v[n] ≤ 109). Algorithm ceFace(v, n) Sum ← v[1] 88
Subiect · pagina 94
Subprograme Probleme currentSum ← v[1] For i ← 2, n execute currentSum ← max(v[i], currentSum + v[i]) Sum ← max(Sum, currentSum) EndFor Return Sum EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Algoritmul g˘ases, te suma maxim˘a a unei subsecvent, e continue; B. Complexitatea este O(n); C. Pentru un vector cu toate elementele negative, se va returna cel mai mare element; D. Algoritmul modific˘a vectorul original. 139. ✓ ?Se consider˘a algoritmul ceFace(n), unde n este un num˘ar natural nenul (1 ≤ n ≤ 109). Algorithm ceFace(n) count ← 0 For i ← 1, i · i ≤ n execute If n mod i = 0 then count ← count + 1 If i · i̸ = n then count ← count + 1 EndIf EndIf EndFor Return count EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt false? A. Algoritmul num˘ar˘a divizorii proprii a lui n; B. Complexitatea este O(√n); C. Pentru n = 1, rezultatul este 0; D. Pentru numere prime, rezultatul este ˆıntotdeauna 2. 140. ✓ ?Se consider˘a algoritmul ceFace(n, k), unde n s, i k sunt numere naturale nenule (1 ≤ n, k ≤ 104). Algorithm ceFace(n, k) s ← 1 For i ← 1, n execute If i mod k = 0 then s ← s · i EndIf EndFor Return s EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? 89
Subiect · pagina 95
Subprograme Probleme A. Subalgoritmul poate returna orice num˘ar din intervalul [0, 104]; B. Dac˘a ar lipsi linia cu if(i % k == 0), rezultatul funct, iei ar fi factorialul lui n; C. Rezultatul funct, iei va fi un num˘ar divizibil cu k dac˘a s, i numai dac˘a n ≥ k; D. Pentru cazul ˆın care n < k, subalgoritmul returneaz˘a mereu o cifr˘a. 141. ✓ ?Se consider˘a algoritmul ceFace(n), unde n este un num˘ar natural nenul (2 ≤ n ≤ 109). Algorithm ceFace(n) For i ← 2, n DIV 2 execute If n mod i = 0 then Return 0 EndIf EndFor Return 1 EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Algoritmul returneaz˘a cˆat, i divizori are num˘arul n; B. Algoritmul verific˘a dac˘a num˘arul este prim, dar se poate face mai eficient; C. Algoritmul are complexitatea O(√n); D. Niciun r˘aspuns de mai sus. 142. ✓ ?Se consider˘a algoritmul ceFace(v, n, k), unde n s, i k sunt numere naturale (1 ≤ k < n ≤ 106), iar v este un vector de n numere ˆıntregi (−109 ≤ v[1], v[2], . . . , v[n] ≤ 109). Algorithm ceFace(v, n, k) For i ← 2, n execute v[i] ← v[i] + v[i − 1] EndFor Return v[n] − v[k] EndAlgorithm Care dintre urm˘atoarele afirmat, ii despre funct, ie sunt adev˘arate? A. Algoritmul poate returna s, i valori negative; B. Algoritmul este p˘atratic; C. Algoritmul calculeaz˘a suma subsecvent, ei dintre indicii [k + 1, n]; D. Dac˘a numerele din vector sunt pozitive s, i elementele ordonate cresc˘ator, rezulta- tul este ˆıntotdeauna pozitiv s, i nenul. 143. ✓ ?Se consider˘a algoritmul ceFace(n) definit al˘aturat, unde n este un num˘ar natural, n ≤ 1000 s, i a este un tablou unidimensional cu cel mult 105 elemente, init, ial toate nule. 90
Subiect · pagina 96
Subprograme Probleme Algorithm ceFace(n) a[1] ← 1 cf ← 1 For i ← 1, n execute cr ← 0 For j ← 1, cf execute temp ← a[j] ∗ i + cr a[j] ← temp MOD 10 cr ← temp DIV 10 EndFor While cr̸ = 0 execute cf ← cf + 1 a[cf ] ← cr MOD 10 cr ← cr DIV 10 EndWhile EndFor For i ← cf, 1, −1 execute scrie a[i] EndFor EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Algoritmul scrie pe ecran num˘arul de cifre al tuturor valorilor x!, unde x ∈ [1, n]; B. Algoritmul scrie pe ecran valoarea lui n!; C. Pentru n = 10, programul afis, eaz˘a pe ecran 3628800; D. Pentru n = 5, programul afis, eaz˘a 11123. 144. ✓ ?Se consider˘a algoritmul ceFace(v, n), unde v este un vector de n numere ˆıntregi (−109 ≤ v[1], v[2], . . . , v[n] ≤ 109), iar n este un num˘ar natural nenul (1 ≤ n ≤ 106). Algorithm ceFace(v, n) result ← 0 i ← 1 While i ≤ n execute While i < n and v[i] ≤ v[i + 1] execute i ← i + 1 EndWhile While i < n and v[i] ≥ v[i + 1] execute i ← i + 1 EndWhile result ← result + 1 i ← i + 1 EndWhile Return result EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Algoritmul num˘ar˘a vˆarfurile din vector (elemente precedate de o secvent, ˘a cresc˘atoare s, i urmate de una descresc˘atoare); B. Complexitatea este O(n); C. Pentru un vector strict cresc˘ator returneaz˘a n/2; D. Pentru un vector sortat cresc˘ator returneaz˘a 1. 145. ✓ ?Se consider˘a algoritmul ceFace(n), unde n este un num˘ar natural nenul (1 ≤ n ≤ 106). 91
Subiect · pagina 97
Subprograme Probleme Algorithm ceFace(n) sum ← 0 For i ← 1, n execute If n mod i = 0 then d ← i While d > 0 execute sum ← sum + (d mod 10) d ← d DIV 10 EndWhile EndIf EndFor Return sum EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt false? A. Algoritmul calculeaz˘a suma cifrelor tuturor divizorilor lui n; B. Complexitatea este O(n); C. Pentru numere prime returneaz˘a 1 + suma cifrelor lui n; D. Pentru n = 1 returneaz˘a 1. 146. ✓ ?Se consider˘a algoritmul ceFace(v, n), unde v este un vector de n numere ˆıntregi (−109 ≤ v[1], v[2], . . . , v[n] ≤ 109), iar n este un num˘ar natural nenul (1 ≤ n ≤ 106). Algorithm ceFace(v, n) maxLen ← 2 len ← 2 dif f ← v[2] − v[1] For i ← 2, n − 1 execute If v[i + 1] − v[i] = dif f then len ← len + 1 Else maxLen ← max(maxLen, len) len ← 2 dif f ← v[i + 1] − v[i] EndIf EndFor Return max(maxLen, len) EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Algoritmul g˘ases, te lungimea celei mai lungi progresii aritmetice consecutive din vector; B. Complexitatea este O(n); C. Pentru un vector cu valori constante returneaz˘a n; D. Pentru un vector cu elemente distincte returneaz˘a ˆıntotdeauna 2. 147. ✓ ?Se consider˘a algoritmul ceFace(v, n), unde v este un vector de n numere ˆıntregi (−109 ≤ v[1], v[2], . . . , v[n] ≤ 109), iar n este un num˘ar natural nenul (1 ≤ n ≤ 103). Algorithm ceFace(v, n) 92
Subiect · pagina 98
Subprograme Probleme result ← 0 For i ← 1, n execute For j ← i, n execute If v[i] = v[j] then result ← max(result, j − i) EndIf EndFor EndFor Return result EndAlgorithm Subprogramul max(a,b) returneaz˘a maximul dintre cele doua numere, unde a s, i b numere ˆıntregi. Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Algoritmul g˘ases, te distant, a maxim˘a ˆıntre dou˘a elemente egale; B. Are complexitate O(n); C. Pentru un vector cu elemente distincte returneaz˘a 0; D. Pentru un vector cu elemente constante returneaz˘a n − 1. 148. ✓ ?Se consider˘a algoritmul ceFace(v, n, k), unde v este un vector de n numere ˆıntregi (−109 ≤ v[1], v[2], . . . , v[n] ≤ 109), 1 ≤ n ≤ 103, iar k este un num˘ar natural nenul (1 ≤ k ≤ n). Algorithm ceFace(v, n, k) sum ← 0 For i ← 1, k execute sum ← sum + v[i] EndFor maxSum ← sum For i ← k + 1, n execute sum ← sum + v[i] − v[i − k] maxSum ← max(maxSum, sum) EndFor Return maxSum EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Algoritmul g˘ases, te suma maxim˘a a k elemente consecutive; B. Are complexitate O(n · k); C. Pentru k = 1 returneaz˘a maximul din vector; D. Pentru k = n returneaz˘a suma tuturor elementelor. 149. ✓ ?Se consider˘a algoritmul ceFace(n), unde n este un num˘ar natural (1 ≤ n ≤ 109). Algorithm ceFace(n) result ← 0 While n > 0 execute cif ra ← n mod 10 If cif ra mod 2 = 0 then result ← result · 10 + cif ra 93
Subiect · pagina 99
Subprograme Probleme EndIf n ← n DIV 10 EndWhile temp ← 0 While result > 0 execute temp ← temp · 10 + result mod 10 result ← result DIV 10 EndWhile Return temp EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Algoritmul p˘astreaz˘a doar cifrele pare din num˘ar ˆın ordinea lor init, ial˘a; B. Pentru un num˘ar care cont, ine doar cifre impare returneaz˘a 0; C. Are complexitate O(log n); D. Modific˘a ordinea cifrelor ˆın num˘arul rezultat. 150. ✓ ?Se consider˘a algoritmul ceFace(v, n), unde v este un vector de n numere ˆıntregi (−109 ≤ v[1], v[2], . . . , v[n] ≤ 109), iar n este un num˘ar natural nenul (1 ≤ n ≤ 106). Algorithm ceFace(v, n) result ← 0 count ← 0 For i ← 1, n execute If v[i] > 0 then count ← count + 1 If count > result then result ← count EndIf Else count ← 0 EndIf EndFor Return result EndAlgorithm Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? A. Algoritmul g˘ases, te lungimea celei mai lungi secvent, e de numere pozitive conse- cutive; B. Pentru un vector cu toate elementele negative returneaz˘a 0; C. Complexitatea este O(n2); D. Pentru un vector cu toate elementele pozitive returneaz˘a n/2. 94
Subiect · pagina 100
7 Recursivitate Acest capitol acoper˘a • ˆInt, elegerea conceptului de recursivitate s, i elementele sale fundamentale • Aplicarea modelului matematic s, i ecuat, iilor de recurent, ˘a 7.1 Teorie Recursivitatea este o tehnic˘a fundamental˘a ˆın programare care permite rezolvarea proble- melor complexe prin descompunerea lor ˆın subprobleme mai simple. Un algoritm recursiv este un algoritm care se autoapeleaz˘a pentru a rezolva o problem˘a mai mic˘a de acelas, i tip, reprezentˆand o implementare direct˘a a principiului matematic al induct, iei.[2] Elementele Fundamentale ale Recursivit˘at, ii • Cazul de baz˘a (condit, ia de terminare): – Reprezint˘a scenariul trivial al problemei, care poate fi rezolvat direct – Asigur˘a convergent, a algoritmului, prevenind buclele infinite – Pot exista unul sau mai multe cazuri de baz˘a • Pasul recursiv: – Reduce problema curent˘a la una sau mai multe instant, e mai simple – Fiecare apel recursiv apropie execut, ia de cazul de baz˘a Tipuri de Recursivitate • Recursivitate liniar˘a: – Implic˘a un singur apel recursiv per execut, ie – Exemplu: calculul factorialului, c˘autare binar˘a • Recursivitate arborescent˘a: – Implic˘a multiple apeluri recursive per execut, ie – Exemplu: Fibonacci recursiv naiv • Recursivitate indirect˘a (mutual˘a): – Apare atunci cˆand funct, iile se apeleaz˘a reciproc – Este util˘a ˆın procesarea structurilor de date complexe
Continuă pregătirea
Vezi arhiva completăAlte subiecte de la aceeași facultate
Examen de admitere · 2026Informatică · Sesiunea iulieDeschide fișa Examen de admitere · 2026Matematică · Sesiunea iulieDeschide fișa Concurs de pregătire · 2026Informatică · Concursul Mate-Info UBBDeschide fișa Concurs de pregătire · 2026Matematică · Concursul Mate-Info UBBDeschide fișa Examen de admitere · 2025Informatică · Sesiunea iulieDeschide fișa Examen de admitere · 2025Matematică · Sesiunea iulieDeschide 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 Matematică și Informatică. Documentul este etichetat după instituție, facultate, program și tipul probei folosind inventarul public verificat. Consultă metodologia actuală a instituției pentru condițiile examenului viitor.
Există și barem sau răspunsuri pentru acest subiect?
Nu există un barem public asociat în inventarul verificat pentru acest document. ProfesorBun nu generează și nu inventează răspunsuri oficiale. Poți folosi subiectul pentru antrenament, dar corectarea trebuie făcută cu metodologia instituției, cu materiale oficiale suplimentare sau împreună cu un profesor.
Cum folosesc acest subiect în pregătirea pentru admitere?
Rezolvă documentul fără ajutor și respectă timpul prevăzut de metodologia examenului. Corectează cu baremul disponibil, marchează capitolele unde ai pierdut puncte și repetă exerciții similare. Compară apoi cu alte probe din aceeași facultate și confirmă programa curentă pe site-ul oficial al instituției.