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 %.

▶ Ćwicz ten temat fiszki, quiz i prawda/fałsz — z wynikiem i powtórkami

Ważne daty

Ważne postacie

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:

  1. Najmniejsza wspólna dzielna
  2. Największa wielokrotność dwóch liczb
  3. Największy wspólny dzielnik
  4. 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:

  1. iloraz wyniesie zero
  2. reszta z dzielenia wyniesie zero
  3. obie liczby będą nieparzyste
  4. 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:

  1. 6
  2. 4
  3. 36
  4. 12
Pokaż odpowiedź

D. 12 — 84 % 36 = 12, a 36 % 12 = 0, więc NWD to 12.

4. Euklides był:

  1. greckim matematykiem starożytnym
  2. polskim programistą
  3. twórcą języka Python
  4. 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?

  1. dodajemy r do a i zaczynamy od nowa
  2. zamieniamy a z b i zerujemy b
  3. a przyjmuje wartość b, a b wartość r
  4. 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