Najwiekszy wspolny dzielnik, najmniejsza wspolna wielokrotnosc, zastosowania
ð Podstawa programowa: I.2aNWD(a, b) to najwieksza liczba naturalna, przez ktora dziela sie zarowno a, jak i b.
Przyklad: NWD(12, 18) = 6, bo dzielniki 12 to {1,2,3,4,6,12}, dzielniki 18 to {1,2,3,6,9,18}, wspolne: {1,2,3,6}, najwiekszy: 6.
Najstarszy znany algorytm (ok. 300 p.n.e.)! Opiera sie na fakcie, ze NWD(a,b) = NWD(a-b, b) dla a > b.
ALGORYTM NWD_Odejmowanie(a, b):
1. DOPOKI a != b:
a. JESLI a > b: a = a - b
b. W PRZECIWNYM RAZIE: b = b - a
2. ZWROC a (lub b, sa rowne)
Przyklad: NWD(48, 18)
48 != 18: 48 > 18, wiec a = 48 - 18 = 30
30 != 18: 30 > 18, wiec a = 30 - 18 = 12
12 != 18: 12 < 18, wiec b = 18 - 12 = 6
12 != 6: 12 > 6, wiec a = 12 - 6 = 6
6 = 6: KONIEC
NWD(48, 18) = 6Szybsza wersja: NWD(a, b) = NWD(b, a MOD b). Konczymy, gdy b = 0.
ALGORYTM NWD_Modulo(a, b):
1. DOPOKI b != 0:
a. r = a MOD b
b. a = b
c. b = r
2. ZWROC a
Przyklad: NWD(48, 18)
a=48, b=18: r = 48 MOD 18 = 12, a=18, b=12
a=18, b=12: r = 18 MOD 12 = 6, a=12, b=6
a=12, b=6: r = 12 MOD 6 = 0, a=6, b=0
b=0: KONIEC
NWD(48, 18) = 6NWW(a, b) to najmniejsza liczba naturalna, ktora jest wielokrotnoscia zarowno a, jak i b.
Zwiazek z NWD:
NWW(a, b) = (a * b) / NWD(a, b)
Przyklad: NWW(12, 18)
NWD(12, 18) = 6
NWW(12, 18) = (12 * 18) / 6 = 216 / 6 = 36
Sprawdzenie: 36/12=3 (OK), 36/18=2 (OK)Aby skrocic ulamek a/b, dzielimy licznik i mianownik przez NWD(a, b):
Przyklad: Skroc ulamek 48/18
NWD(48, 18) = 6
48/6 = 8, 18/6 = 3
48/18 = 8/3Aby dodac ulamki o roznych mianownikach, szukamy NWW mianownikow:
Przyklad: 5/12 + 7/18
NWW(12, 18) = 36
5/12 = 15/36 (mnozmy przez 3)
7/18 = 14/36 (mnozmy przez 2)
15/36 + 14/36 = 29/36Oblicz NWD wersja z reszta z dzielenia (MOD). Zapisz kazdy krok:
a) NWD(56, 42)
b) NWD(120, 45)
c) NWD(91, 28)
a) NWD(56, 42):
a=56, b=42: r=56%42=14, a=42, b=14
a=42, b=14: r=42%14=0, a=14, b=0
NWD(56, 42) = 14
b) NWD(120, 45):
a=120, b=45: r=120%45=30, a=45, b=30
a=45, b=30: r=45%30=15, a=30, b=15
a=30, b=15: r=30%15=0, a=15, b=0
NWD(120, 45) = 15
c) NWD(91, 28):
a=91, b=28: r=91%28=7, a=28, b=7
a=28, b=7: r=28%7=0, a=7, b=0
NWD(91, 28) = 7Oblicz NWW, korzystajac ze wzoru NWW(a,b) = a*b/NWD(a,b):
a) NWW(8, 12)
b) NWW(15, 20)
c) NWW(7, 13)
a) NWW(8, 12):
NWD(8,12): 12%8=4, 8%4=0 -> NWD=4
NWW = 8*12/4 = 96/4 = 24
b) NWW(15, 20):
NWD(15,20): 20%15=5, 15%5=0 -> NWD=5
NWW = 15*20/5 = 300/5 = 60
c) NWW(7, 13):
NWD(7,13): 13%7=6, 7%6=1, 6%1=0 -> NWD=1
NWW = 7*13/1 = 91
(7 i 13 sa wzglednie pierwsze)a) Skroc ulamki: 36/48, 75/100, 84/126
b) Dodaj ulamki: 3/8 + 5/12
c) Dodaj ulamki: 7/15 + 11/20
a) Skracanie:
36/48: NWD(36,48)=12, 36/12=3, 48/12=4 => 3/4
75/100: NWD(75,100)=25, 75/25=3, 100/25=4 => 3/4
84/126: NWD(84,126): 126%84=42, 84%42=0 -> NWD=42
84/42=2, 126/42=3 => 2/3
b) 3/8 + 5/12:
NWW(8,12) = 8*12/NWD(8,12) = 96/4 = 24
3/8 = 9/24, 5/12 = 10/24
9/24 + 10/24 = 19/24
c) 7/15 + 11/20:
NWW(15,20) = 15*20/NWD(15,20) = 300/5 = 60
7/15 = 28/60, 11/20 = 33/60
28/60 + 33/60 = 61/60 = 1 i 1/60Dla pary NWD(252, 105):
a) Oblicz algorytmem z odejmowaniem - ile krokow?
b) Oblicz algorytmem z MOD - ile krokow?
c) Jaki jest stosunek liczby krokow?
a) Wersja z odejmowaniem:
252-105=147, 147-105=42, 105-42=63, 63-42=21,
42-21=21, 21=21 -> NWD=21
Liczba krokow: 5
b) Wersja z MOD:
a=252, b=105: r=252%105=42, a=105, b=42
a=105, b=42: r=105%42=21, a=42, b=21
a=42, b=21: r=42%21=0, a=21, b=0
NWD = 21
Liczba krokow: 3
c) Stosunek: 5/3 ≈ 1.67
Wersja z MOD wykonala o 40% mniej krokow.
Dla wiekszych liczb roznica bylaby jeszcze wieksza.