Python-программа находит наибольший общий делитель (HCF) или наибольший общий делитель (GCD)

Полное руководство по примерам Python

В этом примере вы узнаете, как найти GCD двух чисел двумя различными способами: функцией и циклом, а также алгоритмом Эвклида

Чтобы понять этот пример, вы должны знать следующееPython-программированиеТема:

• Функция Python

• Рекурсия Python

• Параметры функции Python

Наибольший общий делитель (H.C.F) или наибольший общий делитель (G.C.D) - это наибольший положительный целое число, которое может идеально делить два данных числа. Например, H.C.F(12, 14) равно 2.

Исходный код: использование цикла

# Python-программа находит H.C.F двух чисел
# Определение функции
def compute_hcf(x, y):
# Выбор меньшего числа
　　　　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("H.C.F. составляет", compute_hcf(num1, num2))

Результат вывода

H.C.F. составляет 6

Здесь два целых числа, хранящиеся в переменных num1 и num2, передаются функции compute hcf(). Функция вычисляет H.C.F. этих чисел и возвращает её.

В этой функции мы сначала определяем меньший из двух чисел, который может быть только меньше или равен наименьшему числу. Затем мы используем цикл for от 1 до этой цифры.

В каждом итерации мы проверяем, идеально ли наши числа делят два вводимых числа. Если да, мы храним этот номер как H.C.F., в конце цикла мы получаем наибольший номер, который идеально делит два числа.

Указанный метод легко понять и реализовать, но не очень эффективен. Одним из более эффективных методов поиска HCF является алгоритм Эвклида.

Алгоритм Эвклида

Этот алгоритм основан на следующем факте: HCF двух чисел также делит их разницу.

В этом алгоритме мы делим больше на меньше, затем берем остаток. Теперь делим меньше на этот остаток. Повторяем до тех пор, пока оставшееся не станет 0.

Например, если мы хотим найти hcf 54 и 24, мы делим 54 на 24. Оставшееся 6. 24 делится на 6, оставшееся 0. Таким образом, 6 является необходимым hcf

Исходный код: использование алгоритма Эвклида

# Функция поиска HCF использует алгоритм Эвклида
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 становится 0, мы получаем hcf x.

Полное руководство по примерам Python