Klasa 4 · rozdział 4 · lekcje 22–26

NWD, sito i złożoność

Euklides liczy największy wspólny dzielnik resztą z dzielenia — iteracyjnie i rekurencyjnie. Sito wykreśla wielokrotności. Potem nazywasz, jak liczba kroków rośnie z rozmiarem danych: stała, logarytmiczna, liniowa, kwadratowa.

Po tym rozdziale powinieneś umieć

  • napisać NWD jako funkcję bez we/wy, z nagłówkiem, i policzyć ślad reszt;
  • napisać wersję rekurencyjną z warunkiem stopu oraz NWW;
  • wypełnić sito i pominąć 0 oraz 1;
  • porównać liczbę kroków Euklidesa z naiwnym szukaniem dzielników;
  • użyć oznaczeń O(1), O(log n), O(n), O(n²) na przykładach z lekcji;
  • skrócić ułamek metodą, która woła NWD.

1. NWD w układzie INF.04

NWD(48, 18) = 6. Euklides nie wypisuje dzielników. Zamienia parę (a, b) na (b, a % b), aż b stanie się 0. Wynikiem jest a. Funkcja nie czyta klawiatury.

aba % b
481812
18126
1260
60stop, NWD = 6
// Nazwa: nwd
// Opis: największy wspólny dzielnik algorytmem Euklidesa
// Parametry: a, b — liczby całkowite; przed pętlą brane są wartości bezwzględne
// Zwraca: NWD; nwd(a, 0) zwraca |a|
// We/wy: brak
int nwd(int a, int b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

nwd(48, 18), nwd(18, 48) i nwd(-48, 18) dają 6. nwd(17, 5) daje 1 — liczby względnie pierwsze. Para (0, 0) nie ma NWD; w main odrzucasz ją przed wywołaniem albo rzucasz wyjątek z rozdziału 2.

Naiwne szukanie schodzi od mniejszej liczby w dół i sprawdza a % d == 0 && b % d == 0. Dla 48 i 18 startujesz od 18 i idziesz aż do 6 — kilkanaście dzieleń. Euklides zrobił trzy reszty. Im większe liczby, tym różnica jest wyraźniejsza.

2. Rekurencja i NWW

Ten sam przepis: jeśli b jest 0, wynikiem jest a. W przeciwnym razie NWD(a, b) = NWD(b, a % b). Warunek stopu jest obowiązkowy — bez niego wywołania nie mają końca.

int nwdRek(int a, int b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    if (b == 0) return a;
    return nwdRek(b, a % b);
}

// NWW(a, b) = |a| / NWD * |b|  — dzielenie przed mnożeniem
int nww(int a, int b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    if (a == 0 || b == 0) return 0;
    return a / nwd(a, b) * b;
}

nww(4, 6) = 12. nww(3, 5) = 15. Dzielenie stoi przed mnożeniem, żeby iloczyn a · b nie urósł wcześniej, niż musi, w typie int.

Iteracja czy rekurencja Wynik jest ten sam. Pętla nie dokłada ramek wywołań. Rekurencja jest krótsza w zapisie i wprost powtarza zdanie „NWD(a, b) = NWD(b, reszta)”. Przy liczbach z lekcji obie wersje są bezpieczne. Wybór uzasadniasz czytelnością albo limitem wywołań, nie gustem „rekurencja jest nowocześniejsza”.

3. Sito Eratostenesa

Liczba pierwsza ma dokładnie dwa dzielniki naturalne: 1 i samą siebie. 1 nie jest pierwsza. Jedna liczba: test dzielników od 2 do pierwiastka. Cały przedział 2…N: sito wykreśla wielokrotności.

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

void sito(bool skreslona[], int N) {
    for (int i = 0; i <= N; i++) skreslona[i] = false;
    skreslona[0] = skreslona[1] = true;
    for (int i = 2; i * i <= N; i++) {
        if (!skreslona[i]) {
            for (int j = i * i; j <= N; j += i)
                skreslona[j] = true;
        }
    }
}

Dla N = 30 zostają 2 3 5 7 11 13 17 19 23 29. Start wykreśleń od i·i jest poprawny: mniejsze wielokrotności i zdjął już mniejszy czynnik. 1 jest wykreślona na starcie, nie „przypadkiem”. czyPierwsza(1) → fałsz, czyPierwsza(2) → prawda, czyPierwsza(91) → fałsz (7 · 13).

Brzegi, które sprawdzasz osobno: N < 2 (pusta lista pierwszych), liczba 2 (jedyna parzysta pierwsza), kwadrat liczby pierwszej (49 przy N ≥ 49 musi być wykreślona).

4. Złożoność — wstęp

Złożoność mówi, jak rośnie liczba kroków, gdy rośnie rozmiar danych n. Nie mierzymy tu sekund na jednym komputerze. Liczymy operacje dominujące: reszty, porównania, wykreślenia. Zapis O(...) czyta się „rośnie jak”. Stałe i drobniejsze składniki na tym poziomie pomijasz.

ZapisJak rośniePrzykład z lekcji
O(1) Liczba kroków nie zależy od n szczyt stosu na wektorze, odczyt t[i]
O(log n) n można wielokrotnie przepołowić; kroków jest około „ile razy” Wyszukiwanie binarne. Euklides dla typowych liczb też szybko maleje (reszta jest mniejsza)
O(n) Raz na element, albo kilka razy na element Wyszukiwanie liniowe. Jedno przejście po tablicy
O(n²) Pętla w pętli po n Sortowanie bąbelkowe. Naiwne NWD schodzące od mniejszej liczby też bywa liniowe względem tej liczby, nie kwadratowe — nie mieszaj nazw

Sito dla zakresu n odwiedza wielokrotności. Robi wyraźnie mniej osobnych testów niż czyPierwsza wołane n razy, i na końcu masz odpowiedzi dla wszystkich liczb, nie dla jednej. Szkolnie wystarczy: „rośnie wolniej niż n osobnych testów do pierwiastka”. Dokładny wzór sita (n log log n) nie jest wymagany na dopuszczający; na bardzo dobry umiesz powiedzieć, że wyszukiwanie liniowe jest O(n), a binarne O(log n).

Policz ręcznie Ile warunków n % d == 0 wykona czyPierwsza(97)? Dzielniki 2…9, bo 10² = 100 > 97. Osiem sprawdzeń. Euklides dla 48 i 18 wykonał trzy reszty. To są konkretne liczby kroków, nie hasło „szybciej”.

5. NWD w klasie Ułamek

Algorytm staje się metodą, gdy ma stan. Ułamek trzyma licznik i mianownik prywatnie i skraca się przy tworzeniu. NWD może być zwykłą funkcją albo metodą statyczną klasy narzędziowej — nie potrzebuje this.

class Ulamek {
    int licznik, mianownik;
    void skroc() {
        int d = nwd(licznik, mianownik);
        if (d > 0) { licznik /= d; mianownik /= d; }
    }
public:
    Ulamek(int l, int m) : licznik(l), mianownik(m) {
        if (m == 0) throw invalid_argument("mianownik 0");
        if (m < 0) { licznik = -licznik; mianownik = -mianownik; }
        skroc();
    }
    int getLicznik() const { return licznik; }
    int getMianownik() const { return mianownik; }
};

Ulamek u(2, 4);
cout << u.getLicznik() << "/" << u.getMianownik();   // 1/2

Ulamek(2, -4) przenosi znak do licznika: −2/4, po skróceniu −1/2. Ulamek(-2, -4) po przeniesieniu znaku jest 2/4, potem 1/2. Mianownik zero nie tworzy obiektu. To jest NWD „obiektowo”: algorytm zostaje funkcją bez we/wy, klasa pilnuje umowy ułamka.

Metoda statyczna static int nwd(int a, int b) w klasie Matma wołasz Matma::nwd(48, 18). Wynik ten sam co z wolnej funkcji. Static wybierasz, gdy NWD ma mieszkać przy narzędziach klasy, a nie przy jednym ułamku.

Ćwiczenia do samodzielnego wykonania

Folder: Dokumenty\cwiczenia-po\klasa-4\rozdzial-04.

Ćwiczenie 1. Ślad 54 i 24 łatwe

Tabela reszt na kartce. NWD ma wyjść 6. Potem funkcja bez cin, nagłówek komentarzem, we/wy w main.

Ćwiczenie 2. Rekurencja i NWW średnie

nwdRek(54, 24) = 6. nww(4, 6) = 12, nww(3, 5) = 15. Wskaż warunek stopu w kodzie.

Ćwiczenie 3. Sito do 50 średnie

Wypisz liczby pierwsze ≤ 50. 1 nie wchodzi. 49 jest wykreślona. Osobno czyPierwsza dla 1, 2, 9, 17, 91.

Ćwiczenie 4. Kroki średnie

Policz reszty Euklidesa dla 48 i 18 oraz liczbę dzieleń naiwnego zejścia od 18. Napisz, które O z tabeli pasuje do liniowego przejścia tablicy, a które do binarnego szukania (następny rozdział — tu wystarczy nazwa).

Ćwiczenie 5. Ułamek trudne

Klasa Ulamek. Przypadki: 2/4 → 1/2, 2/−4 → −1/2, mianownik 0 → wyjątek. NWD zostaje poza main.

Ćwiczenie 6. Dwie drogi do pierwszych trudne

Zakres od A do B (B ≤ 1000). Wersja z czyPierwsza w pętli i wersja sitem do B. Wyniki identyczne. Napisz, którą zostawiasz, gdy B rośnie, i nazwij to wzrostem liczby kroków, nie „komputer jest wolny”.

Sprawdź się

1. NWD(48, 18) wynosi:
2. Warunek stopu rekurencyjnego NWD:
3. Sito:
4. Wyszukiwanie liniowe na n elementach opisujesz jako:
5. NWW liczymy:

Wymagania na ocenę

Dział 4 planu (lekcje 22–26). Ocena wyższa zawiera wymagania na oceny niższe.

OcenaUczeń
2 Omawia NWD własnymi słowami. Uzupełnia funkcję NWD lub sito według wzoru.
3 Implementuje NWD iteracyjnie w funkcji bez we/wy. Implementuje sito dla n z lekcji. We/wy jest w main.
4 Implementuje NWD rekurencyjnie i NWW. Wskazuje warunek stopu. Porównuje liczbę kroków Euklidesa i naiwnego szukania dzielników.
5 Programuje NWD obiektowo (metoda statyczna albo klasa Ulamek). Opisuje złożoność sita i wyszukiwania na poziomie „rośnie z n” oraz O(n) kontra O(log n). Testuje brzegi: równe liczby, 1, liczby pierwsze.
6 Uzasadnia wybór iteracji albo rekurencji. Łączy NWD z innym zadaniem (skracanie ułamka) i odrzuca mianownik zero.

Lista „już umiem”