Największy wspólny dzielnik z Pythonem

Czynnik to liczba, która może przejść do innej liczby bez reszty. Dywidenda dzieli dzielnika, aby podać iloraz. Jeśli dywidenda i dzielnik są liczbą całkowitą i jeśli iloraz ma resztę zero (bez reszty), wówczas dzielnik nazywany jest czynnikiem dywidendy. Największy wspólny dzielnik jest skrócony, g.C.D lub po prostu gcd. Inną nazwą największego wspólnego dzielnika jest najwyższy wspólny czynnik, w skrócie H.C.F.

Znalezienie g.C.F z definicji

Problem polega na znalezieniu najwyższego wspólnego czynnika zwanego również największym wspólnym dzielnikiem dla liczb 108 i 240.

Rozwiązanie:

Wszystkie czynniki większe niż 1 są umieszczane w poniższej tabeli:

108: 2 3 4 6 9 12 18 27 36 54 108
240: 2 3 4 5 6 8 10 12 15 16 20 24 30 48 60 120 240

Pierwszy rząd ma czynniki 108 w kolejności rosnącej. Drugi rząd ma czynniki 240 w kolejności rosnącej.

Wspólne czynniki (dzielniki) dla 108 i 240 to: 2, 3, 4, 6 i 12.

Przejąd, największy czynnik (dzielnik), który jest wspólny dla liczb 108 i 240, to 12. To znaczy GCD lub H.C.F dla 108 i 240 to 12.

Pisanie programu, który znajdzie GCD, jak wyjaśniono powyżej, potrwa zbyt długo. Dwie krótsze metody znalezienia GCD to: GCD według odejmowania i GCD według podziału.

GCD przez odejmowanie

Przegląd z powyższej tabeli GCD dla 108 i 240 ma 12. Oznacza to, że jeśli 12 będzie dodawane wielokrotnie, wynik stanie się 108, co jest mniejsze z obu liczb. Jeśli dodanie 12 będzie kontynuowane, wynik stanie się 240, co jest większą z obu liczb. To jest:

12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 = 108
12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 = 240

To jest:

108 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 = 240

Co znaczy:

108 + 132 = 240

Jeśli GCD można wielokrotnie dodawać, aby podać dowolną liczbę (108 i 240), z której wymagany jest GCD, może być możliwe wielokrotne odejmowanie, zaczynając od podanych liczb, aby mieć GCD. W rzeczywistości możliwe jest wielokrotne wykonywanie określonego rodzaju odejmowania i zdobyć GCD. To zaczyna się od różnicy podanych liczb.

Problem: Znajdź największego wspólnego dzielnika (najwyższy wspólny czynnik) dla 108 i 240 przez odejmowanie.

Rozwiązanie:

240 - 108 = 132
132 - 108 = 24
108 - 24 = 84
84 - 24 = 60
60 - 24 = 36
36 - 24 = 12
24 - 12 = 12
12 - 12 = 0

Między 108 a 240, 240 to większa liczba. Po różnicy tych podanych liczby różnica powstałej różnicy (132 dla pierwszego kroku) i podtrenat (108 dla pierwszego kroku) są uzyskiwane wielokrotnie, aż końcowa różnica wyniesie zero. W krokach mniejsza liczba jest odejmowana od większej liczby. Na ostatnim kroku minuend i podtwórcy są takie same. Ta sama wartość jest największym wspólnym dzielnikiem.

Niech liczby, których GCD jest potrzebne, będą „a” i „b”. Jeśli liczby te nie mają GCD większe niż 1, oznacza to, że ich największym wspólnym dzielnikiem wynosi 1. W programowaniu złożoność czasu na znalezienie GCD przez odejmowanie wynosi O (A+B). Jeśli „A” to 1, a B 6, wówczas kroki bez programowania będą:

6 - 1 = 5
5 - 1 = 4
4 - 1 = 3
3 - 1 = 2
2 - 1 = 1
1 - 1 = 0

GCD tutaj jest 1. Jest tu sześć kroków, a nie siedem kroków (A + B). Jednak w programowaniu maksymalna możliwa liczba operacji kodu jest tym, co jest traktowane jako złożoność czasu.

Kodowanie GCD przez odejmowanie

Funkcją największego wspólnego dzielnika według odejmowania w Pythonie jest:

def gcds (a, b):
Jeśli A == B:
Zwrot a
Jeśli A> B:
Return GCDS (A - B, B)
w przeciwnym razie:
Return GCDS (A, B - A)

Pierwsze stwierdzenie zajmuje się ostatnim krokiem matematycznym. Następne stwierdzenie złożone (jeśli/else) odejmuje odejmowanie między minuendem a różnicą, w zależności od tego, który jest większy.

Dogłębne spojrzenie na odejmowanie matematyki GCD

240 - 108 = 132
132 = 12 x 11 (132 ma 12 jako czynnik)
132 - 108 = 24
24 = 12 x 2 (24 ma 12 jako czynnik)
108 - 24 = 84
84 = 12 x 7 (84 ma 12 jako czynnik)
84 - 24 = 60
60 = 12 x 5 (60 ma 12 jako czynnik)
60 - 24 = 36
36 = 12 x 3 (36 ma 12 jako czynnik)
24 - 12 = 12
12 = 12 x 1 (12 ma współczynnik lub 12)
24 - 12 = 12
12 = 12 x 1 (12 ma współczynnik lub 12)

Ostatni krok ma różnicę 0. Oznacza koniec kroków odejmowania i daje GCD jako podtrzymanie lub minuend.

GCD według podziału

Między 108 a 240 GCD jest większe niż 1.

12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 = 108
12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 = 240

To jest:

108 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 = 240

Co znaczy:

108 + 132 = 240

To jest:

12 x 9 + 12 x 11 = 240

Również 108 = 12 x 9 i 240 = 12 x 20.

Teraz, jeśli GCD można pomnożyć przez liczbę całkowitą (dodatnia liczba całkowita), aby podać dowolną liczbę (108 lub 240), z której wymagany jest GCD, może być możliwe wielokrotne wykonywanie podziału, zaczynając od wielokrotnego podziału, zaczynając od wielokrotnego podziału, zaczynając od Biorąc pod uwagę liczby, aby mieć GCD. W rzeczywistości możliwe jest wielokrotne wykonywanie określonego rodzaju podziału i zdobyć GCD. Ten podział jest specjalnym powtarzającym się działem modułu. Zaczyna się od podziału modułu danych liczb.

W dziale modułu, gdy dywidenda jest podzielona przez dzielnika, pozostała część ilorazu jest odpowiedzią.

Problem: Znajdź największego wspólnego dzielnika (najwyższy wspólny czynnik) dla 108 i 240 według podziału modułu:

Rozwiązanie:

240 % 108 = 24 (i.mi. 2 R 24)
108 % 24 = 12 (i.mi. 4 R 12)
24 % 12 = 0 (i.mi. 2 R 0)

Na ostatniej linii, gdzie pozostała część wynosi zero, dzielnik jest największym wspólnym dzielnikiem (najwyższy wspólny czynnik).

Ten problem polega na znalezieniu GCD między 108 a 240 według podziału. Rozwiązanie tutaj podjęło 3 kroki. Poprzedni problem był podobny, ale polegało na tym, aby poszukiwać tego samego GCD przez odejmowanie; I miał 8 kroków. Podczas gdy złożoność czasu dla metody odejmowania wynosi O (A + B), złożoność czasu dla metody podziału wynosi O (log (A + B)).

W podziale modułu nie ma znaczenia, czy „A” jest większe niż B czy B, jest większe niż „A”; Pozostała część to ta sama pozytywna liczba całkowita.

Znajdź matematycznie, największy wspólny dzielnik według podziału, dla liczb, 5 i 2.

Rozwiązanie:

5 % 2 = 1
1 % 1 = 0

GCD to 1. To wymagało dwóch matematycznych kroków.

Kodowanie GCD według podziału

Słowo „podział” odnosi się do podziału modułu. Funkcja to:

def gcdd (a, b):
if (a % b == 0):
zwrot b
w przeciwnym razie:
Zwrot GCDD (B, A % B)

Część IF if/else-construct zajmuje się ostatnim stwierdzeniem matematycznym, dla kroków podziału modułu. W przeciwnym razie część zajmuje się rzeczywistym działem modulo (w wyniku czego pozostała część). W podziale modułu nie ma znaczenia, czy „A” jest większe niż B czy B, jest większe niż „A”; Pozostała część to ta sama pozytywna liczba całkowita.

Aby zadzwonić i wydrukować GCD, można użyć następującego kodu:

RET = GCDD (240, 108)
print (ret, end = '\ n')

Dogłębne spojrzenie na podziały matematyczne GCD

240 % 108 = 24 (GCD między 240 a 108 to 12)
24 = 12 x 2 (24 ma 12 jako czynnik)
108 % 24 = 12 (GCD między 108 a 24 to 12)
12 = 12 x 1 (12 ma 12 jako czynnik)
24 % 12 = 0 (GCD między 24 a 12 to 12)

Wykazano tutaj, że:

GCD (A, B) = GCD (B, R)

gdzie „A” i B są dwiema różnymi liczbami całkowitymi, a „R” to reszta podziału między A i B. B może być większe niż „A” lub „A” może być większe niż B. Tak więc, jeśli pozostała część podziału nie jest zerowa, wówczas największy wspólny dzielnik między dwiema liczbami jest taki sam jak największy wspólny dzielnik między dzielnikiem a resztą. Spada to w różnych krokach, aż reszta wyniesie zero, nawet jeśli GCD to 1.

Ostatni krok ma resztę 0. Oznacza koniec kroków podziału modułu, a GCD jest dzielnikiem.

Wniosek

Największy wspólny dzielnik można określić za pomocą powtarzanych odejmów lub powtarzających się podziałów modulo.

Jeśli jest to odejmowanie, to po odjęciu podanych liczb, reszta odejmowania jest między różnicą a minuend, w zależności od tego, który jest większy. Gdy różnica wynosi zero, poddana jest równa minuendowi i albo jest GCD.

Jeśli jest według podziału, powtarzane podziały są dywizjami modułu. W tej sytuacji, po podziale modułu podanych liczb, reszta podziałów modułu jest między dzielą a resztą, w zależności od tego, który jest większy. Gdy reszta wynosi zero, dzielnik jest GCD. Ściśle mówiąc, w dziale modułu nie ma znaczenia, czy „A” jest większe niż B lub B, jest większe niż „A”; Pozostała część to ta sama pozytywna liczba całkowita.