Zasady gry

bg‑gray2

Treści zawarte w tym materiale wykraczają poza podstawę programową dla klas IV - VI szkoły podstawowej. Jeśli jednak chcesz dowiedzieć się więcej i poznać algorytm Euklidesa, który służy do obliczania NWD (największego wspólnego dzielnika) dwóch liczb naturalnych, wraz z przykładami wykorzystania go w języku Scratch, to zachęcamy cię do zapoznania się z tym materiałem.

Do zrozumienia niniejszego materiału potrzebna jest znajomość liczb naturalnych i całkowitych, ułamków zwykłych i dziesiętnych oraz wiedza na temat środowiska języka Scratch. Wszystkie te informacje oraz wiele innych możesz znaleźć w dostępnych materiałach.

Aby zrozumieć poruszane w tym materiale zagadnienia, przypomnij sobie:

W poniższym materiale stworzymy interaktywną grę, która pomaga zrozumieć koncepcję ułamków zwykłych.

Algorytm Euklidesa służy do wyznaczania największego wspólnego dzielnika dwóch liczb naturalnych. W tym materiale pokażemy jego zastosowanie do skracania ułamków zwykłych

ROsptnqm7Hn6G
Film prezentuje działanie aplikacji ułatwiającej zrozumienie pojęcia ułamka zwykłego. Na ekranie znajdują się czterdzieści cztery kwadraty. Narysowane w czterech rzędach, w każdym rzędzie po jedenaście kwadratów. Dwa górne rzędy są wyróżnione kolorem, dwa dolne są bez koloru. Na dole ekranu znajduje się stworek, który zadaje pytanie Jaka część figury jest zamalowana?. Wpisane są kolejno wartości: licznik - dwadzieścia dwa, mianownik - czterdzieści cztery. Stworek mówi Dobrze, ale można skrócić ułamek, po czym kliknięta została zielona flaga u góry ekranu, która spowodowała zresetowanie wcześniejszych odpowiedzi. Teraz w miejsce licznika została wpisana cyfra jeden, a mianownika - cyfra dwa. Po wpisaniu pojawił się dymek z napisem Brawo!.

Na filmie pokazano aplikację, która służy do graficznego przedstawienia ułamka zwykłego. Najpierw duszek losuje mianownik i licznik ułamka oraz przedstawia go w postaci figury podzielonej na zamalowane i niezamalowane kwadraty (możesz zaproponować własną reprezentację graficzną ułamka, np. w postaci kawałków pizzy). Następnie prosi o podanie licznika i mianownika ułamka, czyli informacji, jaka część figury jest zamalowana. W kolejnym kroku sprawdza poprawność odpowiedzi.

Duszek przedstawia graficznie ułamek

Rozpocznij od rozplanowania sceny. Pamiętaj, że jej rozmiar to 480 na 360 pikseli.

2
Ćwiczenie 1

Zastanów się, jaką przyjąć długość boku pojedynczego kwadratu, ile ich umieścić w jednym wierszu, ile maksymalnie wierszy zmieści się na scenie, aby zostało wolne miejsce dla duszka wyświetlającego komunikaty. Ustal na tej podstawie zakres losowania mianownika i licznika ułamka.

R15JD6qRZiXxs
Miejsce na wpisanie tekstu
Notatnik
Źródło: GroMar Sp. z o.o., licencja: CC BY 3.0.
2
Ćwiczenie 2

Zastanów się, w jaki sposób duszek narysuje kwadraty na scenie. Wymyślone rozwiązanie zapisz w poniższym notesie.

R1IP7ePHXdwxo
Miejsce na zapisanie odpowiedzi
Notatnik
Źródło: GroMar Sp. z o.o., licencja: CC BY 3.0.
2
Ćwiczenie 3

Narysuj w edytorze graficznym dwa kwadraty o długości boku np. 40, jeden zamalowany, drugi przezroczysty.

RCpruyxTkXIOH
Dwa duszki – kwadraty
Źródło: Maciej Borowiecki, Janusz Wierzbicki, licencja: CC BY 3.0.
R10cJeOfnr5sN
Ćwiczenie 3
Jak dodać duszka, którego możesz namalować wykorzystując wbudowane narzędzie graficzne w Scratchu? Możliwe odpowiedzi: 1. asd, 2. das, 3. ad
Źródło: GroMar Sp. z o.o., licencja: CC BY 3.0.

W projekcie będą więc występowały dwa duszki:

  1. Ukryty duszek – kwadrat, którego zadaniem będzie (np. po kliknięciu w zieloną flagę) wylosowanie mianownika i licznika oraz przygotowanie zadania na scenie, czyli przystemplowanie odpowiedniej liczby kwadratów zgodnie z wylosowanymi wartościami.

  2. Kotek (lub inna dowolnie przez ciebie wybrana postać), którego zadaniem będzie poproszenie o podanie odpowiedzi oraz sprawdzenie jej poprawności.

1
Ćwiczenie 4

Ułóż w programie Scratch algorytm dla duszka reprezentowanego przez kwadrat. Skrypt ma wylosować dwie wartości dla zmiennych licznik i mianownik
(wykorzystaj obliczenia wykonane w pierwszym ćwiczeniu). Następnie, skrypt powinien narysować tyle pustych kwadratów, ile wynosi różnica zmiennych mianownik - licznik oraz tyle pełnych kwadratów, ile wynosi zmienna licznik.

Rl787N8J8fLUo
Ćwiczenie 4
W jakiej kategorii znajdują się bloki umożliwiające edytowanie wartości zmiennych? Możliwe odpowiedzi: 1. Zmienne, 2. Zdarzenia, 3. Wyrażenia
Źródło: GroMar Sp. z o.o., licencja: CC BY 3.0.

Duszek sprawdza odpowiedź

Drugi duszek powinien poprosić o podanie odpowiedzi (licznik i mianownik ułamka określającego, jaka część figury jest zamalowana) oraz sprawdzić jej poprawność. Podane wartości trzeba zapamiętać w zmiennych o czytelnych nazwach, np. licznik_odp, mianownik_odp.

2
Ćwiczenie 5

Jak sprawdzić poprawność odpowiedzi udzielonej przez gracza? Czy porównanie wylosowanych wartości licznika i mianownika ułamka z wczytanymi wartościami wystarczy? Odpowiedź zapisz w poniższym notatniku.

RuS3mExMlsQk0
Miejsce na zapisanie odpowiedzi
Notatnik
Źródło: GroMar Sp. z o.o., licencja: CC BY 3.0.
2
Ćwiczenie 6

Spróbuj sformułować warunek logiczny, który będzie uwzględniać redukcję ułamka (skracanie). Wynikiem będzie prawda, jeżeli wartość wynosi tyle samo co, podany w odpowiedzi licznik podzielony przez podany w odpowiedzi mianownik, w przeciwnym wypadku wynikiem ma być fałsz. Odpowiedź zapisz poniżej.

RdAL8XSHaLG5t
Miejsce do zapisania odpowiedzi
Notatnik
Źródło: GroMar Sp. z o.o., licencja: CC BY 3.0.
R5G9unklbn1Qy
Ćwiczenie 6
Jak nazywa się kategoria w której możesz znaleźć bloki związane z porównywaniem wartości zmiennych? W tej samej kategorii możesz również znaleźć blok związany z losowaniem liczby z określonego zakresu. Możliwe odpowiedzi: 1. Czujniki, 2. Zdarzenia, 3. Wyrażenia
Źródło: GroMar Sp. z o.o., licencja: CC BY 3.0.
1
Ćwiczenie 7

Zapisz w liście kroków algorytm dla duszka sprawdzającego odpowiedź.

ROhhJhjOFy1Vq
Miejsce do zapisania odpowiedzi
Notatnik
Źródło: GroMar Sp. z o.o., licencja: CC BY 3.0.

Ułóż w programie Scratch skrypt dla duszka sprawdzającego odpowiedź zgodnie z listą kroków powyżej. Pamiętaj o warunku logicznym z poprzedniego ćwiczenia.

RYECq24q9EL7H
Ćwiczenie 7
Jak nazywa się kategoria w której możesz znaleźć bloki związane z odczytywaniem i reagowaniem na różnego rodzaju informacje z otoczenia, takie jak wartości z innych bloków? Możliwe odpowiedzi: 1. Czujniki, 2. Zdarzenia, 3. Wyrażenia
Źródło: GroMar Sp. z o.o., licencja: CC BY 3.0.

Przetestuj działanie programu. Zastanów się, czy i jak można jeszcze poprawić sprawdzanie odpowiedzi. Czy uzasadnione jest wyświetlanie komunikatu „Brawo, to jest poprawna odpowiedź!”, kiedy grający poda prawidłowo wartość ułamka, ale go nie skróci? Może lepiej w takiej sytuacji wyświetlić komunikat np. „Dobrze, ale ten ułamek można jeszcze skrócić...”. Czy potrafisz sformułować taki warunek i poprawić skrypty?

Wykorzystanie algorytmu Euklidesa

W tym etapie konieczna jest wiedza o zasadzie działania algorytmu Euklidesa. Możesz zapoznać się z tematem w materiałach: Klasyczny Algorytm Euklidesa z resztą z dzieleniaPs7XRBNbCKlasyczny Algorytm Euklidesa z resztą z dzielenia oraz Stosowanie funkcji w języku Python do realizacji algorytmu Euklidesa z odejmowaniemP1BvUOkroStosowanie funkcji w języku Python do realizacji algorytmu Euklidesa z odejmowaniem.

Algorytm Euklidesa to metoda obliczania największego wspólnego dzielnika (NWD) dwóch liczb naturalnych. Algorytm ten opiera się na właściwościach reszty z dzielenia, czyli na tym, że reszta z dzielenia jednej liczby przez drugą jest mniejsza od drugiej liczby. Istnieją dwie główne wersje algorytmu: wersja z odejmowaniem i wersja z resztą dzielenia (modulo).

Ważne!

Do badania podzielności możesz wykorzystać operację arytmetyczną moduloiuak7gU6CL_d715e232modulo, czyli resztę z dzielenia dwóch liczb całkowitych. Operacja modulo zwraca resztę z dzielenia jednej liczby przez drugą i oznacza jest symbolem % lub skrótem mod stawianym między dwoma liczbami.

Wykorzystanie wersji algorytmu Euklidesa z operacją arytmetyczną modulo znacznie zredukuje liczbę wykonywanych operacji.

Przykłady operacji modulo (obliczania reszty z dzielenia)

Przykład 1:

  • Wynikiem 7 mod 3 (7 modulo 3 lub 7 % 3) będzie 1, ponieważ 7 dzielone przez 3 to 2, a reszty zostaje 1.

  • Aby to sprawdzić, można wykonać operacje 3 × 2 = 6, a następnie 7 - 6 = 1, co odpowiada również 7 = 3 × 2 + 1.

  • Czyli w ostatecznym zapisie 7 % 3=1.

Przykład 2:

  • Wynikiem 16 mod 8 (16 modulo 8 lub 16 % 8) będzie 0, ponieważ 16 dzielone przez 8 to 2, a reszty zostaje 0.

  • Aby to sprawdzić, można wykonać operacje 8 × 2 = 16.

  • Czyli w ostatecznym zapisie 16 % 8=0.

2
Ćwiczenie 8

Korzystając z dołączonych materiałów omawiających algorytm Euklidesa,  przygotuj krótką prezentacjęPOBu79p1Pprezentację na temat Euklidesa, jego dzieł i omawianego algorytmu.

Ważne!

Planując prezentację pamiętaj o zastosowaniu zasady 5 plus minus 2, która mówi, aby prezentując na stronie jakąkolwiek informację, najlepiej zastosować nie mniej niż 3 i nie więcej niż 7 elementów. Ma to na celu uniknięcie przytłaczania odbiorcy zbyt dużą liczbą opcji.

Mając potrzebną wiedzę łatwo odpowiesz na pytanie, co trzeba zrobić, aby skrócić ułamek. Wystarczy znaleźć największą liczbę naturalną taką, która dzieli bez reszty zarówno licznik jak i mianownik ułamka, następnie podzielić licznik i mianownik przez ten dzielnik. Taką liczbę nazywamy największym wspólnym dzielnikiem i oznaczamy NWD.

Powyżej znajdują się linki do materiałów przedstawiających zasady działania algorytmu. Przykład poniżej pozwoli ci lepiej zrozumieć jego praktyczne zastosowanie.

Przykład obliczenia NWD dla liczb 7648, algorytmem Euklidesa z zastosowaniem operacji odejmowania.

Tabela z przykładem obliczania NWD dla liczb 76 i 48

a

b

76

48

76 - 48 = 28

48

28

48 - 28 = 20

28 - 20 = 8

20

8

20 - 8 = 12

8

12 - 8 = 4

8 - 4 = 4

4

1
Ćwiczenie 9

Zapisz w postaci listy kroków algorytm Euklidesa znajdowania największego wspólnego dzielnika dwóch liczb całkowitych dodatnich (z wykorzystaniem odejmowania).

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

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ą modulo z wykorzystaniem reszty z dzielenia. Na przykład dla a=256a=48 otrzymujemy:

Tabela z obliczeniami NWD dla 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

Rozwiązanie z wykorzystaniem modulo (wersja z dwoma zmiennymi)

a

b

256

48

256 : 48 = 5 reszta 16

(256 mod 48 = 16)

48

16

48 : 16 = 3 reszta 0

48 mod 16 = 0

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:

Rozwiązanie z wykorzystaniem modulo (wersja ze trzema zmiennymi)

a

operator

b

równa się

wynik (reszta)

256

mod

48

=

16

48

mod

16

=

0

Operator mod oznacza operację wyznaczania reszty z dzielenia.

Wróćmy do przykładu obliczenia NWD dla liczb 76 oraz 48 i rozwiążmy go algorytmem Euklidesa z wykorzystaniem reszty z dzielenia (zastosowaniem operacji modulo). Na początek zapiszmy to w dwóch kolumnach, podobnie jak przy odejmowaniu.

Tabela z przykładem obliczania NWD dla 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

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

1
Ćwiczenie 10

Zapisz 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 dwa sposoby:

  • z dwoma zmiennymi ab i z instrukcją warunkową podobną, jak w przypadku algorytmu Euklidesa z odejmowaniem ,

  • wersję ze zmienną pomocniczą reszta.

Odpowiedź możesz umieścić w poniższym notatniku.

ROmBXBss4w38a
(Uzupełnij).
Notatnik
Źródło: GroMar Sp. z o.o., licencja: CC BY 3.0.
2
Ćwiczenie 11

Znasz już kilka algorytmów znajdowania największego wspólnego dzielnika. Zastanów się i  ewentualnie przedyskutuj z kolegami i koleżankami, który z nich wykona mniej powtórzeń.

3
Ćwiczenie 12

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

Informacje na temat tworzenia własnych bloków znajdziesz w materiale Projektowanie automatu biletowego w programie ScratchDZP9YtLoFProjektowanie automatu biletowego w programie Scratch. Zostało to wyjaśnione w ćwiczeniu 17.

R9KwdJowPRZOP
Ćwiczenie 12
W jakiej kategorii znajduje się opcja, która umożliwia utworzenie nowego bloku? Możliwe odpowiedzi: 1. Czujniki, 2. Zdarzenia, 3. Wyrażenia, 4. Moje bloki
Źródło: GroMar Sp. z o.o., licencja: CC BY 3.0.
iuak7gU6CL_d715e232

Modyfikujemy program

Modyfikacja projektu będzie polegała na tym, aby rozpoznawać trzy stany:

  1. Grający udzielił poprawnej odpowiedzi ze skróconym ułamkiem.

  2. Grający udzielił poprawnej odpowiedzi co do wartości ułamka, ale go nie skrócił.

  3. Grający udzielił błędnej odpowiedzi.

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

R5uiKekjSs30N
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 3.0.

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

3
Ćwiczenie 13

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

RusMAP2wAvfnc
Miejsce do zapisania rozwiązania
Notatnik
Źródło: GroMar Sp. z o.o., licencja: CC BY 3.0.
R1Py4slZ5I5ld
Ćwiczenie 13
Jak nazywa się kategoria, która służy do kontrolowania pozycji duszków? Możliwe odpowiedzi: 1. Ruch, 2. Zdarzenia, 3. Wyrażenia
Źródło: GroMar Sp. z o.o., licencja: CC BY 3.0.

Zadanie uzupełniające

3
Ćwiczenie 14

Przygotuj skrypt, w którym duszek poprosi o podanie wymiarów prostokąta, tj. szerokości i wysokości. Następnie duszek powinien zwrócić obliczoną minimalną liczbę kwadratów, którymi można wypełnić prostokąt, jak również długość ich boku.

Specyfikacja problemu:

Dane: Prostokąt o szerokości s i wysokości w.

Wynik: Minimalna liczba takich samych kwadratów, którymi można wypełnić prostokąt oraz długość boku pojedynczego kwadratu

Przykład: prostokąt o długości s=250w=150.
Minimalna liczba kwadratów wynosi 15 (długość boku kwadratu wynosi 50).

R1LOfqpvCnhAn
Prostokąt o wymiarach 3 × 5
Źródło: GroMar Sp. z o.o., licencja: CC BY 3.0.
RGXXryHbvMKWX
Ćwiczenie 14
Jak nazywa się kategoria w której możesz znaleźć bloki związane z kontrolowaniem skryptów pod pewnymi warunkami? Możliwe odpowiedzi: 1. Ruch, 2. Zdarzenia, 3. Wyrażenia, 4. Kontrola
Źródło: GroMar Sp. z o.o., licencja: CC BY 3.0.