Kolekcje i algorytmy

STL - Standard Template Library

• Standard Template Library Programmer's Guide
• Kontenery (kolekcje) STL Containers
  • vector - tablica o zwiększającym się rozmiarze
  • forward_list lista jednokierunkowa i |list lista dwukierunkowa, sekwencja elementów o błyskawicznym czasie wstawiania i usuwania elementów
  • stack stos (kolejka LIFO), queue kolejka FIFO
  • set zbiór (uporządkowany)
  • map słownik (uporządkowany względem kluczy)
    map<char,int> slownik
• STL Algorithms
• Wskaźniki na funkcję, funktory i lambdy
  • nazwa funkcji jest wskaznikiem do tej funkcji
  • obiekt funkcyjny (funktor), klasa przeciążająca operator wywołania funkcji ()
  • 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 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ę 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ściowymstd::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 <sstream>
 
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 <cctype> :
  • isalpha - czy znak?
  • tolower - zamien na małą litrę
  • toupper - zamień na wielką literę
• z biblioteki <iostream> :
  • get(char z) - weź znak ze strumienia wejściowego
  • put(char z) - połóż znak w strumieniu wyjściowym
  • eof() - czy koniec pliku?

Dodatkowe ćwiczenia:

• wypisz 3 najczęściej występujące wrazy. Wykorzystaj w tum celu algorytm 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 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ę 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} $$

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:

1. użytkownik podaje wartość całkowitą n określającą liczbę strzałów do tarczy
2. tworzony jest pojemnik o rozmiarze n zawierający jako elementy punty na płaszczyźnie. W roli pojemnika wykorzystaj kolekcję vector, forward_list lub 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 pair<T1, T2>
3. wypełnij pojemnik punktami o losowych współrzędnych $[x,y]$ z zakresu $[0, 1]$. Wykorzystaj w tym celu szablon funkcji 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 rand, która zwraca losową wartość całkowitą z zakresu od 0 do RAND_MAX.
4. 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 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.
5. 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 Zadanie 10