Page 17 - informatyka 8

1.3 Algorytm Euklidesa

Podejmij temat O O Odczytaj hasło zapisane wspak. Powiedz, co wiesz na jego temat.
KINLEIZD YNLÓPSW YZSKĘIWJAN

Na lekcjach matematyki na pewno wyznaczaliście największy wspólny dziel- Największy wspólny dzielnik
I.2II.1, II.2,
nik dwóch liczb naturalnych. (NWD) dwóch liczb całkowitych
Na przykład: – największa liczba naturalna,
– 128 dzieli się przez: 1, 2, 4, 8, 16, 32, 64, 128, przez którą dzielą się bez reszty
obie liczby.
– 56 dzieli się przez: 1, 2, 4, 7, 8, 14, 28, 56.
NWD = 8
Sposób wyszukiwania największego wspólnego dzielnika (NWD) dwóch liczb
naturalnych, zwany algorytmem Euklidesa, uznany jest za jeden z najstar-
szych, opisanych algorytmów na liczbach. Opiera się na założeniu, że NWD Ciekawe!
dwóch liczb nie zmienia się, jeżeli od większej liczby odejmujemy liczbę mniejszą. Euklides z Aleksandrii (IV–III w.
Taki sposób wyznaczania NWD nazywany jest wersją z odejmowaniem. p.n.e) był greckim matematykiem,
– Jeśli dwie liczby są różne, to od większej odejmujemy mniejszą, a następnie porów- twórcą podstaw geometrii i au-
nujemy różnicę oraz odjemnik z poprzedniego odejmowania i znowu od większej torem słynnego dzieła Elementy
liczby odejmujemy mniejszą (czynności te powtarzany dotąd, aż obie liczby będą (gr. Stoicheia geometrias) prze-
sobie równe – tyle wynosi największy wspólny dzielnik dwóch liczb). tłumaczonego na wiele języków,
– Jeśli mniejsza liczba jest równa zero, to największy wspólny dzielnik jest równy przez wieki stanowiącego wzór
dla nauk ścisłych. Sformułował
drugiej liczbie. szereg podstawowych twierdzeń,
– Jeśli liczby są sobie równe, to największy ich wspólny dzielnik wynosi tyle, ile które udowodnił na drodze logicz-
wynosi każda z liczb. nego rozumowania.

Opis algorytmu wyszukiwania największego wspólnego dzielnika Weź pod uwagę
dwóch liczb naturalnych (wersja z odejmowaniem) podane pary liczb

1 Podaj dwie liczby, np. 128, 56. 128, 56
2 Od większej liczby odejmij mniejszą liczbę, czyli 128 – 56 = 72. 56, 72

Weź pod uwagę różnicę i odjemnik.
3 56, 16
Od większej liczby odejmij mniejszą liczbę, czyli 72 – 56 = 16.
Weź pod uwagę różnicę i odjemnik z poprzedniego odejmowania.
4 16, 40
Od większej liczby odejmij mniejszą liczbę, czyli 56 – 16 = 40.
Weź pod uwagę różnicę i odjemnik z poprzedniego odejmowania.
5 16, 24
Od większej liczby odejmij mniejszą liczbę, czyli 40 – 16 = 24.
Weź pod uwagę różnicę i odjemnik z poprzedniego odejmowania.
6 16, 8
Od większej liczby odejmij mniejszą liczbę, czyli 24 – 16 = 8.
Weź pod uwagę różnicę i odjemnik z poprzedniego odejmowania.
7 8, 8
Od większej liczby odejmij mniejszą, czyli 16 – 8 = 8.
8 Obie liczby są sobie równe, zatem największym wspólnym dzielnikiem liczb 128 i 56 jest liczba 8.

15