Liceum Klasa I 45 minut PP: I.2a | s. 342

Lekcja 6: NWD i NWW - algorytm Euklidesa, dzialania na ulamkach

Najwiekszy wspolny dzielnik, najmniejsza wspolna wielokrotnosc, upraszczanie ulamkow

📋 Podstawa programowa: I.2a
NWDNWWalgorytmydzieleniereszta
00:00
Wprowadzenie
5 min
00:05
Teoria
18 min
00:23
Cwiczenia
15 min
00:38
Podsumowanie
7 min
📚

Teoria

▼

Najwiekszy wspolny dzielnik (NWD)

NWD (a, b) (ang. GCD - Greatest Common Divisor) to najwieksza liczba, ktora dzieli jednoczesnie a i b bez reszty.

Przyklad: Dzielniki 12: {1, 2, 3, 4, 6, 12}. Dzielniki 18: {1, 2, 3, 6, 9, 18}. Wspolne dzielniki: {1, 2, 3, 6}. NWD(12, 18) = 6.

Algorytm Euklidesa (wersja z odejmowaniem)

Jeden z najstarszych algorytmow w matematyce (ok. 300 p.n.e.). Opiera sie na obserwacji: NWD(a, b) = NWD(a-b, b) dla a > b.

ALGORYTM EUKLIDESA (odejmowanie):
WEJSCIE: dwie liczby naturalne a, b
  1. DOPOKI a != b:
     2. JESLI a > b: a = a - b
     3. W PRZECIWNYM RAZIE: b = b - a
  4. ZWROC a (lub b, bo sa rowne)
KONIEC

Sledzenie: NWD(48, 18):

a=48, b=18 -> a>b -> a=48-18=30
a=30, b=18 -> a>b -> a=30-18=12
a=12, b=18 -> b>a -> b=18-12=6
a=12, b=6  -> a>b -> a=12-6=6
a=6,  b=6  -> a==b -> KONIEC
NWD(48, 18) = 6

Algorytm Euklidesa (wersja z reszta z dzielenia - szybsza!)

Zamiast odejmowac wielokrotnie, mozemy uzyc operacji modulo (reszta z dzielenia): NWD(a, b) = NWD(b, a mod b).

ALGORYTM EUKLIDESA (modulo):
WEJSCIE: dwie liczby naturalne a, b
  1. DOPOKI b != 0:
     2. temp = b
     3. b = a mod b
     4. a = temp
  5. ZWROC a
KONIEC

Sledzenie: NWD(48, 18):

a=48, b=18 -> b!=0 -> a=18, b=48%18=12
a=18, b=12 -> b!=0 -> a=12, b=18%12=6
a=12, b=6  -> b!=0 -> a=6,  b=12%6=0
a=6,  b=0  -> b==0 -> KONIEC
NWD(48, 18) = 6

Implementacja w Pythonie:

def nwd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# Testy
print(nwd(48, 18))   # 6
print(nwd(100, 75))  # 25
print(nwd(17, 13))   # 1 (liczby wzglednie pierwsze)

Najmniejsza wspolna wielokrotnosc (NWW)

NWW (a, b) (ang. LCM - Least Common Multiple) to najmniejsza liczba, ktora jest jednoczesnie wielokrotnoscia a i b.

Zwiazek NWW z NWD:

NWW(a, b) = (a * b) / NWD(a, b)

Przyklad: NWW(12, 18) = (12 * 18) / NWD(12, 18) = 216 / 6 = 36.

Sprawdzenie: Wielokrotnosci 12: {12, 24, 36, 48...}. Wielokrotnosci 18: {18, 36, 54...}. Pierwsza wspolna: 36.

def nww(a, b):
    return (a * b) // nwd(a, b)

# Testy
print(nww(12, 18))  # 36
print(nww(4, 6))    # 12
print(nww(7, 5))    # 35

Zastosowanie NWD - upraszczanie ulamkow

Aby uprascic ulamek, dzielimy licznik i mianownik przez ich NWD:

# Przyklad: 48/18
# NWD(48, 18) = 6
# 48/6 = 8, 18/6 = 3
# 48/18 = 8/3

def uproc_ulamek(licznik, mianownik):
    d = nwd(abs(licznik), abs(mianownik))
    return licznik // d, mianownik // d

print(uproc_ulamek(48, 18))   # (8, 3)
print(uproc_ulamek(24, 36))   # (2, 3)
print(uproc_ulamek(100, 75))  # (4, 3)

Zastosowanie NWW - dodawanie ulamkow

Do dodawania ulamkow o roznych mianownikach potrzebujemy wspolnego mianownika - i tu przydaje sie NWW:

# Dodawanie: 3/4 + 5/6
# NWW(4, 6) = 12
# 3/4 = 9/12
# 5/6 = 10/12
# 9/12 + 10/12 = 19/12

def dodaj_ulamki(l1, m1, l2, m2):
    wspolny_m = nww(m1, m2)
    nowy_l = l1 * (wspolny_m // m1) + l2 * (wspolny_m // m2)
    return uproc_ulamek(nowy_l, wspolny_m)

print(dodaj_ulamki(3, 4, 5, 6))  # (19, 12)
✏️

Zadania

▼
Latwe

Zadanie 1: NWD algorytmem Euklidesa

Oblicz NWD nastepujacych par liczb, uzywajac algorytmu Euklidesa z reszta z dzielenia. Pokaz pelne sledzenie (trace):
a) NWD(56, 42)
b) NWD(120, 45)
c) NWD(91, 39)

Pokaz przykladowe rozwiazanie 
a) NWD(56, 42):
   a=56, b=42 -> a=42, b=56%42=14
   a=42, b=14 -> a=14, b=42%14=0
   NWD(56, 42) = 14

b) NWD(120, 45):
   a=120, b=45 -> a=45, b=120%45=30
   a=45,  b=30 -> a=30, b=45%30=15
   a=30,  b=15 -> a=15, b=30%15=0
   NWD(120, 45) = 15

c) NWD(91, 39):
   a=91, b=39 -> a=39, b=91%39=13
   a=39, b=13 -> a=13, b=39%13=0
   NWD(91, 39) = 13
Latwe

Zadanie 2: NWW z wykorzystaniem NWD

Oblicz NWW nastepujacych par liczb, korzystajac ze wzoru NWW(a,b) = a*b/NWD(a,b):
a) NWW(8, 12)
b) NWW(15, 20)
c) NWW(9, 14)

Pokaz przykladowe rozwiazanie 
a) NWD(8, 12) = 4
   NWW(8, 12) = 8*12/4 = 96/4 = 24

b) NWD(15, 20) = 5
   NWW(15, 20) = 15*20/5 = 300/5 = 60

c) NWD(9, 14) = 1 (wzglednie pierwsze)
   NWW(9, 14) = 9*14/1 = 126
Srednie

Zadanie 3: Upraszczanie ulamkow

Uproc nastepujace ulamki, uzywajac NWD:
a) 36/48
b) 75/100
c) 144/180
d) 91/119

Pokaz przykladowe rozwiazanie 
a) NWD(36, 48) = 12 -> 36/48 = 3/4
b) NWD(75, 100) = 25 -> 75/100 = 3/4
c) NWD(144, 180) = 36 -> 144/180 = 4/5
d) NWD(91, 119) = 7 -> 91/119 = 13/17
Trudne

Zadanie 4: Kalkulator ulamkow

Napisz program w Pythonie, ktory pobiera dwa ulamki (licznik1/mianownik1 i licznik2/mianownik2) i oblicza ich sume, roznice, iloczyn i iloraz. Wyniki powinny byc uproszczone.

Pokaz przykladowe rozwiazanie 
def nwd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def nww(a, b):
    return (a * b) // nwd(a, b)

def uproc(l, m):
    d = nwd(abs(l), abs(m))
    return l // d, m // d

def dodaj(l1, m1, l2, m2):
    wm = nww(m1, m2)
    nl = l1 * (wm // m1) + l2 * (wm // m2)
    return uproc(nl, wm)

def odejmij(l1, m1, l2, m2):
    return dodaj(l1, m1, -l2, m2)

def pomnoz(l1, m1, l2, m2):
    return uproc(l1 * l2, m1 * m2)

def podziel(l1, m1, l2, m2):
    return uproc(l1 * m2, m1 * l2)

# Przyklad: 3/4 i 5/6
l1, m1 = 3, 4
l2, m2 = 5, 6

print(f"{l1}/{m1} + {l2}/{m2} = {dodaj(l1,m1,l2,m2)}")
print(f"{l1}/{m1} - {l2}/{m2} = {odejmij(l1,m1,l2,m2)}")
print(f"{l1}/{m1} * {l2}/{m2} = {pomnoz(l1,m1,l2,m2)}")
print(f"{l1}/{m1} / {l2}/{m2} = {podziel(l1,m1,l2,m2)}")

# Wynik:
# 3/4 + 5/6 = (19, 12)
# 3/4 - 5/6 = (-1, 12)
# 3/4 * 5/6 = (5, 8)
# 3/4 / 5/6 = (9, 10)
🎥

Materialy wideo

▼
Największy wspólny dzielnik
PPEInterklasa
NWD i NWW - metody obliczania - przykłady
Matemaks
🎧

Podcasty

▼
✔️

Quiz - sprawdz sie!

▼
📜

Podstawa programowa

▼
← Lekcja 5: Badanie pierwszosci Lekcja 7: Srodowisko programistyczne →