1. Discussion based on course subjects (40 minutes)

  1. data types
  2. data types conversions
  3. operators for integer/real numbers: priority and associativity
  4. special operators: comma, ? :, sizeof()

2. Exercises

  1. (0,60p) Implement an approximate calculation for PI, using the following reccurence formulas, defined below:
    Click here for solution. Other solution is here: https://www.wikihow.com/Calculate-Pi -> Calculate Pi Using an Infinite Series
  2. (1,5p) Scrieţi un program eficient, în care să folosiţi un ciclu fără număr cunoscut de paşi, pentru a calcula valorile funcţiilor e^x, sin(x) şi cos(x), folosind formulele de mai jos (0,5p pentru fiecare formulă).
    Click aici pentru solutii.
  3. (1,00p) Definiţi o structură de date pentru a stoca informaţiile despre un pache de 52 cărţi (fără jokeri), având numerele 2, 3, …, 10, precum şi literele A (as), J (valet), Q (damă), K (rege), în cele 4 simboluri (treflă, caro, cupă şi pică) (0,25p). Generaţi tot pachetul de cărţi (0,25p), apoi scrieţi secvenţe de cod pentru a amesteca aceste cărţi (0,50p). Pentru a genera un număr întreg aleator, între 0 şi t-1 se poate apela funcţia rand astfel: rand()%t. Funcţia se găseşte în stdlib.h.
    Click aici pentru solutie.
  4. (0,60p) Se consideră funcția f:R->R, continuă pe intervalul [a,b]. Dandu-se valorile reale a si b (a<b), precum si functia f, sa se calculeze o aproximare buna pentru integrala de la a la b din f(x) dx.
    Atentie! Functia se va scrie ca parte componenta din program, sub forma float f(float x) { ….. return …; }, de exemplu float f(float x) { return x*x-sin(x); }
    Indicație: Se poate folosi metoda dreptunghiurilor medii, pentru aproximarea integralei. Vezi: http://www.didactic.ro/materiale-didactice/13052_formula-dreptunghiurilor-pentru-calculul-aproximativ-al-integralei
  5. (0,50p) Se consideră funcția f:R->R, continuă pe intervalul [a,b], cu f(a)*f(b)<0. Să se scrie un program C++, care să determine o soluție a ecuației f(x)=0, folosind metoda următoare:
    Dacă a<b, se calculează m=(a+b)/2, apoi f(m). Dacă f(m) este foarte apropiat de zero, atunci m este o soluție a ecuației. Dacă nu, atunci se verifică dacă graficul funcției ar intersecta cel puțin o dată axa Ox, pe intervalul [a,m], respectiv [m,b] și se rezolvă problema doar pe acel interval.
    Programul va avea scris corpul functiei ca parte integranta din program, de exemplu float f(float x) { return x*x-3; }, de la tastatura citindu-se doar a si b (a<b a.i f(a)*f(b)<0).
    Click aici pentru solutie
  6. (0,30p) Să se scrie un program C++ care să determine rădăcina pătrată a numărului real pozitiv x, ca limită a șirului de numere an, definit astfel: a0=1, an=1/2*(an-1+x/an-1). Se pot calcula repetitiv termeni ai șirului, până când diferența dintre ultimii doi este destul de mică. Se va evita folosirea vectorilor sau a functiilor recursive.
    Click aici pentru solutie
  7. (0,60p) In jocul Patratelor alunecatoare (glisante), cei doi jucatori joaca cu piesele albastre, respectiv versi, amplasate initial pe tabla alternativ, ca in figura urmatoare. In mijloc este spatiu liber.http://ro.goobix.com/jocuri-online/patratele-alunecatoare/

    Jocul are următoarele reguli:

    • fiecare jucător realizează alternativ câte o mutare, cu propriile piese (albastru sau verde), începând cu jucatorul detinand piesele albastre;
    • o mutare constă în interschimbarea pătratului liber (alb) cu unul din pătratele alăturate
    • pentru a fi interschimbate, pătratele trebuie să aibă o latură în comun
    • jucătorul care nu mai poate muta pierde jocul

    (0,20p) Definiti o structura de date adecvata pentru a reprezenta o situatie din acest joc, stocand dimensiunea tablei de joc (numarul de linii = numarul de coloane), locurile unde sunt amplasate piesele celor doi jucatori, locul spatiului liber (alb), precum si cine urmeaza sa mute. (0,40p)Scrieti o secventa de program sau o functie care testeaza daca unul dintre jucatori a castigat.
    Click aici pentru solutie

  8. (0,70p) Definiți un tip de date adecvat pentru reprezentarea unei situatii din jocul de șah, stocând date despre:
    1. numele jucătorilor cu piesele albe, respectiv negre;
    2. cine este jucătorul care urmează să mute;
    3. așezarea curentă a pieselor de ambele culori, pe tabla de șah.
      Cu această structură definită, scrieți o secvență de cod pentru a plasa pe tabla de șah toate piesele așa cum sunt ele la începutul jocului de șah.
      Click aici pentru solutie.
  9. (1,20p) Presupunem că puteți lucra în modul grafic, pe un ecran cu latime*inaltime pixeli în care coordonatele colțului stânga sus sunt (0, 0), iar ale colțului dreapta-jos sunt (latime-1, inaltime-1). În acest mod grafic, dispuneți de următoarele primitive grafice
    • o funcție grafică void setcolor(unsigned int c), care stabilește culoarea pentru a desena următoarele linii, până la schimbarea culorii de un alt apel al acestei funcții (inițial se consideră c=0, implicit); c este un cod de culoare, care corespunde unei valori între 0 și 15, de exemplu 0=negru, 1=albastru, 2=roșu etc.
    • o funcție grafică void setwidth(unsigned int g), care stabilește grosimea (1<=g<=10, implicit g=1) de desenare a următoarelor linii, până la un nou apel al acestei funcții;
    • o funcție grafică void line(unsigned int x1, unsigned int y1, unsingned int x2, unsigned int y2) care trasează o linie între punctul de coordonate (x1, y1) și cel de coordonate (x2, y2), în culoarea curentă, de grosimea curentă;
    • o funcție void setfillcolor(unsigned int c), care stabilește culoarea de umplere pentru următoarele apeluri ale funcției fill de mai jos; c este implicit 0 (negru), dar poate fi orice valoarea 0<=c<=15;
    • o funcție void fill(unsigned int x1, unsigned int x2, unsigned int c), care colorează (prin umplere) în culoarea stabilită de funcția setfillcolor, conturul închis, mărginit de o linie poligonală închisă, având culoarea c. Colorarea începe în punctul de coordonate (x1, y1), care se presupune a fi în interiorul acelei linii poligonale.
      (0,30p) Definiți o structură de date adecvată pentru a reprezenta o stea regulată cu un număr de colțuri (cel puțin 3), cu marginea de o anumită culoare și grosime, cu o anumită culoare în interior, cu o anumită mărime și o anumită „deschidere” a colțurilor, cu o anumită amplasare sub un anumit unghi față de orizontală a primului colț. Se pot folosi funcțiile trigonometrice sin și cos, din math.h.
      (0,90p) Scrieți o funcție care să deseneze o asemenea stea, oarecare, amplasată oriunde și oricum, de culoare oarecare etc.
      Click aici pentru solutie.
  10. (0.40p) Să se definească un tip de date pentru reprezentarea numerelor complexe şi să se scrie secvențe de cod sau funcţii pentru diferite operaţii cu astfel de numere: adunare, scădere, înmulțire și împărțire. Click aici pentru solutie.
    Click aici pentru o alta solutie. (explicatii la pagina 89 din lucrarea de aici.)
  11. (0,30p) Definiți un tip de date adecvat pentru reprezentarea unei date calendaristice, apoi scrieți o secvență de cod sau o funcție pentru determinarea zilei următoare unei zile date.
  12. (0.75p) Definiți o structură de date pentru a reprezenta datele personale ale unor concurenți la un concurs (nume, prenume, vârstă, sex), precum și punctajul obținut de fiecare concurent. Scrieți un program C++ care să citească aceste date, apoi, folosind un algoritm de sortare, ordonați descrescător persoanele de sex masculin cu vârste între 16 și 20 ani, în funcţie de punctaj şi afișați lista ordonată.
  13. (0.50p) Definiți o structură de date corespunzătoare pentru a memora simpatiile de diferite grade dintre cele NrF fete și NrB băieți dintr-o grupă de studenți, știind că avem relații de simpatie atât de la fete pentru băieți, cât și de la băieți pentru fete. Scrieți un algoritm pentru a determina care este cea mai simpatizată fată din grupă, ca sumă a simpatiilor băieților. De asemenea, scrieți un algoritm pentru a determina care sunt băieții care nu sunt deloc simpatizați de această fată.
  14. (1,00p) Definiți o structură de date pentru jocul Snake, în care pe tablă (de culoare galbenă) se află șarpele (reprezentat de pătrățele verzi, cu excepția capului care este roșu), precum și diferite fructe (de culori roșu (1p) sau albastru (2p)), care pot fi mâncate de șarpe. Codificați printr-un câmp al structurii de date definite și direcția de deplasare a șarpelui. Scrieți o secvență de cod sau o funcție pentru a verifica dacă șarpele lăsat în pace, în situația curentă, ar urma să se mânânce pe sine, să iasă din tabla de joc sau să mânânce un fruct.
  15. (0,70p) Definiți o structură de date adecvată pentru a stoca datele despre codul numeric personal al unei persoane, apoi scrieți o secvență în C++ (o funcție) care să verifice dacă un anumit CNP ar putea fi corect. Informații despre CNP se găsesc la adresa: https://ro.wikipedia.org/wiki/Cod_numeric_personal
  16. (0.70p) Să se parcurgă o matrice cu n linii și m coloane sub formă de spirală și să se populeze celulele matricei cu primele nxm numere prime.
    Click aici pentru solutie.
  17. (1,00p) Să se parcurgă o matrice patratică în zig-zag, începand din colțul stânga sus, prin deplasări dreapta, apoi stânga-jos, apoi jos, apoi dreapta sus ș.a.m.d.
    Click aici pentru o solutie.
    O alta solutie este aici: https://www.codeproject.com/Tips/1116385/ZigZag-Algorithm-in-a-Grid
  18. (0.25p) Scrieţi o funcţie bitcount(n) care să contorizeze numărul de biţi pe 1 dintr-un argument întreg.
    Click aici pentru solutie.
  19. (0.5p) Scrieţi o funcţie getbits(x, p, n) care să returneze (cadrat la dreapta) câmpul de lungime n biţi al lui x, care începe la poziţia p. Click aici pentru solutie.
  20. (0,80p) Jocul Piticot constă în parcurgerea de n jucători (2<=n<=4) a unui traseu ce constă din m căsuţe consecutive,  numerotate de la 1 la n. Pionii celor n jucători au culori diferite şi încep să se deplaseze de la punctul de start, o căsuţă cu numărul 0. Scopul jocului este să se ajungă la ultima căsuţă. Pionii se deplasează pe rând, alternativ, în funcţie de valorile zarului, aşa cum pică la fiecare jucător (1..6). Există, pe traseu, anumite căsuţe (10%) unde, de îndată ce a ajuns acolo un pion, el sare automat către o altă căsuţă normală, fie ea înainte, fie înapoi. Există şi alte căsuţe (10%), unde un pion ajuns va trebui să stea o tură, precum şi căsuţe unde pionul poate să avanseze, jucătorul dând din nou cu zarul.
    Definiţi o structură de date pentru a stoca informaţiile menţionate mai sus pentru tabla de joc (0,50p), pentru poziţiile curente ale pionilor din joc (0,20p), precum şi pentru cine urmează să dea cu zarul în vederea deplasării (0,10p).
  21. (1,00p) Un student la informatică doreşte să îî facă un program de testare a culturii generale prietenei sale. El va genera un număr de minim 10 şi maxim 50 întrebări, fiecare din ele având una sau mai multe variante de răspuns, din 5 posibile. Definiţi o structură de date pentru stocarea unui asemenea test de cultură generală, cu tot cu răspunsurile corecte şi greşite (0,30p), precum şi răspunsurile date de prietena sa (0,20p). Ştiind că fiecare dintre întrebări la care s-a răspuns perfect corect primeşte acelaşi punctaj şi că punctajul maxim este 10, 1 punct fiind din oficiu, scrieţi o secvenţă de cod care să calculeze punctajul pe care l-a primit la test prietena studentului nostru, în funcţie de răspunsurile sale (0,50p).
  22. (0,60) Se considera o codificare a numerelor naturale, folosind baza 3, dar cu cifrele 0,1 si !. Cifra ! are valoarea -1, cifra 0 valoarea 0, iar cifra 1 valoarea 1. De exemplu, numarul 8=1*3^2+0*3^1+(-1)*3^0 se va codifica prin 10!, numarul 7=1*3^2+(-1)*3^1+1*3^0 se va codifica prin 1!1, iar numarul 17=1*3^3+(-1)*3^2+0*3^1+(-1)*3^0 se va codifica prin 1!0!. Scrieti secvente de cod (sau functii) care sa codifice din baza 10 in acest cod, respectiv sa decodifice din acest cod in baza 10 un numar natural oarecare n.