SDA Lucrarea 2 Backup: Diferență între versiuni

De la WikiLabs
(Exerciții)
Linia 73: Linia 73:
 
* Grupa 1
 
* Grupa 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):
 
*# 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):
*#* [[Fișier:sda_lab1_ex1_1.txt]] - rezultatul corect este ##
+
*#* [[Fișier:sda_lab2_ex1_1.txt]] - rezultatul corect este ##
*#* [[Fișier:sda_lab1_ex1_2.txt]] - rezultatul corect este ##
+
*#* [[Fișier:sda_lab2_ex1_2.txt]] - rezultatul corect este ##
*#* [[Fișier:sda_lab1_ex1_3.txt]] - rezultatul corect este ##
+
*#* [[Fișier:sda_lab2_ex1_3.txt]] - rezultatul corect este ##
 
*# Definiți și implementați un algoritm ''divide-et-impera'' care să calculeze produsul scalar între doi vectori de tip întreg pe 8 biți citite din următoarele fișiere (prima valoare din fișier reprezintă numărul de valori):
 
*# Definiți și implementați un algoritm ''divide-et-impera'' care să calculeze produsul scalar între doi vectori de tip întreg pe 8 biți citite din următoarele fișiere (prima valoare din fișier reprezintă numărul de valori):
*#* [[Fișier:sda_lab1_ex2_1.txt]] - rezultatul corect este ##
+
*#* [[Fișier:sda_lab2_ex2_1.txt]] - rezultatul corect este ##
*#* [[Fișier:sda_lab1_ex2_2.txt]] - rezultatul corect este ##
+
*#* [[Fișier:sda_lab2_ex2_2.txt]] - rezultatul corect este ##
*#* [[Fișier:sda_lab1_ex2_3.txt]] - rezultatul corect este ##
+
*#* [[Fișier:sda_lab2_ex2_3.txt]] - rezultatul corect este ##
 +
*# Definiți și implementați un algoritm ''divide-et-impera'' care să calculeze produsul scalar între doi vectori de tip întreg pe 8 biți citite din următoarele fișiere (prima valoare din fișier reprezintă numărul de valori):
 +
*#* [[Fișier:sda_lab2_ex2_1.txt]] - rezultatul corect este ##
 +
*#* [[Fișier:sda_lab2_ex2_2.txt]] - rezultatul corect este ##
 +
*#* [[Fișier:sda_lab2_ex2_3.txt]] - rezultatul corect este ##

Versiunea de la data 6 martie 2016 19:43

Î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ă subprobleme 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-impere:

  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):
    2. Definiți și implementați un algoritm divide-et-impera care să calculeze produsul scalar între doi vectori de tip întreg pe 8 biți citite din următoarele fișiere (prima valoare din fișier reprezintă numărul de valori):
    3. Definiți și implementați un algoritm divide-et-impera care să calculeze produsul scalar între doi vectori de tip întreg pe 8 biți citite din următoarele fișiere (prima valoare din fișier reprezintă numărul de valori):