Wersja zoptymalizowana (wykorzystująca operacje dzielenia i obliczania reszty z dzielenia) - I_R_W14_M04_Java Algorytm Euklidesa

RNS6MKEE6EVKC

Polecenie 1

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

R1TKSP7SJZ4DJ

Ź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/DD42AMVEE

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

R1P5MVXLP4F6Z1

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

Polecenie 2

Zaproponuj zapis 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 a i b.

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

RLZXUSFXLGU621

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

Oto implementacja algorytmu w języku Java:

int NWD_modulo(int x, int y):
	int modulo = 0;
	while y > 0:
		modulo = x%y
		x = y
		y = modulo
	return x

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

int NWD_modulo_zliczanie(int x, int y):
    int dzielenia = 0
    int modulo = 0;
	while y > 0:
		modulo = x % y
		x = y
		y = modulo
        dzielenia += 1

	System.out.print('NWD'+x+'liczba dzieleń'+dzielenia)

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

NWD_modulo_zliczanie(927566801,22)
NWD 1 ; 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. Spróbuj napisać ten program.

Ćwiczenie 1

Napisz program, który wyznaczy największy wspólny dzielnik liczb a, b i c.

Specyfikacja problemu:

Dane:

a, b, c – liczby naturalne;

Wynik:

nwd – liczna naturalna; największy wspólny dzielnik;

R1JQFRQMLHP9F

Algorytm Euklidesa z odejmowaniem

Krótkie podsumowanie