I Liceum Ogólnokształcące w Jarosławiu - Informatyka

Algorytm Euklidesa i działania na ułamkach

Jeden z najstarszych algorytmów obliczeniowych – wyznaczanie NWD metodą Euklidesa oraz zastosowanie go do dodawania ułamków zwykłych.

1Patchworkowe kołdry – skąd NWD?

Kołdra patchworkowa powstaje ze zszycia wielu mniejszych kawałków tkanin. Wyobraź sobie, że przygotowujesz projekt małej kołdry o wymiarach 112 × 88 cm, która ma być uszyta z jak największych kwadratowych kawałków równej wielkości. Jakiej długości bok powinien mieć taki kawałek?

Długość boku takiego kwadratu musi być największą możliwą liczbą, która dzieli liczby wyrażające długość i szerokość całej kołdry. Innymi słowy – szukamy największego wspólnego dzielnika liczb 112 i 88. Ponieważ 88 = 8 · 11 oraz 112 = 8 · 2 · 7, odpowiedź wynosi 8 cm.

Warto wiedzieć: Odcinanie jak największego kwadratu od danego prostokąta to przykład zastosowania strategii algorytmicznej zwanej podejściem zachłannym.
2Największy wspólny dzielnik (NWD)

Największy wspólny dzielnik (NWD) dwóch liczb całkowitych dodatnich a i b to największa liczba całkowita, która jest dzielnikiem obu tych liczb. Jeśli a jest dzielnikiem b, to liczba a jest największym wspólnym dzielnikiem liczb a i b.

O dwóch liczbach, które nie mają wspólnego dzielnika większego od 1, mówi się, że są względnie pierwsze.

3 Algorytm naiwny wyznaczania NWD

Jedno z rozwiązań: szukamy wspólnego dzielnika liczb a i b wśród coraz mniejszych liczb, zaczynając od dzielnika o wartości równej mniejszej z tych liczb. Poszukiwanie NWD zakończy się najpóźniej w momencie, gdy wspólny dzielnik będzie równy 1.

  • 1Jeśli a > b, to zamień wartości a i b miejscami.
  • 2Dla wartości d równych kolejno a, a−1, a−2, …, 1 powtarzaj kroki 3, 4 i 5.
  • 3Wyznacz resztę z dzielenia a przez d.
  • 4Wyznacz resztę z dzielenia b przez d.
  • 5Jeśli obie reszty wyznaczone w krokach 3 i 4 są równe 0, to zwróć wartość d i zakończ algorytm.
Algorytm naiwny dla pary liczb: 112 i 88 sprawdza każdą z liczb: 88, 87, 86, …, 9, 8, więc wykonuje ponad 80 dzieleń. Dla liczb wielocyfrowych, np. 100 000 014 oraz 99 999 999, byłoby to miliard operacji – poważne obciążenie dla komputera.
4 Wycinanka Euklidesa

Wróćmy do przykładu z kołdrą 112 × 88 cm. Krok po kroku odcinamy jak największy kwadrat od prostokąta, który powstał w poprzednim kroku. Po pewnej liczbie kroków otrzymamy prostokąt, który jest kwadratem.

Wymiary prostokąta Długość boku kwadratu
112 × 8888
88 × 2424
64 × 2424
40 × 2424
24 × 1616
16 × 88
8 × 8koniec

Obserwacja: NWD(a, b) = NWD(a, b−a) dla a < b. Ta równość jest podstawą algorytmu Euklidesa.

5 Algorytm Euklidesa (z odejmowaniem)
  • 1Dopóki a ≠ b, powtarzaj kroki 2 i 3.
  • 2Jeśli a > b, to a = a − b.
  • 3W przeciwnym razie b = b − a.
  • 4Zwróć wartość a.
Zapamiętaj: Największy wspólny dzielnik dwóch liczb naturalnych można wyznaczyć bez konieczności szukania wspólnych dzielników tych liczb. Należy zastosować algorytm Euklidesa.
6 Algorytm Euklidesa – wersja z dzieleniem

Jeśli w algorytmie Euklidesa jedna liczba jest dużo większa od drugiej, wielokrotnie powtarza się odejmowanie od niej tej samej liczby. Wielokrotne odejmowanie możemy zastąpić wyznaczeniem reszty z dzielenia większej liczby przez mniejszą.

Wartość zmiennej aWartość zmiennej b
19642
196 % 42 = 2842
2842 % 28 = 14
28 % 14 = 014
  • 1Dopóki a ≠ 0 i b ≠ 0, powtarzaj kroki 2 i 3.
  • 2Jeśli a > b, to a = a % b.
  • 3W przeciwnym razie b = b % a.
  • 4Jeśli a ≠ 0, to zwróć a.
  • 5W przeciwnym razie zwróć b.
Warto wiedzieć: Operacja dzielenia i modulo pochłania stosunkowo dużo czasu pracy procesora. W najszybszych implementacjach dzielenie z resztą zastępuje się odejmowaniem oraz przesunięciami bitów (o jeden w prawo), które procesory wykonują szybko. W ten sposób NWD można wyznaczyć ok. 60% szybciej.
2 Wizualizacja – wyznaczanie NWD krok po kroku

Wpisz dwie liczby całkowite dodatnie i obserwuj kroki algorytmu Euklidesa (wersja z dzieleniem).

3 Implementacja algorytmu Euklidesa w Pythonie

Algorytm naiwny – sprawdzanie dzielników od a do 1

def NWD(a, b):
    if a > b:
        a, b = b, a
    for d in range(a, 0, -1):
        if a % d == 0 and b % d == 0:
            return d

a = int(input("Podaj liczbę a: "))
b = int(input("Podaj liczbę b: "))
print("NWD(" + str(a) + "," + str(b) + "= ", NWD(a, b))
Funkcja NWD zapisana jest w wierszach 1–6. W wierszu 3 kod zamienia wartości zmiennych tak, aby zawsze w zmiennej a była mniejsza, a w zmiennej b – większa wartość. Zastosowano skrótowy zapis zamiany wartości zmiennych: a, b = b, a.

Algorytm Euklidesa – wersja z odejmowaniem

def NWD(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a
Po zakończeniu działania pętli while wartości obu zmiennych a i b są równe największemu wspólnemu dzielnikowi początkowych wartości a i b. W przypadku liczb, które nie mają wspólnego dzielnika większego niż 1, funkcja zwraca wartość 1.

Algorytm Euklidesa – wersja z dzieleniem (najszybsza)

def NWD(a, b):
    while a != 0 and b != 0:
        if a > b:
            a = a % b
        else:
            b = b % a
    if a != 0:
        return a
    else:
        return b

a = int(input("Podaj liczbę a: "))
b = int(input("Podaj liczbę b: "))
print("NWD(" + str(a) + "," + str(b) + "= ", NWD(a, b))
Przykładowe uruchomienie:
Podaj liczbę a: 112
Podaj liczbę b: 88
NWD(112,88)= 8

Porównanie liczby iteracji – naiwny vs. Euklides (z dzieleniem)

Funkcja str służy do przekształcania danych na napisy (ciągi znaków). Operator + pozwala na scalanie napisów i może być wykorzystany np. jako element funkcji print.
4 14.3 Działania na ułamkach zwykłych

Żeby dodać dwa ułamki zwykłe, wystarczy pomnożyć ich mianowniki i dodać liczniki mnożone odpowiednio przez mianowniki:

a/b + c/d = (a·d + c·b) / (b·d) = e/f

Aby doprowadzić ułamek do postaci nieskracalnej, wystarczy podzielić liczby e i f przez NWD(e, f).

Specyfikacja problemu dodawania dwóch ułamków

Dane: cztery liczby całkowite – licznik i mianownik jednego ułamka oraz licznik i mianownik drugiego ułamka.

Wynik: dwie liczby całkowite – licznik i mianownik sumy ułamków, zapisane w postaci nieskracalnej.

Kod źródłowy programu Suma ułamków

def NWD(a, b):
    while a != 0 and b != 0:
        if a > b:
            a = a % b
        else:
            b = b % a
    if a != 0:
        return a
    else:
        return b

def suma(a, b, c, d):
    e = a * d + c * b
    f = b * d
    nwd_ef = NWD(e, f)
    print(str(e // nwd_ef) + "/" + str(f // nwd_ef))

licz_1 = int(input("Liczba 1 - licznik: "))
mian_1 = int(input("Liczba 1 - mianownik: "))
licz_2 = int(input("Liczba 2 - licznik: "))
mian_2 = int(input("Liczba 2 - mianownik: "))

print("\n" + str(licz_1) + "/" + str(mian_1) + " + ", end="")
print(str(licz_2) + "/" + str(mian_2) + " = ", end="")
suma(licz_1, mian_1, licz_2, mian_2)
W liniach 1–10 zdefiniowano funkcję wyznaczającą NWD zgodnie z algorytmem Euklidesa (wersja z dzieleniem), a w liniach 12–16 zdefiniowano funkcję suma, która jest funkcją niezwracającą wartości, ponieważ nie zawiera instrukcji return. Zadaniem tej funkcji jest wykonanie obliczeń i wyświetlenie efektu na ekranie. Dlatego też w linii 25 znajduje się wywołanie funkcji suma bez funkcji print.

Kalkulator dodawania ułamków

+
=
5 Ćwiczenia sprawdzające