SDA Lucrarea 2 Backup

În acest laborator veți relua și recapitula noțiunile legate funcții recursive și citire și scriere din fișiere.

Utilizarea fișierelor in C

Pentru a recapitula modurile de scriere și citire din fișiere în limbajul C, puteți recapitula PC Laborator 13.

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.