Na lekcjach informatyki w klasie ósmej poznamy podstawowe algorytmy na liczbach naturalnych stosowane w matematyce i informatyce. Zapiszemy je w języku programowania Python. W tym temacie:

In eighth-grade computer science, we will learn fundamental algorithms on natural numbers used in mathematics and computer science. We will implement them in Python. In this topic:

1. poznasz i zaprogramujeszyou will learn and program algorytm badania podzielności liczb,the divisibility testing algorithm,
2. poznasz i zaprogramujeszyou will learn and program algorytm Euklidesa w dwóch wersjach: z odejmowaniem i z resztą z dzielenia,Euclid's algorithm in two versions: subtraction and division remainder,
3. poznasz i zaprogramujeszyou will learn and program algorytm wyodrębniania cyfr danej liczby.the digit extraction algorithm.

1 Badanie podzielności liczb naturalnych Testing Divisibility of Natural Numbers

Tabela 1. Testowanie algorytmu badania podzielności

Table 1. Testing the divisibility algorithm

a = int(input("Wprowadź wartość dzielnej: "))
b = int(input("Wprowadź wartość dzielnika: "))

if a % b == 0:
    print("a jest podzielne przez b")
else:
    print("a nie jest podzielne przez b")

input("\n\nAby zakończyć, naciśnij Enter")

2 Algorytm Euklidesa Euclid's Algorithm

2a. Wersja z odejmowaniem

2a. Subtraction version

Euklides zauważył, że NWD dwóch liczb jest taki sam jak NWD ich różnicy. Dlatego od większej liczby odejmujemy mniejszą i zastępujemy większą otrzymaną różnicą – powtarzamy, dopóki obie liczby nie będą równe.

Euclid noticed that the GCD of two numbers equals the GCD of their difference. We subtract the smaller from the larger and replace the larger with the result – we repeat until both numbers are equal.

a = int(input("Podaj pierwszą liczbę: "))
b = int(input("Podaj drugą liczbę: "))

while a != b:
    if a > b:
        a = a - b
    else:
        b = b - a

print("NWD =", a)
input("\n\nAby zakończyć, naciśnij Enter")

2b. Wersja z resztą z dzielenia

2b. Division remainder version

Wersja z resztą z dzielenia jest znacznie szybsza. Wykonujemy kolejne dzielenia: dzielną zastępujemy dzielnikiem, a dzielnik – resztą z dzielenia, aż reszta wyniesie 0. Wynikiem jest ostatnia niezerowa reszta.

The division remainder version is much faster. We repeatedly divide: replace the dividend with the divisor and the divisor with the remainder, until the remainder equals 0.

Tabela 3. Testowanie algorytmu Euklidesa – wersja z resztą (a=28, b=35)

Table 3. Testing Euclid's algorithm – remainder version (a=28, b=35)

a = int(input("Podaj pierwszą liczbę: "))
b = int(input("Podaj drugą liczbę: "))

while b != 0:
    dzielnik = b        # zapamiętaj aktualny dzielnik
    b = a % b           # reszta z dzielenia
    a = dzielnik        # dzielnik staje się nową dzielną

print("NWD =", a)
input("\n\nAby zakończyć, naciśnij Enter")

3 Wyodrębnianie cyfr danej liczby naturalnej Extracting Digits of a Natural Number

Tabela 4. Testowanie algorytmu wyodrębniania cyfr (liczba = 647)

Table 4. Testing digit extraction algorithm (number = 647)

liczba = int(input("Podaj liczbę: "))
print("Cyfry liczby", liczba, "od ostatniej:")

if liczba == 0:
    print(liczba)                      # przypadek szczególny
else:
    while liczba != 0:
        cyfra = liczba % 10             # cyfra jedności
        print(cyfra)
        liczba = (liczba - cyfra) // 10  # usuń cyfrę jedności

input("\n\nAby zakończyć, naciśnij Enter")

while liczba != 0:
    cyfra = liczba % 
    print(cyfra)
    liczba = (liczba - cyfra) //