Misja druga: Ćwicz i zwyciężaj - PYI_R_W14_M05 Zastosowanie algorytmu Euklidesa

RO449A2SQESXT

Polecenie 1

Zapoznaj się z poniższym zadaniem typu maturalnego. Następnie przeanalizuj prezentację, w której przedstawione zostało rozwiązanie zadania.

Podpunkt a)

Wykorzystując funkcję NWD oraz następującą zależność:

$N W D (a_{1}, a_{2}, . . ., a_{n}) = N W D (N W D (a_{1}, a_{2}, . . ., a_{n - 1}), a_{n})$

możemy wyznaczyć największy wspólny dzielnik n liczb całkowitych dodatnich aIndeks dolny 1, aIndeks dolny 2, ..., aIndeks dolny n.

Przykład:

$N W D (15, 24, 60) = N W D (N W D (15, 24), 60) =$

$= N W D (3, 60) = 3$

Uzupełnij poniższą tabelkę i dla wskazanych n liczb całkowitych dodatnich aIndeks dolny 1, aIndeks dolny 2, ..., aIndeks dolny n oblicz ich największy wspólny dzielnik.

aIndeks dolny 1, aIndeks dolny 2, ..., aIndeks dolny n	NWD(aIndeks dolny 1, aIndeks dolny 2, ..., aIndeks dolny n)
36, 24, 72, 150
119, 187, 323, 527, 731
121, 330, 990, 1331, 110, 225

Dane:
	liczby całkowite dodatnie a i b.
Wynik:
	Największy wspólny dzielnik liczb a i b.

funkcja NWD(a, b)
	dopóki b != 0 wykonuj
		r = a mod b
		a = b
		b = r
        
	zwróć a i zakończ

Powyższe zadanie zostało stworzone przez CKE i pochodzi ze zbioru zadań maturalnych z informatyki (zadanie nr 18.2), dostępnego na oficjalnej stronie internetowej CKE.

R124CP3XM5GVX1

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

Podpunkt b)

Napisz algorytm, który korzystając z funkcji NWD(a, b), wyznaczy największy wspólny dzielnik ciągu liczb aIndeks dolny 1, aIndeks dolny 2, ..., aIndeks dolny n.

Specyfikacja problemu:

Dane:

aIndeks dolny 1₁, aIndeks dolny 2₂, ..., aIndeks dolny n_n – liczby całkowite dodatnie.

Wynik:

Największy wspólny dzielnik liczb aIndeks dolny 1₁, aIndeks dolny 2₂, ..., aIndeks dolny n_n.

RMC92OZ5UX4CU

R1UJUM78SZVL61

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

Misja pierwsza: Ćwicz i zwyciężaj

Strefa wyzwań