В този пример ще се научите да намирате GCD на две числа, използвайки два различни метода: функция и цикли и, евклидов алгоритъм
За да разберете този пример, трябва да имате познанията по следните теми за програмиране на Python:
- Функции на Python
- Python рекурсия
- Аргументи на функцията на Python
Най-високият общ коефициент (HCF) или най-големият общ делител (GCD) на две числа е най-голямото положително цяло число, което перфектно разделя двете дадени числа. Например, HCF от 12 и 14 е 2.
Изходен код: Използване на цикли
# 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))
Изход
HCF е 6
Тук на compute_hcf()функцията се предават две цели числа, съхранени в променливи num1 и num2 . Функцията изчислява HCF тези две числа и го връща.
Във функцията първо определяме по-малкото от двете числа, тъй като HCF може да бъде само по-малко или равно на най-малкото число. След това използваме forцикъл, за да преминем от 1 към това число.
Във всяка итерация проверяваме дали нашият номер разделя перфектно двете входни числа. Ако е така, съхраняваме числото като HCF. При завършване на цикъла се оказваме с най-голямото число, което перфектно разделя двете числа.
Горният метод е лесен за разбиране и прилагане, но не е ефективен. Много по-ефективен метод за намиране на HCF е евклидовият алгоритъм.
Евклидов алгоритъм
Този алгоритъм се основава на факта, че HCF от две числа също разделя тяхната разлика.
В този алгоритъм разделяме по-големия на по-малък и вземаме остатъка. Сега разделете по-малкото на този остатък. Повторете, докато остатъкът остане 0.
Например, ако искаме да намерим HCF от 54 и 24, ние разделяме 54 на 24. Остатъкът е 6. Сега, ние разделяме 24 на 6 и остатъкът е 0. Следователно, 6 е необходимата HCF
Изходен код: Използване на евклидовия алгоритъм
# 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)
Тук се привличаме, докато y стане нула. Операторът x, y = y, x % yправи размяна на стойности в Python. Щракнете тук, за да научите повече за размяната на променливи в Python.
Във всяка итерация поставяме стойността на y в x и остатъка (x % y)в y едновременно. Когато y стане нула, имаме HCF в x.
