Algorytm Euklidesa — NWD
Informatyka, klasa 6 · Algorytmy
Najważniejsze w skrócie
NWD, czyli największy wspólny dzielnik, to największa liczba, przez którą dwie liczby dzielą się bez reszty. Na przykład NWD(12, 18) = 6. Już około 300 lat p.n.e. grecki matematyk Euklides opisał sposób liczenia NWD — to jeden z najstarszych znanych algorytmów.
W wersji z odejmowaniem od większej liczby odejmujemy mniejszą, aż obie będą równe — ta wspólna wartość to NWD. Dla 48 i 18 mamy kolejno pary: 30 i 18, 12 i 18, 12 i 6, 6 i 6, więc NWD = 6. Wersja z resztą jest szybsza: parę (a, b) zastępujemy parą (b, reszta z dzielenia a przez b), aż reszta wyniesie 0 — wtedy wynikiem jest a.
Algorytm łatwo narysować jako schemat blokowy: romb z pytaniem „czy b = 0?” i pętla wracająca do dzielenia. NWD przydaje się do skracania ułamków: 18/48 dzielimy przez NWD = 6 i od razu mamy 3/8. W Pythonie całe obliczenie mieści się w pętli while z operatorem %.
Ważne daty
- ok. 300 p.n.e. — Euklides opisuje algorytm w „Elementach”
- NWD(a, b) — największy wspólny dzielnik liczb a i b
- a % b — reszta z dzielenia a przez b w Pythonie
- NWD = 1 — liczby względnie pierwsze, np. 8 i 15
- NWW — a · b : NWD(a, b), np. NWW(4, 6) = 12
Ważne postacie
- Euklides — grecki matematyk, autor „Elementów”
- Wersja z odejmowaniem — prosta, ale wolna przy dużej różnicy liczb
- Wersja z resztą — szybka, używana w programach
- Romb — blok decyzji „czy b = 0?” na schemacie
Pojęcia
- Co to NWD dwóch liczb?
- Największa liczba, przez którą obie dzielą się bez reszty.
- Na czym polega wersja algorytmu z odejmowaniem?
- Od większej liczby odejmujemy mniejszą, aż obie będą równe.
- Na czym polega wersja algorytmu z resztą?
- Parę (a, b) zastępujemy parą (b, a % b), aż reszta wyniesie 0.
- Ile wynosi NWD(48, 18)?
- 6 — reszty to kolejno 12, 6 i 0.
- Ile wynosi NWD(60, 45)?
- 15 — bo 60 % 45 = 15, a 45 % 15 = 0.
- Kim był Euklides?
- Greckim matematykiem żyjącym około 300 lat p.n.e., autorem „Elementów”.
- Jakim znakiem liczymy resztę z dzielenia w Pythonie?
- Znakiem %, np. 17 % 5 daje 2.
- Po co NWD przy ułamkach?
- Dzielimy licznik i mianownik przez NWD i od razu dostajemy ułamek nieskracalny.
- Skróć ułamek 45/60 z pomocą NWD.
- NWD(45, 60) = 15, więc 45/60 = 3/4.
- Co to liczby względnie pierwsze?
- Liczby, których NWD wynosi 1, np. 8 i 15.
- Ile wynosi NWD(a, 0)?
- a — bo każda liczba dzieli zero.
- Co jest wynikiem, gdy algorytm z resztą się kończy?
- Ostatnia niezerowa reszta, czyli liczba a w chwili, gdy b = 0.
Sprawdź się
1. NWD to skrót od:
- Najmniejsza wspólna dzielna
- Największa wielokrotność dwóch liczb
- Największy wspólny dzielnik
- Najmniejszy wspólny dzielnik
Pokaż odpowiedź
C. Największy wspólny dzielnik — Chodzi o największą liczbę, przez którą obie liczby dzielą się bez reszty.
2. W wersji z resztą algorytm kończy się, gdy:
- iloraz wyniesie zero
- reszta z dzielenia wyniesie zero
- obie liczby będą nieparzyste
- reszta stanie się większa od dzielnika
Pokaż odpowiedź
B. reszta z dzielenia wyniesie zero — Reszta 0 oznacza, że ostatni dzielnik dzieli poprzednią liczbę — to jest NWD.
3. NWD(84, 36) wynosi:
- 6
- 4
- 36
- 12
Pokaż odpowiedź
D. 12 — 84 % 36 = 12, a 36 % 12 = 0, więc NWD to 12.
4. Euklides był:
- greckim matematykiem starożytnym
- polskim programistą
- twórcą języka Python
- rzymskim cesarzem i dowódcą legionów
Pokaż odpowiedź
A. greckim matematykiem starożytnym — Euklides z Aleksandrii napisał „Elementy”, w których opisał ten sposób szukania NWD.
5. Co robimy po obliczeniu reszty r = a % b?
- dodajemy r do a i zaczynamy od nowa
- zamieniamy a z b i zerujemy b
- a przyjmuje wartość b, a b wartość r
- kończymy algorytm i wypisujemy r
Pokaż odpowiedź
C. a przyjmuje wartość b, a b wartość r — Liczby przesuwają się o jedno miejsce, a pętla wraca do sprawdzenia, czy nowe b jest zerem.
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