Algorytmy klasyczne
Informatyka, klasa 8 · Algorytmy
Najważniejsze w skrócie
Algorytm Euklidesa znajduje największy wspólny dzielnik. W wersji z resztami: dopóki b ≠ 0, zamieniamy (a, b) na (b, a mod b). Gdy b osiągnie 0, wynikiem jest a.
Sito Eratostenesa wykreśla wielokrotności kolejnych liczb pierwszych — to, co zostanie niewykreślone, jest liczbą pierwszą. Sprawdzanie pierwszości pojedynczej liczby wystarczy prowadzić do jej pierwiastka.
Warto znać też algorytm sumowania i szukania maksimum: przechodzimy raz przez zbiór, pamiętając jedną wartość. Złożoność mówi, jak rośnie liczba operacji wraz z rozmiarem danych.
Ważne daty
- NWD(a,b) — dopóki b≠0: (a,b) ← (b, a mod b)
- NWD(48,18) — 48,18 → 18,12 → 12,6 → 6,0 = 6
- Sito — wykreśl wielokrotności liczb pierwszych
- Pierwszość — sprawdzaj dzielniki do √n
- Maksimum — jedno przejście, pamiętaj największy
Ważne postacie
- Euklides — algorytm NWD z resztami
- Eratostenes — sito liczb pierwszych
- Złożoność — jak rośnie liczba operacji
- Maksimum — jedno przejście przez zbiór
Pojęcia
- Co wyznacza algorytm Euklidesa?
- Największy wspólny dzielnik dwóch liczb.
- Jak wygląda krok Euklidesa z resztami?
- (a, b) zamieniamy na (b, a mod b), dopóki b ≠ 0.
- Ile wynosi NWD(48,18)?
- 6.
- Co robi sito Eratostenesa?
- Wykreśla wielokrotności liczb pierwszych, zostawiając liczby pierwsze.
- Do jakiej wartości sprawdzamy dzielniki liczby n?
- Do pierwiastka z n.
- Co to liczba pierwsza?
- Liczba naturalna większa od 1 mająca dokładnie dwa dzielniki.
- Jak znaleźć maksimum w zbiorze?
- Przejść raz i pamiętać największą dotąd wartość.
- Co mówi złożoność algorytmu?
- Jak rośnie liczba operacji przy większych danych.
- Ile wynosi NWD(15, 25)?
- Pięć — to największy wspólny dzielnik obu liczb.
- Ile wynosi 17 mod 5?
- Dwa — to reszta z dzielenia.
- Czy liczba 1 jest liczbą pierwszą?
- Nie — ma tylko jeden dzielnik, a liczba pierwsza musi mieć dokładnie dwa.
- Jak z NWD obliczyć NWW dwóch liczb?
- Dzieląc iloczyn tych liczb przez ich NWD.
Sprawdź się
1. Algorytm Euklidesa wyznacza…
- Liczby pierwsze
- NWD
- Średnią
- Maksimum
Pokaż odpowiedź
B. NWD — Euklides służy do wyznaczania NWD.
2. Sprawdzając pierwszość liczby 97, dzielniki testujemy do…
- 97
- 48
- 10
- 2
Pokaż odpowiedź
C. 10 — Wystarczy sprawdzić dzielniki do √97, czyli do 9.
3. Pierwszy krok algorytmu Euklidesa dla pary (36, 24) daje parę…
- (24, 36)
- (24, 12)
- (12, 0)
- (36, 12)
Pokaż odpowiedź
B. (24, 12) — Reszta z dzielenia 36 przez 24 wynosi 12.
4. Liczba 91 jest…
- Pierwsza
- Złożona
- Parzysta
- Mniejsza od 50
Pokaż odpowiedź
B. Złożona — 91 to iloczyn 7 i 13 — łatwo ją pomylić z liczbą pierwszą.
5. Sito Eratostenesa służy do znajdowania:
- liczb pierwszych
- liczb parzystych
- największej liczby
- średniej
Pokaż odpowiedź
A. liczb pierwszych — Wykreślamy kolejno wielokrotności 2, 3, 5 i dalszych, a nieskreślone zostają liczby pierwsze. Liczby parzyste wypadają już przy pierwszym kroku.
Więcej pytań — razem 50 fiszek, pytań i zdań prawda/fałsz — czeka w ćwiczeniach.
▶ Ćwicz ten temat fiszki, quiz i prawda/fałsz — z wynikiem i powtórkami