Algorytmy — C++

Po co się tego uczymy?

Uczeń ma dostać algorytm w małych porcjach: nazwa, zastosowanie, sposób działania i kod. Dzięki temu materiał nadaje się do samodzielnej nauki, a nie tylko do kopiowania.

Teoria

Algorytmy poniżej są ułożone w osobnych kartach. Każda karta wyjaśnia problem prostym językiem, pokazuje kroki działania i daje krótki przykład kodu z polskimi nazwami zmiennych.

Przykład z życia

Ta wersja jest przygotowana dla języka C++. Każdy algorytm ma osobną kartę: nazwę po polsku, proste wyjaśnienie, kroki działania i krótki kod z polskimi nazwami zmiennych.

Ucz się aktywnie: najpierw przeczytaj opis, potem przejdź kod linijka po linijce, a na końcu zmień dane wejściowe i sprawdź wynik.

Badanie podzielności i operator modulo

liczbymod

Modulo zwraca resztę z dzielenia. Jeżeli reszta z dzielenia przez dzielnik wynosi 0, liczba jest przez niego podzielna.

oblicz resztę z dzielenia
porównaj resztę z zerem
zwróć odpowiedź logiczną

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

bool czyPodzielna(int liczba, int dzielnik) {
    return dzielnik != 0 && liczba % dzielnik == 0;
}

int main() {
    cout << boolalpha << czyPodzielna(24, 6);
    cout << "n";
    return 0;
}

Przykład uruchomienia: cout << boolalpha << czyPodzielna(24, 6);

NWD — algorytm Euklidesa przez odejmowanie

liczbyNWD

Największy wspólny dzielnik nie zmienia się, gdy od większej liczby odejmujemy mniejszą. Powtarzamy to, aż obie liczby będą równe.

porównaj dwie liczby
od większej odejmij mniejszą
zatrzymaj się, gdy liczby są równe

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

int nwdOdejmowanie(int a, int b) {
    a = abs(a); b = abs(b);
    while (a != b) {
        if (a > b) a -= b;
        else b -= a;
    }
    return a;
}

int main() {
    cout << nwdOdejmowanie(48, 18);
    cout << "n";
    return 0;
}

Przykład uruchomienia: cout << nwdOdejmowanie(48, 18);

NWD modulo i NWW przez NWD

liczbyNWDNWW

Wersja modulo jest szybsza: zamiast odejmować wiele razy, od razu bierzemy resztę z dzielenia. NWW liczymy ze wzoru: a razy b podzielone przez NWD.

zamień parę (a, b) na (b, a % b)
powtarzaj, aż b będzie zerem
NWW policz ze wzoru

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

int nwd(int a, int b) {
    while (b != 0) {
        int reszta = a % b;
        a = b; b = reszta;
    }
    return abs(a);
}
int nww(int a, int b) { return abs(a * b) / nwd(a, b); }

int main() {
    cout << nwd(48, 18) << " " << nww(12, 18);
    cout << "n";
    return 0;
}

Przykład uruchomienia: cout << nwd(48, 18) << " " << nww(12, 18);

Liczba pierwsza i rozkład na czynniki

liczbypierwsze

Liczba pierwsza ma dokładnie dwa dzielniki: 1 i samą siebie. Wystarczy sprawdzać dzielniki do pierwiastka z liczby, bo większe dzielniki miałyby parę mniejszą od pierwiastka.

odrzuć liczby mniejsze od 2
sprawdzaj dzielniki od 2 do √n
przy rozkładzie dziel przez znaleziony czynnik tak długo, jak się da

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

bool czyPierwsza(int liczba) {
    if (liczba < 2) return false;
    for (int dzielnik = 2; dzielnik * dzielnik <= liczba; dzielnik++)
        if (liczba % dzielnik == 0) return false;
    return true;
}

int main() {
    cout << boolalpha << czyPierwsza(29);
    cout << "n";
    return 0;
}

Przykład uruchomienia: cout << boolalpha << czyPierwsza(29);

Sito Eratostenesa

liczbypierwsze

Sito tworzy listę kandydatów na liczby pierwsze i wykreśla wielokrotności kolejnych liczb pierwszych. To szybki sposób na wszystkie liczby pierwsze do n.

załóż, że liczby od 2 są pierwsze
dla kolejnej niewykreślonej liczby wykreśl jej wielokrotności
zostaw niewykreślone wartości

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

vector<int> sito(int granica) {
    vector<bool> pierwsza(granica + 1, true);
    pierwsza[0] = pierwsza[1] = false;
    for (int liczba = 2; liczba * liczba <= granica; liczba++)
        if (pierwsza[liczba])
            for (int w = liczba * liczba; w <= granica; w += liczba) pierwsza[w] = false;
    vector<int> wynik;
    for (int i = 2; i <= granica; i++) if (pierwsza[i]) wynik.push_back(i);
    return wynik;
}

int main() {
    for (int x : sito(30)) cout << x << " ";
    cout << "n";
    return 0;
}

Przykład uruchomienia: for (int x : sito(30)) cout << x << " ";

Szybkie potęgowanie

liczbydziel i zwyciężaj

Zamiast mnożyć podstawę tyle razy, ile wynosi wykładnik, rozbijamy wykładnik na połowy. Gdy wykładnik jest nieparzysty, dokładamy jedną podstawę do wyniku.

jeśli wykładnik jest nieparzysty, pomnóż wynik przez podstawę
podstawę podnieś do kwadratu
wykładnik podziel całkowicie przez 2

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

long long szybkaPotega(long long podstawa, long long wykladnik) {
    long long wynik = 1;
    while (wykladnik > 0) {
        if (wykladnik % 2 == 1) wynik *= podstawa;
        podstawa *= podstawa;
        wykladnik /= 2;
    }
    return wynik;
}

int main() {
    cout << szybkaPotega(2, 10);
    cout << "n";
    return 0;
}

Przykład uruchomienia: cout << szybkaPotega(2, 10);

Schemat Hornera

liczbywielomiany

Horner pozwala obliczyć wartość wielomianu bez osobnego liczenia kolejnych potęg. Wynik budujemy od lewej: mnożymy przez x i dodajemy następny współczynnik.

zacznij od wyniku 0
dla każdego współczynnika wykonaj: wynik = wynik * x + współczynnik
po ostatnim współczynniku masz wartość wielomianu

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

int horner(vector<int> wspolczynniki, int x) {
    int wynik = 0;
    for (int wspolczynnik : wspolczynniki)
        wynik = wynik * x + wspolczynnik;
    return wynik;
}

int main() {
    cout << horner({2, 3, 1}, 2);
    cout << "n";
    return 0;
}

Przykład uruchomienia: cout << horner({2, 3, 1}, 2);

Fibonacci iteracyjnie i rekurencyjnie

rekurencjaiteracja

Ciąg Fibonacciego zaczyna się od 0 i 1, a każdy następny wyraz jest sumą dwóch poprzednich. Wersja iteracyjna jest szybka, rekurencyjna dobrze pokazuje ideę, ale dla dużych n jest wolna.

iteracyjnie trzymaj dwie ostatnie wartości
rekurencyjnie użyj wzoru F(n)=F(n-1)+F(n-2)
pamiętaj o warunku stopu dla 0 i 1

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

long long fibIteracyjnie(int n) {
    long long poprzedni = 0, aktualny = 1;
    while (n--) {
        long long nastepny = poprzedni + aktualny;
        poprzedni = aktualny; aktualny = nastepny;
    }
    return poprzedni;
}
long long fibRekurencyjnie(int n) { return n < 2 ? n : fibRekurencyjnie(n-1) + fibRekurencyjnie(n-2); }

int main() {
    cout << fibIteracyjnie(10) << " " << fibRekurencyjnie(10);
    cout << "n";
    return 0;
}

Przykład uruchomienia: cout << fibIteracyjnie(10) << " " << fibRekurencyjnie(10);

Silnia i wydawanie reszty zachłannie

liczbyzachłanny

Silnia mnoży kolejne liczby od 1 do n. Wydawanie reszty zachłannie zawsze wybiera największy nominał, który mieści się w pozostałej kwocie.

silnia: mnoż wynik przez kolejne i
reszta: wybierz największy możliwy nominał
odejmij jego wielokrotność od kwoty

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

long long silnia(int n) {
    long long wynik = 1;
    for (int liczba = 2; liczba <= n; liczba++) wynik *= liczba;
    return wynik;
}

int main() {
    cout << silnia(5);
    cout << "n";
    return 0;
}

Przykład uruchomienia: cout << silnia(5);

Sortowanie bąbelkowe

sortowanieO(n²)

Porównujemy sąsiednie elementy i zamieniamy je miejscami, jeśli są w złej kolejności. Największe wartości „wypływają” na koniec tablicy.

przechodź po parach sąsiadów
zamień, jeśli lewy jest większy od prawego
po każdej rundzie ostatni element jest już na miejscu

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

vector<int> sortowanieBabelkowe(vector<int> tablica) {
    for (int koniec = tablica.size() - 1; koniec > 0; koniec--)
        for (int i = 0; i < koniec; i++)
            if (tablica[i] > tablica[i+1]) swap(tablica[i], tablica[i+1]);
    return tablica;
}

int main() {
    for (int x : sortowanieBabelkowe({5, 2, 8, 1})) cout << x << " ";
    cout << "n";
    return 0;
}

Przykład uruchomienia: for (int x : sortowanieBabelkowe({5, 2, 8, 1})) cout << x << " ";

Sortowanie przez wybór

sortowanieO(n²)

W każdej rundzie szukamy najmniejszego elementu w nieposortowanej części i przenosimy go na początek tej części.

ustaw pozycję początku nieposortowanej części
znajdź indeks minimum
zamień minimum z początkiem

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

vector<int> sortowanieWybor(vector<int> tablica) {
    for (int poczatek = 0; poczatek < tablica.size(); poczatek++) {
        int minimum = poczatek;
        for (int i = poczatek + 1; i < tablica.size(); i++) if (tablica[i] < tablica[minimum]) minimum = i;
        swap(tablica[poczatek], tablica[minimum]);
    }
    return tablica;
}

int main() {
    for (int x : sortowanieWybor({5, 2, 8, 1})) cout << x << " ";
    cout << "n";
    return 0;
}

Przykład uruchomienia: for (int x : sortowanieWybor({5, 2, 8, 1})) cout << x << " ";

Sortowanie przez wstawianie

sortowanieO(n²)

Bierzemy kolejny element i wstawiamy go w odpowiednie miejsce w już posortowanej lewej części tablicy. Działa podobnie do układania kart w ręce.

weź element z nieposortowanej części
przesuwaj większe elementy w prawo
wstaw element w powstałe miejsce

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

vector<int> sortowanieWstawianie(vector<int> tablica) {
    for (int i = 1; i < tablica.size(); i++) {
        int element = tablica[i], j = i - 1;
        while (j >= 0 && tablica[j] > element) { tablica[j+1] = tablica[j]; j--; }
        tablica[j+1] = element;
    }
    return tablica;
}

int main() {
    for (int x : sortowanieWstawianie({5, 2, 8, 1})) cout << x << " ";
    cout << "n";
    return 0;
}

Przykład uruchomienia: for (int x : sortowanieWstawianie({5, 2, 8, 1})) cout << x << " ";

Sortowanie przez scalanie

sortowaniedziel i zwyciężaj

Dzielimy tablicę na połowy, sortujemy połówki, a potem scalamy dwie posortowane listy w jedną. To klasyczne „dziel i zwyciężaj”.

podziel tablicę na dwie części
posortuj każdą część rekurencyjnie
scal dwie posortowane części

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

vector<int> scal(vector<int> lewa, vector<int> prawa) {
    vector<int> wynik;
    int i = 0, j = 0;
    while (i < lewa.size() && j < prawa.size()) {
        if (lewa[i] <= prawa[j]) wynik.push_back(lewa[i++]);
        else wynik.push_back(prawa[j++]);
    }
    while (i < lewa.size()) wynik.push_back(lewa[i++]);
    while (j < prawa.size()) wynik.push_back(prawa[j++]);
    return wynik;
}

vector<int> sortowanieScalanie(vector<int> tablica) {
    if (tablica.size() <= 1) return tablica;
    int srodek = tablica.size() / 2;
    vector<int> lewa(tablica.begin(), tablica.begin() + srodek);
    vector<int> prawa(tablica.begin() + srodek, tablica.end());
    return scal(sortowanieScalanie(lewa), sortowanieScalanie(prawa));
}

int main() {
    for (int x : sortowanieScalanie({5, 2, 8, 1})) cout << x << " ";
    cout << "n";
    return 0;
}

Przykład uruchomienia: for (int x : sortowanieScalanie({5, 2, 8, 1})) cout << x << " ";

Quicksort — sortowanie szybkie

sortowaniedziel i zwyciężaj

Wybieramy element osiowy, dzielimy dane na mniejsze, równe i większe od niego, a potem sortujemy części rekurencyjnie.

wybierz pivot
podziel elementy względem pivota
posortuj rekurencyjnie lewą i prawą część

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

vector<int> quicksort(vector<int> tablica) {
    if (tablica.size() <= 1) return tablica;
    int pivot = tablica[tablica.size()/2];
    vector<int> mniejsze, rowne, wieksze;
    for (int x : tablica) { if (x < pivot) mniejsze.push_back(x); else if (x == pivot) rowne.push_back(x); else wieksze.push_back(x); }
    mniejsze = quicksort(mniejsze); wieksze = quicksort(wieksze);
    mniejsze.insert(mniejsze.end(), rowne.begin(), rowne.end());
    mniejsze.insert(mniejsze.end(), wieksze.begin(), wieksze.end());
    return mniejsze;
}

int main() {
    for (int x : quicksort({5, 2, 8, 1})) cout << x << " ";
    cout << "n";
    return 0;
}

Przykład uruchomienia: for (int x : quicksort({5, 2, 8, 1})) cout << x << " ";

Sortowanie przez zliczanie

sortowaniekubełkowe

Działa dobrze, gdy wartości są liczbami całkowitymi z niedużego zakresu. Zliczamy, ile razy występuje każda wartość, a potem odtwarzamy posortowaną tablicę.

utwórz tablicę liczników
zwiększ licznik dla każdej wartości
wypisz wartości tyle razy, ile wynosi licznik

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

vector<int> sortowanieZliczanie(vector<int> tablica, int maksimum) {
    vector<int> liczniki(maksimum + 1), wynik;
    for (int liczba : tablica) liczniki[liczba]++;
    for (int wartosc = 0; wartosc <= maksimum; wartosc++)
        while (liczniki[wartosc]--) wynik.push_back(wartosc);
    return wynik;
}

int main() {
    for (int x : sortowanieZliczanie({3, 1, 2, 3, 0}, 3)) cout << x << " ";
    cout << "n";
    return 0;
}

Przykład uruchomienia: for (int x : sortowanieZliczanie({3, 1, 2, 3, 0}, 3)) cout << x << " ";

Wyszukiwanie liniowe i binarne

wyszukiwanie

Liniowe sprawdza element po elemencie i działa zawsze. Binarne działa tylko na danych posortowanych, ale za każdym krokiem odrzuca połowę zakresu.

liniowe: idź od początku do końca
binarne: sprawdź środek
przesuń lewy lub prawy koniec zakresu

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

int szukajBinarnie(vector<int> tablica, int szukana) {
    int lewy = 0, prawy = tablica.size() - 1;
    while (lewy <= prawy) {
        int srodek = (lewy + prawy) / 2;
        if (tablica[srodek] == szukana) return srodek;
        if (tablica[srodek] < szukana) lewy = srodek + 1; else prawy = srodek - 1;
    }
    return -1;
}

int main() {
    cout << szukajBinarnie({1, 4, 7, 9}, 7);
    cout << "n";
    return 0;
}

Przykład uruchomienia: cout << szukajBinarnie({1, 4, 7, 9}, 7);

Minimum, maksimum i lider

wyszukiwanielider

Minimum i maksimum znajdujemy jednym przejściem po tablicy. Lider to wartość, która występuje częściej niż połowa elementów; algorytm Boyera-Moore’a wybiera kandydata i potem go sprawdza.

przechodź po danych raz
aktualizuj minimum i maksimum
dla lidera kasuj pary różnych wartości

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

pair<int,int> minimumMaksimum(vector<int> tablica) {
    return {*min_element(tablica.begin(), tablica.end()), *max_element(tablica.begin(), tablica.end())};
}

int main() {
    auto p = minimumMaksimum({3, 8, 1}); cout << p.first << " " << p.second;
    cout << "n";
    return 0;
}

Przykład uruchomienia: auto p = minimumMaksimum({3, 8, 1}); cout << p.first << " " << p.second;

Palindrom i zliczanie znaków

tekst

Palindrom czyta się tak samo od lewej i od prawej. Zliczanie znaków polega na przejściu po tekście i zwiększaniu licznika dla każdego znaku.

porównaj tekst z jego odwróceniem
dla zliczania użyj słownika/mapy
zwiększ licznik znaku

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

bool czyPalindrom(string tekst) {
    string odwrocony = tekst;
    reverse(odwrocony.begin(), odwrocony.end());
    return tekst == odwrocony;
}

int main() {
    cout << boolalpha << czyPalindrom("kajak");
    cout << "n";
    return 0;
}

Przykład uruchomienia: cout << boolalpha << czyPalindrom("kajak");

Wyszukiwanie wzorca w tekście

tekst

W wersji naiwnej przykładamy wzorzec do każdego miejsca w tekście i sprawdzamy zgodność znak po znaku. KMP i Rabin-Karp robią to szybciej, ale idea nadal zaczyna się od pojęcia wzorca.

wybierz pozycję startową
porównaj fragment tekstu ze wzorcem
zapisz pozycję, jeśli pasuje

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

vector<int> znajdzWzorzec(string tekst, string wzorzec) {
    vector<int> pozycje;
    for (int i = 0; i + wzorzec.size() <= tekst.size(); i++)
        if (tekst.substr(i, wzorzec.size()) == wzorzec) pozycje.push_back(i);
    return pozycje;
}

int main() {
    for (int x : znajdzWzorzec("abrakadabra", "abra")) cout << x << " ";
    cout << "n";
    return 0;
}

Przykład uruchomienia: for (int x : znajdzWzorzec("abrakadabra", "abra")) cout << x << " ";

Porządkowanie leksykograficzne i szyfry

tekstszyfry

Porządkowanie leksykograficzne to sortowanie tekstów jak w słowniku. Szyfr Cezara przesuwa litery, GADERYPOLUKI podmienia pary liter, a RSA pokazuje ideę klucza jawnego i prywatnego.

dla sortowania porównuj napisy
dla Cezara przesuń literę w alfabecie
dla RSA pamiętaj: to demonstracja matematyczna na małych liczbach

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

string cezar(string tekst, int przesuniecie) {
    for (char &znak : tekst) if (isalpha(znak)) {
        char baza = isupper(znak) ? 'A' : 'a';
        znak = char((znak - baza + przesuniecie + 26) % 26 + baza);
    }
    return tekst;
}

int main() {
    cout << cezar("Ala ma kota", 3);
    cout << "n";
    return 0;
}

Przykład uruchomienia: cout << cezar("Ala ma kota", 3);

Metoda bisekcji

numeryczne

Bisekcja szuka miejsca zerowego funkcji w przedziale. Jeśli funkcja zmienia znak między końcami przedziału, dzielimy przedział na pół i zostawiamy tę połowę, gdzie nadal jest zmiana znaku.

policz środek przedziału
sprawdź znak funkcji na końcu i w środku
zawęź przedział

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

double bisekcja(function<double(double)> funkcja, double lewy, double prawy) {
    while (prawy - lewy > 1e-6) {
        double srodek = (lewy + prawy) / 2;
        if (funkcja(lewy) * funkcja(srodek) <= 0) prawy = srodek; else lewy = srodek;
    }
    return (lewy + prawy) / 2;
}

int main() {
    cout << bisekcja([](double x){ return x*x - 2; }, 0, 2);
    cout << "n";
    return 0;
}

Przykład uruchomienia: cout << bisekcja([](double x){ return x*x - 2; }, 0, 2);

Pole pod wykresem i metoda Newtona

numeryczne

Pole pod wykresem można przybliżyć prostokątami albo trapezami. Metoda Newtona/Herona poprawia przybliżenie pierwiastka, uśredniając wynik z ilorazem liczby przez wynik.

podziel przedział na małe części
zsumuj pola prostokątów lub trapezów
dla pierwiastka poprawiaj przybliżenie aż do wymaganej dokładności

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

double pierwiastekNewtona(double liczba) {
    double wynik = liczba;
    while (abs(wynik * wynik - liczba) > 1e-6)
        wynik = (wynik + liczba / wynik) / 2;
    return wynik;
}

int main() {
    cout << pierwiastekNewtona(9);
    cout << "n";
    return 0;
}

Przykład uruchomienia: cout << pierwiastekNewtona(9);

Rekurencja — wieże Hanoi

rekurencja

Rekurencja oznacza, że funkcja wywołuje samą siebie dla mniejszego problemu. W Hanoi najpierw przenosimy n-1 krążków, potem największy, potem znów n-1.

ustal warunek stopu
rozwiąż mniejszy problem
wykonaj jeden ruch główny
rozwiąż drugi mniejszy problem

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

void hanoi(int ile, char zrodlo, char pomoc, char cel) {
    if (ile == 0) return;
    hanoi(ile - 1, zrodlo, cel, pomoc);
    cout << zrodlo << " -> " << cel << "n";
    hanoi(ile - 1, pomoc, zrodlo, cel);
}

int main() {
    hanoi(3, 'A', 'B', 'C');
    cout << "n";
    return 0;
}

Przykład uruchomienia: hanoi(3, 'A', 'B', 'C');

Algorytm zachłanny — plecak ułamkowy

zachłanny

Algorytm zachłanny podejmuje lokalnie najlepszą decyzję. W plecaku ułamkowym bierzemy przedmioty według największej wartości na jednostkę wagi.

policz wartość na kilogram
posortuj malejąco
bierz cały przedmiot albo jego część

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

double plecakUlamkowy(vector<pair<double,double>> przedmioty, double pojemnosc) {
    sort(przedmioty.begin(), przedmioty.end(), [](auto a, auto b) {
        return a.first / a.second > b.first / b.second;
    });
    double wynik = 0;
    for (auto [wartosc, waga] : przedmioty) {
        double biore = min(waga, pojemnosc);
        wynik += biore * wartosc / waga;
        pojemnosc -= biore;
        if (pojemnosc == 0) break;
    }
    return wynik;
}

int main() {
    cout << plecakUlamkowy({{60, 10}, {100, 20}, {120, 30}}, 50);
    cout << "n";
    return 0;
}

Przykład uruchomienia: cout << plecakUlamkowy({{60, 10}, {100, 20}, {120, 30}}, 50);

Programowanie dynamiczne — monety i LCS

dynamiczne

Programowanie dynamiczne zapamiętuje wyniki mniejszych podproblemów. Dzięki temu nie liczymy wielokrotnie tego samego, jak w naiwnej rekurencji.

zdefiniuj małe podproblemy
zapisuj ich wyniki w tablicy
buduj odpowiedź od prostych przypadków do trudniejszych

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

int najmniejMonet(int kwota, vector<int> monety) {
    vector<int> dp(kwota + 1, 1000000); dp[0] = 0;
    for (int suma = 1; suma <= kwota; suma++)
        for (int moneta : monety) if (moneta <= suma)
            dp[suma] = min(dp[suma], dp[suma - moneta] + 1);
    return dp[kwota];
}

int main() {
    cout << najmniejMonet(11, {1, 5, 7});
    cout << "n";
    return 0;
}

Przykład uruchomienia: cout << najmniejMonet(11, {1, 5, 7});

Backtracking — hetmany i labirynt

backtracking

Backtracking próbuje kolejnych decyzji, a gdy ścieżka prowadzi do błędu, cofa się i sprawdza następną możliwość. To metoda „spróbuj, sprawdź, cofnij”.

wybierz możliwy ruch
sprawdź, czy jest poprawny
idź głębiej rekurencyjnie
jeśli się nie uda, cofnij wybór

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

vector<vector<int>> hetmany(int n) {
    vector<vector<int>> rozwiazania;
    vector<int> kolumny;

    function<bool(int,int)> czyPoprawne = [&](int wiersz, int kolumna) {
        for (int i = 0; i < kolumny.size(); i++)
            if (kolumny[i] == kolumna || abs(kolumny[i] - kolumna) == abs(i - wiersz)) return false;
        return true;
    };

    function<void(int)> szukaj = [&](int wiersz) {
        if (wiersz == n) { rozwiazania.push_back(kolumny); return; }
        for (int kolumna = 0; kolumna < n; kolumna++) {
            if (czyPoprawne(wiersz, kolumna)) {
                kolumny.push_back(kolumna);
                szukaj(wiersz + 1);
                kolumny.pop_back();
            }
        }
    };

    szukaj(0);
    return rozwiazania;
}

int main() {
    auto rozwiazania = hetmany(4); cout << rozwiazania.size();
    cout << "n";
    return 0;
}

Przykład uruchomienia: auto rozwiazania = hetmany(4); cout << rozwiazania.size();

Struktury danych: tablica, stos, kolejka, drzewo, kopiec, graf

struktury danych

Struktura danych decyduje, jak przechowujesz informacje. Tablica daje szybki dostęp po indeksie, stos działa LIFO, kolejka FIFO, kopiec szybko zwraca minimum/maksimum, a graf opisuje połączenia.

dobierz strukturę do operacji
stos: ostatni wchodzi, pierwszy wychodzi
kolejka: pierwszy wchodzi, pierwszy wychodzi
graf zapisz jako listę sąsiedztwa albo macierz

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

void pokazStruktury() {
    vector<int> tablica = {3, 1, 4};

    stack<int> stos;
    stos.push(10);
    stos.push(20);
    int zeStosu = stos.top();
    stos.pop();

    queue<int> kolejka;
    kolejka.push(10);
    kolejka.push(20);
    int zKolejki = kolejka.front();
    kolejka.pop();

    priority_queue<int, vector<int>, greater<int>> kopiec;
    kopiec.push(30);
    kopiec.push(5);

    vector<vector<int>> graf = {{1, 2}, {0}, {0}};
    cout << tablica[0] << " " << zeStosu << " " << zKolejki << " " << kopiec.top() << " " << graf[0].size();
}

int main() {
    pokazStruktury();
    cout << "n";
    return 0;
}

Przykład uruchomienia: pokazStruktury();

BFS i DFS

grafy

BFS przeszukuje graf wszerz, poziomami, używając kolejki. DFS idzie jak najgłębiej, używając rekurencji albo stosu.

zaznacz start jako odwiedzony
BFS: zdejmuj z kolejki
DFS: odwiedzaj rekurencyjnie sąsiadów

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

vector<int> bfs(vector<vector<int>> graf, int start) {
    vector<int> odwiedzone(graf.size()), kolejnosc;
    queue<int> kolejka; odwiedzone[start] = 1; kolejka.push(start);
    while (!kolejka.empty()) { int v = kolejka.front(); kolejka.pop(); kolejnosc.push_back(v);
        for (int sasiad : graf[v]) if (!odwiedzone[sasiad]) { odwiedzone[sasiad] = 1; kolejka.push(sasiad); }}
    return kolejnosc;
}

int main() {
    for (int x : bfs({{1,2},{},{}}, 0)) cout << x << " ";
    cout << "n";
    return 0;
}

Przykład uruchomienia: for (int x : bfs({{1,2},{},{}}, 0)) cout << x << " ";

Dijkstra — najkrótsza ścieżka

grafyścieżki

Dijkstra znajduje najkrótsze odległości od startu w grafie z nieujemnymi wagami. Zawsze wybiera jeszcze nieprzetworzony wierzchołek o najmniejszym znanym koszcie.

ustaw odległość startu na 0
wybierz najbliższy wierzchołek z kolejki priorytetowej
popraw odległości sąsiadów

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

vector<int> dijkstra(vector<vector<pair<int,int>>> graf, int start) {
    const int INF = 1000000000;
    vector<int> odleglosc(graf.size(), INF);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> kolejka;
    odleglosc[start] = 0;
    kolejka.push({0, start});

    while (!kolejka.empty()) {
        auto [koszt, wierzcholek] = kolejka.top();
        kolejka.pop();
        if (koszt != odleglosc[wierzcholek]) continue;
        for (auto [sasiad, waga] : graf[wierzcholek]) {
            int nowy = koszt + waga;
            if (nowy < odleglosc[sasiad]) {
                odleglosc[sasiad] = nowy;
                kolejka.push({nowy, sasiad});
            }
        }
    }
    return odleglosc;
}

int main() {
    vector<vector<pair<int,int>>> graf = {{{{1, 3}, {2, 1}}, {}, {{1, 1}}}}; for (int x : dijkstra(graf, 0)) cout << x << " ";
    cout << "n";
    return 0;
}

Przykład uruchomienia: vector<vector<pair<int,int>>> graf = {{{{1, 3}, {2, 1}}, {}, {{1, 1}}}}; for (int x : dijkstra(graf, 0)) cout << x << " ";

Minimalne drzewo rozpinające — Prim i Kruskal

grafyMST

Minimalne drzewo rozpinające łączy wszystkie wierzchołki najtańszym zestawem krawędzi. Prim rozbudowuje jedno drzewo, a Kruskal bierze krawędzie od najlżejszej i pilnuje, żeby nie zrobić cyklu.

Prim: zacznij od dowolnego wierzchołka
Kruskal: posortuj krawędzie rosnąco
dodawaj krawędź tylko, gdy łączy różne składowe

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

struct Dsu {
    vector<int> rodzic;
    Dsu(int n) : rodzic(n) { iota(rodzic.begin(), rodzic.end(), 0); }
    int znajdz(int x) { return rodzic[x] == x ? x : rodzic[x] = znajdz(rodzic[x]); }
    bool polacz(int a, int b) {
        a = znajdz(a); b = znajdz(b);
        if (a == b) return false;
        rodzic[a] = b;
        return true;
    }
};

vector<tuple<int,int,int>> kruskal(int liczbaWierzcholkow, vector<tuple<int,int,int>> krawedzie) {
    sort(krawedzie.begin(), krawedzie.end());
    Dsu dsu(liczbaWierzcholkow);
    vector<tuple<int,int,int>> wynik;
    for (auto [waga, a, b] : krawedzie)
        if (dsu.polacz(a, b)) wynik.push_back({waga, a, b});
    return wynik;
}

int main() {
    for (auto [waga, a, b] : kruskal(3, {{1, 0, 1}, {3, 0, 2}, {2, 1, 2}})) cout << a << "-" << b << "(" << waga << ") ";
    cout << "n";
    return 0;
}

Przykład uruchomienia: for (auto [waga, a, b] : kruskal(3, {{1, 0, 1}, {3, 0, 2}, {2, 1, 2}})) cout << a << "-" << b << "(" << waga << ") ";

Analiza złożoności Big-O

Big-O

Big-O mówi, jak rośnie czas lub pamięć algorytmu, gdy rośnie liczba danych. Nie mierzy sekund, tylko tempo wzrostu: O(n) rośnie liniowo, O(log n) bardzo wolno, O(n²) szybko robi się kosztowne.

policz dominującą pętlę lub rekurencję
pomijaj stałe
porównuj algorytmy dla dużych danych

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <cmath>
#include <tuple>
#include <utility>
#include <iomanip>
using namespace std;

void pokazBigO(vector<int> tablica) {
    // O(n) - jedna pętla po tablicy
    for (int liczba : tablica) cout << liczba << " ";
    cout << "n";

    // O(n^2) - pętla w pętli
    for (int a : tablica)
        for (int b : tablica)
            cout << "(" << a << "," << b << ") ";
}

int main() {
    pokazBigO({1, 2, 3});
    cout << "n";
    return 0;
}

Przykład uruchomienia: pokazBigO({1, 2, 3});

Komentarz i wyjaśnienie kodu

Nie trzeba uczyć się wszystkich przykładów naraz. Najpierw wybierz algorytmy liczbowe i wyszukiwanie, potem sortowanie, a na końcu rekurencję, programowanie dynamiczne i grafy.

Ćwiczenie samodzielne

Wybierz trzy karty. Dla każdej: przepisz kod ręcznie, uruchom go dla innych danych i dopisz komentarz własnymi słowami, co robi każda ważna linia.

Zadania do pracy własnej

Wybierz 5 algorytmów i przygotuj do każdego po dwa testy danych wejściowych.
Porównaj dwa algorytmy rozwiązujące podobny problem, np. wyszukiwanie liniowe i binarne albo sortowanie bąbelkowe i szybkie.
Wybierz jeden trudniejszy algorytm: Dijkstra, Kruskal, LCS albo hetmany. Narysuj dane wejściowe i opisz działanie krok po kroku.

Typowe błędy

Uruchamianie wyszukiwania binarnego na nieposortowanej tablicy.
Brak warunku stopu w rekurencji.
Mylenie liczby wierzchołków z liczbą krawędzi przy złożoności grafów.

Nawiązanie do egzaminu zawodowego

Algorytmy wspierają programowanie konsolowe, desktopowe i mobilne w INF.04. To fundament do pisania kodu, który nie tylko działa, ale działa przewidywalnie i wydajnie.