Algorytmy z podstawy programowej
Podstawa programowa informatyki wymienia kilkanaście klasycznych algorytmów, które uczeń ma umieć zapisać jako program: od algorytmu Euklidesa w klasie 7 po sortowanie przez wstawianie i ciąg Fibonacciego w liceum. Na tych stronach każdy z nich ma opis idei, kod w Pythonie i C++, tabelę z przebiegiem i listę typowych błędów, a także zapisy wymagane w szkole: specyfikację, listę kroków, pseudokod w stylu arkuszy maturalnych i schemat blokowy. Sortowania i wyszukiwanie binarne mają dodatkowo drzewo decyzyjne policzone z prawdziwych przebiegów algorytmu.
Każdy przykład przejdziesz krok po kroku w kursie Algorytmy z podstawy programowej: w przeglądarce, bez instalowania niczego i bez konta. Przycisk Krok wykonuje jedną linię, a podgląd pokazuje wartości zmiennych. Zadania sprawdzają się automatycznie po uruchomieniu programu, a przycisk Algorytm przy lekcji pokazuje listę kroków, pseudokod i schemat blokowy bez wychodzenia z edytora.
Otwórz kurs algorytmów w przeglądarce
Dla zakresu rozszerzonego w liceum i technikum jest drugi kurs: Algorytmy: zakres rozszerzony. Rekurencja, szybkie potęgowanie, rozkład na czynniki pierwsze, jednoczesne minimum i maksimum, sortowanie przez scalanie i szybkie, metoda połowienia, pierwiastek metodą Herona z błędami obliczeń, schemat Hornera, fraktale, podciągi, stos i kolejka z odwrotną notacją polską, metoda zachłanna, programowanie dynamiczne, grafy (przeszukiwanie wszerz, algorytm Dijkstry), szyfrowanie RSA z podpisem elektronicznym i kompresja RLE, z krokowaniem i stosem wywołań.
Algorytmy według etapu nauki
| Algorytm | Etap w podstawie | Gdzie wraca | Strona |
|---|---|---|---|
| Algorytm Euklidesa (NWD, NWW) | klasy 7-8 | liceum, matura | algorytm Euklidesa |
| Cyfry liczby, suma cyfr, palindromy | klasy 7-8 | liceum, matura | suma cyfr liczby |
| Wyszukiwanie liniowe i binarne | klasy 7-8 (liniowe) | liceum, matura | wyszukiwanie liniowe i binarne |
| Sortowanie przez wybieranie | klasy 7-8 | liceum, technikum | sortowanie przez wybieranie |
| Liczby pierwsze, sito Eratostenesa | klasy 7-8 (podzielność), liceum (pierwszość) | matura | liczby pierwsze i sito |
| Systemy liczbowe | liceum, zakres podstawowy | matura | systemy liczbowe |
| Szyfr Cezara | liceum, zakres podstawowy | matura | szyfr Cezara |
| Sortowanie bąbelkowe | liceum, zakres podstawowy | technikum, matura | sortowanie bąbelkowe |
| Sortowanie przez wstawianie | liceum, zakres podstawowy | technikum, matura | sortowanie przez wstawianie |
| Ciąg Fibonacciego | liceum, zakres podstawowy | matura | ciąg Fibonacciego |
Opis wymagań dla każdego etapu, razem z tym, co ćwiczyć w bloczkach w klasach 1-6, znajdziesz na stronie informatyka w szkole.
Algorytmy na liczbach
Najstarsze i najkrótsze algorytmy dotyczą liczb całkowitych. Wszystkie opierają się na dwóch operacjach: reszcie z dzielenia (%) i dzieleniu całkowitym (// w Pythonie, / na liczbach całkowitych w C++).
- Algorytm Euklidesa liczy największy wspólny dzielnik bez szukania dzielników: parę (a, b) zamienia na (b, a % b), aż druga liczba będzie zerem. Z NWD wynika NWW i skracanie ułamków.
- Liczby pierwsze i sito Eratostenesa: sprawdzanie pierwszości dzielnikami do pierwiastka, sito dla wszystkich liczb do granicy i rozkład na czynniki pierwsze.
- Suma cyfr liczby: schemat
n % 10in // 10, który odwiedza cyfry od końca. Z niego wynika odwracanie liczby i palindromy. - Systemy liczbowe: zamiana na system dwójkowy przez zbieranie reszt z dzielenia przez 2 i powrót schematem Hornera.
- Ciąg Fibonacciego: wersja z pętlą, rekurencyjna i rekurencja z zapamiętywaniem wyników, czyli pierwszy krok do programowania dynamicznego.
Algorytmy na tekstach
Napis to ciąg znaków, a każdy znak ma swój kod liczbowy. W Pythonie zamieniają je funkcje ord() i chr(), w C++ wystarczy rzutowanie typu char na int. Szyfr Cezara przesuwa każdą literę o stałą liczbę miejsc w alfabecie: to dobre ćwiczenie z reszty z dzielenia (po Z wracamy do A) i z obsługi znaków spoza alfabetu. Kluczy jest tylko 25, więc szyfr łatwo złamać, sprawdzając wszystkie.
Wyszukiwanie i sortowanie
Wyszukiwanie liniowe sprawdza elementy po kolei i działa na każdej liście. Wyszukiwanie binarne wymaga listy posortowanej, ale w każdym kroku odrzuca połowę danych, więc w milionie elementów potrzebuje około 20 porównań.
Trzy proste sortowania z podstawy różnią się pomysłem:
| Sortowanie | Pomysł | Porównania | Kiedy dobre |
|---|---|---|---|
| przez wybieranie | wybierz najmniejszy element i postaw go na początku | zawsze n(n-1)/2 | gdy zamiany są kosztowne (najwyżej n-1 zamian) |
| bąbelkowe | zamieniaj sąsiadów w złej kolejności | do n(n-1)/2 | z flagą kończy szybko na danych posortowanych |
| przez wstawianie | wstaw kolejny element w posortowaną część | od n-1 do n(n-1)/2 | dane prawie posortowane, małe tablice |
Wszystkie trzy mają złożoność O(n²) w najgorszym przypadku. Szybsze sortowania (przez scalanie, szybkie) wymagają rekurencji i pojawiają się w zakresie rozszerzonym. Ćwiczy je kurs Algorytmy: zakres rozszerzony.
Zakres rozszerzony
Algorytmy z zakresu rozszerzonego mają osobne strony, z tymi samymi zapisami: listą kroków, pseudokodem (także z funkcjami i rekurencją), schematami blokowymi i drzewami wywołań albo drzewami decyzyjnymi.
| Algorytmy | Strona |
|---|---|
| Rekurencja (silnia, NWD), szybkie potęgowanie, fraktal linijki | rekurencja i szybkie potęgowanie |
| Minimum i maksimum metodą par, sortowanie przez scalanie i szybkie | sortowanie przez scalanie i szybkie |
| Metoda połowienia, metoda Herona, błędy obliczeń, schemat Hornera | metody numeryczne |
| Najdłuższy fragment niemalejący, maksymalna suma fragmentu | podciągi |
| Stos, kolejka, odwrotna notacja polska, poprawność nawiasów | odwrotna notacja polska |
| Wydawanie reszty, plan zajęć, najmniej monet, najdłuższy wspólny podciąg | metoda zachłanna i programowanie dynamiczne |
| Przeszukiwanie wszerz, algorytm Dijkstry | grafy: BFS i Dijkstra |
| Klucze RSA, odwrotność modulo, podpis elektroniczny | szyfrowanie RSA |
| Kodowanie i dekodowanie długości serii | kompresja RLE |
Rozkład liczby na czynniki pierwsze jest na stronie liczby pierwsze i sito.
Jak ćwiczyć: kurs z krokowaniem
Kurs Algorytmy z podstawy programowej ma 10 tematów, w każdym przykłady do przejścia krok po kroku i zadania z automatycznym sprawdzaniem. Dobre pierwsze lekcje:
- Algorytm Euklidesa z resztą z dzielenia,
- Sito Eratostenesa do 50,
- Zamiana liczby dziesiętnej na dwójkową,
- Wyszukiwanie binarne w liście posortowanej,
- Sortowanie bąbelkowe z przebiegami.
Krokowanie najwięcej daje przy pętlach zagnieżdżonych i rekurencji: widać, która pętla właśnie się obraca, które elementy są porównywane i ile razy funkcja wywołuje samą siebie. Kod w C++ z tych stron uruchomisz w kursie Podstawy C++, też z krokowaniem.
Dla nauczycieli
Każdy algorytm z tych stron to gotowy temat lekcji: przykłady do omówienia przy tablicy (krokowanie na rzutniku), zadania do samodzielnej pracy i automatyczne sprawdzanie. W BitWizards przydzielasz kurs klasie, udostępniasz tematy stopniowo, widzisz postęp uczniów i przebieg pisania ich kodu (podgląd na żywo i odtwarzanie historii). Platforma jest darmowa dla szkół - jak zacząć. Programowanie w Pythonie i C++ opisują też strony Python i C++.