1. Discutarea unor teme din curs (10-15 minute)

  • Declararea tablourilor
  • Exemple cu vectori și matrice
  • Definirea funcțiilor
  • Exemple de funcții care returnează o valoare, exemple de funcții de tip void
  • Parametri transmiși prin valoare / referință
  • Variabile locale vs variabile globale vs parametri formali
  • Tablouri şi pointeri
  • Legătura pointerilor cu tablourile, aritmetica pointerilor
  • Șiruri de caractere
  • Exemple

2. Exerciții (85-90 minute)

Atenție! Pentru fiecare din următoarele funcții se va realiza și un program de test. Generați date de intrare pentru teste, așa încât să fie cât mai diverse (valori minime, valori maxime, valori având anumite particularități etc.).

2.1. Exerciții cu date simple

  1. (0,20) Fie următoarele structuri de date pentru a reprezenta un punct, respectiv un segment de dreaptă, în spațiul euclidian:
    struct punct { float x; float y; };
    struct segment { punct A; punct B; };
    Scrieți o funcție punctMijloc(segment S); care returnează coordonatele mijlocului unui segment S.
  2. (0.20p) Scrieti o funcție iterativă, care pentru un număr n returnează al n-lea numar din șirul lui Fibonnaci (fib(0)=0,fib(1)=1,fib(n)=fib(n-1)+fib(n-2), pt. n>1)
    Ex: fib(3) = fib(2) + fib(1) = fib(1) + fib(0) + 1 = 1 + 0 + 1 = 2
    unsigned int fibonnaci_it(int index);
  3. (0.20p) Scrieti o funcție iterativă, care pentru un număr n returnează suma primilor n numere din șirul lui Fibonnaci (fib(0)=0,fib(1)=1,fib(n)=fib(n-1)+fib(n-2), pt. n>1)
    Ex: sumafib(3) = fib(0) + fib(1) + fib(2) + fib(3) = 0 + 1 + 1 + 2=4
    unsigned int sumafib(int index);
  4. (0.20p) Scrieti o funcție recursivă care pentru un număr n returnează al n-lea număr din șirul lui Fibonnaci (fib(0)=0,fib(1)=1,fib(n)=fib(n-1)+fib(n-2), pt. n>1)
    Ex: fib(3) = fib(2) + fib(1) = fib(1) + fib(0) + 1 = 1 + 0 + 1 = 2
    unsigned int fibonnaci_rec(int index);
  5. (0,20p) Scrieti o functie recursiva care calculeaza factorialul unui numar natural n. long factorial_rec(long n)
  6. (0.20p) Scrieti o funcție care testează dacă un an este bisect.
    bool isLeapYear(unsigned short year);
  7. (0.20p) Scrieti o funcție care testează dacă un număr este divizibil prin suma primei si a ultimei sale cifre. De exemplu, numarul 192 este divizibil prin 3 (1+2).
    bool esteDivizibil(unsigned long numar);
  8. (0,30p) Scrieti o functie recursiva in C++, pentru a implementa functia lui Ackermann, definita astfelac:NxN->N
    ac(m,n)=n+1, daca m=0; ac(m,n)=ac(m-1,1), daca n=0 si ac(m,n)=ac(m-1,ac(m,n-1)), daca m,n>0
  9. (0.25p) Scrieți o funcție care verifică dacă un număr este palindrom. Un număr este palindrom dacă citit de la dreapta la stanga este egal cu numărul citit de la stânga la dreapta. Ex: 13231 este palindrom dar 12331 nu este palindrom
    bool isPalindrom(unsigned long long number); Puteti scrie si o functie auxiliara, unsigned long long oglindit(unsigned long long number); care detemina oglinditul unui numar natural.
  10. (0.40p) Scrieți o funcție care, pentru un număr natural, calculează suma cifrelor reprezentării lui binare. unsigned int sumBinaryFigure(unsigned long long number);
  11. (0.50p) Spunem că un număr natural este perfect dacă este egal cu suma divizorilor săi strict mai mici decât el. Scrieți o funcție care returnează suma celor mai mari două numere perfecte mai mici decat un număr (number >= 30) dat.
    unsigned long perfectNumbers(unsigned int number);

2.2. Exerciții cu vectori

  1. (0,20p) Scrieți o funcție iterativă care calculează suma elementelor negative dintr-un vector de numere întregi.
  2. (0,40p) Fie definit un vector de numere intregi ca o structura de forma
    struct vector { unsigned int nrElemente; int element[200]; };
    Scrieți o funcție care, pentru un vector dat testeaza daca el este ordonat crescator: bool esteOrdonat(vector v);
  3. (0.75p) Scrieți o funcție care pentru un interval închis dat [left, right] returnează numărul de numere ce au număr maxim de divizori primi.
    Exemplu: Pentru  [30, 45] numerele cu număr maxim de divizori primi = 30,42 (au cate 3 divizori primi, nici un alt număr din interval nu are mai mulți   divizori primi) iar functia va returna 2.
    unsigned short primeDivisors(unsigned int left, unsigned int right);
  4. (1,20p) Două numere naturale impare consecutive și prime se numesc numere prime gemene. Scrieți o funcție care determină primele count perechi de numere prime gemene mai mari decât un lowerBound dat.
    Exemplu: Pentru count = 1 și lowerBound = 2 funcția va returna o matrice cu un rând (un rezultat) și 2 coloane (pereche de numere – două numere): 3 5
    matrix primeTwins(unsigned int count, unsigned int lowerBound);
  5. (1,30p) Se consideră un șir de n intervale închise întregi. Două intervale consecutive în șir care au intersecția nevidă se reunesc și se înlocuiesc în șir cu intervalul reuniune. Operația se repetă până când nu mai sunt în șir două intervale consecutive cu intersecția nevidă. Scrieti o functie care să determine câte intervale există în șir după realizarea acestor operații.
  6. Fie următoarele definiții pentru multimi de numere intregi;
    #define MAX_MULTIME 100
    struct multime { unsigned int nrElemente; int element[MAX_MULTIME]; }Scrieți funcțiile următoare:
    bool esteMultime(multime M), care testează dacă M este într-adevăr o mulțime (elementele unei mulțimi nu trebuie să se repete) (0,30p)
    bool apartine(int E, multime M), care testează dacă un element E aparține mulțimii M; (0,30p)
    void reuniune(multime A, multime B, multime& C), care reuneste in C multimile A si B; (0,50p)
    void intersectie(multime A, multime B, multime& C), care intersecteaza multimile A si B si obtine multimea C; (0,50p)
    void diferenta(multime A, multime B, multime& C), care pune in C diferenta A\B; (0,50p)
    void diferentaSimetrica(multime A, multime B, multime& C), care pune in C diferenta simetrica a multimilor A si B, adica reuniunea A\B U B\A; (0,20p)

2.3. Exerciții cu tablouri stocate ca structuri

Se considera urmatoarele declaratii:

#define MAX_ARRAY_LENGTH 100 
#define MAX_ARRAY_LENGTH_LONG 1000 
struct vector { 
  unsigned int length; 
  int values[MAX_ARRAY_LENGTH]; }; 
struct matrix { 
  unsigned int lines; 
  unsigned int columns; 
  unsigned int values[MAX_ARRAY_LENGTH][MAX_ARRAY_LENGTH]; }; 
struct smaze { 
  char maze[MAX_ARRAY_LENGTH_LONG][MAX_ARRAY_LENGTH_LONG]; 
  unsigned int noOfRows; 
  int noOfColumns; 
  unsigned int rowOfDeparture; 
  unsigned int columnOfDeparture; 
  unsigned int rowOfExit; 
  unsigned int columnOfExit; };
  1. (0.50p) Scrieți o funcție care primește doi vectori ca parametru și returnează 0 dacă sunt egali, 1 daca primul este inclus în al doilea, 2 dacă al doilea este inclus în primul și 3 altfel.
    Ex: Pentru [1,2,3] si [3,1,2] funcția returnează 0;
    Pentru [1,2,3] si [3,2] funcția returnează 2;
    Pentru [1,2,3] si [3,2,4] funcția returnează 3.
    unsigned char checkVectorInclude(vector vecOne, vector vecTwo);
  2. (0.60p) Scrieți o funcție care pentru un vector de  lungime n și un număr a verifică dacă elementele din vector sunt primele n numere din sirul lui Fibonnaci începând cu numărul a (>=2).
    Ex: Pentru vectorul [3,5,2] de lungime n=3 și numarul a=2 functia va returna true;
    Pentru vectorul de lungime 3 [3,4,2] si numarul a=2 functia va returna false.
    bool isPartOfFibonnaci(vector vec, unsigned int startingNumber);
  3. (0.70p) Scrieți o funcție care primește ca parametri un vector de n numere  și un vector de n-1 caractere reprezentând operații pe biți și returnează rezultatul aplicării operațiilor pe numere. Operațiile sunt aplicate astfel: prima operație se aplică pe primele două numere, a doua operație se aplică pe rezultatul primei operații și al treilea număr, a treia operație pe rezultatul operației a doua și al patrulea număr ș.a.m.d.
    unsigned long bitOperations(long numbers[], char operations[], unsigned int n);
  4. (0.60p) Se citește un vector x cu n numere întregi. Sa se reașeze elementele din x astfel încât mai întâi să apară elementele negative, apoi cele pozitive, păstrând ordinea atât a elementelor negative, cât și a celor pozitive (O(n)).
  5. (0,75p) Se citește un vector a cu n numere întregi, n<1001. Să se calculeze s = suma maximă care poate fi obținută dintr-o secvență de elemente de pe poziții consecutive din vector, in O(n).
    Exemplu: n=9, a=[-2,1,-3,4,-1,2,1,-5,4]. Rezultatul va fi s=6.
  6. (1,00p) Scrieți o funcție care pentru un vector de lungime n verifică dacă elementele din vector sunt primele n numere din șirul lui Fibonnaci în ordinea apariției lor in șir. Ex: Pentru vectorul [0,1,1,2,3,5,8,13,21] funcția va returna true; Pentru vectorul [0,1,1,3,2,4] si [0,1,1,2,4] funcția va returna false.
    bool areOrderedFibonnaci(vector v);(0.50p)
  7. Scrieți o funcție care pentru un vector de lungime n verifică dacă elementele din vector sunt primele n numere din șirul lui Fibonnaci în ordinea apariției lor in șir, in ordine inversa. Ex: Pentru vectorul [21,13,8,5,3,2,1,1,0] funcția va returna true; Pentru vectorul [0,1,1,3,2,4] si [0,1,1,2,4] funcția va returna false.
    bool areReverseOrderedFibonnaci(vector v);
  8. Scrieți o funcție pentru următoarea situație. Se consideră a) un vector de n numere a căror reprezentare binară reprezintă mulțimi de numere din intervalul [0,63]. De exemplu, codificarea binară 00100011 (pe 8 biți), corespunzătoare numărului zecimal 35, reprezintă mulțimea {0,1,5} (biții setați pe 1). b) un vector de n-1 caractere, fiecare caracter reprezentând o operatie între mulțimi: ’U’ = reuniune, ’A’ = intersecție, ’\’ = A – B, ’/’ = B – A și returnează numărul obținut prin aplicarea operațiilor pe numerele primite ca parametru astfel:
    • Prima operație se aplică pe primele două numere
    • A doua operație se aplică pe rezultatul operației anterioare și al treilea numar
    • A treia operație se aplică pe rezultatul operației anteriore și al patrulea număr
    • ș.a.md.

    Ex: Pentru sets=[1,2,3] și operations=[’U’,’\’] funcția va calcula 001(1) reunit cu 010(2) și va avea rezultatul 011 iar 011 minus 011(3) va avea rezultatul 000(0) si funcția va returna 0.
    unsigned long setOperations(long sets[], char operations[], unsigned int n);

  9. (0.70p) Scrieți o funcție care primește ca parametri o matrice patratică n*n, un număr de rotații stânga și un număr de rotații dreapta și returnează matricea cu rotații stânga, respectiv dreapta în funcție de numerele primite ca parametri.
    matrix rotate(matrix mat, unsigned int rotLeft, unsigned int rotRight);
  10. (0,90p) Scrieți o funcție care primește ca parametru o matrice cu m linii (rânduri) și n coloane și verifică daca matricea conține primele (m*n) elemente din sirul lui Fibonnaci in spirală, pornind din colțul stânga sus.
    Ex: Pentru [0,1] [2,1] și [0, 1, 1] [13,21,2] [8, 5, 3] returnează true; Pentru [0,1] [1,2] returnează false.
    bool fibonnaciSpirale(matrix);
  11. (0,75p) Scrieți o funcție care primește o matrice de 1 și 0, și returnează matricea modificată astfel: dacă într-o celulă se găsește 0, toată linia și coloana respectivă vor fi umplute cu 0. Ex: Pentru matricea [1, 0, 1] [1, 1, 1] [1, 1, 1] funcția va returna [0, 0, 0] [1, 0, 1] [1, 0, 1]
    void transformMatrix(matrix mat);
  12. (1,00p) Scrieți o funcție care primește un labirint sub forma unei matrice, poziția celulei de plecare și poziția celulei de iesire și returnează lungimea drumului minim de la plecare la ieșire. Fiecare celulă din matrice va avea va avea valoare 1 (perete) sau 0 (drum).
    unsigned int minRouteLength(smaze labirint);
  13. (0.20p fiecare) Scrieti cate o functie pentru a calcula:
    • suma elementelor de sub diagonala secundara a unei matrice patratice;
    • suma elementelor de pe o coloana oarecare a matricei;
    • suma elemtelor dintr-o matrice, cu exceptia unei liniilor si coloanelor de pe margine.
  14. (0.50p) Scrieți o funcție care pentru un vector și o matrice primite ca parametri verifică dacă vectorul se regasește ca linie și/sau coloană în matrice.
    bool checkIsIn(vector vec, matrix mat);

2.4. Exercitii cu siruri de caractere

  1. (0.25p fiecare) Exercitii cu siruri de caractere (de exemplu rescrierea funcțiilor uzuale din <string.h>)
  2. (1,00p) Scrieți o funcție care desparte un cuvânt în limba română în silabe, aplicând regulile de la http://www.limba-romana.net/lectie/Reguli-de-despartire-a-cuvintelor-in-silabe/72/
  3. (0,50p) Scrieți o funcție care primește la intrare un șir de caractere folosind taguri HTML pentru bold, italic și underline și le elimină.
  4. (1,50p) Scrieți o funcție care codifică un număr natural între 0 și 100000000 într-un șir de caractere, reprezentând numărul scris cu litere, în limba română. De exemplu, pentru numărul 70054 rezultatul funcției va fi „saptezecidemiicincizecisipatru”.
  5. (1,50p) Scrieți o funcție care primeste ca argumente doua siruri de caractere, reprezentand numere naturale<=30 in limba romana, scrise cu litere si returneaza o structura ce contine:
    1. suma lor;
    2. diferenta lor
    3. produsul lor
    4. raportul lor, daca acesta poate fi calculat;
      exprimat sub forma de litere, inclusiv cu virgula, daca asa iese rezultatul.

2.5. Exerciții simple cu vectori

    1. (0,05p fiecare)
      Scrieti functii cu numele f1, f2, f3 si definite corespunzator (de ex. int f1(int x[100], int n) {…}) pentru a calcula urmatoarele expresii:
      a) f1= 1*x[1]+2*x[2]+3*x[3]+…+n*x[n];
      b) f2 = 1*x[n]+2*x[n-1]+3*x[n-2]+…+2*x[n-1]+1*x[n];
      c) f3 = x[1]+x[1]*x[2]+x[1]*x[2]*x[3]+…+x[1]*x[2]*…*x[n];
    2. (0,05p fiecare) Scrieti functii cu numele f4, f5, f6, si definite corespunzator (de ex. int f4(int x[100], int y[100], int n) {…} )pentru a calcula urmatoarele expresii:
      a) f4= min(x[1],y[1])+min(x[2],y[2])+…+min(x[n],y[n]);
      b) f5 = x[1]/y[n]-x[2]/y[n-1]+x[3]/y[n-2]-…+…-…….. x[n]/y[1];
      c) f6 = s(x[1]+y[1])+s(x[2]+y[2])+…+s(x[n]+y[n]), unde s(a) este suma cifrelor numarului a;
    3. (0,05 fiecare) Scrieti functii cu numele f7, f8, f9 si definite corespunzator (de ex. void f7(int x[100], int y[100], int z[100], int n) {…} )pentru a calcula valorile vectorului z in functie de valorile vectorilor x si y, astfel:
      a) z[1]= min(x[1],y[1]) si z[2]=min(x[2],y[2]) si … si z[n]=min(x[n],y[n]);
      b) z[1] =cmmdc(x[1],y[n]) si z[2]=cmmdc(x[2],y[n-1]) si … si z[n]=cmmdc(x[n],y[1]), unde cmmdc(a,b) este cel mai mare divizor comun al numerelor a si b;
      c) z[1] = uc(x[1]+y[1]), z[2]=uc(x[2]+y[2]),…, z[n]=uc(x[n],y[n]), unde uc(a) este ultima cifra a numarului a;
    4. (0,05 fiecare) Scrieti functii cu numele f10, f11, f12 si definite corespunzator (de ex. bool f10(int x[100], int y[100], int z[100], int n) {…} ) pentru a testa daca valorile vectorului z verifica anumite conditii, in functie de valorile vectorilor x si y, astfel:
      a) z[1]==x[1]*y[1] si z[2]==x[2]*y[2] si … si z[n]==x[n]*y[n];
      b) z[1]==cmmmc(x[1]*2,y[n]*3) si z[2]=cmmmc(x[2]*2,y[n-1]*3) si … si z[n]==cmmmc(x[n]*2,y[1]*3), unde cmmmc(a,b) este cel mai mic multiplu comun al numerelor a si b;
      c) z[1]==pc(x[1]+y[1]*1) si z[2]==pc(x[2]+y[2]*2) si … si z[n]==pc(x[n]+y[n]*n), unde pc(a) este prima cifra a numarului a;
    5. (0,05 fiecare) Scrieti functii cu numele f13, f14, f15 si definite corespunzator (de ex. int f15(int x[100], int n) {…} ) pentru a returna valoarea k1, k2, k3, care reprezinta:
      a) k1 = 1, daca toate elementele din x sunt identice intre ele, respectiv 0 in caz contrar;
      b) k2 = numarul de perechi de elemente prime intre ele, aflate pe pozitii egal distantate de centrul vectorului;
      c) k3 = numarul de aparitii ale valorii x[1] in vectorul x;
    6. (0,05 fiecare) Scrieti functii cu numele f16, f17, f18 si definite corespunzator (de ex. void f16(int x[100], int n) {…} ) pentru a modifica vectorul x, astfel incat elementele acestuia sa ajunga in ordinea urmatoare:
      a) x[n], x[n-1], x[n-2], …, x[3], x[2], x[1];
      b) x[2], x[1], x[4], x[3], …., x[n], x[n-1]; (aici n este par)
      c) x[2], x[3], x[4], …, x[n], x[1];
    7. (0,05 fiecare) Scrieti functii cu numele f19, f20, f21 si definite corespunzator (de ex. void f19(int x[100], int n) {…} ) pentru a modifica vectorul x, astfel incat elementele acestuia sa ajunga in ordinea urmatoare (sau sa aiba valorile urmatoare):
      a) x[n],x[1],x[2],…,x[n-1];
      b) x[1], 0, x[3], 0, x[5], 0, …;
      c) 1*x[1], 2*x[2], 3*x[3], …, n*x[n];
    8. (0,05 fiecare) Scrieti functii cu numele f22, f23, f24 si definite corespunzator (de ex. void f23(int x[100], int n) {…} ) pentru a modifica vectorul x, astfel incat elementele acestuia sa ajunga in ordinea urmatoare (sau sa abia valorile urmatoare):
      a) x[1], -x[2], x[3], -x[4], …, ;
      b) 0, x[2], x[3], 0, x[5], x[6], 0, x[8], x[9], …;
      c) n*x[1], (n-1)*x[2], (n-2)*x[3], …, 1*x[n];
    9. (0,05 fiecare) Scrieti functii cu numele f25, f26, f27 si definite corespunzator (de ex. int f25(int x[100], int n) {…} ) pentru a calcula valoarea k4, k5, k6, care reprezinta:
      a) k4 = numarul de elemente din x care sunt egale cu suma vecinilor sai;
      b) k5 = numarul de perechi de elemente prime intre ele, aflate pe pozitii consecutive in vector;
      c) k6 = numarul de elemente negative din vector, aflate pe pozitii divizibile prin 3;
    10. (0,05 fiecare) Scrieti functii cu numele f28, f29, f30 si definite corespunzator (de ex. int f28(int x[100], int n) {…} ) pentru a calcula valoarea k7, k8, k9, care reprezinta:
      a) k7 = numarul de elemente din x care sunt mai mari decat media aritmetica a elementelor vectorului;
      b) k8 = numarul de elemente din vector care sunt egale cu oglinditele lor;
      c) k9 = numarul de elemente pozitive si pare din vector, aflate pe pozitii impare;