Lab 01 - vector, algorytmy

Wstęp - kontener vector

W C++ kontenerem lub kolekcją nazywamy strukturę danych, która pozwala na przechowywanie wielu elementów tego samego typu.

Najprostszym kontenerem, który będziemy wykorzystywać podczas niektórych z dzisiejszych zadań jest vector. Kontenery z biblioteki standardowej zdefiniowane są w nagłówkach o nazwie takiej samej jak nazwa kontenera, stąd aby użyć vectora musimy załączyć jego nagłówek:

#include <vector>

Wewnętrznie wektor jest tablicą, "opakowaną" w klasę dostarczającą interfejs ułatwiający wiele czynności takich jak zmianę jego rozmiaru, dodawanie elementów, kopiowanie całego wektora czy użycie algorytmów.

Tworzenie wektorów

Klasa vector jest szablonem - może przechowywać dowolny typ zmiennych, obiektów, jednak musi on być znany w trakcie kompilacji i podajemy go w momencie tworzenia wektora w nawiasach ostrych:

std::vector<int> v1; // utworzenie pustego wektora v1 przechowującego elementy typu int

vector możemy utworzyć na kilka sposobów, poza pustym kontenerem (jak powyżej), możemy od razu zainicjalizować go wartościami:

std::vector<int> some_zeros(5); // 5-elementowy wektor o domyślnych wartościach (0 dla typów liczbowych)
std::vector<double> four_pies(4, 3.14); // 4-elementowy wektor, wszystkie elementy o wartości 3.14

Możliwe jest również użycie listy inicjalizacyjnej:

std::vector<std::string> messages = {"nope", "cool", "OK"}; // 3-elementowy wektor z podanymi wartościami

Wektory mogą przechowywać klasy, struktury; elementami wektora mogą być też inne kolekcje, np. kolejny wektor, pozwalając na stworzenie wielowymiarowych struktur:

std::vector<std::vector<int>> matrix; // wektor wektorów (struktura dwuwymiarowa)

Dostęp do elementów wektora

Ponieważ wektor jest wewnętrznie tablicą, możliwy jest swobodny dostęp do poszczególnych elementów, dokładnie tak jak w tablicy (pamiętaj, że indeksowanie zaczyna się od 0):

std::vector<double> numbers = {1.0, -100, 1.4142};
std::cout << numbers[1] << std::endl; // wypisze -100
numbers[2] = 3.14; // zmodyfikuje trzeci element

Bieżący rozmiar wektora można sprawdzić metodą size(). W ten sposób możemy np. przejrzeć kontener tak jak tablicę:

for (int i = 0; i < numbers.size(); i++) {
   std::cout << numbers[i] << std::endl;
}

W przypadku kontenerów dużym ułatwieniem jest możliwość korzystania z pętli skróconej typu range-based for loop:

                            // wykonuje pętlę dla każdego elementu w numbers, w każdym przebiegu
for (double &n : numbers) { // tworzy zmienną n - referencję do danego elementu
    std::cout << n << std::endl;
}

Możliwy jest również dostęp z wykorzystaniem iteratorów - obiektów zachowujących się jak wskaźniki, ale dedykowanych konkretnemu typowi kontenera. Więcej o iteratorach dowiesz się na kolejnych zajęciach.

for (std::vector<double>::iterator it = numbers.begin(); it != numbers.end(); it++) {
    std::cout << *it << std::endl; // it zachowuje się jak wskaźnik, musimy wyłuskać spod niego wartość
}

Modyfikacja wektora

Najczęściej wykonywane operacje modyfikujące zawartość wektora to:

• emplace_back(value) - dodaje wartość na końcu wektora, np. numbers.emplace_back(777.0);
• resize(size) - zmienia rozmiar wektora na podaną wartość
• clear() - usuwa wszystkie elementy i zmienia rozmiar wektora na 0

Chociaż wektor może być dowolnie modyfikowany, każda zmiana jego rozmiaru może się wiązać z koniecznością zaalokowania nowej pamięci i przeniesienia wszystkich elementów. Jeśli znasz liczbę elementów w trakcie tworzenia kolekcji, warto utworzyć od razu wektor o zadanej wielkości.

Kopiowanie, przekazywanie do funkcji

Wektor, podobnie jak inne kontenery, ma zaimplementowane mechanizmy kopiujące jego zawartość element po elemencie w przypadku zapisywania do nowej zmiennej.

std::vector<int> a = {3, 4, 5};
std::vector<int> b = a; // spowoduje utworzenie nowego wektora (zaalokowanie nowej pamięci)
                        // i skopiowanie zawartości element po elemencie
b[1] = 100; // modyfikuje tylko wektor b

Oznacza to, że w przypadku przekazywania wektora jako argumentu do funkcji poprzez wartość, zostanie on niepotrzebnie skopiowany, a jakiekolwiek zmiany będą odbywały się na kopii, wewnątrz funkcji.

Jeśli argument ma podlegać modyfikacji należy go przekazać jako referencję (znak & przed nazwą argumentu), a jeśli modyfikacja oryginalnej kolekcji nie jest wymagana, należy przekazywać argument jako const reference:

void print_vector(const std::vector<int> &param) {
    /* read-only stuff */ 
}

Dokumentacja

W instrukcji przedstawiono jedynie podstawową funkcjonalność, szegółowy opis można znaleźć w dokumentacji, np:

http://www.cplusplus.com/reference/vector/vector/

https://en.cppreference.com/w/cpp/container/vector

🛠🔥 Zadania do samodzielnego wykonania 🛠🔥

🛠 Zadanie 1: wypełnianie i wyświetlanie wektora

Utwórz wektor liczb całkowitych o rozmiarze podanym przez użytkownika w konsoli.

Napisz dwie funkcje:

• fill_progressive, która wypełni przekazany do niej wektor kolejnymi liczbami całkowitymi od 1 do n, gdzie n to długość wektora
• print_vector, która wyświetli elementy wektora w konsoli, oddzielone przecinkami

Przykładowo:

std::vector<int> vec(6);
fill_progressive(vec);
print_vector(vec);

Wynik:

1, 2, 3, 4, 5, 6

🛠 Zadanie 2: min/max

Napisz funkcję min_max znajdującą minimum i maksimum w przekazanym do niej wektorze liczb typu double. Znalezione wartości zwróć przez dwa argumenty-referencje:

double min;
double max;
std::vector<double> values = {-1.0, 100, 3.14, -999.9, 21.37};

min_max(values, min, max); // wpisze znalezione wartości do zmiennych min i max

🛠 Zadanie 3: silnia

Napisz funkcję factorial, która wyznaczy silnię z przekazanego argumentu bez użycia rekurencji. Aby umożliwić operacje na dużych liczbach całkowitych wykorzystaj typ zmiennych uint64_t.

Przykładowe wywołanie funkcji powinno wyglądać następująco:

uint64_t result = factorial(15);
std::cout << result << std::endl; // wynik: 1307674368000

🛠 Zadanie 4: silnia rekurencyjna

Napisz funkcję factorial_r, która wyznaczy silnię z przekazanego argumentu z użyciem rekurencji. Aby umożliwić operacje na dużych liczbach całkowitych wykorzystaj typ zmiennych uint64_t. Wykorzystaj definicję silni:

Przykładowe wywołanie funkcji powinno wyglądać następująco:

uint64_t result = factorial_r(15);
std::cout << result << std::endl;

Wynik:

1307674368000

🛠 Zadanie 5: liczby pierwsze

Napisz funkcję is_prime sprawdzającą czy podana liczba jest liczbą pierwszą (dzieli się bez reszty tylko przez 1 i siebie samą), tak aby można było jej użyć w poniższym przykładzie:

int prime_or_not_prime = 13;
if (is_prime(prime_or_not_prime)) {
    std::cout << prime_or_not_prime << " is prime!" << std::endl;
} else {
    std::cout << prime_or_not_prime << " is not prime!" << std::endl;
}

Jaki jest największy potencjalny dzielnik, jaki warto sprawdzać dla danej liczby?

Następnie zapytaj użytkownika o wprowadzenie zakresu (dolna i górna granica) i wykorzystując funkcję is_prime wyświetl liczby pierwsze z żądanego zakresu, np:

> 1
> 10
2 3 5 7

Zastanów się jak można przyspieszyć przeszukiwanie zakresu - czy jakieś liczby można łatwo pominąć?

🛠 Zadanie 6: wzór na π

Szczególny przypadek szeregu naprzemiennego, zwany wzorem Leibniza, pozwala na wyznaczenie przybliżenia liczby π:

Napisz funkcję leibniz_pi, która obliczy π z zadaną dokładnością zadaną w parametrze - sumuj wyrazy tak długo, aż kolejny dodawany wyraz nie będzie mniejszy niż zadana dokładność. Możesz porównać uzyskany wynik ze stałą M_PI z nagłówka <cmath>.

double stop_at = 0.001;
double pi_approx = pi_leibniz(stop_at);

std::cout << pi_approx << std::endl;
std::cout << "error: " << pi_approx - M_PI << std::endl;

🛠 Zadanie 7: rysowanie kwadratu

Napisz funkcję draw_square, która narysuje w konsoli pusty w środku kwadrat o zadanym boku, złożony ze znaków #:

draw_square(4);

Wynik:

####
#  #
#  #
####

Następnie zmodyfikuj funkcję poprzez dodanie dwóch parametrów logicznych left_diagonal i right_diagonal. Ustawienie jednego z nich (bądź obu) na wartość true powinno powodować narysowanie wewnątrz kwadratu odpowiednich przekątnych, przykładowo:

draw_square(6, true, false);

Wynik:

######
##   #
# #  #
#  # #
#   ##
######

draw_square(7, true, true);

Wynik:

#######
##   ##
# # # #
#  #  #
# # # #
##   ##
#######

🛠 Zadanie 8: NWD - algorytm Euklidesa

Algorytm Euklidesa pozwala znaleźć największy wspólny dzielnik dwóch liczb. Dla danych liczb a i b algorytm można opisać słownie jako:

1. oblicz c jako resztę z dzielenia a przez b
2. zastąp a liczbą b, następnie b liczbą c
3. jeżeli wartość b wynosi 0, to a jest szukaną wartością NWD, w przeciwnym wypadku przejdź do kroku 1

Zastanów się jak przenieść powyższy opis na mechanizmy (pętle, warunki) języka C++. Napisz funkcję gcd(a, b) implementującą opisany algorytm i zwracającą uzyskany wynik.

Autorzy: Jakub Tomczyński