У овом примеру ћете научити да пронађете ГЦД два броја користећи две различите методе: функцију и петље и, Еуклидов алгоритам
Да бисте разумели овај пример, требало би да имате знање о следећим Питхон програмским темама:
- Питхон функције
- Питхон Рецурсион
- Аргументи функције Питхон
Највећи заједнички фактор (ХЦФ) или највећи заједнички делитељ (ГЦД) два броја је највећи позитивни цели број који савршено дели два дата броја. На пример, ХЦФ од 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))
Оутпут
ХЦФ је 6
Овде се две целобројне вредности смештене у променљиве нум1 и нум2 преносе compute_hcf()функцији. Функција израчунава ХЦФ ова два броја и враћа их.
У функцији прво одредимо мањи од два броја, јер ХЦФ може бити мањи или једнак најмањем броју. Затим користимо forпетљу за прелазак са 1 на тај број.
У свакој итерацији проверавамо да ли наш број савршено дели оба улазна броја. Ако је то случај, чувамо број као ХЦФ. По завршетку петље на крају имамо највећи број који савршено дели оба броја.
Горе наведени метод је једноставан за разумевање и примену, али није ефикасан. Много ефикаснији метод за проналажење ХЦФ-а је Еуклидов алгоритам.
Еуклидов алгоритам
Овај алгоритам заснован је на чињеници да ХЦФ два броја дели и њихову разлику.
У овом алгоритму делимо веће са мањима и узимамо остатак. Сада, поделите мање са овим остатком. Понављајте док остатак не постане 0.
На пример, ако желимо да пронађемо ХЦФ од 54 и 24, делимо 54 са 24. Остатак је 6. Сада, делимо 24 са 6, а остатак је 0. Дакле, 6 је потребан ХЦФ
Изворни код: Коришћење Еуклидовог алгоритма
# 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)
Овде петљамо док и не постане нула. Изјава x, y = y, x % yврши замену вредности у Питхону. Кликните овде да бисте сазнали више о замени променљивих у Питхону.
У свакој итерацији (x % y)истовремено постављамо вредност и у к, а остатак у и. Када и постане нула, имамо ХЦФ у к.
