o przedmiocie
Kurs C++17 i STL
C++17 to najnowsza wersja języka C++.
Język C++ prawdza się, gdy chcemy zapewnić wysoką wydajność programu.
Język ten jest stale rozwijany a kolejne jego specyfikacje,
czyli C++11, C++14 i C++17, przyniosły wiele udogodnień.
Aby w pełni wykorzystać potencjał języka C++ należy go używać wraz z biblioteką standardową STL.
C++ wraz z STL to doskonałe narzędzie do implementowania oprogramowania wysokiej jakości.
Wymagane przygotowanie
- Umiejętność programowania strukturalnego i proceduralnego w języku C99.
- Znajomość podstaw programowania obiektowego w języku C++98.
- Umiejętność czytania dokumentacji technicznej w języku angielskim.
- Znajomość podstaw algorytmiki.
Cel kursu
- Nauka nowoczesnych technik programowania w języku C++17/20.
- Poznanie obszernych fragmentów biblioteki standardowej STL.
literatura
Podrędznik podstawowy
- N.M.Josuttis: C++. Biblioteka standardowa. Podręcznik programisty. Wydanie 2. Wydawnictwo Helion, Gliwice 2014.
Literatura uzupełniająca
- B.Stroustrup: Język C++. Kompendium wiedzy. Wydanie 4. Wydawnictwo Helion, Gliwice 2014.
- J.Galowicz: C++17 STL. Receptury. Wydawnictwo Helion, Gliwice 2018.
Literatura dodatkowa
- J.Grębosz: Opus magnum C++11. Programowanie w języku C++. Tom 1, 2, 3. Wydawnictwo Helion, Gliwice 2018.
- S.Rao: C++. Dla każdego. Wydanie 7. Wydawnictwo Helion, Gliwice 2014.
- S.Prata: Język C++. Szkoła programowania. Wydanie 6. Wydawnictwo Helion, Gliwice 2012.
Literatura elektroniczna
Kompilatory online C++17
laboratorium
Zasady zaliczenia przedmiotu
- Ogólnie:
-
W semestrze będzie opublikowanych (na tej stronie) kilkanaście prostych list
z zadaniami do zaprogramowania.
Na każdej liście znajdą się zadania za sumaryczną ilość około 10 punktów
(przeważnie będzie to dokładnie 10 punktów).
Zatem za samodzielnie zaprogramowane zadania z listy i oddane w terminie można
będzie dostać do 10 punktów (chociaż listy z zadaniami mogą różnić się trudnością).
- Terminy:
-
Zadania do zaprogramowania będą ogłaszane w tygodniu poprzedzającym termin ich realizacji.
Zadania należy oddawać w wyznaczonym terminie w trakcie trwania pracowni.
Spóźnienia nie będą tolerowane, za wyjątkiem uzasadnionych sytuacji życiowych:
choroba potwierdzona zwolnieniem lekarskim, wezwanie do Sądu, itp.
- Prezentacje:
-
Programy należy prezentować osobiście w czasie pracowni - z każdym studentem
chciałbym indywidualnie omówić jego rozwiązanie oraz wskazać wady i braki w programie.
Po pracowni program należy mi przekazać (będę jeszcze robić weryfikację antyplagiatową) na SKOS.
W trakcie prezentacji programu trzeba się liczyć z pytamiami dotyczącymi zadania:
metoda rozwiązania, zastosowane konstrukcje językowe, wykorzystane technologie czy klasy biblioteczne itp.
- Rozwiązania:
-
Kody źródłowe własnych programów należy zapisywać na SKOS,
ponieważ tylko wtedy rozwiązania zadań będą podlegały weryfikacji autorskiej i ocenie.
Jeśli student nie mógł uczestniczyć w zajęciach z powodu awarii połączenia internetowego,
to oprócz programu ma przekazać sprawozdanie z realizacji zadania (co zostało zaprogramowane
i w którym miejścu w pliku źródłowym oraz czego nie udało się osiągnąć).
- Oceny:
-
Aby zaliczyć laboratorium na ocenę dostateczną trzeba do końca
semestru zdobyć 50% z wszystkich możliwych do uzyskania punktów;
na ocenę bardzo dobrą trzeba będzie zgromadzić 90% punktów;
oceny pośrednie pozostją w liniowej zależności od przedstawionych wymagań granicznych.
Zadania laboratoryjne
- 24, 25 października 2022: nowe elementy języka C++
- Zadanie 1 (1 pkt).
-
Sprawdź, czy w stosowanym przez Ciebie kompilatorze (co najmniej C++17) działają trójznaki
(ang. trigraphs), takie jak na przykład
??-
co tłumaczy się na znak tyldy
˜
, itp.
Co zrobić, aby kompilator właściwie zinterpretował występujące w programie trójznaki?
- Zadanie 2 (1 pkt).
-
Wypisz na standardowym wyjściu
std::out
surowy łańcuch znaków
(ang. raw string) zawierający:
- adres naszego Instytutu (w pierwszej linii pełną nazwę Instytutu, w drugiej ulicę
z numerem, w trzeciej kod pocztowy i miasto);
- ścieżkę bezwzględną do katalogu z programami użytkowymi w systemie Windows;
- różne sekwencje znaków cudzysłowia i nawiasów okrągłych (a w szczególności
sekwencję
)"
).
- Zadanie 3 (1 pkt).
-
Stwórz alias dla typu będącego zbiorem
std::set<>
łańcuchów znakowych.
Następnie zadeklaruj i zainicjalizuj taki zbiór używając jednolitej inicjalizacji.
Na koniec przejdź po tym zbiorze pętlą for dla zakresów (ang. range-based
for-each loop)) dedukując automatycznie typ elementów zbioru; wypisz w pętli
wszystkie łańcuchy na standardowym wyjściu std::cout
).
- Zadanie 4 (1 pkt).
-
Zdefiniuj silnie stypizowany typ wyliczeniowy dla kilku wybranych imion męskich i żeńskich,
którego elementy będa typu
uint_16
.
Następnie zdefiniuj funkcję, która jako argumenty przyjmuje komunikat typu
string
i imię odbiorcy zdefiniowanego wcześniej typu wyliczeniowego (funkcja
może wypisywać komunikat personalnie skierowany do wskazanej osoby używając instrukcji
switch-case).
- Zadanie 5 (1 pkt).
-
Zdefiniuj funkcję rekurencyjną, która będzie wyznaczała n-tą liczbę Lucasa.
Funkcja ta ma przyjmować argument typu
uint32_t
i powinna automatycznie
dedukować typ wyniku.
- Zadanie 6 (1 pkt).
-
Napisz program, który dla podanych współczynników równania kwadratowego wyliczy wyróżnik
tego równania (często oznaczany symbolem Δ) i w zależności od jego wartości wypisze
miejsca zerowe.
Użyj do tego celu instrukcji warunkowej if-else z lokalnym inicjalizatorem dla
wyróżnika.
- Zadanie 7 (1 pkt).
-
Napisz program, który dla podanej daty wypisze ją z nazwą miesiąca (na przykład:
11 października 2022).
Użyj do tego celu instrukcji wyboru switch-case z lokalnym inicjalizatorem
miesiąca w dacie.
- Zadanie 8 (1 pkt).
-
Napisz program, który posortuje ciąg rekordów opisujących osoby
vector<osoba>
.
Sortowanie przeprowadź według nazwisk, imion i wieku (rok urodzenia).
Wykorzystaj do tego zaprzyjaźniony z klasą osoba
operator
porównywania pary osób (porównywanie leksykograficzne tupli zawierających
nazwisko, imię i rok urodzenia generowanych funkcją tie
).
- Zadanie 9 (2 pkt).
-
Dany jest wektor zawierający uporządkowany ciąg liczb całkowitych
vector<int>
; dane w tym wektorze są uporządkowane niemalejąco;
wiemy też, że w ciągu tym niektóre wartości moga się wielokrotnie powtarzać
(na przykład: 1, 2, 3, 3, 4, 5, 5, 5, 6, 7, 7, 7, 7, 8, 9).
Wykorzystaj operator statku kosmicznego <=>
do zaprogramowania
algorytmu (wyszukiwanie binarne) wyznaczającego parę iteratorów reprezentujących
zakres zawierający zadaną wartość.
Wynikiem tej funkcji ma być para iteratorów; wykorzystaj mechanizm wiązania
strukturalnego do przypisana wyznaczonych iteratorów do pary zmiennych
poczatek
oraz koniec
.
- 7, 8 listopada 2022: sprytne wskaźniki
- Zadanie 1 (3 pkt).
-
Zdefiniuj prostą klasę zawierającą licznik typu
uint64_t
,
początkowo ustawiony na wartość 1.
W kasie tej, oprócz innych funkcjonalności, umieść wirtualny destruktor,
który wypisze komunikat ze stanem licznika na standardowym wyjściu dla
błędów cerr
.
-
Następnie stwórz n-elementową tablicę takich liczników
i opakuj ją wskaźnikiem
unique_ptr
(opakowanie ma dotyczyć
tablicy a nie pojedynczch liczników).
-
Napisz też funkcję, która wywoła się rekurencyjnie m razy
z argumentem będącym wskaźnikiem na taką tablicę (wskaźnik
unique_ptr
ustaw za pomocą przniesienia).
W i-tym wywołaniu funkcja ta ma losowo wybrane elementy
zwiększyć o i-tą z kolei liczbę naturalną.
-
Na koniec wywołaj tą funkcję, a po jej wywołaniu wypisz wartości
wszystkich n liczników umieszczonych w tablicy.
Parametry n i m możesz ustalić w programie arbitralnie.
- Zadanie 2 (3 pkt).
-
Zdefiniuj klasę opakowującą plik tekstowy
line_writer
.
Obiekt takiej klasy ma przetrzymywać wskaźnik/referencję do strumienia
plikowego ofstream
stworzonego i otwartego w konstruktorze.
Zadaniem obiektów tej klasy będzie pisanie do pliku wiersz po wierszu.
Klasa ta powinna zamykać strumień w destruktorze.
-
Dalej w programie głównym stwórz kilka wskaźników
shared_ptr
odnoszących się do tego samego obiektu plikowego.
Niech każdy fragment programu posiadający taki własny wskaźnik zapisze
w tym pliku swoje dane.
Plik powinien zostać zamknięty dopiero, gdy wszystkie sprytne wskaźniki
zostaną zlikwidowane.
- Zadanie 3 (4 pkt).
-
Zdefiniuj klasę
alpaca
reprezentującą pojedynczą alpakę
w stadzie alpak (zarówno w konstruktorze jak i w destruktorze wypisuj
spersonalizowane komunikaty dotyczące alpaki).
W obiekcie tym powinno być zapisane imię alpaki typu string
(imiona niech unikatowe w stadzie), jej płeć jako typ wyliczeniowy,
wskaźnik na ojca i matkę typu shared_ptr<alpaca>
(dopuszczamy przypadek nieznanego ojca lub matki oznaczonego za pomocą
noname
) oraz wskaźnik na kolekcję jej dzieci typu
vector<weak_ptr<alpaca>>
.
-
Stado alpak niech będzie kolekcją obiektów typu
alpaca
- można opakować jakąś popularną kolekcję standardową, na przykład
set<alpaca>
(porównywanie alpak względem imion).
Przeprowadź symulację życia alpak w stadzie: hodowca może dokupić alpakę
z innego stada (wtedy jej rodzice są nieznani), alpaka może się urodzić
w stadzie (wtedy jej rodzice są członkami stada, a przynajmniej matka)
i wreszcie alapaka może umrzeć albo zostać sprzedana (należy ją wtedy usunąć z kolekcji).
Zaobserwuj, co się stanie, gdy słaby wskaźnik weak_ptr
stanie się wskaźnikiem wiszącym (po zwolnieniu zasobu przez wskaźnik
macierzysty shared_ptr
).
- 14, 22 listopada 2022: czasomierze
- Zadanie 1 (1 pkt).
-
Wypisz najmniejszą i największą wartość jaką można zapisać w typie
long long int
.
Na ilu bitach jest ta liczba zapisywana i ile to będzie cyfr dziesiętnych?
- Zadanie 2 (1 pkt).
-
Jaka jest najbliższa 0 liczba dodatnia dla typów
float
i double
?
Jakie są maksymalne wartości zapisywane w tych typach?
Jaka jest różnica pomiędzy 1 a najmniejszą liczbą >1 w tych typach?
- Zadanie 3 (2 pkt).
-
Zdefiniuj początkowe liczby harmoniczne posługując się statyczną arytmetyką liczb wymiernych
z wykorzystaniem szablonu
ratio
.
Jaką największą liczbę harmoniczną udało Ci się zdefiniować?
- Zadanie 4 (3 pkt).
-
Zdefinuj szablon funkcji, które przeniesie wartość ze wskazanego obiektu do innego obiektu.
Uwzględnij dwa aspekty: po pierwsze obiekt źródłowy może być zadany przez wartość/referencję
albo przez wskaźnik (rozróżnij te dwa przypadki za pomocą cechy typowej
is_pointer
),
a po drugie obiekt docelowy ma być wskazany przez referencję niekoniecznie tego samego typu
(ustal możliwość konwersji za pomocą cechy typowej is_convertible
)
- Zadanie 5 (3 pkt).
-
Stwórz macierze o rozmiarach odpowiednio 100×100, 1000×1000 i 10000×10000
i wypełnij je losowymi wartościami z zakrsu od 0.5 do 2.0.
Następnie podnieś do kwadratu każdą z tych macierzy mierząc czas wykonania tych operacji
za pomocą obiektu
duration
.
Dla małych macierzy powtórz operację wielokrotnie a potem zmierzony czas podziel przez tą wielokrotność.
Do pomiaru czasu użyj czasomierzy opartych na zegarze high_resolution_clock
.
- 28, 29 listopada 2022: funktory
- Zadanie 1 (2 pkt).
-
Zaimplementuj funktor
compose_f_gx_hx
realizujący złożenie dwuargumentowe
f(g(x), h(x)). Podaj przykład jego użycia.
- Zadanie 2 (2 pkt).
-
Zaimplementuj funktor do składania funkcji poprzez wykonywanie ich po kolei.
Funkcja
po_kolei(f1, f2)(x)
powinna wykonać najpierw f1(x)
a potem f2(x)
.
Wartości zwracane przez te funkcje mają być ignorowane.
Funkcja po_kolei()
powinna zwracać taki funktor, aby możliwe było dalsze składanie,
na przykład po_kolei(po_kolei(f1, f2), f3)(x)
.
- Zadanie 3 (5 pkt).
-
Stwórz w swoim programie trzy zbiory danych różnego typu
vector<double>
,
list<string>
i set<int>
.
Wypełnij te kontenery przypadkowymi wartościami (możesz losować albo arbitralnie coś wpisać).
Następnie na zbiorach tych wykonaj pewne obliczenia z użyciem zdefiniowanych przez ciebie funktorów
(obiekty funkcyjne albo lambdy):
-
Wypisz wszystkie wartości z zadanego zakresu (większe od a i mniejsze od b).
-
Wypisz co k-tą wartość zaczynając od pozycji p-tej.
-
Wyznacz średnią arytmetyczną (dotyczy kolekcji z liczbami).
-
Wyznacz element minimalny i maksymalny (zwróć parę wartości).
-
Wyznacz sumę (albo konkatenację dla łańcuchów znakowych) wszystkich elementów.
Do każdego zadania zdefiniuj obiekt funkcyjny (ze stanem wewnętrznym) i użyj go w pętli for-each.
- Zadanie 4 (1 pkt).
-
Zdefiniuj rekurencyjną lambdę do wyliczenia n-tej liczby Fibonacciego
(tylko dla naturalnych wartości n).
Następnie przetestuj tą lambdę na kilku niedużych wartościach
umieszczonych w kolekcji
vector<int>
(umieść tam także jakąś liczbę ujemną).
- 5, 6 grudnia 2022: kolekcje
- Zadanie 1 (5 pkt).
-
Zaprogramuj algorytm stacji rozrządowej Dijkstry, który przekształca wyrażenie arytmetyczne
z postaci infiksowej z nawiasami do postaci postfiksowej bez nawiasów (Odwrotna Notacja Polska).
Wykorzystaj do tego celu kolekcje standardowe.
-
Funkcja realizująca przekształcenie powinna otrzymywać jako argument łańcuch znakowy
string
i zwracać ciąg symboli list<symbol>
.
W swoim algorytmie najpierw podziel wejściowe wyrażenie arytmetyczne na kolejkę
leksemów (liczby, operatory, nawiasy) a dopiero potem zrealizuj przekształcenie z wykorzystaniem stosu.
- Zadanie 2 (5 pkt).
-
Zdefiniuj strukturę danych do przetrzymywania automatu skończonego wraz z jego stanami, funkcjami przejść itd.
Wykorzystaj do tego celu kolekcje standardowe.
-
W programie głównym zdefiniuj dwa proste automaty skończone:
-
automat sprawdzający, czy liczba binarna (alfabet złożony z cyfr dwójkowych: 0, 1) ma taki zapis,
że pomiędzy każdymi kolejnymi jedynkami występuje co najmniej jedno zero;
-
automat sprawdzający, czy liczba dziesiętna (alfabet złożony z cyfr dziesiętnych: 0, 1, ..., 9)
jest podzielna przez 3.
Przetestuj działanie tych automatów na ciągach cyfr przekazanych do programu przez argumenty wywołania.
- 12, 13 grudnia 2022: iteratory i algorytmy
- Zadanie 1 (3 pkt).
-
Pojedyncza osoba jest opisana za pomocą iminia, nazwiska, wieku, wagi i wzrostu
(zdfiniuj klasę reprezentującą osobę
person
).
Dane o 11 osobach są zgromadzone w deku deque<person>
.
Wykonaj po kolei następujące czynności:
- posortuj osoby według współczynnika BMI (funkją porównującą niech będzie lambda);
posortowaną grupę osób wypisz na standardowym wyjściu;
- osoby odchudziły się na obozie sportowym i straciły 10% swojej pierwotnej wagi
(funkją modyfikującą niech będzie lambda);
zmodyfikowaną grupę osób wypisz na standardowym wyjściu;
- podziel osoby na dwie grupy: ciężkie z wagą powyżej 100[kg] i lekkie z wagą
niewiększą niż 100[kg] (użyj lambdy jako predykatu);
wypisz grupę osób po podziale na standardowym wyjściu;
- ustaw osobę o środkowym w tej populacji wzroście na pozycji 5 (pośrodku listy);
wypisz grupę osób po takiej modyfikacji na standardowym wyjściu;
- losowo poprzestawiaj między sobą pierwsze 5 osób a potem ostatnie 5 osób;
wypisz grupę osób po takiej modyfikacji na standardowym wyjściu;
- wypisz osobę najstarszą i najmłodszą na standardowym wyjściu
(nie korzystaj z sortowania danych).
- Zadanie 2 (2 pkt).
-
Pojedynczy punkt jest opisany za pomocą współrzędnych, koloru w postaci RGB i nazwy
(zdfiniuj klasę reprezentującą punkt
point
).
Dane o 17 kolorowych punktach na płaszczyźnie są zgromadzone w liście list<point>
.
Wykonaj po kolei następujące czynności:
- usuń z listy wszystkie punkty, których nazwy są dłuższe niż 5 znaków;
wypisz pozostałe na liście punkty;
- policz ile jest punktów leżących w I, II, III i IV ćwiartce układu współrzędnych;
- posortuj punkty ze względu na ich jasność (luminancja koloru RGB jest określona wzorem
0.3⋅R + 0.59⋅G + 0.11⋅B); wypisz punkty po posortowaniu;
- policz ile jest ciemnych punktów, dla których luminancja ma warość poniżej 64;
prznieś te punty do innej listy i wypisz je.
- Zadanie 3 (2 pkt).
-
Napisz funkcję, która zwróci najczęściej pojawiający się element w zbiorze danych oraz liczbę jego wystąpień.
Dane to liczby całkowite z pewnego wąskiego zakresu umieszczone w wektorze
vector<int>
.
Jeśli więcej niż jeden element pojawia się pojawia się taką samą maksymalną liczbę razy,
to funkcja powinna zwrócić wszystkie je wszystkie - na przykład dla danych {1, 1, 3, 5, 8, 9, 5, 8, 8, 5}
powinny zostać zwrócone dwie pary {5, 3} oraz {8, 3} (pierwsza pozycja w parze to wartość a druga to liczba wystąpień).
- Zadanie 4 (2 pkt).
-
Napisz progam, który oblicza i wyświetla histogram zawierający częstość występowania liter alfabetu angielskiego
(bez rozróżniania małych i dużych liter) w zadanym tekście.
Tekst pobierz z pliku tekstowego, którego nazwę przekażesz do progamu poprzez argumenty wywołania.
Częstość występowania danej litery jest zdefiniowana jako proporcja liczby wystąpień tej litery
w stosunku do wszstkich liter w tekście (częstość musi być określona na podstawie liczby liter a nie rozmiaru tekstu).
- Zadanie 5 (1 pkt).
-
Napisz funkcję, która wygeneruje wszystkie możliwe permutacje podanego napisu
string
.
- 19, 20 grudnia 2022: liczby pseudolosowe
- Zadanie 1 (1 pkt).
-
Zdefiniuj szablon funkcji, która losowo spermutuje zadaną tablicę obiektów.
Każda permutacja ma być jednakowo prawdopodobna.
-
Uwaga: funkcję permutującą zdefiniuj samodzielnie, nie korzystaj z algorytmu
shuffle()
.
- Zadanie 2 (2 pkt).
-
Zdefiniuj własny rozkład prawdopodobieństwa, który będzie losował liczby z zadanego przedziału:
liczby całkowite ze zbioru {a, ..., b-1} albo liczby rzeczywiste z przedziału [a, b).
Liczby ze środka przedziału powinny się pojawiać rzadko a liczby zbliżone do brzegów zadanego przedziału często.
-
Uwaga: można wykorzystać rozkład
uniform_int_distribution<>
oraz uniform_real_distribution<>
ale należy samodzielnie przekształcić otrzymane wartości aby spełniały warunki zadania.
- Zadanie 3 (3 pkt).
-
Napisz program, który wygeneruje 1000 losowych liczb z rozkładem:
- jednostajnym, używając
uniform_real_distribution
;
- dwumianowym, używając
binomial_distribution
;
- normalnym, używając
normal_distribution
.
Wygenerowane liczby zapisz w pliku .csv (dla każdego rozkładu w osobnym pliku).
Zrób w arkuszu kalkulacyjnym wykresy dla danych wygenerowanych w taki sposób,
aby sprawdzić poprawność zastosowanego rozkładu prawdopodobieństwa.
-
Z formatem pliku CSV można się zapoznać na przykład na Wikipedii:
https://pl.wikipedia.org/wiki/CSV_(format_pliku)
https://en.wikipedia.org/wiki/Comma-separated_values
- Zadanie 4 (4 pkt).
-
Napisz program, który wygeneruje losowy tekst złożony tylko z małych
liter alfabetu angielskiego i spacji (bez znaków interpunkcyjnych).
Długość tekstu oraz nazwę pliku .txt do zapisania tekstu podaj poprzez
argumenty wywołania progamu.
Litery w tym tekście mają się pojawiać z częstotliwością zgodną ze statystyką podaną w
tabelce
(rozkład taki musisz więc samodzielnie zdefiniować/zaprogramować).
Kolejne słowa w tekście mają być odzielone pojedynczymi spacjami.
Każde słowo ma mieć losową długość z zakresu od 1 do 12 liter a długości te
mają być wybierane zgodnie z rozkładem dwumianowym.
- 9, 10 stycznia 2023: liczby zespolone
- Zadanie 1 (2 pkt).
-
Zdefiniuj funkcję obliczającą wartość wielomianu zespolonego.
Współczynniki wielomianu umieść w kolekcji vector<complex<double>>.
Wykorzystaj do tego funkcję accumulate i labdę (z modyfikatorem mutable).
- Zadanie 2 (3 pkt).
-
Zdefiniuj funkcje pracujące na liczbach zespolonych, które będą wyliczać wartość:
- funkcji gamma Eulera $\Gamma(z) = \frac{1}{z} \prod_{n=1}^{\infty}
\frac{(1+\frac{1}{n})^z}{1+\frac{z}{n}}$
- i odwrotności tej funkcji $\frac{1}{\Gamma(z)} = ze^{\gamma z} \prod_{n=1}^{\infty}
\left(\left(1+\frac{z}{n}\right)e^{-\frac{z}{n}}\right)$.
Symbol $\gamma$ reprezentuje stałą Eulera-Mascheroniego wynoszącą około 0.5772156649.
Funkcje te mają liczyć wartość funkcji w zadanym punkcie zespolonym z określoną dokładnością
(liczba iteracji).
- Zadanie 3 (5 pkt).
-
Zdefiniuj funkcję pracującą na liczbach zespolonych, które będą wyliczać wartość
funkcji dzeta Riemanna $\zeta(z) = \sum_{n = 1}^{\infty} \left(\frac{1}{n}\right)^z$.
Szereg ten jest zbieżny dla takich $z$, których część rzeczywista jest $>1$.
Funkcja ta ma liczyć wartość funkcji w zadanym punkcie zespolonym z określoną dokładnością
(liczba iteracji).
-
Policz i stablicuj wartości tej funkcji na prostej krytycznej $\Re(z) = 0.5$
z hipotezy Riemanna (musisz użyć innego wzoru).
Wygenerowane liczby zapisz w pliku .csv (w osobnych kolumnach części rzeczywiste i urojone).
Następnie zrób w arkuszu kalkulacyjnym podwójny wykres dla danych wygenerowanych w taki sposób
(nałożone na siebie wykresy dla części rzeczywistych i urojonych).
-
Z formatem pliku CSV można się zapoznać na przykład na Wikipedii:
https://pl.wikipedia.org/wiki/CSV_(format_pliku)
https://en.wikipedia.org/wiki/Comma-separated_values
- 16, 17 stycznia 2023: wyrażenia regularne
- Zadanie 1 (1 pkt).
-
Zdefiniuj wyrażenie regularne do rozpoznawania prawidłowo zapisanej godziny.
Zapis godziny to liczba godzin (0-23) i liczba minut (0-59) oddzielone dwukropkiem
(obydwie liczby zapisane za pomoca dwóch cyfr); opcjonalnie w godzinie mogą sie pojawić sekundy (0-59).
-
Przykłady prawidłowo zapisanych godzin:
14:17, 09:15, 23:37:08.
Przykłady wadliwie zapisanych godzin:
14.16 (kropka zamiast dwukropka),
19:5 (minuty zapisane jedną cyfrą),
21:32:07,10 (zbyt duża dokładność).
-
Przetestuj wyrażenie na danych wprowadzonych ze standardowego wejścia.
- Zadanie 2 (2 pkt).
-
Zdefiniuj wyrażenie regularne do rozpoznawania prawidłowo zapisanej daty.
Zapis daty składa się z numeru dnia w miesiącu (1-31), numeru miesiąca(1-12) i roku;
liczby te mają być od siebie oddzielone minusem (numer dnia i miesiąca zapisane za pomoca
dwóch cyfr a rok za pomocą czterech).
Zadbaj o sprawdzanie górnych ograniczeń na liczbę dni w poszczególnych miesiącach
(nie musisz sprawdzać przestępności roku, chociaż byłoby to ciekawe wyzwanie - można założyć, że luty ma 28 dni).
-
Przykłady prawidłowo zapisanych dat:
15-09-1999, 05-12-2018, 28-02-2021.
Przykłady wadliwie zapisanych dat:
03/07/1917 (ukośnik zamiast myślnika),
6-3-1945 (dni i miesiące zapisane jedną cyfrą),
29-02-2022 (liczba dni w miesiącu lutym przekracza 28).
-
Przetestuj wyrażenie na danych wprowadzonych ze standardowego wejścia.
- Zadanie 3 (2 pkt).
-
Zdefiniuj wyrażenie regularne do rozpoznawania prawidłowo zapisanej nazwy miejscowości
w Polsce (nie używaj polskich naków diakrytycznych, tylko podobnych liter w alfabecie angielskim,
na przykład zamiast litery ż użyj litery z).
Zapis nazwy miejscowości to ciąg słów, gdzie każde słowo rozpoczyna się z dużej litery.
Poszczególne słowa mogą być odseparowane dowolną liczbą białych znaków.
W nazwach miejscowości zdarzają się też połączenia słów za pomocą myślnika (w okolicach
łącznika nie występują białe znaki).
-
Przykłady prawidłowo zapisanych nazw miejscowości:
Wroclaw, Bielsko-Biala, Tarnowskie Gory.
Przykłady wadliwie zapisanych nazw miejscowości:
WARSZAWA (cała nazwa zapisana dużymi literami),
Zle mieso (druga część nazwy z małej litery),
Zimna-Wodka-07 (trzecia część nazwy zawiera cyfry).
-
Przetestuj wyrażenie na danych wprowadzonych ze standardowego wejścia.
- Zadanie 4 (2 pkt).
-
Zdefiniuj wyrażenie regularne do rozpoznawania prawidłowo zapisanej liczby zespolonej.
Zapis liczby zespolonej składa się z dwóch liczb rzeczywistych (z opcjonalna możliwością
wystąpienia części ułamkowej po kropce dziesiętnej) połączonych znakiem plusa albo minusa
(w pierwszej liczbie opcjonalny znak minusa), przy czym druga liczba jest zakończona małą
albo dużą literą "i"; całość jest ujęta w nawiasy okrągłe.
-
Przykłady prawidłowo zapisanych liczb zespolonych:
(12+3I), (7.4-0.5i), (2+0.01i).
Przykłady wadliwie zapisanych liczb zespolonych:
3+4I (brak nawiasów okrągłych),
(3,14-2,72i) (przecinek zamiast kropki dziesiętnej),
(5.7i) (brak części rzeczywistej).
-
Przetestuj wyrażenie na danych wprowadzonych ze standardowego wejścia.
- Zadanie 5 (3 pkt).
-
Zadefiniuj wyrażenie regularne wykrywające hiperłącze w dokumencie HTML
- chodzi o znacznik
<a href="..."> ... </a>
.
Następnie użyj tego wyrażenia do wypisania na standardowym wyjściu
wszystkich znalezionych w tekście hiperłączy (bez opakowania w postaci
znacznia <a>
- sama treść atrybutu href
).
-
Przetestuj wyrażenie na tekście ze wskazanych za pomocą argumentów wywołania programu
plików typu HTML (html, php, itp.).
- 23, 24 stycznia 2023: iteratory strumieniowe i plikowe
- Zadanie 1 (2 pkt).
-
Odczytaj ze standardowego wejścia ciąg liczb rzeczywistych pooddzielanych białymi znakami.
Używając iteratora strumieniowego
istream_iterator
odczytaj te liczby, zapisz
w wektorze a następnie policz średnią arytmetyczną i odchylenie standardowe dla tego zbioru
danych i wypisz wyniki na standardowym wyjściu z dokładnością do 3 miejsc po kropce dziesiętnej.
- Zadanie 2 (2 pkt).
-
Niech $\Phi(n)$ oznacza funkcję Eulera (tocjent), która dla każdej dodatniej liczby naturalnej
zwraca liczbę liczb naturalnych nie większych od $n$ i względnie pierwszych z $n$.
Dla zadanej wartości $k$ stablicuj kolejne wartości tocjenta $\Phi(1), \Phi(2), \ldots, \Phi(k)$
a następnie zapisz je do pliku
phi.txt
, używając iteratora strumieninowego
ostream_iterator
z separatorem w postaci średnika i spacji "; "
.
Wartość $k$ przekaż do programu poprzez argumenty wywołania.
- Zadanie 3 (2 pkt).
-
Napisz program, który sprawdzi czy w lokalnym systemie plików istnieją podane pliki lub foldery.
Jeśli tak, to wypisz ich najważniejsze parametry (ścieżka kanoniczna, data ostatniej modyfikacji,
rozmiar dla pliku itp.).
Nazwy plików i folderów przekaż do programu poprzez argumenty wywołania.
- Zadanie 4 (2 pkt).
-
Napisz program, który wypisze zawartość wskazanego katalogu w lokalnym systemie plików.
Jeśli podany przez użytkownika katalog nie istnieje, to wypisz stosowną informację na standardowe
wyjście dla błędów.
Najpierw wypisz nazwę kanoniczną wskazanego katalogu a potem jego zawartość,
przy czym najpierw wypisz katalogi (w kolejności alfabetycznej) a potem pliki
(również w kolejności alfabetycznej).
Wypisując zawartość folderu posłuż się iteratorem
directory_iterator
.
Nazwę katalogu pobierz ze standardowego wejścia.
- Zadanie 5 (2 pkt).
-
Napisz program, który policzy i wypisze sumę rozmiarów wszystkich plików we wskazanym
katalogi i jego podkatalogach.
Jeśli podany przez użytkownika katalog nie istnieje, to wypisz stosowną informacjęna standardowe
wyjście dla błędów.
Analizując zawartość katalogu i podkatalogów posłuż się iteratorem
recursive_directory_iterator
.
Nazwę katalogu pobierz ze standardowego wejścia.
- 30, 31 stycznia 2023: lokalizacja
- Zadanie 1 (2 pkt).
-
Zdefiniuj napis typu
wstring
zawierający wszystkie polskie znaki diakrytyczne
i wypisz go na standardowym wyjściu wcout
.
Napis powinien być sensownym zdaniem w języku polskim!
- Zadanie 2 (3 pkt).
-
Wypisz w trzech różnych lokalizacjach następujące dane (kilka oznacza >2):
- kilka liczb całkowitych i zmiennopozycyjnych;
- kilka wartości pieniężnych;
- bieżącą datę i godzinę.
- Zadanie 3 (2 pkt).
-
Przekonwertuj plik tekstowy używający kodowania UTF-8 na Unicode.
- Zadanie 4 (3 pkt).
-
W wektorze
vector<wstring>
znajdują się nazwy różnych zwierząt i roślin
(wstaw do kontenera kilkanaście różnych nazw).
Posortuj je używając kolatora dla polskiej lokalizacji a potem wypisz na standardowe wyjście.
- 6, 7 lutego 2023: metaprogramowanie
- Zadanie 1 (1 pkt).
-
Wykorzystując metaprogramowanie zdefiniuj szablon obiektu funkcyjnego,
pozwalającego obliczyć na poziomie kompilacji n-tą liczbę Lucasa
dla liczby naturalnej n ≥ 0.
Funkcja powinna działać (w trakcie kompilacji) w liniowym czasie O(n).
- Zadanie 2 (2 pkt).
-
Wykorzystując metaprogramowanie zdefiniuj szablon obiektu funkcyjnego,
pozwalającego obliczyć na poziomie kompilacji współczynnik dwumianowy (nk)
dla liczb naturalnych 0 ≤ k ≤ n.
Funkcja powinna działać (w trakcie kompilacji) w liniowym czasie O(n).
- Zadanie 3 (1 pkt).
-
Wykorzystując metaprogramowanie zdefiniuj szablon obiektu funkcyjnego,
pozwalającego obliczyć na poziomie kompilacji największy wspólny dzielnik NWD(a, b)
dla liczb naturalnych a, b ≥ 1
dla naturalnych liczb 0 ≤ k ≤ n.
Funkcja powinna działać (w trakcie kompilacji) w logarytmicznym czasie O(log a + log b).
- Zadanie 4 (2 pkt).
-
Wykorzystując metaprogramowanie zdefiniuj szablon funkcji liczącej iloczyn skalarny dwóch wektorów:
template<size_t N> double inner(double *x, double *y);
Parametrem szablonu ma być dlugość mnożonych wektorów.
Zmodyfikuj poprzedni szablon funkcji liczącej iloczyn skalarny w taki sposób,
aby drugim parametrem był typ danych:
template<size_t N, typename T = double> T inner(T *x, T *y);
- Zadanie 5 (4 pkt).
-
Wykorzystując metaprogramowanie zdefiniuj szablon klasy będącej opakowanien dla obiektu
określonego w parametrze typu
template<typename T> struct obj_holder
.
Opakowanie to ma konieczne zaalokować pamięć dla obiektu na stosie, jeśli
jest on mały (jego rozmiar jest niewięszy niż sizeof(string)
) i nie jest tablicą
albo na stercie w przeciwnym przypadku.
W strukturze obj_holder
zdefiniuj alias type
dla docelowego typu
ustalony w oparciu o selektor std::conditional<>
- będzie to albo
struktura on_stack
(dla małych obiektów) albo on_heap
(dla dużych
obiektów tworzonych dynamicznie na stercie, pamiętaj aby w destruktorze tego opakowania
zwolnić przydzieloną pamięć).
W obu tych strukturach zaimplementuj semantykę wskaźników, czyli operator wyłuskania
(gwiadka *
) udostępniający referencję do obiektu i operator dostępu do składowych
(strzałka ->
) udostępniający adres obiektu.
W kolejnym kroku zdefiniuj szablon klasy będącej opakowanien dla tablicy obiektów
określonego w parametrze typu template<typename T> struct arr_holder
.
Zaadoptuj poprzednie definicje na przypadek dotyczący tablic - struktura array_on_heap
dla małych tablic tworzonych na stercie i albo array_in_file
dla dużych tablic
przechowywanych w plikach o dostępie swobodnym (pojęcie "mały" i "duży"
w odniesieniu do tablic należy rozsądnie doprecyzować).
W obu tych strukturach zaimplementuj semantykę indeksowania.
Skos
Ranking
- Prognozowane oceny po wszystkich 12 listach zadań
- wspólne zestawienie dla wszystkich grup (poniedziałek 18, wtorek 16 i 18).
- Ostatnia szansa na poprawienie oceny na początku lutego.
wykłady
11 października 2022 r: nowe elementy języka w C++
organizacja zajęć
nowe elementy języka C++ 11/14/17/20
- trójznaki
- surowe łańcuchy znakowe
- pętla for-each
- jednolita inicjalizacja
- stypizowane typy wyliczeniowe
- dedukcja typów za pomocą
auto
i decltype
- instrukcje if i switch-case z częścią inicjalizującą zmienne lokalne dla tych instrukcji
- instrukcja constexpr-if
- operatory porównań
slajdy: organizacja.pdf, nowe.pdf
25 października 2022 r: sprytne wskaźniki
sprytne wskaźniki
- wskaźniki współdzielone
shared_ptr
- słabe wskaźniki
weak_ptr
- wskaźniki unikatowe
unique_ptr
slajdy: wskazniki.pdf
8 listopada 2022 r: czasomierze
zegary
- limity liczbowe
- cechy typowe
- współczynniki ułamkowe
ratio
- zegary
clock
, punkty time_point
i odcinki czasowe duration
- czas w systemie POSIX
slajdy: czasomierze.pdf
22 listopada 2022 r: funktory
29 listopada 2022 r: kolekcje standardowe
kolekcje standardowe
- wartościowa semantyka kolekcji
- elementy kolekcji
- rodzaje kolekcji i ich implementacja
- tablice
- wektory i deki
- listy dwukierunkowe i jednokierunkowe
- zbiory i multizbiory
- mapy i multimapy
- zbiory i mapy nieuporządkowane
- adaptery kolekcji
slajdy: kolekcje.pdf
6 grudnia 2022 r: iteratory i algorytmy
iteratory
- klasyfikacja iteratorów
- iteratory wyjściowe i wejściowe
- iteratory postępujące i dwukierunkowe
- iteratory dostępu swobodnego
- iteratory i zakresy danych
- iteratory strumieniowe
algorytmy
- klasyfikacja algorytmów
- iteratory i zakresy w algorytmach
- algorytm
for_each
- algorytmy niemodyfikujące:
- zliczanie elementów
count
- wartość minimalna i maksymalna
min_element
, max_element
, minmax_element
- wyszukiwanie pierwszego pasującego elementu
find
- wyszukiwanie pierwszego podzakresu
search
- porównywanie zakresów
equal
- wykrywanie sekwencji tych samych elementów w innym porządku
is_permutation
- porównywanie leksykograficzne
lexicographical_compare
- sprawdzanie czy zakres jest uporządkowany
is_sorted
, is_sorted_until
- sprawdzanie rozdzielenia elementów
is_partitioned
, partition_point
- sprawdzanie czy zakres jest kopcem
is_heap
, is_heap_until
- wszystkie
all_of
, którykolwiek any_of
, żaden none_of
- algorytmy modyfikujące:
- kopiowanie
copy
, copy_backward
- przenoszenie elementów między zakresami
move
, move_backward
- przekształcanie elementów
transform
- wymienianie elementów
swap_ranges
- przypisywanie tej samej wartości
fill
- przypisywanie wartości generowanych
generate
- zastępowanie wartości wewnątrz zakresu
replace
, replace_copy
- algorytmy usuwające:
- usuwanie elementów z zakresu
remove
, remove_copy
- usuwanie kolejnych powtórzeń
unique
, unique_copy
- algorytmy mutujące:
- odwracanie kolejności elementów
reverse
, reverse_copy
- przesunięcia cykliczne elementów
rotate
, rotate_copy
- permutacje elementów
next_permutation
, prev_permutation
- tasowanie elementów
random
, random_shuffle
- rozdzielenie elementów
partition
, stable_partition
, partition_copy
- algorytmy sortujące:
- sortowanie elementów
sort
, stable_sort
- sortowanie częściowe
partial_sort
, partial_sort_copy
- wybór n-tego co do wielkości elementu
nth_element
- algorytmy sortujące:
- sortowanie elementów
sort
, stable_sort
- sortowanie częściowe
partial_sort
, partial_sort_copy
- wybór n-tego co do wielkości elementu
nth_element
- algorytmy kopcowe
- utworzenie kopca
make_heap
- wstawienie elementu do kopca
push_heap
- przesunięcie elementu największego na koniec kopca
pop_heap
- sortowanie kopcowe
sort_heap
- algorytmy przeznaczone dla zakresów posortowanych
- sprawdzanie obecności elementu
binary_search
- wyszukiwanie pierwszej lub ostatniej możliwej pozycji
lower_bound
, upper_bound
- scalanie elementów
merge
, inplace_merge
- wyznaczanie sumy dwóch posortowanych zbiorów
set_union
- wyznaczanie iloczynu dwóch posortowanych zbiorów
set_intersection
- wyznaczanie różnicy dwóch posortowanych zbiorów
set_difference
, set_symmetric_difference
- algorytmy numeryczne
- iterowanie i kumulowanie obliczeń
accumulate
- iloczynu skalarny
inner_product
- sumy częściowe
partial_sum
slajdy: iteratory.pdf, (w trakcie edycji)
13 grudnia 2022 r: generatory liczb pseudolosowych
generatory liczb pseudolosowych
- mechanizmy losowości
- rozkłady
slajdy: losowe.pdf
20 grudnia 2022 r: liczby zespolone
liczby zespolone
- szablon klasy
complex<>
- funkcje i operatory działające na liczbach zespolonych
slajdy: zespolone.pdf
3 stycznia 2023 r: wyrażenia regularne
wyrażenia regularne
- budowa wyrażeń regularnych
- klasa
regex
- funkcje dopasowujące
- podwyrażenia
- iterowanie po dopasowaniach
slajdy: regularne.pdf
10 stycznia 2023 r: iteratory strumieniowe i plikowe
iteratory strumieniowe i plikowe
- iterator strumieniowy wejściowy
istream_iterator
- iterator strumieniowy wyjściowy
ostream_iterator
- klasa
std::filesystem::path
i funkcja std::filesystem::exists()
- iteratory po systemie plików
directory_iterator
i recursive_directory_iterator
slajdy: pliki.pdf
17 stycznia 2023 r: lokalizacja
zestawy znaków
- kodowanie znaków
- zestawy znaków obsługiwane w C++
- literały napisowe
- cechy znaków
char_traits
lokalizacja
- obiekty ustawień lokalnych
locale
- aspekty ustawień lokalnych
facet
- formatowanie liczb, wartości pieniężnych, czasu i daty
- klasyfikacja znaków
- konwersja standardów kodowania znaków
- sortowanie łańcuchów znakowych
slajdy: lokalizacja.pdf
24 stycznia 2023 r: metaprogramowanie
metaprogramowanie
- przypadki użycia metaprogramowania
- funkcje typowe
- aliasy i predykaty typów
- trejty które wiążą typy z ich właściwościami
- struktury sterujące
Conditional
i Select
- iteracja za pomocą szablonów rekurencyjnych
- definicja warunkowa
Enable_if
slajdy: meta.pdf
31 stycznia 2023 r: współbieżność wysokopoziomowa
współbieżność wysokopoziomowa
- wątki w procesie jako niezależne ścieżki obliczeń
- wątki sprzętowe, systemowe i programowe
thread
- asynchroniczne wykonywanie zadań za pomocą funkcji
async()
- strategie wykonywania zadań przez funkcję
async()
: launch::async
i launch::deferred
- klasy reprezentujące wynik działania funkcji zrealizowanej przez wątek
future<>
i shared_future<>
- odbieranie wyniku od futury za pomocą funkcji
get()
- funkcja
get()
i valid()
działająca na obiekcie futury
- oczekiwanie na zakończenie i wynik zadania w futurze za pomocą funkcji
wait_for()
i wait_until()
- status futury:
future_status::deferred
, future_status::timeout
, future_status::ready
- obsługa wyjątków w trakcie pracy wątku
- futury współdzielone
shared_future<>
- wstrzymanie realizacji zadania za pomocą funkcji
yield()
- synchroniazacja pracy wątków za pomocą funkcji
join()
- usypianie wątków za pomocą funkcji
this_thread::sleep_for()
slajdy: wspolbiezne.pdf