Lekcja 30,31,32
Embedded Files
Cele lekcji:
Przypomnisz sobie pojęcia: Największy wspólny dzielnik, najmniejsza wspólna wielokrotność oraz algorytm Euklidesa.
Poznasz przykład zastosowania algorytmu Euklidesa do wykonania na ułamkach zwykłych.
Nauczysz się stosować funkcje języka Python, które nie zwracają wartości.
Algorytm Euklidesa (Największy Wspólny Dzielnik)
Algorytm Euklidesa jest również ważną koncepcją nauczaną na kursach matematyki i zajmuje się najwyższym wspólnym podzielnikiem. Nazywany także największym wspólnym dzielnikiem, NWD jest największym wspólnym dzielnikiem między dwiema liczbami całkowitymi. Podobnie jak podział euklidesowy, jest również uważany za część prostej arytmetyki. Aby znaleźć NWD, konieczne jest sporządzenie listy wszystkich dzielników, które posiadają dwie liczby. Na przykład weźmy 10 i 26:
10: 1,2,5,10
26: 1, 2, 4, 9, 13
W tym przypadku największym wspólnym dzielnikiem byłaby liczba 2. Aby uniknąć konieczności sporządzania listy wszystkich możliwych dzielników dla każdej liczby, algorytm euklidesowy składa się z szeregu podziałów euklidesowych.
Stosując tę koncepcję, wystarczy po prostu podzielić największą liczbę przez najmniejszą i przystąpić do dzielenia, aż reszta będzie równa 0. Algorytm euklidesowy jest wyjaśniony w siódmej księdze „Elementów”.
Euklides najpierw przedstawia swoje badania w formie problemu geometrycznego. Następnie szuka jednostki miary dla dwóch segmentów. Aby to zrobić, postanawia odjąć najmniejszy segment od największego i kontynuować, aż znajdzie idealną miarę. Ta metoda jest teraz podstawą wszystkich podziałów i przyczyną bólu głowy w szkole podstawowej!
Algorytm naiwny obliczający NWD (matoda naiwna)
Algorytm naiwny obliczający NWD (matoda naiwna)
# algorytm siłowy (naiwny) sprawszający wszystkie możliwe dzielniki zaczynając od największego możliwego
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
print("Mariusz B. Lekcja 30")
print("Program obliczający największy wspólny dzielnik 2 liczb")
print("------------------------------")
a = int(input("Podaj pierwszą liczbę: "))
b = int(input("Podaj drugą liczbę: "))
print('NWD(' + str(a) + ',' + str(b) + ') = ', NWD(a, b))
input("Koniec programu naciśnij Enter")
Ćwiczenia - lekcja30:
Wykonaj minimum 2 zadania z * ze strony 242
Lekcja 31 [238-..]
Lekcja 31 [238-..]
Algorytm naiwny wyznaczania NWD:
(sprawdzanie wszystkich wariantów dzielnika zaczynając od liczby mniejszej) ćwiczenie 2
Wykorzystanie algorytmu Euklidesa (wersja z odejmowaniem) do wyznaczania NWD:
Kod źródłowy funkcji realizującej algorytm Euklidesa (wersja z odejmowaniem) ćwiczenie 4
def NWD(a, b):
while a != b:
if a > b:
a = a - b
else:
b = b - a
return a
Ćwiczenie 2 [str. 233]
Zapisz kod źródłowy programu L31-p1.py i uruchom program dla różnych par wpisanych z klawiatury.
Sprawdź działanie instrukcji z wiersza 11 wpisując wynik bez zastosowania funkcji str(), np:
print("NWD(", a, ",", b, ") =", NWD(a, b))
Jaka różnicę dostrzegasz?
Ćwiczenie 4 [str. 235]
Uruchom program z Ćwiczenia 2 i porównaj czas jego działania dla 2 par liczb: 112 i 88 oraz 1234567899 i 12345678999 Co zauważasz jak można to wytłumaczyć?
Zadania na poszczególne oceny (L30,31,32) zadania * [str. 242-243] (zdobądź gwiazdki):
dopuszczający 4*
dostateczny 6*
dobry 9*
bardzo dobry 12*
celujący 15*
film 1 Rozkład liczby na czynniki pierwsze, NWD i NWW [9:01]
film 2 NWD metoda dzielenia z resztą (Algorytm Euklidesa) [3:52]
film 3 Rozkład liczby na czynniki pierwsze NWD NWW [13:19]
film 4 NWP metoda z odejmowaniem (Algorytm Euklidesa) [7:14]
Page updated
Report abuse