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:
- 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, Pa și Pb. În mod optim această împărțire se face exact la jumătate.
- Se rezolvă problemele Pa și Pb (folosind eventual același algoritm) și se obțin două rezultate parțiale Ra și Rb.
- 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
- 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:
#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
- 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
- Fișier:Sda lab2 ex1 1.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 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
- Fișier:Sda lab2 ex2 1.txt - rezultatul corect este
- 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
- Fișier:Sda lab2 ex1 1.txt - rezultatul corect este
- 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:
- Grupa 2
- 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
- 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.
- Grupa 3
- 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(10) = 00000000(2), bitCount[0] = 0
1(10) = 00000001(2), bitCount[1] = 1
2(10) = 00000010(2), bitCount[2] = 1
3(10) = 00000011(2), bitCount[3] = 2
...
255(10) = 11111111(2), bitCount[255] = 8 - 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.
- Să se scrie o funcție care să precalculeze într-un vector
- Grupa 4