SDA Lucrarea 2

În acest laborator se introduc noțiuni noi de Programare Orientată pe Obiecte: clasa, obiectul, metoda, constructorul, destructorul, namespace și template.

Structurile in C

Ne amintim că în C, o structură e definită printr-un nume, care reprezintă numele tipului de date, precum și un număr de câmpuri, adică una sau mai multe varibile, definite prin tip și nume, ce reprezintă datele componente ale structurii:

struct Person {
    char name[128];
    uint8_t age;
    char cnp[14];
    char address[256];
};

Structura Person este un tip de dată, prin urmare putem declara și utiliza variabile de tipul acestei structuri:

int main() {
    struct Person somePerson;
    return 0;
}

În codul de mai sus, s-a declarat o varibilă de tip struct Person, cu numele somePerson. Prin definirea unei variabile de tipul structurii, de fapt s-au definit în mod automat toate variabilele membre ale acesteia: name, age etc. Având o variabilă de tipul structurii, membrii acesteia se pot accesa cu operatorul .:

int main() {
    struct Person somePerson;
    somePerson.age = 20;
    return 0;
}

Dacă avem un pointer la o structură, putem accesa membrii acesteia în două moduri:

1. Prin dereferențierea pointerului (adică obținerea valorii de la adresa respectivă), folosind operatorul *.
2. Prin utilizarea operatorului -> care este analog operatorului ., dar se folosește cu variabile de tip pointer-la-structură, în loc de variabile de tip structură:

int main() {
    struct Person somePerson;
    somePerson.age = 20;

    struct Person * somePersonPointer = &somePerson;

    /* Varianta 1 */
    strcpy((*somePersonPointer).name, "Andrei");

    /* Varianta 2 */
    strcpy(somePersonPointer->name, "Andrei");

    return 0;
}

Funcțiile recursive - Clasa de algoritmi Divide-et-impera

Definirea și utilizarea funcțiilor recursive se pot recapitula citind PC Laborator 10.

Divide-et-impera

Clasa de algoritmi divide-et-impera se referă la algoritmii în care problema inițială se împarte în două probleme de același fel, în care datele de intrare nu se suprapun. Se rezolvă aceste două sub-probleme obținând două rezultate parțiale care apoi se combină pentru a obține rezultatul final.

Pașii de rezolvare a unei probleme folosind Divide-et-impera:

1. Dacă problema este elementară, se întoarce direct rezultatul.
2. Se împarte problema inițială P (adică datele de intrare) în două probleme de același fel, P_a și P_b. În mod optim această împărțire se face exact la jumătate.
3. Se rezolvă problemele P_a și P_b (folosind eventual același algoritm) și se obțin două rezultate parțiale R_a și R_b.
4. R_a și R_b se combină într-un mod care ține de aplicație și se obține rezultatul final R.

De cele mai multe ori, algoritmii de tip divide-et-impera se implementează cu ajutorul funcțiilor recursive.

Exemplu de algoritm și implementare

Cerință

Se cere să se scrie un algoritm divide-et-impera care să calculeze maximul unui vector de valori în virgulă mobilă. 

Rezolvare

1. Dacă vectorul are un singur element, se întoarce elementul respectiv.
2. Se împarte vectorul în două jumătăți egale (sau cel mult cu diferență de un element, dacă lungimea este impară).
3. Se calculează maximul fiecărei jumătăți folosind același algoritm.
4. Se calculează maximul global din maximul fiecărei jumătăți.

Implementarea în C:

#include <stdio.h>
#include <stdlib.h>

float getMaximum (float * array, unsigned start, unsigned stop) {
    if (start == stop) return array[start];

    float max1 = getMaximum(array, start, (start + stop) / 2);
    float max2 = getMaximum(array, (start + stop) / 2 + 1, stop);

    return max1 > max2 ? max1 : max2;
}

int main(){
    unsigned size;
    printf("size = ");
    scanf("%u", &size);

    float *array = (float*)malloc(size * sizeof(float));
    unsigned i;
    for(i=0; i<size; i++) {
        printf("array[%u] = ", i);
        scanf("%f", &array[i]);
    }

    float max = getMaximum(array, 0, size - 1);

    free(array);

    printf("Max is = %f\n", max);
    return 0;
}

Exerciții

• Grupa 1
  1. Definiți și implementați un algoritm divide-et-impera care să calculeze suma unui vector de elemente de tip întreg pe 16 biți citite din următoarele fișiere (prima valoare din fișier reprezintă numărul de valori) - atenție, rezultatul poate fi pe un număr foarte mare de biți:
     • Fișier:Sda lab2 ex1 1.txt - rezultatul corect este 55
     • Fișier:Sda lab2 ex1 2.txt - rezultatul corect este -63041
     • Fișier:Sda lab2 ex1 3.txt - rezultatul corect este -999712
  2. Definiți și implementați un algoritm divide-et-impera care să calculeze produsul scalar între doi vectori de tip întreg pe 16 biți citite din următoarele fișiere (prima valoare din fișier reprezintă numărul de valori) - atenție, rezultatul poate fi pe un număr foarte mare de biți:
     • Fișier:Sda lab2 ex2 1.txt - rezultatul corect este 130
     • Fișier:Sda lab2 ex2 2.txt - rezultatul corect este -177671557
     • Fișier:Sda lab2 ex2 3.txt - rezultatul corect este 732104297
  3. Definiți și implementați un algoritm divide-et-impera care să calculeze media valorilor dintr-un vector de tip întreg pe 16 biți citite din următoarele fișiere (prima valoare din fișier reprezintă numărul de valori) - media se va reprezenta ca virgulă mobilă cu simplă precizie. Atenție și la vectorii cu dimensiune impară, unde media acestuia depinde de dimensiunile exacte ale jumătăților.
     • Fișier:Sda lab2 ex1 1.txt - rezultatul corect este 5.5
     • Fișier:Sda lab2 ex1 2.txt - rezultatul corect este -630.41
     • Fișier:Sda lab2 ex1 3.txt - rezultatul corect este -99.97
• Grupa 2
  1. Să se scrie un program care să afișeze cea mai mare diferența dintre elementele a doi vectori de valori întregi pe 64 de biți folosind un algoritm de tip divide-et-impera. Datele se vor citi din fișier.
     
     De exemplu pentru:
     A = [0,1,2,3]
     B = [5,6,9,10]
     A[0] - B[0] = 0-5 = -5
     A[1] - B[1] = 1-6 = -5
     A[2] - B[2] = 2-9 = -7
     A[3] - B[3] = 3-10 = -7
     
     să afișeze -7
• Grupa 3
  1. Să se scrie o funcție care să precalculeze într-un vector bitCount de întregi pe 8 biți fără semn, numărul de biți 1 din fiecare byte de la 0 la 255.
     0₍₁₀₎ = 00000000₍₂₎, bitCount[0] = 0
     1₍₁₀₎ = 00000001₍₂₎, bitCount[1] = 1
     2₍₁₀₎ = 00000010₍₂₎, bitCount[2] = 1
     3₍₁₀₎ = 00000011₍₂₎, bitCount[3] = 2
     ...
     255₍₁₀₎ = 11111111₍₂₎, bitCount[255] = 8
  2. Să se scrie un program de tip Divide-et-impera care să citească un fișier oarecare și să calculeze numărul de biți 1 din acel fișier.
• Grupa 4
  1. Folosind metoda Divide-et-impera, scrieți o funcție care să determine dacă un vector cu elemente întregi pe 16 de biți fără semn este ordonat crescător.