Печать

Алгоритм Евклида. Нахождение НОД

Алгоритм Евклида — это один из старейших численных алгоритмов для нахождения наибольшего общего делителя двух целых чисел. Алгоритм назван в честь греческого математика Евклида (III век до н. э.), который впервые его описал.

def nod(x, y):
    while (x != y):
        if x > y:
            x = x - y
        else:
            y = y - x
    return x

x = int(input('Введите первое число: '))
y = int(input('Введите второе число: '))
print('Наибольший общий делитель', nod(x, y))

Лист. 1. Функция нахождения наибольшего общего делителя двух целых чисел с вычитанием меньшего числа из большего числа.

Введите первое число: 30855
Введите второе число: 41514
Наибольший общий делитель 561

Лист. 2. Результат работы программы нахождения наибольшего общего делителя двух целых чисел.

def nod(x, y):
    while (x != y):
        x, y = abs(x - y), min(x, y)
    return x

x = int(input('Введите первое число: '))
y = int(input('Введите второе число: '))
print('Наибольший общий делитель', nod(x, y))

Лист. 3. Функция нахождения наибольшего общего делителя двух целых чисел с вычитанием меньшего числа из большего числа.

В программе листинг 2-а используются функции abs() и min() вместо операторов if и else в программе листинг 1.

def nod(x, y):
    while x != y:
        x, y = abs(x - y), x
    return x
        
while True:
    x = int(input('Введите первое число: '))
    y = int(input('Введите второе число: '))
    print('Наибольший общий делитель', nod(x, y))

Лист. 4. Функция нахождения наибольшего общего делителя двух целых чисел с вычитанием.

В программе листинг 2-б используется функции abs(), а функция min() и оператор if и else оказываются лишними. Однако, без функции min количество итераций цикла while увеличивается более чем в 1.5 раз.

def nod(x, y):
    while x != y:
        print(f'{x} - {y}')
        x, y = max(x, y) - min(x, y), min(x, y)
    return x
        
while True:
    x = int(input('Введите первое число: '))
    y = int(input('Введите второе число: '))
    print('Наибольший общий делитель', nod(x, y))

Лист. 5. Функция нахождения наибольшего общего делителя двух целых чисел с вычитанием из большего числа меньшего. Вариант, без использования функции abs.

Введите первое число: 30855
Введите второе число: 41514
30855 - 41514
10659 - 30855
20196 - 10659
9537 - 10659
1122 - 9537
8415 - 1122
7293 - 1122
6171 - 1122
5049 - 1122
3927 - 1122
2805 - 1122
1683 - 1122
561 - 1122
Наибольший общий делитель 561

Лист. 6. Результат работы программы нахождения наибольшего общего делителя двух целых чисел.

def nod(x, y):
    while (x % y !=0 and y % x !=0):
        if x > y:
            x = x % y
        else:
            y = y % x
    return min(x, y)

x = int(input('Введите первое число: '))
y = int(input('Введите второе число: '))
print('Наибольший общий делитель', nod(x, y))

Лист. 7. Функция нахождения наибольшего общего делителя двух целых чисел с нахождением остатка от деления большего числа на меньшее.

def nod(x, y):
    while (x % y !=0 and y % x !=0):
        x, y = max(x, y) % min (x, y), min(x, y)
    return min(x, y)

x = int(input('Введите первое число: '))
y = int(input('Введите второе число: '))
print('Наибольший общий делитель', nod(x, y))

Лист. 8. Функция нахождения наибольшего общего делителя двух целых чисел с нахождением остатка от деления большего числа на меньшее.

В программе листинг 8 используются функции max() и min() вместо операторов if и else в программе листинг 7.

def nod(x, y):
    if (y != 0):
        return nod(min(x, y), max(x, y) % min (x, y))
    else:
        return x

x = int(input('Введите первое число: '))
y = int(input('Введите второе число: '))
print('Наибольший общий делитель', nod(x, y))

Лист. 9. Рекурсивная функция нахождения наибольшего общего делителя двух целых чисел.

Рекурсивная функция нахождения наибольшего общего делителя двух целых чисел в программе листинг 5 написана исходя из следующих двух утверждений:

  1. Пусть Y = X⋅Q + R, тогда НОД (X, Y) = НОД (X, R), где Q целая часть, а R дробная часть от деления Y/X.
  2. НОД(R, 0) = R для любого ненулевого R (так как 0 делится на любое целое число).
def nod(x, y):
    while y != 0:
        x, y = y, x % y
    return x

x = int(input('Введите первое число: '))
y = int(input('Введите второе число: '))
print('Наибольший общий делитель', nod(x, y))

Лист. 10. Функция нахождения наибольшего общего делителя двух целых чисел без рекурсии.

Функция нахождения наибольшего общего делителя двух целых чисел без рекурсии в программе листинг 10 написана исходя из тех же двух утверждений что и программа листинг 9.

Следует заметить, что в программе листинг 10, так же как и в остальных выше приведённых программах с нахождением остатка от деления большего числа на меньшее используется нахождение остатка от деления большего числа на меньшее. Но в отличие от других приведённых выше программ, выбор большего и меньшего значения аргументов x и y в программе листинг 10 осуществляется за счёт лишней итерации цикла while, вместо использования функций min() и max(). Кроме того, эта лишняя итерация цикла while в программе листинг 10 происходит только в том случае, когда x оказывается меньше y. А это случается только один раз, когда аргументы функции следуют в порядке, с начала меньший, а затем больший.

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

def nod(x, y):
    if (y != 0):
        return nod(y, x % y)
    else:
        return x

x = int(input('Введите первое число: '))
y = int(input('Введите второе число: '))
print('Наибольший общий делитель', nod(x, y))

Лист. 11. Рекурсивная функция нахождения наибольшего общего делителя двух целых чисел.

def nod(x, y):
    return x if (y == 0) else nod(y, x % y)

x = int(input('Введите первое число: '))
y = int(input('Введите второе число: '))
print('Наибольший общий делитель', nod(x, y))

Лист. 12. Рекурсивная функция нахождения наибольшего общего делителя двух целых чисел с использованием тернарного оператора Python.

def nod(x, y): return x if (y == 0) else nod(y, x % y)

x = int(input('Введите первое число: '))
y = int(input('Введите второе число: '))
print('Наибольший общий делитель', nod(x, y))

Лист. 12-2. Рекурсивная функция нахождения наибольшего общего делителя двух целых чисел одной строкой.

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

© Диордица Александр, гор. Лыткарино, 01.08.2021.