====== Kolekcje i algorytmy ====== ===== STL - Standard Template Library ===== * [[http://www.sgi.com/tech/stl/|Standard Template Library Programmer's Guide]] * Kontenery (kolekcje) [[http://www.cplusplus.com/reference/stl/|STL Containers]] * [[https://cplusplus.com/reference/vector/vector/|vector]] - tablica o zwiększającym się rozmiarze * [[https://cplusplus.com/reference/forward_list/forward_list/forward_list|forward_list]] lista jednokierunkowa i |[[https://cplusplus.com/reference/list/list/|list]] lista dwukierunkowa, sekwencja elementów o błyskawicznym czasie wstawiania i usuwania elementów * [[https://cplusplus.com/reference/stack/stack/|stack]] stos (kolejka LIFO), [[https://cplusplus.com/reference/queue/queue/|queue]] kolejka FIFO * [[https://cplusplus.com/reference/set/set/|set]] zbiór (uporządkowany) * [[https://cplusplus.com/reference/map/map/|map]] słownik (uporządkowany względem kluczy) \\ {{zajecia:po:map_stl.png?300|}} ''map slownik'' * [[http://www.cplusplus.com/reference/algorithm/|STL Algorithms]] * [[https://cppdev.pl/funkcje#obiekt-funkcyjny-funktor|Wskaźniki na funkcję, funktory i lambdy]] * nazwa funkcji jest wskaznikiem do tej funkcji * [[https://cpp0x.pl/dokumentacja/funktor/1143|obiekt funkcyjny]] (funktor), klasa przeciążająca operator wywołania funkcji ''()'' * [[https://pl.wikibooks.org/wiki/C%2B%2B/Funkcje_anonimowe|funkcje anonimowe (lambda)]] **Wskaźnik do funkcji** bool czy_parzysta(int n) { return (n +1) % 2; } remove_if(lista.begin(), lista.end(), czy_parzysta); **Obiekt funkcyjny** class A { public: bool operator()(int n) { return (n +1) % 2; } }; A a; remove_if(lista.begin(), lista.end(), a); **Funkcje lambda** remove_if(lista.begin(), lista.end(), [ ](int n){ return (n+1)%2; } ); ===== Ćwiczenie: słownik wyrazów ====== Napisz program, który wypisze w porzadku alfabetycznym słownik wyrazów występujących w pliku tekstowym. Nazwę pliku (lub ścieżkę do pliku) podaje użytkownik na początku działania programu. Jeżeli podany plik udało się otworzyc i przeczytać to program wypisze posortowaną listę wyrazów z pliku wraz z informacją o liczbie wystąpień danego słowa w pliku. Przykładowe wyjście programu: Nazwa pliku: tekst.txt ala 5 kota 2 ma 1 Do realizacji zadania wykorzystaj kontener słownik **[[http://www.cplusplus.com/reference/map/map/|map]]**, którego elementami jest para (''pair'') składająca się z wyrazu (klucz słownika) oraz liczby całkowitej określającej liczbę wystąpień wyrazu w tekście. Kolekcja ''map'' automatycznie umieszcza elementy w drzewie binarnym posortowanym względem klucza. Zaimplementuj klasę ''**Wyraz**'' reprezentująca pojedynczy wyraz z tekstu, czyli łańcuchów znakowy składający się z liter 'A-Za-z'. Klasa ''**Wyraz**'' posiada następującą specyfikację: * wykorzystuje kolekcję **[[http://www.cplusplus.com/reference/vector/vector/|vector]]** do przechowywania liter (ewentualnie może wykorzystywać tablicę znaków, obiekt ''string'', lub szablon ''Wektor'' z poprzednich zajęć). * przeciąża operator ''<<'' wypisujący przechowywany wyraz w strumieniu wyjściowym''std::ostream'' * przeciąża operator ''>>'' czytający pierwszy napotkany wyraz ze strumienia wejściowego ''std::istream''. Pamiętaj, że wyrazy w strumieniu mogą być oddzielone od siebie dowolną ilością znaków nie będących literami. Przy wczytywaniu napisu należy zignorować wszystkie początkowe znaki nie będące literami. Jeśli nastąpił błąd odczytu lub w strumieniu nie znaleziono wyrazu to wówczas tworzony jest wyraz pusty. * przeciąża operator ''<'' porównujący dwa wyrazy alfabetycznie. Przy porównywaniu małe i duże litery traktujemy równoważne, wiec wyraz "Ala", "ala" i "ALA" będą identyczne. * konstruktor domniemany tworzy pusty wyraz * konstruktor kopiujący * funkcja składowa ''Dlugosc()'' zwraca liczbę liter w wyrazie Przykład działania klasy ''Wyraz'': std::stringstream ss; // z biblioteki ss << "!@&#&*(Ala_ma++kota" << endl; Wyraz w; while(!ss.eof()) { ss >> w; cout << w << endl; } Wynik działania: Ala ma kota Przydatne funkcje: * z biblioteki '''' : * ''[[http://www.cplusplus.com/reference/cctype/isalpha/|isalpha]]'' - czy znak? * ''[[http://www.cplusplus.com/reference/cctype/tolower/|tolower]]'' - zamien na małą litrę * ''[[http://www.cplusplus.com/reference/cctype/toupper/|toupper]]'' - zamień na wielką literę * z biblioteki '''' : * ''[[http://www.cplusplus.com/reference/istream/istream/get/|get(char z)]]'' - weź znak ze strumienia wejściowego * ''[[http://www.cplusplus.com/reference/istream/istream/put|put(char z)]]'' - połóż znak w strumieniu wyjściowym * ''[[http://www.cplusplus.com/reference/istream/istream/eof|eof()]]'' - czy koniec pliku? Dodatkowe ćwiczenia: * wypisz 3 najczęściej występujące wrazy. Wykorzystaj w tum celu algorytm [[https://cplusplus.com/reference/algorithm/sort/|sort]] oraz dodatkową funkcję porównującą dwa elementy słownika ze względu na liczbę wystąpień * wypisz najdłuższy wyraz ze słownika. Wykorzystaj w tym celu algorytm ''[[https://cplusplus.com/reference/algorithm/max_element/|max_element]]'' oraz obiekt funkcyjny służący do porównania dwóch wyrazów ze względu na długość * wypisz w osobnych grupach wyrazy o liczbie znaków ''n=1, 2, 3, ...'' aż do najdłuższego wyrazu. Wykorzystaj w tym celu funkcję [[https://cplusplus.com/reference/algorithm/find_if/|find_if]] oraz funkcję lambda sprawdzającą warunek, czy wyraz posiada długość ''n'' Przykładowe działanie programu dla pliku ''containers.txt'' zawierającego treść: ''The STL contains sequence containers and associative containers. The containers are objects that store data.'' Podaj nazwe pliku: containers.txt and 1 are 1 associative 1 containers 3 contains 1 data 1 objects 1 sequence 1 STL 1 store 1 that 1 The 2 Trzy najdluzsze wyrazy 3 : containers 2 : The 1 : and Najdluzszy wyraz to: associative, liczba znakow: 11 Wyrazy pogrupowane wzgledem liczby znakow: 3 : and, are, STL, The, 4 : data, that, 5 : store, 7 : objects, 8 : contains, sequence, 10 : containers, 11 : associative, ===== Zadanie 10: Liczba PI ===== Napisz program, który wyznaczy przybliżoną wartość liczby $\pi$ za pomocą całkowania Monte Carlo. Metoda Monte Carlo sprowadza się do wyznaczenia pola powierzchni ćwiartki koła o promieniu $r=1$ za pomocą procesu losowego, w którym wykonujemy $n$ losowań punktów w obszaru kwadratu o boku 1. Przybliżona wartość pola ćwiartki koła będzie równa $\frac{k}{n}$, gdzie $k$ to liczba trafień w tarczę koła (ćwiartki) a $n$ to liczba wszystkich losowań. Ćwiartka koła na odcinku $[0,1]$ opisana jest funkcją $$y = \sqrt{1-x^2} $$ {{ zajecia:mn1_2021_2:mc_pi.png?400 |}} Z wzoru na pole koła wynika że pole ćwiartki koła $P = \frac{1}{4}\pi r^2 = \frac{\pi}{4}$, stąd przybliżona wartość $$\pi = 4\cdot P \approx 4 \frac{k}{n} $$. Program działa w następujący sposób: - użytkownik podaje wartość całkowitą ''n'' określającą liczbę strzałów do tarczy - tworzony jest pojemnik o rozmiarze ''n'' zawierający jako elementy punty na płaszczyźnie. W roli pojemnika wykorzystaj kolekcję [[https://cplusplus.com/reference/vector/vector/|vector]], [[https://cplusplus.com/reference/forward_list/forward_list/|forward_list]] lub [[https://cplusplus.com/reference/list/list/|list]]. Pojemnik przechowuje punkty na płaszczyźnie określone wpółrzędnymi $(x, y)$ o wartościach rzeczywistych. Utwórz klasę reprezentującą punkt lub wykorzystaj szablon [[https://cplusplus.com/reference/utility/pair/?kw=pair|pair]] - wypełnij pojemnik punktami o losowych współrzędnych $[x,y]$ z zakresu $[0, 1]$. Wykorzystaj w tym celu szablon funkcji [[https://cplusplus.com/reference/algorithm/generate/|generate]]. Trzecim argumentem tej funkcji jest generator, czyli funkcja zwracająca pojedynczy punkt o losowych współrzędnych. Zrealizuj ten generator za pomocą funkcji, obiektu funkcyjnego lub funkcji lambda. Losowanie wartości z zakresu $[0,1]$ możesz zrealizowac za pomocą funkcji [[https://cplusplus.com/reference/cstdlib/rand/?kw=rand|rand]], która zwraca losową wartość całkowitą z zakresu od 0 do ''RAND_MAX''. - policz liczbę punktów w pojemniku spełniających warunek $x^2+y^2 \le 1$, czyli liczbę trafień w tarczę. W tym celu wykorzystaj algorytm [[https://cplusplus.com/reference/algorithm/count_if/|count_if]], który wyznacza liczbę elementów kolekcji spełniających określony warunek. Trzecim argumentem tej funkcji jest predykat, czyli funkcja, której argumentem jest element kolekcji a wynikiem jest wartość typu ''bool''. - wypisz uzyskaną wyżej liczbę trafień ''k'' oraz przybliżoną wartość liczby $\pi$ równą $4 \frac{k}{n}$. **Przykładowy wynik działania programu** n=100000 Liczba trafien: 78538 pi=3.14152 Rozwiązanie w postaci plików nagłówkowych ''*.h'' i źródłowych ''*.cpp'' umieść w Moodle [[https://moodle.umk.pl/mod/assign/view.php?id=211383|Zadanie 10]]