Zrozum algorytm.
Zobacz każdy krok.
Wybierz temat, zmień dane i prześledź obliczenia we własnym tempie. 31 demonstracji oraz 2 narzędzia do porównań.
Złożoność:
Żółte pola wskazują aktualnie analizowane pozycje. Indeksy tablic zaczynają się od 0. Zmień dane i ponownie przygotuj kroki, aby porównać przykłady. Złożoność dotyczy obliczeń algorytmu, bez zapisywania i rysowania kroków.
Poznaj zasadę działania, przeanalizuj przykład i uruchom kod samodzielnie. Każdy program można skopiować w całości: Python 3 lub C++17.
Jak to działa
Przechodź przez pary sąsiadów od lewej do prawej. Zamieniaj je, gdy lewy element jest większy. Po całym przejściu największa z rozpatrywanych wartości trafia na koniec, więc kolejne przejście może być krótsze. Brak zamian oznacza koniec pracy.
Gdzie spotkasz ten algorytm
Na lekcjach porównywania algorytmów i w zadaniach wymagających własnego prostego sortowania. Dobrze pokazuje różnicę między poprawnością a wydajnością.
Na co uważać
Pętla musi kończyć się przed ostatnim elementem, bo porównujesz a[j+1]. Zamiana wymaga zachowania obu wartości. Porównanie > zachowuje kolejność elementów równych. Czas: O(n²), a z wcześniejszym kończeniem O(n) dla danych już posortowanych.
W praktyce
Dla [3, 1, 2] pierwsze przejście daje [1, 2, 3], drugie potwierdza brak zamian. Dla dużych zbiorów wybierz wydajniejsze sortowanie. Funkcja poniżej zmienia przekazaną listę/wektor; Python zwraca tę samą listę, C++ jej referencję.
Kod Python 3
def sortuj(a):
for koniec in range(len(a) - 1, 0, -1):
zmiana = False
for j in range(koniec):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
zmiana = True
if not zmiana:
break
return a
a = [8, 3, 6, 1, 9, 2]
print(sortuj(a)) # [1, 2, 3, 6, 8, 9]
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
vector<int>& sortuj(vector<int>& a) {
for (int koniec = int(a.size()) - 1; koniec > 0; --koniec) {
bool zmiana = false;
for (int j = 0; j < koniec; ++j) {
if (a[j] > a[j+1]) {
swap(a[j], a[j+1]);
zmiana = true;
}
}
if (!zmiana) break;
}
return a;
}
int main() {
vector<int> a = {8, 3, 6, 1, 9, 2};
for (int x : sortuj(a)) cout << x << " ";
cout << "\n";
}
Jak to działa
Traktuj pierwszy element jako uporządkowany fragment. Zapamiętaj następną wartość i przesuwaj większe elementy fragmentu o jedno miejsce w prawo. W wolne miejsce wpisz zapamiętaną wartość. Powtarzaj aż do końca tablicy.
Gdzie spotkasz ten algorytm
Przy małych zbiorach, danych prawie uporządkowanych i jako składnik bardziej rozbudowanych metod sortowania. Podobnie porządkujesz karty w ręce.
Na co uważać
Zapisz wstawiany element przed przesuwaniem, aby go nie nadpisać. Najpierw sprawdzaj j >= 0, potem odczytuj a[j]. Przesuwanie tylko elementów większych daje stabilne sortowanie. Czas O(n²), najlepszy O(n), pamięć pomocnicza O(1).
W praktyce
Dla [2, 5, 3] zapamiętujemy 3, przesuwamy 5 i wstawiamy 3 między 2 a 5. Obie funkcje sortują w miejscu i obsługują pusty zbiór.
Kod Python 3
def sortuj(a):
for i in range(1, len(a)):
wartosc = a[i]
j = i - 1
while j >= 0 and a[j] > wartosc:
a[j + 1] = a[j]
j -= 1
a[j + 1] = wartosc
return a
a = [8, 3, 6, 1, 9, 2]
print(sortuj(a)) # [1, 2, 3, 6, 8, 9]
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
vector<int>& sortuj(vector<int>& a) {
for (int i = 1; i < int(a.size()); ++i) {
int wartosc = a[i], j = i - 1;
while (j >= 0 && a[j] > wartosc) {
a[j+1] = a[j];
--j;
}
a[j+1] = wartosc;
}
return a;
}
int main() {
vector<int> a = {8, 3, 6, 1, 9, 2};
for (int x : sortuj(a)) cout << x << " ";
cout << "\n";
}
Jak to działa
Na pozycji i ma znaleźć się najmniejsza wartość z pozycji i do końca. Najpierw wyszukaj indeks minimum, a dopiero po przeglądzie zamień ten element z a[i]. Zwiększ i i ponów wyszukiwanie.
Gdzie spotkasz ten algorytm
W nauce wyszukiwania minimum i porównywaniu kosztu odczytów z kosztem zapisów. Wykonuje najwyżej n−1 zamian, chociaż nadal potrzebuje wielu porównań.
Na co uważać
Nie zamieniaj elementów przy każdym znalezieniu mniejszej wartości — przechowuj indeks minimum. Wersja z zamianą nie jest stabilna. Nawet uporządkowane dane wymagają O(n²) porównań; pamięć pomocnicza wynosi O(1).
W praktyce
Dla [4, 2, 3] wybieramy 2, zamieniamy z 4, następnie wybieramy 3. Wynik to [2, 3, 4]. Funkcje modyfikują dane w miejscu.
Kod Python 3
def sortuj(a):
for i in range(len(a) - 1):
minimum = i
for j in range(i + 1, len(a)):
if a[j] < a[minimum]:
minimum = j
a[i], a[minimum] = a[minimum], a[i]
return a
a = [8, 3, 6, 1, 9, 2]
print(sortuj(a)) # [1, 2, 3, 6, 8, 9]
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
vector<int>& sortuj(vector<int>& a) {
for (int i = 0; i + 1 < int(a.size()); ++i) {
int minimum = i;
for (int j = i + 1; j < int(a.size()); ++j)
if (a[j] < a[minimum]) minimum = j;
swap(a[i], a[minimum]);
}
return a;
}
int main() {
vector<int> a = {8, 3, 6, 1, 9, 2};
for (int x : sortuj(a)) cout << x << " ";
cout << "\n";
}
Jak to działa
Dziel tablicę na połowy, dopóki fragmenty nie mają najwyżej jednego elementu. Sortuj obie połowy rekurencyjnie. Podczas scalania porównuj ich pierwsze niewykorzystane elementy i przenoś mniejszy do wyniku. Na końcu dopisz pozostałe wartości.
Gdzie spotkasz ten algorytm
Przy porządkowaniu dużych danych, łączeniu uporządkowanych strumieni i zadaniach wymagających stabilności oraz gwarantowanego czasu O(n log n).
Na co uważać
Po wyczerpaniu jednej połowy dopisz drugą. Przy równości wybieraj element z lewej, aby zachować stabilność. Potrzebna jest dodatkowa pamięć O(n); stos rekurencji ma głębokość O(log n).
W praktyce
Dla [4, 1, 3, 2] połówki stają się [1, 4] i [2, 3], a scalanie daje [1, 2, 3, 4]. Poniższy wariant zwraca nową uporządkowaną kolekcję.
Kod Python 3
def sortuj(a):
if len(a) <= 1:
return a[:]
srodek = len(a) // 2
lewa = sortuj(a[:srodek])
prawa = sortuj(a[srodek:])
i = j = 0
wynik = []
while i < len(lewa) and j < len(prawa):
if lewa[i] <= prawa[j]:
wynik.append(lewa[i])
i += 1
else:
wynik.append(prawa[j])
j += 1
return wynik + lewa[i:] + prawa[j:]
a = [8, 3, 6, 1, 9, 2]
print(sortuj(a)) # [1, 2, 3, 6, 8, 9]
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
vector<int> sortuj(const vector<int>& a) {
if (a.size() <= 1) return a;
auto s = a.begin() + a.size()/2;
auto lewa = sortuj(vector<int>(a.begin(), s));
auto prawa = sortuj(vector<int>(s, a.end()));
vector<int> wynik;
size_t 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;
}
int main() {
vector<int> a = {8, 3, 6, 1, 9, 2};
for (int x : sortuj(a)) cout << x << " ";
cout << "\n";
}
Jak to działa
Wybierz pivot. Przeglądając fragment, odkładaj wartości mniejsze od pivota na jego lewą stronę. Umieść pivot między częściami, a następnie rekurencyjnie sortuj obie strony bez pozycji pivota. Kod używa ostatniego elementu jako pivota, tak jak demonstracja.
Gdzie spotkasz ten algorytm
Przy sortowaniu w pamięci oraz jako punkt wyjścia do algorytmów wyboru k-tego elementu. W praktycznych bibliotekach stosuje się dodatkowe zabezpieczenia przed niekorzystnymi podziałami.
Na co uważać
Po podziale przedziały muszą się zmniejszać. Ostatni element jako pivot jest złym wyborem dla danych uporządkowanych lub wielu jednakowych wartości: czas i głębokość rekurencji mogą wynieść O(n²) i O(n). Sortowanie nie jest stabilne.
W praktyce
Dla [3, 1, 2] pivot 2 oddziela [1] od [3]. Kod sortuje w miejscu. Średni czas to O(n log n); do dużych danych warto użyć losowania pivota lub gotowego sortowania bibliotecznego.
Kod Python 3
def sortuj(a):
def quick(lewy, prawy):
if lewy >= prawy:
return
pivot = a[prawy]
i = lewy
for j in range(lewy, prawy):
if a[j] < pivot:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[prawy] = a[prawy], a[i]
quick(lewy, i - 1)
quick(i + 1, prawy)
quick(0, len(a) - 1)
return a
a = [8, 3, 6, 1, 9, 2]
print(sortuj(a)) # [1, 2, 3, 6, 8, 9]
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
void quick(vector<int>& a, int lewy, int prawy) {
if (lewy >= prawy) return;
int pivot = a[prawy], i = lewy;
for (int j = lewy; j < prawy; ++j) {
if (a[j] < pivot) { swap(a[i], a[j]); ++i; }
}
swap(a[i], a[prawy]);
quick(a, lewy, i-1);
quick(a, i+1, prawy);
}
vector<int>& sortuj(vector<int>& a) {
quick(a, 0, int(a.size()) - 1);
return a;
}
int main() {
vector<int> a = {8, 3, 6, 1, 9, 2};
for (int x : sortuj(a)) cout << x << " ";
cout << "\n";
}
Jak to działa
Utwórz licznik dla każdej dopuszczalnej wartości. Przejdź po danych i zwiększaj odpowiednie liczniki. Następnie odczytaj wartości od najmniejszej do największej, wypisując każdą tyle razy, ile wskazuje jej licznik.
Gdzie spotkasz ten algorytm
Przy ocenach, małych kodach kategorii i innych liczbach całkowitych z niewielkiego zakresu. Jest bliskie budowaniu histogramu częstości.
Na co uważać
Koszt O(n+k) zależy także od zakresu k. Wartości rzędu miliarda mogą wymagać ogromnej tablicy liczników. Przykład celowo przyjmuje tylko 0–99. Rekonstrukcja samych liczb nie wystarcza do stabilnego sortowania rekordów z dodatkowymi polami.
W praktyce
Dla [2, 1, 2] liczniki wartości 1 i 2 wynoszą 1 i 2. Wynik to [1, 2, 2]. Kod zwraca nową kolekcję; pusty zbiór daje pusty wynik.
Kod Python 3
def sortuj(a):
licznik = [0] * 100
for x in a:
if not 0 <= x <= 99:
raise ValueError("Dozwolone liczby: 0–99")
licznik[x] += 1
wynik = []
for x, ile in enumerate(licznik):
wynik.extend([x] * ile)
return wynik
a = [8, 3, 6, 1, 9, 2]
print(sortuj(a)) # [1, 2, 3, 6, 8, 9]
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
vector<int> sortuj(const vector<int>& a) {
vector<int> licznik(100, 0), wynik;
for (int x : a) {
if (x < 0 || x > 99) throw invalid_argument("Zakres 0–99");
++licznik[x];
}
for (int x = 0; x < 100; ++x)
for (int i = 0; i < licznik[x]; ++i) wynik.push_back(x);
return wynik;
}
int main() {
vector<int> a = {8, 3, 6, 1, 9, 2};
for (int x : sortuj(a)) cout << x << " ";
cout << "\n";
}
Jak to działa
Sprawdzaj elementy w kolejności od indeksu 0. Jeśli wartość jest równa szukanej, zwróć jej indeks. Gdy przejdziesz cały zbiór bez dopasowania, zwróć −1. Dane nie muszą być posortowane.
Gdzie spotkasz ten algorytm
Przy pojedynczym wyszukiwaniu w krótkiej liście, przeglądaniu rekordów spełniających warunek albo danych napływających kolejno.
Na co uważać
Wynik 0 oznacza znalezienie na pierwszej pozycji, a nie brak wyniku. Przy powtórzeniach ten wariant zwraca pierwsze wystąpienie. Najgorszy czas O(n), dodatkowa pamięć O(1).
W praktyce
W [8, 3, 6] liczba 6 jest na indeksie 2. Dla 7 funkcja zwróci −1. Nie opłaca się sortować całej listy tylko po to, aby wykonać jedno wyszukiwanie.
Kod Python 3
def szukaj(a, x):
for i, wartosc in enumerate(a):
if wartosc == x:
return i
return -1
print(szukaj([8, 3, 6], 6)) # 2
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
int szukaj(const vector<int>& a, int x) {
for (int i = 0; i < int(a.size()); ++i)
if (a[i] == x) return i;
return -1;
}
int main() {
cout << szukaj({8, 3, 6}, 6) << "\n"; // 2
}
Jak to działa
Utrzymuj lewy i prawy koniec przedziału. Sprawdź jego środek. Gdy środkowa wartość jest za mała, przesuń lewy koniec za środek; gdy za duża, przesuń prawy przed środek. Równość kończy wyszukiwanie.
Gdzie spotkasz ten algorytm
Przy wielokrotnym szukaniu w posortowanych tablicach, słownikach i problemach szukania granicy monotonicznego warunku.
Na co uważać
Dane muszą być niemalejące. Kod zakłada ten warunek, nie sortuje ani nie sprawdza go za Ciebie. Aktualizuj granice o jeden za środek, aby uniknąć nieskończonej pętli. Przy powtórzeniach wynik nie musi być pierwszym wystąpieniem.
W praktyce
W [1, 2, 3, 6, 8, 9] szukamy 6, odrzucając kolejne połowy. Czas O(log n), pamięć O(1). Jeśli musisz wcześniej sortować dane, uwzględnij osobno koszt sortowania.
Kod Python 3
def szukaj(a, x):
lewy, prawy = 0, len(a) - 1
while lewy <= prawy:
srodek = lewy + (prawy - lewy) // 2
if a[srodek] == x:
return srodek
if a[srodek] < x:
lewy = srodek + 1
else:
prawy = srodek - 1
return -1
print(szukaj([1, 2, 3, 6, 8, 9], 6)) # 3
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
int szukaj(const vector<int>& a, int x) {
int lewy = 0, prawy = int(a.size()) - 1;
while (lewy <= prawy) {
int srodek = lewy + (prawy - lewy)/2;
if (a[srodek] == x) return srodek;
if (a[srodek] < x) lewy = srodek + 1;
else prawy = srodek - 1;
}
return -1;
}
int main() {
cout << szukaj({1, 2, 3, 6, 8, 9}, 6) << "\n"; // 3
}
Jak to działa
Ustal F(0)=0 i F(1)=1. Dla n większego od 1 oblicz osobno F(n−1) oraz F(n−2) i dodaj wyniki. Wywołania tworzą drzewo, a te same podproblemy pojawiają się w nim wiele razy.
Gdzie spotkasz ten algorytm
Przy nauce rekurencji, zapamiętywania wyników i liczeniu sposobów wejścia po schodach krokami długości 1 albo 2.
Na co uważać
Nie pomyl numeracji pierwszych wyrazów. Naiwna rekurencja ma czas O(φⁿ) i stos O(n), więc duże n szybko staje się niepraktyczne. Kod ogranicza n do 30, aby przykład nie trwał nadmiernie długo.
W praktyce
F(5)=5, bo F(4)=3 i F(3)=2. Do rzeczywistych obliczeń użyj pętli lub pamięci podręcznej: unikasz wtedy wielokrotnego obliczania tych samych wyrazów.
Kod Python 3
def fibonacci(n):
if not 0 <= n <= 30:
raise ValueError("Przykład: n od 0 do 30")
def f(k):
if k < 2:
return k
return f(k - 1) + f(k - 2)
return f(n)
print(fibonacci(5)) # 5
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
long long fib(int n) {
if (n < 2) return n;
return fib(n-1) + fib(n-2);
}
long long fibonacci(int n) {
if (n < 0 || n > 30) throw invalid_argument("n od 0 do 30");
return fib(n);
}
int main() {
cout << fibonacci(5) << "\n"; // 5
}
Jak to działa
Korzystaj z własności NWD(a,b)=NWD(b,a mod b). Dopóki b jest różne od zera, zastępuj parę liczb drugą liczbą i resztą. Gdy b=0, pierwsza liczba jest wynikiem. Pętla i rekurencja realizują tę samą regułę.
Gdzie spotkasz ten algorytm
Przy skracaniu ułamków, wyznaczaniu wspólnych okresów i obliczaniu NWW. Rozszerzona wersja pozwala również znajdować odwrotności modularne.
Na co uważać
Przykład obsługuje nieujemne liczby. Dla (0,0) przyjmujemy programistyczną konwencję wyniku 0. Zmienne aktualizuj jednocześnie albo przez zmienną pomocniczą. Liczba kroków jest logarytmiczna dla dodatnich argumentów.
W praktyce
Dla (48,18) kolejne pary to (18,12), (12,6), (6,0), więc NWD=6. Iteracyjny kod potrzebuje O(1) pamięci dodatkowej.
Kod Python 3
def nwd(a, b):
if a < 0 or b < 0:
raise ValueError("Podaj liczby nieujemne")
while b != 0:
a, b = b, a % b
return a
print(nwd(48, 18)) # 6
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
long long nwd(long long a, long long b) {
if (a < 0 || b < 0) throw invalid_argument("Liczby nieujemne");
while (b != 0) {
long long reszta = a % b;
a = b;
b = reszta;
}
return a;
}
int main() {
cout << nwd(48, 18) << "\n"; // 6
}
Jak to działa
Aby przenieść n krążków ze słupka A na C, przenieś najpierw n−1 krążków z A na B, korzystając z C. Następnie przenieś największy krążek z A na C. Na końcu przenieś mniejszą wieżę z B na C, korzystając z A.
Gdzie spotkasz ten algorytm
W łamigłówkach i ćwiczeniach rozkładania problemu na mniejsze zadania. To czytelny przykład rekurencji z dwoma wywołaniami i rosnącą wykładniczo liczbą działań.
Na co uważać
Nie kładź większego krążka na mniejszym. Zachowaj role źródła, celu i słupka pomocniczego przy każdym wywołaniu. Dla n=0 nic nie przenosimy. Liczba ruchów to 2ⁿ−1, a stos zajmuje O(n).
W praktyce
Dla 3 krążków potrzeba 7 ruchów. Kod wypisuje polecenia przeniesienia; ze względu na długość wydruku ogranicza przykład do 15 krążków.
Kod Python 3
def hanoi(n, zrodlo="A", pomoc="B", cel="C"):
if not 0 <= n <= 15:
raise ValueError("Przykład: 0–15 krążków")
if n == 0:
return
hanoi(n - 1, zrodlo, cel, pomoc)
print(n, zrodlo, "->", cel)
hanoi(n - 1, pomoc, zrodlo, cel)
hanoi(3) # 7 ruchów
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
void hanoi(int n, char zrodlo='A', char pomoc='B', char cel='C') {
if (n < 0 || n > 15) throw invalid_argument("0–15 krazkow");
if (n == 0) return;
hanoi(n-1, zrodlo, cel, pomoc);
cout << n << " " << zrodlo << " -> " << cel << "\n";
hanoi(n-1, pomoc, zrodlo, cel);
}
int main() {
hanoi(3); // 7 ruchow
}
Jak to działa
Silnia liczby n jest iloczynem liczb od 1 do n. Rekurencja opiera się na n!=n·(n−1)! i kończy na 0!=1. Podczas powrotów z wywołań wykonujemy kolejne mnożenia.
Gdzie spotkasz ten algorytm
Przy liczeniu permutacji, ustawianiu różnych obiektów w kolejności i we wzorach kombinatorycznych.
Na co uważać
Przypadek bazowy musi zwracać 1. Silnia nie jest w tym przykładzie określona dla ujemnych argumentów. W C++ 20! mieści się w long long, ale 21! już nie; oba przykłady ograniczono do n=20.
W praktyce
Dla pięciu różnych książek liczba ustawień wynosi 5!=120. Rekurencja wykonuje O(n) mnożeń i używa O(n) stosu; pętla pozwala ograniczyć pamięć pomocniczą.
Kod Python 3
def silnia(n):
if not 0 <= n <= 20:
raise ValueError("Przykład: n od 0 do 20")
if n == 0:
return 1
return n * silnia(n - 1)
print(silnia(5)) # 120
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
long long silnia(int n) {
if (n < 0 || n > 20) throw invalid_argument("n od 0 do 20");
if (n == 0) return 1;
return n * silnia(n-1);
}
int main() {
cout << silnia(5) << "\n"; // 120
}
Jak to działa
Zapisz sumę od 1 do n jako n plus sumę od 1 do n−1. Dla n=0 zwróć 0. Każde wywołanie zmniejsza problem o jeden, a wynik narasta podczas powrotów.
Gdzie spotkasz ten algorytm
W pierwszych ćwiczeniach rekurencji i analizie sum opisujących liczbę operacji algorytmu, np. 1+2+…+n.
Na co uważać
Brak warunku końcowego powoduje kolejne wywołania aż do wyczerpania stosu. Rekurencja ma czas i pamięć O(n). Kod ogranicza n do 100; dla dużych argumentów użyj wzoru i odpowiednio szerokiego typu.
W praktyce
Dla n=5 wyniki powrotów wynoszą 0, 1, 3, 6, 10, 15. W praktyce tę konkretną sumę szybciej obliczysz wzorem n·(n+1)/2.
Kod Python 3
def suma(n):
if not 0 <= n <= 100:
raise ValueError("Przykład: n od 0 do 100")
if n == 0:
return 0
return n + suma(n - 1)
print(suma(5)) # 15
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
long long suma(int n) {
if (n < 0 || n > 100) throw invalid_argument("n od 0 do 100");
if (n == 0) return 0;
return n + suma(n-1);
}
int main() {
cout << suma(5) << "\n"; // 15
}
Jak to działa
Iloczyn a·b dla nieujemnego b to suma b kopii liczby a. Jeśli b=0, zwróć 0; w przeciwnym razie dodaj a do wyniku mnożenia a przez b−1.
Gdzie spotkasz ten algorytm
W ćwiczeniach definiowania działań przez prostsze operacje i rozumienia parametru, który zbliża rekurencję do końca.
Na co uważać
W tym wariancie drugi argument musi być nieujemny. Zmniejszamy b, nie a. Koszt czasu i stosu wynosi O(b), więc metoda jest niepraktyczna dla dużego mnożnika. Przykład ma jawne ograniczenia danych.
W praktyce
Dla (5,3) otrzymujemy 5+(5+(5+0))=15. Zwykłe mnożenie operatorem * jest właściwym wyborem w codziennym kodzie; tutaj celowo pokazujemy mechanizm rekurencji.
Kod Python 3
def mnoz(a, b):
if not -1000000 <= a <= 1000000 or not 0 <= b <= 100:
raise ValueError("|a| <= 1000000, 0 <= b <= 100")
if b == 0:
return 0
return a + mnoz(a, b - 1)
print(mnoz(5, 3)) # 15
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
long long mnoz(long long a, int b) {
if (a < -1000000 || a > 1000000 || b < 0 || b > 100)
throw invalid_argument("|a| <= 1000000, b od 0 do 100");
if (b == 0) return 0;
return a + mnoz(a, b-1);
}
int main() {
cout << mnoz(5, 3) << "\n"; // 15
}
Jak to działa
Wstaw wierzchołek startowy do kolejki i ustaw jego odległość na 0. Zdejmuj pierwszy oczekujący wierzchołek, a nieodwiedzonych sąsiadów oznaczaj i dodawaj na koniec kolejki. Ich odległość jest o 1 większa. W ten sposób odwiedzasz graf warstwami.
Gdzie spotkasz ten algorytm
W szukaniu najmniejszej liczby przejść w labiryncie, stopnia oddalenia w sieci znajomości i najkrótszych ścieżek w grafach bez wag.
Na co uważać
Oznacz wierzchołek już przy dodaniu do kolejki, aby nie dodawać go wielokrotnie. BFS minimalizuje liczbę krawędzi, nie dowolne koszty. Kod zakłada poprawną listę sąsiedztwa z numerami 0…V−1 oraz poprawny start.
W praktyce
Dla grafu 0–1, 0–2, 1–3 odległości od 0 wynoszą [0,1,1,2]. −1 oznacza brak połączenia ze startem. Czas O(V+E), pamięć pomocnicza O(V).
Kod Python 3
from collections import deque
def bfs(g, start):
odleglosc = [-1] * len(g)
odleglosc[start] = 0
kolejka = deque([start])
while kolejka:
v = kolejka.popleft()
for u in g[v]:
if odleglosc[u] == -1:
odleglosc[u] = odleglosc[v] + 1
kolejka.append(u)
return odleglosc
g = [[1, 2], [0, 3], [0], [1]]
print(bfs(g, 0)) # [0, 1, 1, 2]
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
vector<int> bfs(const vector<vector<int>>& g, int start) {
vector<int> d(g.size(), -1);
queue<int> q;
d[start] = 0;
q.push(start);
while (!q.empty()) {
int v = q.front(); q.pop();
for (int u : g[v]) if (d[u] == -1) {
d[u] = d[v] + 1;
q.push(u);
}
}
return d;
}
int main() {
vector<vector<int>> g = {{1,2}, {0,3}, {0}, {1}};
for (int d : bfs(g, 0)) cout << d << " ";
}
Jak to działa
Oznacz bieżący wierzchołek jako odwiedzony. Dla każdego nieodwiedzonego sąsiada wywołaj tę samą procedurę. Po zbadaniu jego gałęzi wróć do poprzedniego wierzchołka i sprawdź następnego sąsiada.
Gdzie spotkasz ten algorytm
Przy badaniu spójności, przeszukiwaniu drzew, analizie zależności oraz jako podstawa wykrywania cykli i sortowania topologicznego. Te dwa ostatnie zadania wymagają dodatkowych informacji o stanie wierzchołka.
Na co uważać
Samo DFS nie gwarantuje najkrótszej ścieżki. Pomijanie oznaczenia odwiedzin zapętla przejście po cyklu. Głęboki graf może przepełnić stos; wtedy użyj wersji iteracyjnej. Kod zakłada poprawne indeksy w liście sąsiedztwa.
W praktyce
Dla listy sąsiedztwa z przykładu kolejność od 0 to [0,1,3,2]. Zmiana kolejności sąsiadów może zmienić wynik. Czas O(V+E), pamięć O(V); aby zbadać graf niespójny, uruchamiaj przejście także z nieodwiedzonych składowych.
Kod Python 3
def dfs(g, start):
odwiedzony = [False] * len(g)
kolejnosc = []
def odwiedz(v):
odwiedzony[v] = True
kolejnosc.append(v)
for u in g[v]:
if not odwiedzony[u]:
odwiedz(u)
odwiedz(start)
return kolejnosc
g = [[1, 2], [0, 3], [0], [1]]
print(dfs(g, 0)) # [0, 1, 3, 2]
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
vector<int> dfs(const vector<vector<int>>& g, int start) {
vector<bool> widziany(g.size(), false);
vector<int> wynik;
function<void(int)> odwiedz = [&](int v) {
widziany[v] = true;
wynik.push_back(v);
for (int u : g[v]) if (!widziany[u]) odwiedz(u);
};
odwiedz(start);
return wynik;
}
int main() {
vector<vector<int>> g = {{1,2}, {0,3}, {0}, {1}};
for (int v : dfs(g, 0)) cout << v << " ";
}
Jak to działa
Ustaw odległość startu na 0, a pozostałe na nieskończoność. Wybierz nieustalony wierzchołek o najmniejszej odległości. Ustal jego wynik i sprawdź, czy przejście przez niego skraca drogi do sąsiadów. Powtarzaj, dopóki istnieją osiągalne wierzchołki.
Gdzie spotkasz ten algorytm
W wyznaczaniu najtańszych tras, opóźnień połączeń i najkrótszych dróg, gdy wszystkie wagi są nieujemne.
Na co uważać
Ujemne wagi łamią założenie algorytmu. Nie myl braku krawędzi z wagą 0. Kod korzysta z listy sąsiedztwa i liniowego wyboru minimum: O(V²+E), jak wariant demonstracyjny. Kolejka priorytetowa pozwala usprawnić wybór w rzadkich grafach.
W praktyce
W grafie 0→1 o wadze 4, 0→2 o wadze 2 i 2→1 o wadze 1 droga do 1 ma koszt 3. Wynik ∞/INF oznacza brak drogi. Zakładamy poprawne indeksy; w C++ długości rozpatrywanych dróg muszą być mniejsze od INF.
Kod Python 3
def dijkstra(g, start):
if any(w < 0 for krawedzie in g for _, w in krawedzie):
raise ValueError("Wagi muszą być nieujemne")
n = len(g)
d = [float("inf")] * n
ustalony = [False] * n
d[start] = 0
for _ in range(n):
v = -1
for u in range(n):
if not ustalony[u] and (v == -1 or d[u] < d[v]):
v = u
if v == -1 or d[v] == float("inf"):
break
ustalony[v] = True
for u, w in g[v]:
d[u] = min(d[u], d[v] + w)
return d
g = [[(1, 4), (2, 2)], [], [(1, 1)]]
print(dijkstra(g, 0)) # [0, 3, 2]
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
const long long INF = numeric_limits<long long>::max()/4;
vector<long long> dijkstra(const vector<vector<pair<int,int>>>& g, int start) {
for (const auto& edges : g)
for (auto [u,w] : edges)
if (w < 0) throw invalid_argument("Ujemna waga");
int n = int(g.size());
vector<long long> d(n, INF);
vector<bool> ustalony(n, false);
d[start] = 0;
for (int i = 0; i < n; ++i) {
int v = -1;
for (int u = 0; u < n; ++u)
if (!ustalony[u] && (v == -1 || d[u] < d[v])) v = u;
if (v == -1 || d[v] == INF) break;
ustalony[v] = true;
for (auto [u,w] : g[v])
if (d[v] <= INF-w) d[u] = min(d[u], d[v]+w);
}
return d;
}
int main() {
vector<vector<pair<int,int>>> g = {{{1,4},{2,2}}, {}, {{1,1}}};
for (auto d : dijkstra(g, 0)) cout << d << " ";
}
Jak to działa
W komórce dp[i][w] zapisz najlepszą wartość uzyskaną z pierwszych i przedmiotów przy pojemności w. Porównaj pominięcie przedmiotu z jego wzięciem: wtedy dodajesz jego wartość do wyniku dla mniejszej pojemności i wcześniejszych przedmiotów.
Gdzie spotkasz ten algorytm
Przy doborze ograniczonego zestawu zakupów, zadań lub wyposażenia, gdy każdy element można wybrać najwyżej raz, a koszty są całkowite.
Na co uważać
Wariant 0/1 nie pozwala brać przedmiotu wielokrotnie ani dzielić go na części. Kod zakłada dodatnie całkowite wagi, nieujemne wartości i pojemność. Czas i pamięć wynoszą O(nW); koszt zależy od wartości W, więc to algorytm pseudowielomianowy.
W praktyce
Dla (waga,wartość)=(2,3),(3,4),(4,5),(5,8) i W=7 wybieramy przedmioty o wagach 2 i 5, uzyskując 11. Kod zwraca optymalną wartość; zestaw można odtworzyć cofając się po tabeli.
Kod Python 3
def plecak(przedmioty, W):
if W < 0 or any(w <= 0 or v < 0 for w, v in przedmioty):
raise ValueError("Niepoprawna waga, wartość lub pojemność")
dp = [[0] * (W + 1) for _ in range(len(przedmioty) + 1)]
for i, (waga, wartosc) in enumerate(przedmioty, 1):
for w in range(W + 1):
dp[i][w] = dp[i - 1][w]
if waga <= w:
dp[i][w] = max(dp[i][w], dp[i - 1][w - waga] + wartosc)
return dp[-1][W]
print(plecak([(2, 3), (3, 4), (4, 5), (5, 8)], 7)) # 11
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
long long plecak(const vector<pair<int,int>>& p, int W) {
if (W < 0) throw invalid_argument("Ujemna pojemnosc");
for (auto [w,v] : p)
if (w <= 0 || v < 0) throw invalid_argument("Niepoprawny przedmiot");
vector<vector<long long>> dp(p.size()+1, vector<long long>(W+1, 0));
for (size_t i = 1; i <= p.size(); ++i) {
auto [waga, wartosc] = p[i-1];
for (int w = 0; w <= W; ++w) {
dp[i][w] = dp[i-1][w];
if (waga <= w) dp[i][w] = max(dp[i][w], dp[i-1][w-waga]+wartosc);
}
}
return dp.back()[W];
}
int main() {
cout << plecak({{2,3},{3,4},{4,5},{5,8}}, 7) << "\n"; // 11
}
Jak to działa
Porównuj prefiksy dwóch napisów. Jeśli ostatnie znaki są równe, dodaj 1 do wyniku dla obu krótszych prefiksów. W przeciwnym razie wybierz większy wynik po skróceniu jednego z nich. Gotowa tabela pozwala cofnąć się i odtworzyć wspólny podciąg.
Gdzie spotkasz ten algorytm
W porównywaniu wersji tekstu i sekwencji. LCS jest modelem zachowania wspólnej kolejności elementów mimo pominięć i stanowi podstawę niektórych metod pokazywania różnic.
Na co uważać
Podciąg nie musi być spójny: możesz pominąć znaki. To inne zadanie niż najdłuższy wspólny fragment. Może istnieć kilka poprawnych wyników tej samej długości. C++ w tym przykładzie porównuje bajty; dla obu języków użyj tekstu ASCII.
W praktyce
Dla MATURA i NATURA wynikiem jest ATURA o długości 5. Czas O(nm), pamięć O(nm). Gdy potrzebujesz tylko długości, można przechowywać dwa wiersze zamiast całej tabeli.
Kod Python 3
def lcs(a, b):
dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
i, j = len(a), len(b)
wynik = []
while i and j:
if a[i - 1] == b[j - 1]:
wynik.append(a[i - 1])
i, j = i - 1, j - 1
elif dp[i - 1][j] >= dp[i][j - 1]:
i -= 1
else:
j -= 1
return "".join(reversed(wynik))
print(lcs("MATURA", "NATURA")) # ATURA
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
string lcs(const string& a, const string& b) {
int n = int(a.size()), m = int(b.size());
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
for (int i=1; i<=n; ++i) for (int j=1; j<=m; ++j)
dp[i][j] = a[i-1]==b[j-1] ? dp[i-1][j-1]+1 : max(dp[i-1][j],dp[i][j-1]);
string wynik;
int i=n, j=m;
while (i>0 && j>0) {
if (a[i-1]==b[j-1]) { wynik += a[i-1]; --i; --j; }
else if (dp[i-1][j]>=dp[i][j-1]) --i;
else --j;
}
reverse(wynik.begin(), wynik.end());
return wynik;
}
int main() {
cout << lcs("MATURA", "NATURA") << "\n"; // ATURA
}
Jak to działa
Zamień literę na numer od 0 do 25, dodaj przesunięcie i oblicz resztę z dzielenia przez 26. Zamień wynik z powrotem na literę. Reszta sprawia, że po Z znów pojawia się A. Odszyfrowanie używa przeciwnego przesunięcia.
Gdzie spotkasz ten algorytm
W historycznych szyfrach, łamigłówkach i nauce arytmetyki modularnej. To ćwiczenie przetwarzania znaków, a nie sposób ochrony poufnych danych.
Na co uważać
Przykład obsługuje wielkie i małe litery alfabetu łacińskiego ASCII, pozostałe znaki pozostawia bez zmian. W C++ ujemną resztę trzeba znormalizować. Klucz ma tylko 26 wariantów, więc szyfr łatwo złamać.
W praktyce
Dla MATURA i klucza 3 otrzymujemy PDWXUD. Ponowne zastosowanie z kluczem −3 odtwarza tekst. Czas O(n), pamięć wyniku O(n).
Kod Python 3
def cezar(tekst, klucz):
wynik = []
for c in tekst:
if "A" <= c <= "Z":
baza = ord("A")
elif "a" <= c <= "z":
baza = ord("a")
else:
wynik.append(c)
continue
wynik.append(chr(baza + (ord(c) - baza + klucz) % 26))
return "".join(wynik)
s = cezar("MATURA", 3)
print(s) # PDWXUD
print(cezar(s, -3)) # MATURA
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
string cezar(string tekst, int klucz) {
int k = (klucz % 26 + 26) % 26;
for (char& c : tekst) {
if (c >= 'A' && c <= 'Z') c = char('A' + (c-'A'+k)%26);
else if (c >= 'a' && c <= 'z') c = char('a' + (c-'a'+k)%26);
}
return tekst;
}
int main() {
string s = cezar("MATURA", 3);
cout << s << "\n" << cezar(s, -3) << "\n";
}
Jak to działa
W demonstracji wybieramy p=11 i q=13, więc n=143 i φ(n)=120. Wykładniki e=7 i d=103 spełniają e·d mod 120=1. Szyfrujemy liczbę m jako mᵉ mod n, a odszyfrowujemy szyfrogram c jako cᵈ mod n. Szybkie potęgowanie wielokrotnie podnosi podstawę do kwadratu.
Gdzie spotkasz ten algorytm
W kryptografii klucza publicznego, m.in. w schematach szyfrowania i podpisu. Rzeczywiste implementacje stosują duże klucze i odpowiednie schematy kodowania wiadomości.
Na co uważać
To wyłącznie mały przykład matematyczny. Nie chroni danych: moduł łatwo rozłożyć, a surowe RSA bez bezpiecznego dopełnienia nie nadaje się do użycia produkcyjnego. Wiadomość musi spełniać 0≤m<143. Nie stosuj pokazanych stałych jako prawdziwych kluczy.
W praktyce
Dla m=42 szyfrogram wynosi 81, a odszyfrowanie daje 42. Kod C++ ma bezpieczne mnożenia dzięki małemu, stałemu modułowi. Liczba mnożeń modularnych jest O(log e) lub O(log d); dla dużych liczb koszt pojedynczego mnożenia też ma znaczenie.
Kod Python 3
def rsa_demo(m):
if not 0 <= m < 143:
raise ValueError("Wiadomość od 0 do 142")
szyfrogram = pow(m, 7, 143)
odczyt = pow(szyfrogram, 103, 143)
return szyfrogram, odczyt
print(rsa_demo(42)) # (81, 42)
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
long long potega_mod(long long a, int e) {
long long wynik = 1;
while (e > 0) {
if (e % 2 == 1) wynik = wynik * a % 143;
a = a * a % 143;
e /= 2;
}
return wynik;
}
pair<long long,long long> rsa_demo(int m) {
if (m < 0 || m >= 143) throw invalid_argument("Wiadomosc 0–142");
long long c = potega_mod(m, 7);
return {c, potega_mod(c, 103)};
}
int main() {
auto [c, m] = rsa_demo(42);
cout << c << " " << m << "\n"; // 81 42
}
Jak to działa
Przygotuj tablicę kandydatów od 0 do n. Oznacz 0 i 1 jako niepierwsze. Dla każdej nieprzekreślonej liczby p, aż do √n, wykreślaj jej wielokrotności od p². Pozostałe kandydaty są liczbami pierwszymi.
Gdzie spotkasz ten algorytm
Gdy potrzebujesz wszystkich liczb pierwszych do ustalonej granicy albo wielu odpowiedzi na pytanie o pierwszość w tym samym zakresie.
Na co uważać
Nie uznawaj 1 za liczbę pierwszą. Zaczynanie wykreślania od p² unika części powtórzeń, bo mniejsze wielokrotności mają już mniejszy dzielnik. Tablica zajmuje O(n) pamięci; bardzo duża granica wymaga innego podejścia, np. sita segmentowego.
W praktyce
Dla n=20 wynikiem jest [2,3,5,7,11,13,17,19]. Czas klasycznego sita to O(n log log n). Kod ogranicza przykład do miliona, aby rozmiar tablicy był przewidywalny.
Kod Python 3
def sito(n):
if not 0 <= n <= 1000000:
raise ValueError("Przykład: n od 0 do 1000000")
pierwsza = [True] * (n + 1)
pierwsza[0] = False
if n >= 1:
pierwsza[1] = False
p = 2
while p * p <= n:
if pierwsza[p]:
for j in range(p * p, n + 1, p):
pierwsza[j] = False
p += 1
return [i for i, ok in enumerate(pierwsza) if ok]
print(sito(20)) # [2, 3, 5, 7, 11, 13, 17, 19]
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
vector<int> sito(int n) {
if (n < 0 || n > 1000000) throw invalid_argument("n od 0 do 1000000");
vector<bool> pierwsza(n+1, true);
pierwsza[0] = false;
if (n >= 1) pierwsza[1] = false;
for (int p=2; p<=n/p; ++p)
if (pierwsza[p])
for (int j=p*p; j<=n; j+=p) pierwsza[j] = false;
vector<int> wynik;
for (int i=2; i<=n; ++i) if (pierwsza[i]) wynik.push_back(i);
return wynik;
}
int main() {
for (int p : sito(20)) cout << p << " ";
}
Jak to działa
Dziel liczbę całkowicie przez podstawę b, zapisując każdą resztę. Powtarzaj z otrzymanym ilorazem, aż będzie równy 0. Reszty czytane od końca są cyframi wyniku. Dla podstaw większych niż 10 stosujemy także litery.
Gdzie spotkasz ten algorytm
W zapisie binarnym bitów, szesnastkowym zapisie kolorów i adresów oraz zadaniach dotyczących reprezentacji liczb.
Na co uważać
Dla liczby 0 zwróć napis „0”, a nie pusty wynik. Podstawa musi być co najmniej 2. Przykład obsługuje nieujemne liczby i podstawy do 16; dla liczb ujemnych trzeba osobno obsłużyć znak.
W praktyce
42 dzielone przez 2 daje reszty 0,1,0,1,0,1, więc zapis binarny to 101010. Kod buduje listę cyfr i odwraca ją raz. Liczba kroków i pamięć wyniku wynoszą O(log_b n) dla n>0.
Kod Python 3
def konwertuj(n, b):
if n < 0 or not 2 <= b <= 16:
raise ValueError("n >= 0, podstawa od 2 do 16")
if n == 0:
return "0"
cyfry = "0123456789ABCDEF"
wynik = []
while n > 0:
wynik.append(cyfry[n % b])
n //= b
return "".join(reversed(wynik))
print(konwertuj(42, 2)) # 101010
print(konwertuj(255, 16)) # FF
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
string konwertuj(long long n, int b) {
if (n < 0 || b < 2 || b > 16) throw invalid_argument("n >= 0, b od 2 do 16");
if (n == 0) return "0";
string cyfry = "0123456789ABCDEF", wynik;
while (n > 0) {
wynik += cyfry[n % b];
n /= b;
}
reverse(wynik.begin(), wynik.end());
return wynik;
}
int main() {
cout << konwertuj(42, 2) << "\n" << konwertuj(255, 16) << "\n";
}
Jak to działa
Zapisz współczynniki od najwyższej potęgi do wyrazu wolnego. Zacznij od wyniku 0. Dla każdego współczynnika pomnóż dotychczasowy wynik przez x i dodaj ten współczynnik. Zagnieżdżone mnożenia zastępują osobne liczenie potęg.
Gdzie spotkasz ten algorytm
Przy obliczaniu wielomianów, przeliczaniu wartości zapisu pozycyjnego i w numerycznych modelach opartych na wielomianach.
Na co uważać
Zachowaj kolejność współczynników i wpisuj zera dla brakujących potęg. W C++ kod używa long long i zakłada, że wszystkie wyniki pośrednie mieszczą się w tym typie. Python powiększa liczby całkowite automatycznie, ale ich działania nie mają wtedy stałego kosztu.
W praktyce
Wielomian 2x³+3x²+5x+7 dla x=2 daje kolejno 2,7,19,45. Potrzeba O(n) operacji arytmetycznych i O(1) dodatkowej pamięci, poza samym wynikiem liczbowym.
Kod Python 3
def horner(wspolczynniki, x):
wynik = 0
for a in wspolczynniki:
wynik = wynik * x + a
return wynik
print(horner([2, 3, 5, 7], 2)) # 45
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
long long horner(const vector<long long>& a, long long x) {
long long wynik = 0;
for (long long wspolczynnik : a) wynik = wynik*x + wspolczynnik;
return wynik;
}
int main() {
cout << horner({2,3,5,7}, 2) << "\n"; // 45
}
Jak to działa
Najpierw odrzuć n<2. Następnie sprawdzaj możliwe dzielniki od 2 do √n włącznie. Jeśli któryś dzieli liczbę bez reszty, liczba jest złożona. Brak takiego dzielnika oznacza pierwszość: w każdej parze czynników jeden jest nie większy niż √n.
Gdzie spotkasz ten algorytm
Przy sprawdzaniu pojedynczych niewielkich liczb i nauce podzielności. Dla wielu zapytań z ograniczonego przedziału zwykle lepiej przygotować sito.
Na co uważać
Warunek obejmuje pierwiastek, inaczej pomylisz się dla kwadratów, np. 49. Zapis d<=n/d w C++ unika przepełnienia iloczynu d*d. Algorytm O(√n) jest zbyt wolny dla bardzo dużych liczb.
W praktyce
29 nie ma dzielnika wśród 2,3,4,5, więc jest pierwsza. Dla 49 znajdujemy 7 i kończymy. Pamięć dodatkowa wynosi O(1).
Kod Python 3
def czy_pierwsza(n):
if n < 2:
return False
d = 2
while d * d <= n:
if n % d == 0:
return False
d += 1
return True
print(czy_pierwsza(29)) # True
print(czy_pierwsza(49)) # False
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
bool czy_pierwsza(long long n) {
if (n < 2) return false;
for (long long d=2; d<=n/d; ++d)
if (n%d == 0) return false;
return true;
}
int main() {
cout << boolalpha << czy_pierwsza(29) << "\n" << czy_pierwsza(49) << "\n";
}
Jak to działa
Ustaw początek wzorca na każdej możliwej pozycji tekstu. Porównuj kolejne znaki aż do niezgodności albo końca wzorca. Pełne dopasowanie zapisz, a potem przejdź do następnej pozycji startowej, także gdy dopasowania mogą na siebie nachodzić.
Gdzie spotkasz ten algorytm
Przy krótkich tekstach, prostych filtrach i jako punkt odniesienia do bardziej wydajnych metod wyszukiwania wzorców.
Na co uważać
Ostatni możliwy początek to n−m, włącznie. Gdy wzorzec jest dłuższy niż tekst, wynik jest pusty. Tutaj pusty wzorzec pasuje na wszystkich n+1 granicach tekstu. Dla zgodności indeksów Python/C++ użyj ASCII.
W praktyce
W tekście AAAAA wzorzec AAA zaczyna się na pozycjach [0,1,2]. Czas najgorszy O(nm), pamięć robocza O(1) poza listą dopasowań. C++ liczy pozycje bajtów, a Python pozycje znaków Unicode.
Kod Python 3
def szukaj_wzorca(tekst, wzorzec):
wynik = []
for i in range(len(tekst) - len(wzorzec) + 1):
j = 0
while j < len(wzorzec) and tekst[i + j] == wzorzec[j]:
j += 1
if j == len(wzorzec):
wynik.append(i)
return wynik
print(szukaj_wzorca("AAAAA", "AAA")) # [0, 1, 2]
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
vector<int> szukaj_wzorca(const string& t, const string& p) {
int n = int(t.size()), m = int(p.size());
vector<int> wynik;
for (int i=0; i<=n-m; ++i) {
int j=0;
while (j<m && t[i+j]==p[j]) ++j;
if (j==m) wynik.push_back(i);
}
return wynik;
}
int main() {
for (int i : szukaj_wzorca("AAAAA", "AAA")) cout << i << " ";
}
Jak to działa
Najpierw oblicz LPS: dla każdego prefiksu wzorca długość jego najdłuższego właściwego prefiksu będącego również sufiksem. Przy niezgodności znaków wykorzystaj tę informację do skrócenia dopasowanej części wzorca. Pozycja w tekście nie cofa się.
Gdzie spotkasz ten algorytm
Przy liniowym wyszukiwaniu wzorca, analizie powtarzających się fragmentów i danych, w których naiwna metoda wielokrotnie porównywałaby te same znaki.
Na co uważać
Przy niezgodności cofaj j do lps[j−1], nie do lps[j]. Po pełnym dopasowaniu także skorzystaj z LPS, aby znaleźć nakładające się wystąpienia. Kod obsługuje pusty wzorzec jako dopasowanie na każdej granicy tekstu.
W praktyce
Dla AAAAA i AAA dostaniesz [0,1,2] bez rozpoczynania wszystkich porównań od zera. Czas O(n+m), pamięć robocza O(m), dodatkowo wynik. Tak jak w metodzie naiwnej, użyj ASCII, jeśli indeksy w obu językach mają być identyczne.
Kod Python 3
def kmp(t, p):
if not p:
return list(range(len(t) + 1))
lps = [0] * len(p)
j = 0
for i in range(1, len(p)):
while j and p[i] != p[j]:
j = lps[j - 1]
if p[i] == p[j]:
j += 1
lps[i] = j
wynik = []
j = 0
for i, znak in enumerate(t):
while j and znak != p[j]:
j = lps[j - 1]
if znak == p[j]:
j += 1
if j == len(p):
wynik.append(i - len(p) + 1)
j = lps[j - 1]
return wynik
print(kmp("AAAAA", "AAA")) # [0, 1, 2]
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
vector<int> kmp(const string& t, const string& p) {
int n=int(t.size()), m=int(p.size());
vector<int> wynik;
if (m==0) {
for (int i=0; i<=n; ++i) wynik.push_back(i);
return wynik;
}
vector<int> lps(m,0);
int j=0;
for (int i=1; i<m; ++i) {
while (j>0 && p[i]!=p[j]) j=lps[j-1];
if (p[i]==p[j]) ++j;
lps[i]=j;
}
j=0;
for (int i=0; i<n; ++i) {
while (j>0 && t[i]!=p[j]) j=lps[j-1];
if (t[i]==p[j]) ++j;
if (j==m) { wynik.push_back(i-m+1); j=lps[j-1]; }
}
return wynik;
}
int main() {
for (int i : kmp("AAAAA", "AAA")) cout << i << " ";
}
Jak to działa
Stos działa według zasady LIFO: ostatni dodany element jest pierwszym zdejmowanym. Operacja push/append dodaje na wierzch, top lub indeks −1 odczytuje wierzch, a pop usuwa element z wierzchu.
Gdzie spotkasz ten algorytm
Przy cofaniu działań, obliczaniu ONP, sprawdzaniu nawiasów i obsłudze wywołań funkcji. Stos jest strukturą danych, na której można budować różne algorytmy.
Na co uważać
Nie odczytuj ani nie usuwaj z pustego stosu. W C++ top() odczytuje wartość, a pop() tylko ją usuwa; w Pythonie pop() również zwraca wartość. Dodawanie na koniec listy Pythona ma amortyzowany koszt O(1).
W praktyce
Po dodaniu 3,7,2 zdejmiesz 2,7,3. Pamięć wynosi O(n). Kod pokazuje podstawowe operacje i sprawdza pustkę przed odczytem; std::stack używa domyślnego kontenera deque.
Kod Python 3
def demonstracja_stosu(dane):
stos = []
for x in dane:
stos.append(x)
wynik = []
while stos:
wynik.append(stos.pop())
return wynik
print(demonstracja_stosu([3, 7, 2])) # [2, 7, 3]
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
vector<int> demonstracja_stosu(const vector<int>& dane) {
stack<int> stos;
for (int x : dane) stos.push(x);
vector<int> wynik;
while (!stos.empty()) {
wynik.push_back(stos.top());
stos.pop();
}
return wynik;
}
int main() {
for (int x : demonstracja_stosu({3,7,2})) cout << x << " ";
}
Jak to działa
Kolejka działa według FIFO: pierwszy dodany element zostaje obsłużony jako pierwszy. Nowe elementy dopisujemy na końcu, a do obsługi pobieramy z początku.
Gdzie spotkasz ten algorytm
W BFS, kolejkach zadań i buforowaniu zdarzeń oczekujących na obsługę. Kolejność przyjścia może decydować o kolejności pracy.
Na co uważać
W Pythonie usuwanie pierwszego elementu zwykłej listy przez pop(0) ma koszt O(n). Użyj deque i popleft(). W C++ front() odczytuje, a pop() usuwa. Przed oboma działaniami sprawdź, czy kolejka nie jest pusta.
W praktyce
Po dodaniu 3,7,2 odbierzesz 3,7,2. Wybrane kontenery zapewniają O(1) dla dodawania i zdejmowania z końców; przechowywane elementy zajmują O(n) pamięci.
Kod Python 3
from collections import deque
def demonstracja_kolejki(dane):
kolejka = deque()
for x in dane:
kolejka.append(x)
wynik = []
while kolejka:
wynik.append(kolejka.popleft())
return wynik
print(demonstracja_kolejki([3, 7, 2])) # [3, 7, 2]
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
vector<int> demonstracja_kolejki(const vector<int>& dane) {
queue<int> q;
for (int x : dane) q.push(x);
vector<int> wynik;
while (!q.empty()) {
wynik.push_back(q.front());
q.pop();
}
return wynik;
}
int main() {
for (int x : demonstracja_kolejki({3,7,2})) cout << x << " ";
}
Jak to działa
Czytaj tokeny rozdzielone spacjami. Liczbę odkładaj na stos. Dla operatora zdejmij najpierw prawy argument b, potem lewy a, oblicz a operator b i odłóż wynik. Po przetworzeniu całego wyrażenia na stosie musi zostać dokładnie jedna liczba.
Gdzie spotkasz ten algorytm
W kalkulatorach stosowych, interpretowaniu wyrażeń i nauce sposobu, w jaki zapis operacji może wyeliminować nawiasy oraz reguły pierwszeństwa.
Na co uważać
Kolejność argumentów ma znaczenie dla odejmowania i dzielenia. Sprawdzaj liczbę argumentów, dzielenie przez zero, poprawność tokenów i końcowy rozmiar stosu. Przykład używa liczb zmiennoprzecinkowych i dzielenia rzeczywistego.
W praktyce
Zapis 3 4 + 2 * oznacza (3+4)·2 i daje 14. Liczba operacji jest O(n) dla n tokenów, a stos zajmuje O(n). Liczby z częścią ułamkową zapisuj z kropką; zaokrąglenia są naturalną cechą typu float/double.
Kod Python 3
import math
def onp(tekst):
stos = []
for token in tekst.split():
if token in {"+", "-", "*", "/"}:
if len(stos) < 2:
raise ValueError("Za mało argumentów")
b, a = stos.pop(), stos.pop()
if token == "+":
w = a + b
elif token == "-":
w = a - b
elif token == "*":
w = a * b
else:
if b == 0:
raise ValueError("Dzielenie przez zero")
w = a / b
else:
w = float(token)
if not math.isfinite(w):
raise ValueError("Liczba poza zakresem")
stos.append(w)
if len(stos) != 1:
raise ValueError("Niepoprawne wyrażenie")
return stos[0]
print(onp("3 4 + 2 *")) # 14.0
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
double onp(const string& tekst) {
istringstream wejscie(tekst);
string t;
vector<double> stos;
while (wejscie >> t) {
double w;
if (t=="+" || t=="-" || t=="*" || t=="/") {
if (stos.size()<2) throw invalid_argument("Za malo argumentow");
double b=stos.back(); stos.pop_back();
double a=stos.back(); stos.pop_back();
if (t=="+") w=a+b;
else if (t=="-") w=a-b;
else if (t=="*") w=a*b;
else {
if (b==0) throw invalid_argument("Dzielenie przez zero");
w=a/b;
}
} else {
size_t koniec;
w=stod(t, &koniec);
if (koniec!=t.size()) throw invalid_argument("Niepoprawny token");
}
if (!isfinite(w)) throw invalid_argument("Liczba poza zakresem");
stos.push_back(w);
}
if (stos.size()!=1) throw invalid_argument("Niepoprawne wyrazenie");
return stos.back();
}
int main() {
cout << onp("3 4 + 2 *") << "\n"; // 14
}
Jak to działa
Dla każdego węzła odwiedź rekurencyjnie lewe i prawe poddrzewo. W pre-order odczytaj węzeł przed poddrzewami, w in-order między nimi, a w post-order dopiero po obu poddrzewach. Puste poddrzewo kończy wywołanie.
Gdzie spotkasz ten algorytm
Pre-order nadaje się do zapisu struktury drzewa, in-order do uporządkowanego odczytu drzewa BST, a post-order do obliczeń zależnych od wyników dzieci, np. wartości wyrażenia.
Na co uważać
In-order daje posortowany wynik tylko dla drzewa wyszukiwań BST, nie dla każdego drzewa binarnego. Struktura musi rzeczywiście być drzewem: bez cykli i powtarzających się rodziców. Kod korzysta z indeksów, a −1 oznacza brak dziecka.
W praktyce
Dla drzewa 1 z dziećmi 2 i 3 oraz liśćmi 4,5,6,7: pre-order to 1,2,4,5,3,6,7; in-order: 4,2,5,1,6,3,7; post-order: 4,5,2,6,7,3,1. Czas O(n), stos O(h), gdzie h to wysokość drzewa.
Kod Python 3
def przejdz(drzewo, korzen, tryb):
if tryb not in {"pre", "in", "post"}:
raise ValueError("Tryb: pre, in lub post")
wynik = []
def odwiedz(i):
if i == -1:
return
wartosc, lewy, prawy = drzewo[i]
if tryb == "pre":
wynik.append(wartosc)
odwiedz(lewy)
if tryb == "in":
wynik.append(wartosc)
odwiedz(prawy)
if tryb == "post":
wynik.append(wartosc)
odwiedz(korzen)
return wynik
drzewo = [(1,1,2), (2,3,4), (3,5,6), (4,-1,-1),
(5,-1,-1), (6,-1,-1), (7,-1,-1)]
for tryb in ("pre", "in", "post"):
print(tryb, przejdz(drzewo, 0, tryb))
Kod C++17
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <limits>
#include <stdexcept>
#include <sstream>
#include <cmath>
#include <utility>
using namespace std;
struct Wezel { int wartosc, lewy, prawy; };
vector<int> przejdz(const vector<Wezel>& d, int korzen, const string& tryb) {
if (tryb!="pre" && tryb!="in" && tryb!="post")
throw invalid_argument("Tryb: pre, in, post");
vector<int> wynik;
function<void(int)> odwiedz = [&](int i) {
if (i==-1) return;
if (tryb=="pre") wynik.push_back(d[i].wartosc);
odwiedz(d[i].lewy);
if (tryb=="in") wynik.push_back(d[i].wartosc);
odwiedz(d[i].prawy);
if (tryb=="post") wynik.push_back(d[i].wartosc);
};
odwiedz(korzen);
return wynik;
}
int main() {
vector<Wezel> d = {{1,1,2},{2,3,4},{3,5,6},{4,-1,-1},
{5,-1,-1},{6,-1,-1},{7,-1,-1}};
for (string tryb : {"pre", "in", "post"}) {
cout << tryb << ": ";
for (int x : przejdz(d, 0, tryb)) cout << x << " ";
cout << "\n";
}
}
Jak porównywać sortowania
Uruchom sześć metod na tych samych danych. Porównaj osobno liczbę porównań wartości i zapisów do tablicy. Kod każdej metody znajdziesz po wybraniu jej karty.
W praktyce
Sprawdź dane rosnące, malejące, losowe i z powtórzeniami. Liczniki opisują konkretne implementacje; nie są pomiarem czasu. Zliczanie wykonuje dodatkową pracę na licznikach, więc zero porównań par wartości nie oznacza zerowego kosztu.
Jak czytać złożoność
Notacja O opisuje ograniczenie tempa wzrostu kosztu wraz z rozmiarem danych. Wykres i tabela porównują funkcje modelowe, a nie czas wykonania w sekundach.
W praktyce
Przy podwojeniu n koszt liniowy rośnie około dwukrotnie, kwadratowy około czterokrotnie, a wykładniczy dużo szybciej. Uwzględniaj także pamięć, stałe, reprezentację danych i koszt operacji na dużych liczbach.
Sortowanie
Wyszukiwanie
Rekurencja
Grafy
Programowanie dynamiczne
Kryptografia
Teoria liczb
Teksty i wzorce
Struktury danych
Porównania
Materiały edukacyjne Informatyki z pasją. Własne implementacje i objaśnienia. Zakres tematów na podstawie katalogu Pasjonaci IT.