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];
};
<syntaxhighlight/>

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

<syntaxhighlight lang="C">
int main() {
    struct Person somePerson;
    return 0;
}
<syntaxhighlight/>

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

<syntaxhighlight lang="C">
int main() {
    struct Person somePerson;
    somePerson.age = 20;
    return 0;
}
<syntaxhighlight/>

Dacă avem un pointer la o structură, putem accesa membrii acesteia în două moduri:
# Prin dereferențierea pointerului (adică obținerea valorii de la adresa respectivă), folosind operatorul <code>*</code>.
# Prin utilizarea operatorului <code>-></code> care este analog operatorului <code>.</code>, dar se folosește cu variabile de tip pointer-la-structură, în loc de variabile de tip structură:

<syntaxhighlight lang="C">
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;
}
<syntaxhighlight/>


= 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'':
# Dacă problema este elementară, se întoarce direct rezultatul.
# Se împarte problema inițială '''P''' (adică datele de intrare) în două probleme de același fel, '''P<sub>a</sub>''' și '''P<sub>b</sub>'''. În mod optim această împărțire se face exact la jumătate.
# Se rezolvă problemele '''P<sub>a</sub>''' și '''P<sub>b</sub>''' (folosind eventual același algoritm) și se obțin două rezultate parțiale '''R<sub>a</sub>''' și '''R<sub>b</sub>'''.
# '''R<sub>a</sub>''' și '''R<sub>b</sub>''' 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 ===

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

Implementarea în C:
<syntaxhighlight lang="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.