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.
| a | b | a % b |
|---|---|---|
| 48 | 18 | 12 |
| 18 | 12 | 6 |
| 12 | 6 | 0 |
| 6 | 0 | stop, 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.
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.
| Zapis | Jak rośnie | Przykł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).
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.
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ę
Wymagania na ocenę
Dział 4 planu (lekcje 22–26). Ocena wyższa zawiera wymagania na oceny niższe.
| Ocena | Uczeń |
|---|---|
| 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. |