Notițe din liceu (2022-2025) by Daniel: Github (caută fisiere .md sau .excalidraw aici)

  • Curs-0   Citire de numere

    Ce înveți

    • Cum citești valori până la o condiție de oprire.
    • Cum citești exact n valori.
    • Cum citești din fișier până la final (EOF).

    Varianta I: citire până la 0

    cin >> n;
while(n){
    // prelucrare n
    // ...
    cin >> n;
}

    Varianta II: citire a n numere

    cin >> n;
for(i=1;i<=n;i++){
    cin >> x;
    // prelucrare x
    // ...
}

    Varianta III: citire până la finalul fișierului (EOF)

    // ! Nu uita sa imporți librăria !
#include <fstream>
ifstream f("fisier.txt");
    while(f>>n){
    // prelucrare n
}

  • Curs-1   Suma cifrelor

    Varianta I (explicită)

    s = 0;
while(n != 0){
    s = s + n % 10;
    n = n / 10;
}

    Varianta II (compactă)

    s = 0;
while(n)
    s += n % 10, n /= 10;

  • Curs-2   Oglinditul/Inversul/Răsturnatul

    Idee

    Construim un nou număr, cifră cu cifră, luând mereu ultima cifră din n.

    ogl = 0;
while(n != 0){
    ogl = ogl * 10 + n % 10;
    n = n / 10;
}

  • Curs-3   Suma divizorilor

    Varianta I

    s = 0;
for(d = 1; d<=n; d++)
    if(n % d == 0)
    s += d;

    Varianta II (eficientă)

    s = 0;
for(d = 1; d * d < n; d++)
    if(n % d == 0)
        s = s + d + n / d;
if(d * d == n)
    s = s + d;

  • Curs-4   Verificare număr prim

    Varianta I

    nrd = 0;
for(d = 1; d <= n; d++)
    if(n % d == 0)
        nrd++;
if(nrd == 2)
    // prelucrare n
    // ...

    Varianta II (eficientă)

    nrd = 0;
for(d = 1; d * d < n; d++)
    if(n % d == 0)
        nrd = nrd + 2;
if(d * d == n)
    nrd++;
if(nrd == 2)
    // prelucrare n
    // ...

  • Curs-5   cmmdc/cmmmc

    Varianta I: împărțiri repetate (Euclid)

    if(a * b == 0)
    cmmdc = a + b;
else {
    D = a;
    I = b;
    R = D % I;
    while(R != 0){
        D = I;
        I = R;
        R = D % I;
    }
    cmmdc = I;
}
cmmmc = a * b / cmmdc;

    Varianta II: scăderi repetate

    ca = a;
cb = b;
if(a * b == 0)
    cmmdc = a + b;
else {
    while(a != b)
        if(a > b)
            a = a - b;
        else
            b = b - a;
    cmmdc = a;
}
cmmmc = ca * cb / cmmdc;

  • Curs-6   Factori primi

    Exemplu

    90 = 2^1 * 3^2 * 5^1

    Pasn înaintedp după împărțiri
    19021
    24532
    3551

    Varianta I

    d = 2;
while(n != 1){
    p = 0;
    while(n % d == 0){
        n = n/d;
        p++;
    }
    if(p != 0)
        // prelucrare p, d
        // ...
    d++;
}

    Varianta II (eficientă)

    d = 2;
while(d * d <= n){
    p = 0;
    while(n % d == 0){
        p++;
        n = n / d;
    }
    if(p != 0){
        // prelucrare p, d
        // ...
    }
    d++;
}
if(n != 1){
    // prelucrare n^1
    // ...
}

  • Curs-7   Șirul lui Fibonacci

    Verificare: n aparține șirului?

        c  b  a
ex: 1, 1, 2, 3, 5, 8, 13, ...
      +  =
    if(n == 1){
    // n face parte
    // ...
} else {
    c = b = 1;
    a = 0;
    while(a < n){
        a = b + c;
        c = b;
        b = a;
    }
    if(n == a){
        // n face parte
        // ...
    }
}

  • Curs-8   Transformări

    a) Din baza 10 în baza 2

    Exemplu: 69 (baza 10) = 1000101 (baza 2)

    int n = 69;

int nrb = 0;
int p = 1;
while(n != 0) {
    nrb = nrb + p * (n % 2);
    n = n / 2;
    p = p * 10;
}

output=>1000101

    b) Din baza 2 în baza 10

    Exemplu: 1000101 (baza 2) = 69 (baza 10)

    int n = 1000101;

int nrb = 0;
int p = 1;
while(n != 0) {
    nrb = nrb + p * (n % 10);
    n = n / 10;
    p = p * 2;
}

output=>69

    c) Din baza a în baza b

    Exemplu: 123 (baza 4) = 11011 (baza 2)

    Metoda standard: întâi transformi în baza 10, apoi din baza 10 în baza b.

    int n = 123; // număr scris cu cifre 0..9, în baza a
int a = 4;
int b = 2;

int zecimal = 0;
int p = 1;
while(n != 0) {
    zecimal = zecimal + (n % 10) * p;
    n = n / 10;
    p = p * a;
}

int nrb = 0;
p = 1;
while(zecimal != 0) {
    nrb = nrb + p * (zecimal % b);
    zecimal = zecimal / b;
    p = p * 10;
}

output=>11011

  • Curs-vectori-1   Introducere

    Tablouri unidimensionale

    Declarare

    • întregi: int v[100], n, i;
    • reali: float v[100]; int n, i;

    Citire de la tastatură

    cin >> n;
for(i=0;i<n;i++){
    cin >> v[i];
}

  • Curs-vectori-2   Ordonare (Sortare)

    Varianta I

    for(i=0;i<n-1;i++)
    for(j=i+1;j<n;j++)
        if(v[i]>v[j]) // <- descresc sau if(v[i]<v[j]) <- cresc
            swap(v[i],v[j]);

    Varianta II: Bubble Sort

    do {
    OK=1;
    for(i=0;i<n-1;i++){
        if(v[i]>v[i+1]){
            OK=0;
            swap(v[i],v[i+1]);
        }
    }
} while(OK==0);

  • Curs-vectori-3   Eliminare / Adăugare în vector

    Eliminare

    for(i=0;i<n;i++){
    if(v[i]%2==1){ // dacă e impar
        for(j=i;j<n;j++)
            v[j]=v[j+1];
        n--;
        i--;
    }
}

    Adăugare

    for(i=0;i<n;i++){
    if(v[i]%2==1){
        for(j=n;j>i;j--) // pentru adăugare după: j>i+1
            v[j]=v[j-1];
        n++;
        v[i]=2*v[i];
        i++;
    }
}

  • Curs-vectori-4   Căutare binară

    Implementare (pentru șiruri ordonate)

    OK=0;
ls=0;
ld=n-1;
do {
    mij = (ls+ld) / 2;
    if(v[mij]==x){
        OK=1;
    } else {
        if(v[mij]<x)
            ls = mij + 1;
        else
            ld = mij - 1;
    }
} while(OK==0 && ls<=ld);

  • Curs-vectori-5   Interclasare

    Implementare (pentru șiruri ordonate)

    i=0;
j=0;
k=0;
while(i<n && j<m){
    if(a[i]<b[j]){
        c[k]=a[i]; // sau c[k++]=a[i++]
        k++;
        i++;
    } else {
        c[k]=b[j]; // sau c[k++]=b[j++]
        k++;
        j++;
    }
}
while(i<n){c[k]=a[i];k++;i++;}
while(j<m){c[k]=b[j];k++;j++;}

  • Curs-matrici-1   Declarare și citire de matrice

    Ce înveți

    • Cum declari o matrice bidimensională.
    • Cum citești valorile unei matrice.
    • Cum parcurgi elementele unei matrice.

    Declarare

    int m[100][100];  // matrice 100 x 100
int n, p;         // n = număr de linii, p = număr de coloane

    Citire de la tastatură

    cin >> n >> p;  // dimensiunile
for(i=0; i<n; i++)
    for(j=0; j<p; j++)
        cin >> m[i][j];

    Afișare

    for(i=0; i<n; i++){
    for(j=0; j<p; j++)
        cout << m[i][j] << " ";
    cout << "\n";
}

  • Curs-matrici-2   Suma și parcurgerea elementelor

    Suma tuturor elementelor

    s = 0;
for(i=0; i<n; i++)
    for(j=0; j<p; j++)
        s += m[i][j];

    Suma unei linii

    s = 0;
for(j=0; j<p; j++)
    s += m[linie][j];

    Suma unei coloane

    s = 0;
for(i=0; i<n; i++)
    s += m[i][coloana];

    Maxim într-o linie

    max = m[linie][0];
for(j=0; j<p; j++)
    if(m[linie][j] > max)
        max = m[linie][j];

    Parcurgere după diagonale

    // diagonala d pornind din (0, d)
for(i=0; i<n && d+i < p; i++)
    cout << m[i][d+i] << " ";

  • Curs-matrici-3   Transpunerea unei matrice

    Ideea

    Transpusa unei matrice M (n × p) este o matrice MT (p × n) unde rândurile devin coloane și coloanele devin rânduri.

    MT[i][j] = M[j][i]

    Implementare

    int mt[100][100];  // matricea transpusă

for(i=0; i<n; i++)
    for(j=0; j<p; j++)
        mt[j][i] = m[i][j];

// acum mt are dimensiunile p x n
int temp = n;
n = p;
p = temp;
m = mt;

    Transpunere la loc (n = p)

    Dacă matricea este pătratică, o poți transpune în loc:

    for(i=0; i<n; i++)
    for(j=i+1; j<n; j++)
        swap(m[i][j], m[j][i]);

  • Curs-matrici-4   Înmulțirea a două matrice

    Regula

    Dacă A (n × m) și B (m × p), atunci C = A × B are dimensiuni (n × p).

    Elementul C[i][j] = A[i][0]*B[0][j] + A[i][1]*B[1][j] + ... + A[i][m-1]*B[m-1][j]

    Implementare

    int a[100][100], b[100][100], c[100][100];
int n, m, p;  // A: n x m, B: m x p, C: n x p

// inițializare c la 0
for(i=0; i<n; i++)
    for(j=0; j<p; j++)
        c[i][j] = 0;

// înmulțire
for(i=0; i<n; i++){
    for(j=0; j<p; j++){
        for(k=0; k<m; k++)
            c[i][j] += a[i][k] * b[k][j];
    }
}

    Observație

    Înmulțirea de matrice NU este comutativă: A×B ≠ B×A (și uneori nici nu se poate efectua)

  • Curs-matrici-5   Diagonala principală și secundară

    Diagonala principală

    Elementele unde i == j

    // parcurgere
for(i=0; i<n; i++)
    cout << m[i][i] << " ";

// suma
s = 0;
for(i=0; i<n; i++)
    s += m[i][i];

// produsul
p = 1;
for(i=0; i<n; i++)
    p *= m[i][i];

    Diagonala secundară

    Elementele unde i + j == n - 1 (pentru matrice n × n)

    // parcurgere
for(i=0; i<n; i++)
    cout << m[i][n-1-i] << " ";

// suma
s = 0;
for(i=0; i<n; i++)
    s += m[i][n-1-i];

  • Curs-git   Contribuții open-source la acest proiect


    Puteți adauga chiar voi cursuri sau snippeturi de cod :) Mai jos sunt persoane care au ajutat ↓

    Contributori: 0xHansLanda

    Cheers 🍻

    Linkuri utile