В этом примере вы научитесь находить НОД двух чисел, используя два разных метода: функции и циклы и алгоритм Евклида.
Чтобы понять этот пример, вы должны знать следующие темы программирования 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))
Вывод
ХКФ - 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.
