Cele lekcji

Po tej lekcji:

• wiesz, czym są liczby naturalne i algorytm,
• rozumiesz, na czym polega badanie podzielności liczb naturalnych,
• potrafisz zapisać algorytm:
  • w postaci listy kroków,
  • jako schemat blokowy,
  • w języku Python,
• znasz ideę algorytmu Euklidesa w wersji z odejmowaniem,
• potrafisz testować algorytmy na przykładach,
• dokumentujesz swoją pracę w formie raportu na chmurze (Office 365).

Wprowadzenie – czym są algorytmy na liczbach naturalnych

Liczby naturalne

Liczby naturalne to liczby:$$0, 1, 2, 3, 4, 5, \dots$$0,1,2,3,4,5,…

W informatyce bardzo często pracujemy właśnie na liczbach naturalnych, np.:

• liczbie uczniów,
• liczbie punktów,
• liczbie iteracji w pętli,
• numerach elementów listy.

Czym jest algorytm

Algorytm to:

uporządkowany, skończony zestaw kroków prowadzących do rozwiązania konkretnego problemu.

Algorytm:

• zawsze ma początek i koniec,
• składa się z jasnych instrukcji,
• dla tych samych danych wejściowych daje ten sam wynik.

1. Badanie podzielności liczb naturalnych

Problem praktyczny

Chcemy sprawdzić, czy daną liczbę uczniów można podzielić równo na zespoły.

• klasa 8a: 24 uczniów
• klasa 8b: 27 uczniów
• zespoły po 6 osób

Obliczenia:

• 24 ÷ 6 = 4, reszta 0 → da się podzielić,
• 27 ÷ 6 = 4, reszta 3 → nie da się podzielić.

Definicja podzielności

Jeśli reszta z dzielenia dwóch liczb naturalnych jest równa 0, to:

pierwsza liczba (dzielna) jest podzielna przez drugą (dzielnik).

Specyfikacja algorytmu badania podzielności

Dane:

• liczba naturalna a (dzielna),
• liczba naturalna b (dzielnik, b ≠ 0).

Wynik:

• informacja, czy a jest podzielne przez b.

Lista kroków algorytmu

1. Rozpocznij algorytm.
2. Wprowadź wartość liczby a.
3. Wprowadź wartość liczby b.
4. Oblicz resztę z dzielenia: reszta = a mod b.
5. Jeśli reszta = 0, wypisz komunikat:
   „a jest podzielne przez b”.
6. W przeciwnym razie wypisz komunikat:
   „a nie jest podzielne przez b”.
7. Zakończ algorytm.

Schemat blokowy algorytmu

Schemat blokowy przedstawia algorytm graficznie

• bloki wejścia danych,
• obliczenie reszty,
• blok warunkowy (TAK / NIE),
• zakończenie algorytmu.

2. Badanie podzielności w języku Python

Operator modulo

W języku Python do obliczania reszty z dzielenia używamy operatora:

%

Przykłady:

• 10 % 3 = 1
• 12 % 4 = 0

Program:

• pobiera dane z klawiatury,
• oblicza resztę,
• wypisuje odpowiedni komunikat,
• wykorzystuje instrukcję warunkową if … else.

Naciśnij przycisk Run.
Zobacz, co pojawia się w oknie wyników, zapisz sprawdzony kod na swojej chmurze i udostępnij folder nauczycielowi. Opis organizacji plików z lekcji znajduje się w punkcie 6 niniejszej instrukcji.

Ćwiczenia

Ćwiczenie 1

Sprawdź podzielność czterech par liczb:

• a = 34, b = 9
• a = 36, b = 6
• a = 112, b = 4
• a = 2, b = 18

Zapisz rozwiązanie w tabeli – wzoruj się na tabeli

Ćwiczenie 2

Przepisz program z rys. 3.
Zapisz plik pod nazwą Podzielność.py.
Uruchom program dla różnych wartości a i b.

Ćwiczenie 3

Wyjaśnij działanie programu:

• opisz rolę instrukcji if,
• wyjaśnij, czym jest operator %,
• wskaż moment, w którym zapada decyzja o wyniku.

Ćwiczenie 4

Napisz program, który sprawdzi, czy możliwe jest utworzenie równych drużyn w klasie.
Program:

• pobiera liczbę uczniów,
• sprawdza podzielność przez 6,
• wyświetla odpowiedni komunikat (jak na rys. 4).

Zapisz plik pod nazwą Siatkówka.py.

3. Algorytm Euklidesa – wprowadzenie

Co to jest NWD

Największy wspólny dzielnik (NWD) dwóch liczb naturalnych to:

największa liczba naturalna, która dzieli obie liczby bez reszty.

Idea algorytmu Euklidesa

Algorytm Euklidesa pozwala znaleźć NWD dwóch liczb, wykonując kolejne operacje, aż liczby staną się równe.

W wersji z odejmowaniem:

• od większej liczby odejmujemy mniejszą,
• podstawiamy wynik zamiast większej liczby,
• powtarzamy, aż liczby będą równe.

• a = 25, b = 10
• kolejne kroki prowadzą do wyniku: NWD = 5

Specyfikacja algorytmu Euklidesa

Dane:

• liczby naturalne a, b (a ≠ 0, b ≠ 0)

Wynik:

• wartość NWD liczb a i b

Lista kroków algorytmu

1. Wprowadź wartości a i b.
2. Dopóki a ≠ b:
   • jeśli a > b, przypisz a = a - b,
   • w przeciwnym razie przypisz b = b - a.
3. Gdy a = b, wypisz wynik: NWD = a.
4. Zakończ algorytm.

Implementacja w Pythonie

Algorytm realizujemy za pomocą:

• pętli while,
• instrukcji warunkowej if.

Kod odpowiada schematowi blokowemu z rys. 5 i 6 oraz przykładowemu programowi z rys. 7.

Ćwiczenia z algorytmu Euklidesa

Ćwiczenie 5

Sprawdź działanie algorytmu Euklidesa dla:

• a = 3, b = 9
• a = 16, b = 12

Zapisz kolejne kroki w tabeli (jak w tabeli 2).

Ćwiczenie 6

Przepisz program realizujący algorytm Euklidesa w wersji z odejmowaniem.
Zapisz plik pod nazwą Euklides_odejmowanie.py.

Ćwiczenie 7

Zmodyfikuj program tak, aby:

• obliczał NWD dla dziesięciu par liczb,
• pobierał dane z klawiatury,
• wyświetlał wynik po każdej parze.

Zapisz plik pod nazwą Euklides_odejmowanie_10.py.

Zadania rozszerzające

Zadanie A – analiza algorytmu

Wyjaśnij:

• dlaczego algorytm Euklidesa zawsze się kończy,
• w którym momencie pętla while przestaje się wykonywać.

Zadanie B – porównanie algorytmów

Porównaj:

• badanie podzielności,
• algorytm Euklidesa.

Odpowiedz:

• który algorytm jest prostszy,
• który wykonuje więcej kroków,
• do jakich problemów każdy z nich się nadaje.

Dokumentowanie pracy – raport (obowiązkowe)

Całość pracy zapisujesz w raporcie na chmurze (Office 365), zgodnie z ustalonym sposobem pracy w klasie 8.

Raport powinien zawierać:

1. Tytuł lekcji i datę.
2. Krótkie wyjaśnienie pojęć:
   • liczby naturalne,
   • algorytm,
   • podzielność,
   • NWD.
3. Rozwiązania ćwiczeń 1–7.
4. Wklejone fragmenty kodu Python.
5. Odpowiedzi do zadań dodatkowych (jeśli wykonałeś).
6. Wnioski – czego nauczyłeś się na tej lekcji.

Co dalej?

To jest lekcja 1 z 3 w temacie Algorytmy na liczbach naturalnych.

Na kolejnej lekcji:

• przejdziemy do algorytmu Euklidesa z resztą z dzielenia,
• porównamy obie wersje algorytmu,
• skupimy się na efektywności algorytmów.

Na trzeciej lekcji:

samodzielnie zaprojektujesz i opiszesz algorytm.

wykonasz zestaw zadań podsumowujących.

Algorytmy na liczbach naturalnych – część 2

Przypomnienie (krótko, na start lekcji)

Na poprzedniej lekcji:

• poznaliśmy algorytm Euklidesa w wersji z odejmowaniem,
• zapisaliśmy go w postaci listy kroków, schematu blokowego i programu w Pythonie,
• wykonaliśmy ćwiczenia 1–7 z książki.

Dziś:

• przechodzimy do wydajniejszej wersji algorytmu Euklidesa – z resztą z dzielenia,
• uczymy się wydobywania cyfr z liczby naturalnej,
• ćwiczymy pętle while, instrukcje warunkowe i operator modulo (%).

Algorytm Euklidesa – wersja z resztą z dzielenia

Co to jest NWD?

NWD (największy wspólny dzielnik) dwóch liczb naturalnych to:

największa liczba naturalna, która dzieli obie liczby bez reszty.

Przykład:

• NWD(24, 18) = 6
• NWD(28, 35) = 7

Dlaczego wersja z resztą z dzielenia?

Wersja z odejmowaniem:

• działa poprawnie,
• ale bywa wolna (dużo kroków).

Wersja z resztą:

• jest szybsza,
• wykorzystuje operator modulo (%),
• dokładnie ten algorytm jest stosowany w praktyce.

Ćwiczenie 8 – Sprawdzamy działanie algorytmu Euklidesa (z resztą)

Polecenie

Sprawdź działanie algorytmu Euklidesa w wersji z resztą z dzielenia i wyznacz NWD dla liczb:

• a = 56, b = 6
• a = 16, b = 24

Rozwiązanie zapisz w dokumencie tekstowym, wzorując się na tabeli (jak w książce – rys. …).

Przykład – omówienie (do raportu ucznia)

Dla liczb a = 56, b = 6:

1. 56 mod 6 = 2
2. 6 mod 2 = 0
3. Skoro reszta = 0 → NWD = 2

Dla liczb a = 16, b = 24:

1. 24 mod 16 = 8
2. 16 mod 8 = 0
3. NWD = 8

Uczeń zapisuje kolejne kroki, nie tylko wynik.

Zapisywanie algorytmu Euklidesa (z resztą) w języku Python

Idea algorytmu

Dopóki b ≠ 0:

• obliczamy resztę: a mod b
• przesuwamy wartości:
  • a ← b
  • b ← reszta

Gdy b == 0, wynik to a.

Ćwiczenie 9 – Zapis algorytmu w Pythonie

Polecenie

1. Przepisz program realizujący algorytm Euklidesa w wersji z resztą z dzielenia.
2. Zapisz go w pliku Euklides_dzielenie.py.
3. Uruchom program kilkukrotnie, testując różne wartości a i b.
4. Wyjaśnij działanie programu, odnosząc się do listy kroków algorytmu.

(Uczeń korzysta z interfejsu testowego – tak jak na poprzedniej lekcji.)

Ćwiczenie 10 – Modyfikujemy program

Polecenie

1. Zmodyfikuj program z ćwiczenia 9 tak, aby:
   • wyszukiwał NWD dla dziesięciu par liczb wprowadzanych kolejno z klawiatury,
   • wyświetlał wyniki na ekranie.
2. Zapisz program w pliku Euklides_dzielenie_10.py.

Wskazówka dydaktyczna:
To ćwiczenie przygotowuje uczniów do pracy z:

• pętlami,
• większą liczbą danych,
• automatyzacją obliczeń.

Wyodrębnianie cyfr danej liczby naturalnej

O co chodzi?

Czasem chcemy:

• wypisać wszystkie cyfry liczby,
• policzyć ich liczbę,
• sprawdzić, czy dana cyfra występuje w liczbie.

Robimy to od cyfry jedności, korzystając z:

• mod 10 → ostatnia cyfra,
• // 10 → skrócenie liczby.

Przykład (jak w książce)

Dla liczby 647:

• 647 mod 10 = 7
• 647 // 10 = 64
• 64 mod 10 = 4
• 64 // 10 = 6
• 6 mod 10 = 6
• 6 // 10 = 0 → stop

Ćwiczenie 11 – Lista kroków algorytmu

Polecenie

1. Zapoznaj się z opisem algorytmu wyodrębniania cyfr liczby naturalnej.
2. Przeanalizuj schemat blokowy algorytmu (rys. …).
3. Sprawdź działanie algorytmu dla liczby 8945.
4. Zapisz w dokumencie tekstowym listę kroków algorytmu.

Zapisywanie algorytmu wyodrębniania cyfr w Pythonie

Algorytm wykorzystuje:

• pętlę while,
• operator %,
• instrukcję warunkową if.

Ćwiczenie 12 – Program w Pythonie

Polecenie

1. Przepisz program realizujący algorytm wyodrębniania cyfr liczby naturalnej.
2. Zapisz program w pliku Cyfry.py.
3. Uruchom program dla różnych wartości zmiennej liczba.
4. Opisz działanie programu, odnosząc się do schematu blokowego (rys. …).

Ćwiczenie 13 – Modyfikujemy program

Polecenie

1. Zmodyfikuj program z ćwiczenia 12 tak, aby:
   • wyodrębniał cyfry dziesięciu liczb wprowadzanych kolejno z klawiatury,
   • wyświetlał wyniki na ekranie.
2. Zapisz program w pliku Cyfry_10.py.
3. Odpowiedz pisemnie:
   • Ile razy powtarza się pętla while dla liczby trzycyfrowej?
   • A ile razy dla liczby dwucyfrowej?
4. Zmień instrukcję: liczba = (liczba - cyfra) // 10 na: liczba = liczba // 10 Czy program działa tak samo? Uzasadnij odpowiedź.