1. Prezentarea unor chestiuni administrative

1.1. De ce C++

  • Puternic, flexibil (conversii)
  • Structurat
  • Portabilitate (Windows, Apple, Linux, UNIX)
  • Eficient, elegant
  • Perspective în alte limbaje de programare
  • Limbaj al programatorului

1.2. De ce Code::Blocks ?

  • sunteţi obişnuit cu el din liceu
  • gratuit
  • editor simplu și sugestiv
  • permite aranjarea automată a codului (Format use AStyle)

2. Evaluarea inițială a studenților

3. Discutarea unor teme din curs

      1. paradigme de programare
      2. comparație interpretor – compilator
      3. instalarea Code::Blocks și rularea unui program „Hello World!”
      4. utilizarea depanatorului
      5. variabile, constante, expresii

4. Exerciții

    1.  (0.25p) Să se calculeze suma cifrelor pare ale unui număr natural n. De exemplu, pentru n=2410365, va rezulta s=12.
    2.  (0.25p) Să se determine oglinditul unui număr natural n.
    3.  (0.25p) Să se scrie o secvență de cod care verifică dacă un număr natural este prim.
    4. (0.25p) Se da n natural nenul. Sa se calculeze S=1!+2!+3!+…+n! folosind un singur „for”.
    5. (0.25p) Să se verifice dacă un număr p dat este „deosebit” sau nu. Spunem că p este „deosebit” dacă există q astfel încât p=q+s(q), în care s(q) este suma cifrelor lui q.
    6. (0,25p) Se da n natural nenul. Sa se calculeze S=1+1/2+1*3+1/4+1*3*5+1/6+1*3*5*7+1/8+…. (n termeni).
    7. (0.5p) Se citește un număr natural n, apoi se citesc n-1 numere naturale, distincte, între 1 și n. Să se determine care număr lipsește. Nu se folosesc vectori. Exemplu: pentru n=5 și numerele 2,5,1,4, lipsește 3.
      Solutie: Numarul lipsa este n(n+1)/2 – suma numerelor citite rand pe rand.
    8. (0.25p) Se citește un număr natural n. Să se afișeze toate valorile șirului Fibonacci mai mici sau egale cu n (Ex. pentru n=10 se afișează 0 1 1 2 3 5 8).
    9. (0.5p) O insectă poate urca o scară cu n trepte facând sărituri/pași de o treaptă sau de două trepte. Să se scrie o funcție care, pentru un număr n natural, returnează numărul de modalități în care poate urca insecta acea scară. Nu se folosesc vectori. De exemplu, pentru n=4 funcția va returna 5 (modalități).
      Solutie: Notam cu F(n) numarul de modalitati de a urca scara cu n trepte. A urca cele n trepte in toate felurile inseamna a urca n-2 trepte in toate felurile si a face un pas de doua trepte + a urca n-1 trepte in toate felurile si a face un pas de o treapta. Deci F(n)=F(n-2)+F(n-1). Avem F(1)=1 si F(2)=2. Este sirul lui Fibonacci.
    10. (0.5p) Se citește un șir de n numere naturale. Să se determine cel mai mare divizor comun al tuturor numerelor din șir. Nu se folosesc vectori. (Ex. pentru n=4 și valorile 12 36 60 102 se va afișa 6).
    11. (0,75) Se citesc numarul natural a si numarul natural b. Sa se determine ultima cifra a numarului a^b. Solutia cu instructiuni repetitive primeste doar 0,25p.
      Solutie: https://talentedenazdravani.eu/blog/2014/12/08/matematica-ultima-cifra-a-unui-numar-natural/
    12. (0.75p) Se citește un număr natural n, apoi se citesc n numere naturale, distincte, între 1 și n, cu excepția unuia care apare de două ori, iar altul lipsește. Nu se folosesc vectori. Să se determine numărul care apare de două ori și numărul care lipsește.
      Solutie: Se calculeaza suma numerelor pe masura ce se citesc, precum si suma patratelor lor. Fie prima suma = T si suma patratelor = T2. Se stie ca, daca ar fi toate numerele o singura data, am obtine sumele S=n(n+1)/2, respectiv S2=n(n+1)(2n+1)/6. Fie a numarul care apare de doua ori si b numarul lipsa. Avem T-a+b=S => a-b=T-S. Similar T2-a*a+b*b=S2=>a*a-b*b=T2-S2. Avem a*a-b*b=(a-b)*(a+b), deci obtinem si a+b, apoi a si b.
      Mai multe probleme similare, cu discuții și soluții se găsesc la adresa http://www.infoarena.ro/missing-numbers
    13. (0.25p) Să se verifice dacă un număr natural n este palindrom.
    14. (0.5p) Să se afișeze toate numerele naturale de 4 cifre, care sunt prime și au oglinditele numere prime. Nu se folosesc vectori.
    15. (0.5p). Se citește n natural. Să se afișeze următorul romb (ex. pt. n=3):
      ____1
      ___2    1
      __3    2   1
      ___2    1
      ____1
    16. (0.5p) Se citesc cel putin două numere naturale, până la întâlnirea numărului 0. Să se determine cea mai mare diferență în modul între oricare două numere citite. Nu se folosesc vectori.
      Solutie: Cea mai mare diferență în modul este fabs(max-min), unde max este maximul elementelor citite, iar min este minimul elementelor citite, care se pot calcula pe masură ce numerele se citesc.
    17. (0.25p) Să se calculeze suma divizorilor unui număr natural n (cu explicații pentru eficiență).
    18. (0,75p) Se citeste n natural (n este cel putin 2), apoi se citesc n numere reale. Sa se determine (prima) cea mai lunga secventa de numere identice, citite consecutiv. Se va preciza lungimea si numarul de ordine al primului numar din secventa. De exemplu, daca se citeste n=17, iar apoi numerele 2,3,3,4,1,7,7,7,4,8,8,5,5,5,2,2,9) se va afisa lungimea=3, prima pozitie=6 (este secventa 7,7,7).
    19. (0.5p) Se citește un număr natural n. Să se descompună ca sumă de termeni distincți ai șirului Fibonacci. (Ex. pentru n=12 se afișează 8+3+1).
    20. (0.5p) Să se scrie descompunerea în factori primi (ridicați la puterile corespunzătoare) a unui număr natural n.
    21. (0,75p). Să se afișeze toate variantele de a scrie un număr natural n ca sumă de numere consecutive. Nu se folosesc vectori. De exemplu, pentru n=15, putem avea 15=1+2+3+4+5, 15=4+5+6 și 15=7+8.
      Solutie: Cea mai eficienta solutie este cea in care se constata ca n se poate scrie sub forma n=i+(i+1)+(i+2)+…+(i+k-1), deci n=i+i+i+…+i (de k ori)+1+2+3+….+(k-1), deci n=k*i+(k-1)*k/2. i este primul element dintr-o asemenea suma de numere consecutive si i nu poate fi mai mare de n/2. Asadar, se poate determina k din ecuatia de gradul 2, cu necunoscuta k, de mai sus, in functie de i si n. Se ia doar solutia posibila si daca se obtine un numar intreg k, atunci k se determina in functie de i si n in O(1).
      Apoi
      for (i=1; i<=n/2; i++)
      { determina k in functie de n si i din ec. de gr. 2;
      if (k este intreg) scrie numerele de la i la i+k-1; }.  
    22. (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.
    23. (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