R104uaLdFXeRg
Zdjęcie przedstawia płyty sufitowe budynku.

I_P_W14_M05_Java Algorytmy liczbowe w języku Java - Algorytm Euklidesa

Źródło: Alex Lehner, domena publiczna.
Polecenie 1

Obejrzyj prezentację, a następnie porównaj oba warianty algorytmu Euklidesa.

R1a0KHa93jUe8
Dźwiękowe nagranie lekcji
Źródło: Contentplus.pl sp. z o.o., licencja: CC BY-SA 3.0.

Nagranie dostępne pod adresem https://zpe.gov.pl/a/DF1J2ZJ66

Źródło: Contentplus.pl sp. z o.o., licencja: CC BY-SA 3.0.

Dźwiękowe nagranie lekcji

Zapoznaj się z prezentacją, a następnie porównaj oba warianty algorytmu Euklidesa.

RLrdRykASMTbu1
Wysłuchaj nagrania abstraktu i zastanów się, czego jeszcze chciałbyś się dowiedzieć w związku z tematem lekcji.
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.
1
Polecenie 2

W poniższym schemacie przygotuj algorytm wyliczający NWD z zastosowaniem operatora modulo.

Specyfikacja problemu:

Dane:

a, b – liczby, dla których program wyliczy NWD; liczby naturalne dodatnie

Wynik:

Największy wspólny dzielnik liczb

Linia 1. a.

i 

Linia 1. b.

.

1

W poniższym schemacie przygotuj algorytm wyliczający NWD z zastosowaniem operatora dzielenia z resztą.

R1I6t2pZIdv5v1
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.

Przygotuj algorytm w JavaScript wyliczający NWD z zastosowaniem operatora modulo.

Polecenie 3
RmEElmCCX8gya
d

Oto implementacja algorytmu w języku Java:

Linia 1. int NWD podkreślnik modulo otwórz nawias okrągły int x przecinek int y zamknij nawias okrągły dwukropek. Linia 2. int modulo znak równości 0 średnik. Linia 3. while y zamknij nawias ostrokątny 0 dwukropek. Linia 4. modulo znak równości x procent y. Linia 5. x znak równości y. Linia 6. y znak równości modulo. Linia 7. return x.

Wersja programu, która zlicza wykonane operacje, może wyglądać następująco:

Linia 1. int NWD podkreślnik modulo podkreślnik zliczanie otwórz nawias okrągły int x przecinek int y zamknij nawias okrągły dwukropek. Linia 2. int dzielenia znak równości 0. Linia 3. int modulo znak równości 0 średnik. Linia 4. while y zamknij nawias ostrokątny 0 dwukropek. Linia 5. modulo znak równości x procent y. Linia 6. x znak równości y. Linia 7. y znak równości modulo. Linia 8. dzielenia plus znak równości 1. Linia 10. System kropka out kropka print otwórz nawias okrągły apostrof NWD apostrof plus x plus apostrof liczba dzieleń apostrof plus dzielenia zamknij nawias okrągły.

Wyznaczmy NWD dla dużych argumentów funkcji. Okaże się, że liczba wykonywanych operacji jest bardzo mała:

Linia 1. NWD podkreślnik modulo podkreślnik zliczanie otwórz nawias okrągły 927566801 przecinek 22 zamknij nawias okrągły. Linia 2. NWD 1 średnik liczba dzieleń 3.
Dla zainteresowanych

Możemy obliczyć NWD dla więcej niż dwóch liczb.

Obliczenie NWD dla trzech liczb odbywa się w dwóch etapach. Najpierw wyznaczamy NWD dla liczb pierwszej i drugiej oraz NWD liczb drugiej i trzeciej. Następnie obliczamy NWD dla otrzymanych wyników. Przedstawmy tę zasadę za pomocą pseudokodu:

Linia 1. obliczenie NWD otwórz nawias okrągły a przecinek b przecinek c zamknij nawias okrągły dwukropek. Linia 3. do zmiennej tymczasowej x przypisz NWD otwórz nawias okrągły a przecinek b zamknij nawias okrągły. Linia 4. do zmiennej tymczasowej y przypisz NWD otwórz nawias okrągły b przecinek c zamknij nawias okrągły. Linia 6. wynikiem będzie NWD otwórz nawias okrągły x przecinek y zamknij nawias okrągły. Linia 8. kratka inny sposób rozwiązania problemu dwukropek. Linia 9. NWD otwórz nawias okrągły a przecinek b przecinek c zamknij nawias okrągły znak równości NWD otwórz nawias okrągły NWD otwórz nawias okrągły a przecinek b zamknij nawias okrągły przecinek c zamknij nawias okrągły.
Algorytm Euklidesa z odejmowaniem
Krótkie podsumowanie