Добрый день, уважаемые читатели. На повестке дня алгоритм Евклида и алгоритм нахождения линейного представления НОД (без использования расширенного алгоритма Евклида :) ).
Подпишись на группу Вконтакте и Телеграм-канал. Там еще больше полезного контента для программистов.
А на YouTube-канале ты найдешь обучающие видео по программированию. Подписывайся!
Алгоритм Евклида
Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел.
Наибольший общий делитель (НОД) – это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел. Проще говоря, это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД.
Алгоритм нахождения НОД делением для чисел a и b (a > b)
- Делим a на b
- Если остаток равен нулю, то b и есть НОД (следует выйти из цикла).
- Если есть остаток, то a заменяем на b, a b на остаток от деления.
- Переходим к пункту 1.
Теперь же докажем, что алгоритм Евклида всегда заканчивается.
Запрограммируем алгоритм на Python:
In[1]:
def GCD(a, b):
while (b != 0):
a, b = b, a % b
GCD(45, 12)
Out[1]:
3Линейное представление НОД
Cм. также Расширенный алгоритм Эвклида
Таким образом, для вычисления коэфициентов нам необходимо хранить
используя их для вычисления 𝑢_𝑛 и 𝑣_𝑛.
Программируем нахождение линейного представления НОД для 𝑎>0, 𝑏>0:
In[2]:
def linear_representation(a: int, b: int) -> tuple:
# Первое разложение
q = a // b; r = a - q * b
a = b; b = r
# Установка необходимых полей для вычисления континуанты
u_2 = 0
u_1 = 1
u = 1
v_2 = 1
v_1 = -q
v = -q
# Если первое разложения является конечным
if (b == 0):
return u, v + 1
# Алгоритм Евклида
while (a % b != 0):
q = a // b; r = a - q * b;
a = b; b = r
u = -q * u_1 + u_2
v = -q * v_1 + v_2
u_2 = u_1; u_1 = u
v_2 = v_1; v_1 = v
return u, v
def GCD(a, b):
while (b != 0):
a, b = b, a % b
return a
test_data = [(56, 6), (34, 24), (45, 8)]
for a, b in test_data:
u, v = linear_representation(a, b)
print(f"{u}*{a} + {v}*{b} = {GCD(a, b)}")
Out[2]:
1*56 + -9*6 = 2
5*34 + -7*24 = 2
-3*45 + 17*8 = 1 Вот и всё. Оказалось, что это достаточно просто :)
Документ с кодом, который вы можете просмотреть и изменить на своё усмотрение, находится по ссылке.
Также рекомендую прочитать статью Функциональный API библиотеки Keras. А также подписывайтесь на группу ВКонтакте, Telegram и YouTube-канал. Там еще больше полезного и интересного для программистов.
