Kolekcje i algorytmy

STL - Standard Template Library

Wskaźnik do funkcji 

bool czy_parzysta(int n)
{
  return (n +1) % 2;
}
 
remove_if(lista.begin(), lista.end(), czy_parzysta);

Funkcja zwracająca wartość logiczną bool to predykat.

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 porządku alfabetycznym listę wyrazów występujących w pliku tekstowym wskazanym przez użytkownika.

Program powinien:

  • wczytać z pliku tekstowego wszystkie wyrazy, tj. ciągi znaków składające się z liter A-Za-z (małe i wielkie litery traktujemy równoważnie)
  • policzyć liczbę wystąpień każdego wyrazu
  • wypisać na standardowe wyjście posortowaną listę wyrazów wraz z liczbą ich wystąpień w formacie:
  ala      5
  kota     2
  ma       1

Do realizacji zadania wykorzystaj słownik map, którego elementami jest para klucz-wartość (pair<Key,Value>) , gdzie kluczem będzie wyraz a wartością związaną z kluczem będzie liczba całkowita określająca liczbę wystąpień wyrazu (klucza) w tekście. Kolekcja map automatycznie umieszcza elementy w drzewie binarnym posortowanym względem klucza.

Zaimplementuj klasę Wyraz reprezentującą pojedynczy wyraz (łańcuch znakowy składający się z liter A-Za-z), która spełnia poniższą specyfikację:

  • klasa 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ą liczbą 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 wyrazów małe i wielkie litery traktujemy równoważne, wiec wyrazy „Ala”, „ala” i „ALA” będą traktowane jako 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> :
  • z biblioteki <iostream> :

Dodatkowe ćwiczenia:

  1. wypisz 3 najczęściej występujące wrazy. Wykorzystaj w tym celu algorytm sort oraz dodatkową funkcję porównującą dwa elementy słownika ze względu na liczbę wystąpień
  2. 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ść
  3. 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 najczesciej wystepujace 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