Путь Змеи

Советы и хитрости Pythonic - поиск GCD и LCM

Как получить наибольший общий знаменатель и наименьший общий множитель с помощью Python

Для многих из нас поиск наибольшего общего знаменателя между числами был обычным делом в математике в начальной школе. Однако в реальном мире поиск НОД может составлять неотъемлемую часть наших алгоритмов и анализа. В этой статье мы рассмотрим, как получить НОД при различных сценариях.

Давайте начнем!

«Создайте функцию, которая будет принимать два целых числа в качестве входных данных и находить их наибольший общий знаменатель».

Звучит достаточно просто, давайте рассмотрим типичный алгоритм, который находит НОД двух целых чисел. Ниже представлен общий алгоритм:

def get_gcd_1(num1, num2):
    while num1 != num2: 
        if num1 > num2:
            num1 = num1 - num2
        else:
            num2 = num2 - num1
    return num1
print(get_gcd_1(25, 5))
print(get_gcd_1(5, 20))
print(get_gcd_1(30, 10))
print(get_gcd_1(1500, 75))
print(get_gcd_1(20, 35))

Это довольно простой алгоритм, который дает нам НОД. Однако есть способы лучше и эффективнее структурировать алгоритм. Для начала посмотрим, сколько итераций потребуется алгоритму, чтобы найти НОД.

def get_gcd_1(num1, num2):
    while num1 != num2: 
        if num1 > num2:
            num1 = num1 - num2
        else:
            num2 = num2 - num1
        print(num1, num2)
    return num1
print(get_gcd_1(1500, 75))

Мы видим, что алгоритм пройдет 20 итераций, прежде чем будет найден НОД. Если бы мы запускали этот алгоритм на гораздо большем наборе данных, то большое количество итераций определенно было бы проблемой.

Вместо этого давайте попробуем гораздо более простой алгоритм.

def get_gcd_2(num1, num2):
    while num2 != 0:
        num1, num2 = num2, num1 % num2
    return num1
print(get_gcd_2(25, 5))
print(get_gcd_2(5, 20))
print(get_gcd_2(30, 10))
print(get_gcd_2(1500, 75))
print(get_gcd_2(20, 35))

Вторая функция значительно чище первой. Мы также используем оператор % или модульный. По сути, он возвращает оставшееся между двумя числами. Если первое число полностью делится на второе число, тогда операция вернет 0.

print(10 % 5)
print(20 % 7)
print(100 % 99)
print(1000 % 10)
print(25 % 6)

Теперь давайте проверим, сколько итераций должна пройти наша вторая функция GCD, прежде чем она вернет GCD.

def get_gcd_2(num1, num2):
    while num2 != 0:
        num1, num2 = num2, num1 % num2
        print(num1, num2)
    return num1
print(get_gcd_2(1500, 75))

Удивительный! Мы видим, что этот алгоритм даст нам НОД всего за 2 итерации. Это намного эффективнее, чем наша первая функция. Фактически мы можем сделать еще одно улучшение нашей функции. Строка num2! = 0 на самом деле лишняя. Мы можем сократить его до просто while (num2). Наша результирующая функция будет следующей.

def get_gcd_2(num1, num2):
    while (num2):
        num1, num2 = num2, num1 % num2
        print(num1, num2)
    return num1
print(get_gcd_2(1500, 75))

Отлично, мы нашли довольно эффективный алгоритм, позволяющий искать GCD. Отсюда мы можем найти наименьший общий множитель (НОК).

«Создайте функцию, которая будет принимать два целых числа в качестве входных данных и находить их наименьший общий множитель».

Проще говоря, наименьший общий множитель - это наименьшее число, которое без остатка делится на два или более чисел. Чтобы создать функцию, которая может его искать, мы можем использовать нашу функцию GCD.

def get_lcm(num1, num2):
    return (num1*num2)/ get_gcd_2(num1,num2)
print(get_lcm(1500, 75))
print(get_lcm(117 , 33))
print(get_lcm(56, 5))

Мы видим, что функция наименьшего общего множественного числа может извлекать правильные числа. Теперь давайте обобщим наши функции, чтобы они могли работать с любым количеством чисел.

«Создайте функцию, которая будет принимать список целых чисел в качестве входных данных и находить их наибольший общий знаменатель и наименьший общий множитель».

Для этого мы должны импортировать функцию reduce из библиотеки functools.

from functools import reduce
def get_gcd_lcm(list_of_ints):
    help_func = lambda x,y : x if y == 0 else g(y, x % y)  
    gcd = reduce(lambda x,y : help_func(x,y), list_of_ints)
    lcm = reduce((lambda x, y: x * y), list_of_ints) / gcd
    return gcd, lcm
    
results = get_gcd_lcm([75,1500,25,50,100])
print(f'GCD : {results[0]} LCM : {results[1]}')

Отлично, мы смогли сгенерировать функцию, которая может принимать список и генерировать GCD и LCM.

В заключение

В этой статье мы смогли успешно создать функции для поиска НОД и НОК списка целых чисел. Оба значения очень полезны для специалистов по данным, поскольку они позволяют нам лучше понять данные, которые мы обрабатываем. Хотя эта статья была довольно общей, в будущих статьях мы рассмотрим множество способов использования этой статистики и применим их к реальным данным. На данный момент я надеюсь, что вы смогли найти эту информацию полезной для вашей текущей задачи.