Algoritmi si structuri de date

Probleme Set C

S iruri de numere Recursivitate Tehnici de programare Liste, Stive si Cozi Arbori binari de c autare Grafuri Coduri Human

S iruri de numere

1. (5 pcte) S a se calculeze intersect ia unui sir de n intervale nchise. Dac a intervalul rezultat este vid se va a sa un mesaj corespunz ator. 2. (5 pcte) Pe prima linie a unui sier se g asesc, separate prin c ate un spat iu, o pereche de valori numere ntregi si un num ar real reprezent and coordonatele unui cerc si raza acestuia. Pe a doua linie, un num ar ntreg n si n continuare, pe urm atoarele n linii c ate o pereche de numere ntregi reprezent and coordonatele a n puncte din plan. S a se a seze coordonatele acelor puncte care se a a n interiorul cercului. 3. (5 pcte) Rangul unui element n cadrul unui sir este egal cu num arul de elemente strict mai mici dec at acesta. De exemplu, n sirul 7, 2, 1, 8, 4, 3, 2, 5, 1, rangul lui 4 este 5. Pentru un sir de numere ntregi de dimensiune n, nu neap arat distincte, memorate cu ajutorul unui vector (a) scriet i o funct ie care prime ste ca parametru adresa sirului, dimensiunea si pozit ia unui element si returneaz a rangul acestuia; (b) folosind not iunea de rang, g asit i mediana sirului (elementul care s-ar aa la mijloc dac a sirul ar sortat cresc ator).

Recursivitate

Rezolvat i recursiv urm atoarele probleme. 4. (5 pcte) Din num arul 4 se poate obt ine orice num ar natural n prin aplicarea urm atoarelor operat ii: - se adaug a la sf ar sit cifra 4; - se adaug a la sf ar sit cifra 0; - dac a num arul este par, se mparte la 2. S a se scrie un program care produce un sir de numere construit conform regulilor precedente, sir n care primul num ar este 4 iar ultimul este n.

5. (5 pcte) Metoda coardei. Fie o funct ie f : [a, b] I R de dou a ori derivabil a pe [a, b] av and urm atoarele propriet a ti: - f (a)f (b) < 0; - f (x)f (x) = 0, oricare ar x [a, b]; - f (a)f (a) < 0.
xn1 b) , oricare ar n I N converge strict Atunci sirul x0 = a, xn = xn1 f (xn1 ) f (( xn1 )f (b) cresc ator la unica solut ie a ecuat iei f (x) = 0.

Pentru o funct ie f cu propriet a tile de mai sus s a se calculeze o aproximat ie a solut iei ecuat iei f (x) = 0 cu o eroare > 0. Funct ia f si intervalul [a, b] vor alese de c atre student. Eroarea va introdus a de utilizator (de obicei mai mic a dec at 104 ). Indicat ie. Se creeaz a o funct ie care prime ste ca parametru un num ar real x si returneaz a valoarea real a f (x); la ecare pas se veric a dac a |f (xn )| < , caz n care xn reprezint a aproximat ia solut iei; n caz contrar se calculeaz a urm atorul element din sir si se continu a (recursiv). Exemple de funct ii care veric a toate condit iile de mai sus f : [1, 3] I R; f (x) = x3 8, f : [1, 1] I R; f (x) = ex 1, unde e 2, 718281.

Tehnici de programare

6. (10 pcte) Fiind dat i doi vectori x si y de dimensiune n s a se g aseasc a o permutare a lui y astfel nc at produsul lor scalar s a e minim posibil. 7. (10 pcte) Un profesor dore ste s a mpart a m proiecte celor n elevi ai unei grupe (m n) astfel nc at nici un proiect s a nu r am an a nealocat. Un proiect poate realizat de mai mult i elevi. S a se genereze toate posibilit a tile de a le mp art i. Observat ie. Problema aceasta este echivalent a cu problema de a genera toate funct iile surjective f : {1, 2, . . . , n} {1, 2, . . . , m}. 8. (20 pcte) Se consider a un sir de piese de domino. Fiecare pies a poate rotit a n jurul centrului s au cu 180 . S a se determine sub sirul de piese de lungime maxim a n care oricare dou a piese al aturate au nscrise acela si num ar: al doilea de pe prima pies a coincide cu primul num ar de pe cea de-a doua.

Liste, Stive si Cozi

Se accept a at at implement ari statice, c at si dinamice, ns a pentru cele din urm a se adaug a 5 puncte la ecare problem a. 9. (10 pcte) Implementat i funct ii corespunz atoare lucrului cu liste simplu nl ant uite pentru a permite utilizatorului s a manipuleze o list a init ial vid a folosind meniul de mai jos: 1. Adaug a element la nceputul listei 2. Adaug a element la sf ar situl listei 3. S terge primul element al listei 4. S terge ultimul element al listei 5. A seaz a cont inutul listei. 10. (10 pcte) Implementat i funct ii corespunz atoare lucrului cu stive/cozi pentru a permite utilizatorului s a manipuleze o stiv a/coad a init ial vid a folosind meniul de mai jos: 1. Adaug a element (push) 2. S terge element (pop) 3. A seaz a cont inutul stivei/cozii. 11. (5 pcte) Se cite ste de la tastatur a o expresie aritmetic a cu paranteze rotunde. S a se verice dac a parantezele sunt nchise corect folosind o stiv a. 12. (10 pcte) Fie un labirint reprezentat cu ajutorul unei matrice de ordin n. Spat iile libere, pe unde se poate trece, sunt marcate cu 0, iar cele blocate cu 1. Se dore ste g asirea celei mai scurte c ai de la punctul de plecare, marcat cu 1, la punctul de sosire, marcat cu 2. Exemplu de labirint pentru n = 4 1 0 0 1 0 1 1 2 0 0 1 0 0 0 0 0 Indicat ie. Se adaug a ntr-o coad a pozit ia de plecare; c at timp nu s-a ajuns la punctul de sosire se extrage un element din coad a si se adaug a toate celulele adiacente cu acesta prin care se poate trece; noile celule ad augate sunt marcate cu valoarea incrementat aa celulei extrase. Matricea din exemplu devine: 1 2 3 1 2 1 1 2 3 4 1 8 4 5 6 7 si cel mai scurt drum este de dimensiune 8.

13. (15 pcte) Problema lui Josephus. Folosind o list a simplu nl ant uit a circular a rezolvat i urm atoa-rea problem a: n persoane sunt a sezate n cerc ( si numerotate de la 0 la n 1); pornind de la persoana cu num arul 0, la ecare pas, a k -a persoan a este executat a; ultima persoan a care r am ane este grat iat a; a sat i ordinea n care au loc execut iile.

Arbori binari de c autare

Se accept a at at implement ari statice, c at si dinamice, ns a pentru cele din urm a se adaug a 10 puncte la ecare problem a. 14. (10 pcte) Scriet i un algoritm care inverseaz a un arbore binar de c autare. Un arbore binar de c autare inversat este un arbore binar n care orice nod are cheia mai mare dec at cheile nodurilor din subarborele drept si mai mic a dec at cheile nodurilor din subarborele st ang. Forma arborelui inversat va simetric a fat a de arborele original. 15. (5 pcte) S a se scrie o funct ie care veric a dac a un nod al unui arbore binar oarecare este r ad acina unui arbore binar de c autare.

Grafuri

16. (5 pcte) Determinat i dac a un graf neorientat reprezentat cu ajutorul unei matrice de adiacent a este complet. Un graf neorientat este complet dac a oricare dou a v arfuri ale acestuia sunt adiacente. 17. (5 pcte) Realizat i intersect ia si reuniunea a dou a grafuri reprezentate prin matricele lor de adiacent a. Grafurile nu au neap arat aceea si dimensiune, dar v arfurile vor numerotate n ambele cazuri de la 0. 18. (15 pcte) Implementat i algoritmul Reverse-Delete care construie ste un arbore part ial de cost minim pornind de la un graf ponderat conex. (vezi http://en.wikipedia.org/wiki/Reverse-delete_algorithm)

Coduri Human

Codurile Human reprezint a o modalitate optim a de arhivare a unui text dat. Ideea de baz a este c a ecare caracter va nlocuit cu un cod format din bit i de 0 si 1 astfel nc at un caracter cu frecvent a mare de aparit ie s a aib a un cod c at mai mic posibil fat a de unul cu frecvent a mic a. Codurile asociate sunt coduri cu prex (nici un cod valid nu reprezint a prexul unui alt cod valid). In codarea Human textul dat este analizat pentru a se calcula frecvent a de aparit ie a ec arui caracter. Se construie ste apoi un arbore binar format din noduri frunze (asociate caracterelor) si noduri interne, astfel: se porne ste

cu n noduri libere (frunze), unde n reprezint a num arul de caractere distincte din text; ecare nod cont ine un caracter si frecvent a sa de aparit ie; se creeaz a apoi un nod nou av and ca i 2 noduri cu frecvent a minim a de aparit ie; se continu a analog cu mult imea de noduri din care s-au eliminat cele dou a noduri folosite si la care s-a ad augat noul nod creat; procesul se ncheie atunci c and se r am ane cu un singur nod, acesta devenind si r ad acina unui arbore binar Human. Codul unui caracter se calculeaz a parcurg and lant ul de la r ad acin a la nodul frunz a care l cont ine si consider and 0 dac a se merge pe direct ia ului st ang, respectiv 1 pentru ul drept. Pentru a se dezarhiva un text codat Human trebuie s a se cunoasc a codurile caracterelor (date de arborele Human). Exemplu 1. Pentru textul this is an example of a human tree se calculeaz a urm atoarele frecvent e de aparit ie si se creeaz a arborele Human de mai jos (vezi http: // commons. wikimedia. org/ wiki/ File: Huffman_ tree. svg )

Textul este astfel codat si rezult a arhivarea 011010101000101111110001011111010001 01110001001001001111001111001000111001101101111010111101000111110111010111 -

0100010111011011000000000 pe 135 de bit i, reprezent and o compresie de 53% fat a de num arul de 288 de bit i folosit i pentru memorarea codurilor ASCII corespunz atoare caracterelor din text (36 de caractere 8 bit i de caracter). 19. (45 pcte) Fi sierul date.in cont ine un text format numai din literele mici ale alfabetului latin. (a) Calculat i frecvent a de aparit ie a ec arui caracter in text. (b) Construit i arborele Human corespunz ator textului dat. (c) Calculat i codul ec arui caracter ( sirul de valori 0 si 1 va memorat cu ajutorul unui sir de ntregi, nu de bit i). (d) Arhivat i textul. (e) Dezarhivat i un text codat Human cunosc and arborele Human asociat.

Total 200 puncte.