W tym przykładzie nauczysz się znajdować GCD dwóch liczb przy użyciu dwóch różnych metod: funkcji i pętli oraz algorytmu euklidesowego
Aby zrozumieć ten przykład, powinieneś znać następujące tematy programowania w Pythonie:
- Funkcje Pythona
- Rekursja w Pythonie
- Argumenty funkcji Pythona
Najwyższy wspólny współczynnik (HCF) lub największy wspólny dzielnik (GCD) dwóch liczb to największa dodatnia liczba całkowita, która doskonale dzieli dwie podane liczby. Na przykład HCF 12 i 14 wynosi 2.
Kod źródłowy: używanie pętli
# Python program to find H.C.F of two numbers # define a function def compute_hcf(x, y): # choose the smaller number if x> y: smaller = y else: smaller = x for i in range(1, smaller+1): if((x % i == 0) and (y % i == 0)): hcf = i return hcf num1 = 54 num2 = 24 print("The H.C.F. is", compute_hcf(num1, num2))
Wynik
HCF wynosi 6
Tutaj dwie liczby całkowite przechowywane w zmiennych num1 i num2 są przekazywane do compute_hcf()funkcji. Funkcja oblicza HCF te dwie liczby i zwraca je.
W funkcji najpierw określamy mniejszą z dwóch liczb, ponieważ HCF może być tylko mniejsza lub równa najmniejszej liczbie. Następnie używamy forpętli, aby przejść od 1 do tej liczby.
W każdej iteracji sprawdzamy, czy nasza liczba doskonale dzieli obie liczby wejściowe. Jeśli tak, przechowujemy tę liczbę jako HCF. Po zakończeniu pętli otrzymujemy największą liczbę, która doskonale dzieli obie liczby.
Powyższa metoda jest łatwa do zrozumienia i wdrożenia, ale nie jest wydajna. O wiele skuteczniejszą metodą znajdowania HCF jest algorytm Euklidesa.
Algorytm euklidesowy
Algorytm ten opiera się na fakcie, że HCF dwóch liczb również dzieli ich różnicę.
W tym algorytmie dzielimy większe przez mniejsze i bierzemy resztę. Teraz podziel mniejsze przez resztę. Powtarzaj, aż reszta będzie równa 0.
Na przykład, jeśli chcemy znaleźć HCF z 54 i 24, dzielimy 54 przez 24. Reszta to 6. Teraz dzielimy 24 przez 6, a reszta to 0. Stąd 6 to wymagane HCF
Kod źródłowy: przy użyciu algorytmu Euklidesa
# Function to find HCF the Using Euclidian algorithm def compute_hcf(x, y): while(y): x, y = y, x % y return x hcf = compute_hcf(300, 400) print("The HCF is", hcf)
Tutaj wykonujemy pętlę, aż y stanie się zerem. Instrukcja x, y = y, x % ypowoduje zamianę wartości w Pythonie. Kliknij tutaj, aby dowiedzieć się więcej o zamianie zmiennych w Pythonie.
W każdej iteracji jednocześnie umieszczamy wartość y w x, a resztę (x % y)w y. Kiedy y staje się zerem, mamy HCF w x.
