SDA Lucrarea 2 Backup

De la WikiLabs
Versiunea din 17 martie 2016 23:06, autor: Radu Hobincu (Discuție | contribuții) (Exerciții)

Î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, Pa și Pb. În mod optim această împărțire se face exact la jumătate.
  3. Se rezolvă problemele Pa și Pb (folosind eventual același algoritm) și se obțin două rezultate parțiale Ra și Rb.
  4. Ra și Rb 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:
    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:
    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.
  • 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.
      010 = 000000002, bitCount[0] = 0
      110 = 000000012, bitCount[1] = 1
      210 = 000000102, bitCount[2] = 1
      310 = 000000112, bitCount[3] = 2, etc.
    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.