C (PDF)

Zadanie C - Zbiory
Punktów do uzyskania: 8
Język programowania: C++
autor zadania: Marek Śmieja

Zadaniem jest zaimplementowanie wybranych funkcjonalności biblioteki dla zbiorów.

Zakładamy, że uniwersum, czyli przestrzeń elementów, składa się liczb naturalnych od 1 do
4095. Zbiór n-elementowy będzie realizowany za pomocą tablicy, w której na pierwszych n
pozycjach będą umieszczone jego elementy (wybrane elementy z uniwersum), a na pozycji
(n+1) będzie znajdował się znak kończący, czyli -1. Z definicji, zbiór nie zawiera duplikatów,
a elementy w tablicy nie muszą być posortowane.
Do zaimplementowania są następujące podprogramy:

1. utworz przyjmująca odniesienia do dwóch tablic o elementach typu int i nazwach a, b
oraz liczbę n będącą długością tablicy a, niezwracająca wartości, która utworzy zbiór
składający się elementów wchodzących w skład tablicy a i zapisze go do tablicy b.
Tablica a może zawierać jakiekolwiek liczby całkowite (nie reprezentuje zbioru), a
wynikowa tablica musi spełniać warunki zbioru z zadania.
2. suma przyjmująca adresy trzech tablic o elementach typu int i nazwach a, b, c
opisujących zbiory, niezwracającą wartości, która wypełni tablicę c sumą zbiorów a i
b.
3. iloczyn przyjmująca odniesienia do trzech tablic o elementach typu int i nazwach a, b,
c opisujących zbiory, niezwracającą wartości, która wypełni tablicę c przecięciem
zbiorów a i b.
4. roznica przyjmująca odniesienia do trzech tablic o elementach typu int i nazwach a,
b, c opisujących zbiory, niezwracającą wartości, która wypełni tablicę c różnicą
zbiorów a i b.
5. roznica_sym przyjmująca odniesienia do trzech tablic o elementach typu int i
nazwach a, b opisujących zbiory, c, niezwracającą wartości, która wypełni tablicę c
różnicą symetryczną zbiorów a i b.
6. dopełnienie przyjmująca odniesienia do dwóch tablic o elementach typu int i
nazwach a, b opisujących zbiory, niezwracającą wartości, która wypełni tablicę b
dopełnieniem zbioru a.
7. dodanie przyjmującą odniesienia do tablicy o elementach typu int i nazwie a
opisującej zbiór oraz argument b typu int, niezwracająca wartości, która doda element
b do zbioru a.
8. czy_podzbior przyjmująca odniesienia do dwóch tablic o elementach typu int i
nazwach a, b opisujących zbiory, która zwróci wartość true jeśli a jest podzbiorem b.
9. czy_rowne przyjmująca odniesienia do dwóch tablic o elementach typu int i nazwach
a, b opisujących zbiory, która zwróci wartość true jeśli a jest równe b.
10. czy_pusty przyjmująca odniesienie do tablicy o elementach typu int i nazwie a
opisującej zbiór, która zwróci wartość true jeśli a jest zbiorem pustym

11. czy_niepusty przyjmująca odniesienie do tablicy o elementach typu int i nazwie a
opisującej zbiór, która zwróci wartość true jeśli a jest zbiorem niepustym
12. czy_nalezy przyjmująca odniesienie do tablicy o elementach typu int i nazwie a
opisującej zbiór oraz element b typu int, która zwróci wartość true jeśli b jest
elementem a
13. srednia_arytmetyczna przyjmująca odniesienie do tablicy o elementach typu int i
nazwie a opisującej niepusty zbiór, a zwracająca wartość double będącą średnią
arytmetyczną elementów wchodzących w skład zbioru a
14. srednia_harmoniczna przyjmująca odniesienie do tablicy o elementach typu int i
nazwie a opisującej niepusty zbiór, a zwracająca wartość double będącą średnią
harmoniczną elementów wchodzących w skład zbioru a
15. min_max przyjmująca odniesienie do tablicy o elementach typu int i nazwie a
opisującej niepusty zbiór oraz referencje do dwóch liczb całkowitych b i c, do których
zostanie zapisana wartość elementu najmniejszego i największego zbioru a,
odpowiednio.
16. statystyki przyjmująca odniesienie do tablicy o elementach typu int i nazwie a
opisującej zbiór, tablicę znakową o nazwie b, przechowującą kody operacji, tablicę
typu double o nazwie c, w której zapiszemy wynik oraz liczbę całkowitą n, będącą
długością tablicy b, niezwracająca wartości. Kody operacji to ‘a’ – średnia
arytmetyczna, ‘h’ – średnia harmoniczna, ‘e’ – minimum i maksimum. W wyniku
wywołania podprogramu kolejne elementy tablicy c powinny zostać wypełnione
wartościami będącymi wynikami wywołania kolejnych operacji zdefiniowanych w
tablicy b.

Powyższe operacje nie mogą modyfikować danych ponad te, które są ściśle wyspecyfikowane
w opisie podprogramów. Dla przykładu, jeśli suma zbiorów daje zbiór n elementowy, to
można zmodyfikować tylko (n+1) pierwszych wyrazów tablicy wynikowej.
Całość implementacji ma znaleźć się w pliku kod.cpp. Archiwum zip zawierające wyłącznie
ten plik ma zostać wysłana do systemu Baca. W szczególności, w pliku kod.cpp nie ma być
funkcji main.
Dla przykładowego maina:

//tworzenie
int a[] = {4,1,3,1,5000};
int b[10];
utworz(a,b,5);
//suma
int c[] = {2,1,-1};
int d[10];
suma(b,c,d);
for(int i = 0; i < 5; ++i){
cout << d[i] << " ";
}

cout << endl;
//min_max
int x,y;
min_max(b,x,y);
cout << x << " " << y << endl;
//operacje logiczne
cout << czy_pusty(b) << " " << czy_niepusty(b) << " " << czy_nalezy(b,5) << endl;
poprawnym wynikiem jest:
4 1 3 2 -1
14
010