Stos (ang. Stack) – struktura danych, w której bezpośredni dostęp jest tylko do ostatnio dodanego elementu. Stos bywa określany także jako kolejka LIFO (z ang. Last In, First Out, czyli: ostatni na wejściu, pierwszy na wyjściu). Stos można sobie wyobrazić jako kilka rzeczy ułożonych „jedna na drugiej” – łatwo można wziąć tylko rzecz leżącą na samym wierzchu, gdyż pozostałe są przykryte.
W tej sekcji przedstawiona jest przykładowa implementacja w języku C++ stosu przechowującego liczby typu int. Opis ten jest adresowany przede wszystkim do osób, które dopiero chcą zrozumieć ideę dynamicznych struktur danych, zatem jest on dość opisowy.
Elementem leżącym na stosie będzie nie sama liczba, ale struktura (nazwijmy ją sobie ElementStosu) zawierająca:
W kodzie programu tworzymy zmienną typu ElementStosu*, która jest wskaźnikiem na element znajdujący się na wierzchu stosu. Początkowo nasz stos jest pusty, więc wskaźnik ten ma przypisaną zerową wartość. Potrzebne nam są teraz funkcje umożliwiające dodanie elementu na stos oraz pobranie elementu ze stosu. Dodanie nowego elementu powinno przebiegać następująco:
Ponieważ zmienna przechowująca początek stosu jest modyfikowana, musimy przekazać ją do funkcji przez referencję (ewentualnie przez wskaźnik). Poniższy kod źródłowy zawiera implementację struktury ElementStosu, funkcji dodającej element na stos i przykładowe wykorzystanie tej funkcji w funkcji main.
struct ElementStosu { int liczba; ElementStosu* nastepny; }; void dodajDoStosu(ElementStosu* &stos, int liczba) { ElementStosu* nowy = new ElementStosu(); nowy->liczba = liczba; nowy->nastepny = stos; stos = nowy; }; int main() { ElementStosu* stos = 0; dodajDoStosu(stos, 2); dodajDoStosu(stos, 5); return 0; }
Zwróćmy uwagę, że po dodaniu liczby 5 tracimy bezpośredni dostęp do liczby 2 – aby się do niej dostać, musielibyśmy przejść przez kolejne wskaźniki: stos->nastepny->liczba. Zastanówmy się teraz, jak pobrać liczbę z wierzchu stosu. Tym razem musimy przestawić wskaźnik wierzchu stosu na drugi element, a pierwszy element przeczytać i usunąć. Wygląda to następująco:
Kod źródłowy takiej funkcji jest następujący:
int pobierzZeStosu(ElementStosu* &stos) { int liczba = stos->liczba; ElementStosu* doUsuniecia = stos; stos = stos->nastepny; delete doUsuniecia; return liczba; };
Warto zauważyć, że wywołanie tej funkcji jest możliwe tylko wtedy, gdy stos nie jest pusty – w przeciwnym razie program zakończy się błędem. Podstawowe funkcje stosu mamy już zaimplementowane. Żeby móc wygodnie przetestować ich działanie napiszmy jeszcze funkcję, która wypisze nam całą zawartość stosu. Jak wspominaliśmy, bezpośredni dostęp mamy tylko do wierzchu stosu. Żeby dostać się głębiej, musimy „przewijać” stos przechodząc po kolejnych wskaźnikach. Algorytm ten jest następujący:
Pełny przykład programu, zawierający wszystkie opisane w tym artykule funkcje, jest zamieszczony poniżej.
#include<iostream> using namespace std; struct ElementStosu { int liczba; ElementStosu* nastepny; }; void dodajDoStosu(ElementStosu* &stos, int liczba) { ElementStosu* nowy = new ElementStosu(); nowy->liczba = liczba; nowy->nastepny = stos; stos = nowy; }; int pobierzZeStosu(ElementStosu* &stos) { int liczba = stos->liczba; ElementStosu* doUsuniecia = stos; stos = stos->nastepny; delete doUsuniecia; return liczba; }; void wypiszStos(ElementStosu* &stos) { ElementStosu* aktualny = stos; while (aktualny != 0) { cout << aktualny->liczba << " "; aktualny = aktualny->nastepny; } cout << "\n"; }; int main() { ElementStosu* stos = 0; dodajDoStosu(stos, 2); dodajDoStosu(stos, 5); dodajDoStosu(stos, 7); wypiszStos(stos); int pobrane = pobierzZeStosu(stos); cout << "Pobrano: " << pobrane << "\n"; wypiszStos(stos); dodajDoStosu(stos, 6); wypiszStos(stos); system("pause"); // Czyszczenie pamięci while (stos != 0) { pobierzZeStosu(stos); } return 0; }
Dodano: 13 kwietnia 2018 21:26, ostatnia edycja: 10 listopada 2018 11:12.
Zanieczyszczenie Giniego (ang. Gini Impurity) – miara niejednorodności danego zbioru wyrażająca się wzorem:
$$G = ∑↙{n} p_n (1-p_n),$$gdzie pn jest prawdopodobieństwem przynależności elementu do klasy n, czyli liczbą elementów danej klasy podzieloną przez liczbę elementów całego zbioru. Jeśli wszystkie elementy zbioru należą do tej samej klasy, zanieczyszczenie Giniego jest równe 0.
Zanieczyszczenia Giniego nie należy mylić ze współczynnikiem Giniego. Są to miary służące do wyrażania zupełnie innych rzeczy. Współczynnik Giniego określa nierównomierność rozkładu i jest wykorzystywany między innymi do liczbowego wyrażania nierówności w dochodach danego społeczeństwa.
Ten artykuł opisuje algorytm zachłanny rozwiązujący problem wydawania reszty. Algorytm ten polega na wybieraniu zawsze największej dostępnej monety, tzn. takiej, która nie jest większa od kwoty pozostałej do wydania.
Algorytm nie zawsze znajduje rozwiązanie optymalne. Przykładowo, dla zbioru nominałów {1, 3, 4} i kwoty 6 algorytm użyje najpierw monety o nominale 4 (pozostaje do wydania kwota 2), potem monety o nominale 1 (pozostaje kwota 1) i jeszcze raz monety o nominale 1. Łącznie algorytm użyje więc trzech monet, podczas gdy rozwiązanie optymalne wymaga użycia tylko dwóch (dwie monety o nominale 3).
Algorytm genetyczny – metaheurystyka inspirowana biologiczną ewolucją.
Pojęcie algorytmu genetycznego nie jest powiązane z żadnym konkretnym problemem obliczeniowym, algorytm ten może być wykorzystywany do rozwiązywania różnych problemów. Algorytm genetyczny nie próbuje rozwiązywać problemu w sposób analityczny, ale próbuje uzyskać jak najlepsze rozwiązania poprzez wybieranie jak najlepszych cech rozwiązań z określonej puli. Implementując algorytm genetyczny należy przedstawić potencjalne rozwiązanie problemu w postaci jakiejś struktury danych, a następnie zdefiniować operacje krzyżowania, mutacji i selekcji. Zakładamy, że z każdym kolejnym pokoleniem rozwiązania występujące w populacji będą coraz lepsze.