Inne wersje algorytmu Euklidesa - Działania matematyczne w Scratch

R1NRdDvSWkeNC

bg‑gray4

Treści zawarte w tym e‑materiale wykraczają poza podstawę programową dla klas IV‑VI. Jeśli jednak:

chcesz dowiedzieć się więcej i poznać różne wersje algorytmu Euklidesa, który służy do obliczania NWD (największego wspólnego dzielnika) dwóch liczb naturalnych, wraz z przykładami wykorzystania,

zachęcamy Cię do zapoznania się z tym e‑materiałem.

Na poprzedniej stronie podano, że algorytm Euklidesa to metoda obliczania największego wspólnego dzielnika (NWD) dwóch liczb naturalnych. Ma on kilka wersji. W tym materiale pokażemy różnice między tymi wersjami. Na początku przyjrzyjmy się działaniu tego algorytmu w wersji z odejmowaniem obliczając NWD liczb 256 i 48.

Tabela z obliczeniami NWD liczb 256 i 48 z zastosowaniem operacji odejmowania.
a	b
256	48
256 - 48 = 208	48
208 - 48 = 160	48
160 - 48 = 112	48
112 - 48 = 64	48
64 - 48 = 16	48
16	48 - 16 = 32
16	32 - 16 = 16
16	16

Zwróć uwagę, że jeżeli jedna liczba jest dużo większa od drugiej, to wielokrotnie będzie następowało odejmowanie od niej tej samej mniejszej liczby. Takie wielokrotne odejmowanie można zastąpić operacją moduloiuak7gU6CL_d715e232modulo, czyli obilczanie reszy dzielenia dwóch liczb całkowitych.

Ważne!

Wynikiem $256 m o d 48$ jest $16$ , ponieważ 256 dzielone przez $48$ to 5, reszty $16$ .

Na przykład dla $a = 256$ i $a = 48$ otrzymujemy:

Tabela z obliczeniami NWD liczb 256 i 48 z zastosowaniem operacji modulo
a	b
256	48
256 : 48 = 5 reszta 16 (256 mod 48 = 16)	48
16	48 : 16 = 3 reszta 0 48 mod 16 = 0

Z tabeli odczytujemy, że $b=0$ , więc $a = NWD(256, 48) = 16$ .

Zwróć uwagę, że zastępując odejmowanie operacją reszty z dzielenia zmienia się warunek końca powtarzania: jedna z wartości musi osiągnąć wartość $0$ .

Teraz zapoznaj się z innym zapisem:

Tabela z obliczeniami NWD liczb 256 i 48 z zastosowaniem operacji modulo w wersji z trzema zmiennymi
a	operator	b	równa się	wynik (reszta)
256	mod	48	=	16
48	mod	16	=	0

Z tabeli odczytujemy, że $reszta = 0$ i $b = NWD(256, 48) = 16$ .

Ćwiczenie 1

Wykorzysataj algorytm Euklidesa z wykorzystaniem reszty z dzielenia (zastosowaniem operacji modulo) do obliczania NWD liczb $76$ oraz $48$ . Zapisz swoje obliczenia w tabeli. Odczytaj NWD.

Tabela z przykładem obliczania NWD liczb 76 i 48 z resztą dzielenia
(wersja z dwoma zmiennymi)
a	b
76	48
76 : 48 = 1 reszta 28 (76 mod 48 = 28)	48
28	48 : 28 = 1 reszta 20 (48 mod 28 = 20)
28 : 20 = 1 reszta 8 (28 mod 20 = 8)	20
8	20 : 8 = 2 reszta 4 (20 mod 8 = 4)
8 : 4 = 2 reszta 0 (8 mod 4 = 0)	4

Z tabeli odczytujemy: $a = 0$ , więc $b = NWD(76, 48) = 4$

Rozwiązanie z wykorzystaniem modulo (wersja ze trzema zmiennymi)
a	operator	b	równa się	wynik (reszta)
76	mod	48	=	28
48	mod	28	=	20
28	mod	20	=	8
20	mod	8	=	4
8	mod	4	=	0

Z tabeli odczytujemy: $reszta = 0$ i $b = NWD(76, 48) = 4$

Ćwiczenie 2

Ułóż w postaci listy kroków algorytm Euklidesa znajdowania największego wspólnego dzielnika dwóch liczb całkowitych dodatnich (z wykorzystaniem reszty z dzielenia). Zapisz dwie wersje z dwoma zmiennymi a, b oraz wersję ze zmienną pomocniczą reszta.

Specyfikacja problemu:
Dane: $a$ i $b$ – liczby całkowite dodatnie.
Wynik: $n w d$ – największy wspólny dzielnik liczb $a$ i $b$ .

Powtarzaj, aż $a = 0$ lub $b = 0$ :
1.1. Jeżeli $a > b$ to:
⠀ 1.1.1. Przypisz a wartość $a \mod b$ .
w przeciwnym przypadku:
⠀ 1.1.2. Przypisz $b$ wartość $b \mod a$ .
Przypisz $n w d$ wartość $a + b$ .

Wprowadzając pomocniczą zmienną można zapisać algorytm trochę prościej, bez użycia instrukcji warunkowej.

Powtarzaj aż $b = 0$ .
1.1. Przypisz zmiennej $r e s z t a$ wartość $a \mod b$ .
1.2. Przypisz $a$ wartość $b$ .
1.3. Przypisz $b$ wartość $r e s z t a$ .
Przypisz $n w d$ wartość $a$ .

Ćwiczenie 3

Stwórz własny blok z dwoma parametrami liczbowymi, który będzie realizował jeden z algorytmów wyliczania największego wspólnego dzielnika.

R9KwdJowPRZOP

Ćwiczenie 3

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

Modyfikujemy program: Jaki to ułamek?

Na trzeciej stronie tego materiału tworzyliśmy interaktywną grę, która pomaga zrozumieć koncepcję ułamków zwykłych. Teraz ją udoskonalimy. Zmiana projektu będzie polegała na tym, aby duszek rozpoznawał trzy stany:

Grający udzielił poprawnej odpowiedzi ze skróconym ułamkiem.
Grający udzielił poprawnej odpowiedzi co do wartości ułamka, ale go nie skrócił.
Grający udzielił błędnej odpowiedzi.

Czy grający udzielił prawidłowej odpowiedzi sprawdzisz używając tego samego warunku, co dotychczas.

R5uiKekjSs30N

Przedstawiono zielony blok w języku Scratch. Zawiera on dwa pola do porównania, oddzielone znakiem =. Po lewej stronie równania jest wartość będąca wynikiem działania <licznik przez mianownik>, a po prawej wynik z <licznik_odp przez mianownik_odp>. — Blok z kategorii Wyrażenia, sprawdzający, czy istnieje równość między dwiema stronami równania
Źródło: GroMar Sp. z o.o., licencja: CC BY-SA 3.0.

Jeśli przyjmuje on wartość prawda, należy korzystając z bloku obliczającego NWD rozstrzygnąć, czy wyświetlić „Brawo, to jest poprawna odpowiedź!!” (stan 1), czy „Dobrze, ale można skrócić ułamek...” (stan 2).

Ćwiczenie 4

Sformułuj warunek logiczny sprawdzający, czy grający podał jako odpowiedź skrócony ułamek i popraw skrypt.

RusMAP2wAvfnc

Notatnik

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

Ćwiczenie 4

Sformułuj warunek logiczny sprawdzający, czy grający podał jako odpowiedź skrócony ułamek.

iuak7gU6CL_d715e232

Poniżej znajduje się pole tekstowe przeznaczone do zapisywania notatek. Możesz w nim zapisać wszystkie informacje, które uważasz za potrzebne.

RODPNT7o0mXlx

Pole tekstowe do zapisywania odpowiedzi i notatek.

Źródło: GroMar, licencja: CC BY 3.0.

Algorytm Euklidesa - wersja z odejmowaniem

Działania matematyczne w Scratch

Modyfikujemy program: Jaki to ułamek?