Модуль 4.5 (Алгоритм Евклида). Алгоритм Евклида позволяет найти наибольший общий делитель (НОД) для двух чисел.
Ниже представлены примеры задач с решением на тему Алгоритм Евклида.
Как расшифровывается аббревиатура НОД?
Наибольший общий делитель
Чему равен НОД чисел 23 и 17
1
Посчитайте при помощи метода, рассказанного в видео, значение НОДа чисел 345 и 555
15
Даны два натуральных числа A и B. Требуется найти их наибольший общий делитель (НОД) методом вычитания
# загружаем данные a,b=map(int,input().split()) while a!=b: # пока переменные не равны if a>b: # вычитаем a-=b # из большего else: # меньшее b-=a # результат НОД print(a)
Та же самая задача, необходимо найти НОД двух чисел, только теперь нужно модернизировать свой код при помощи нахождения остатка от деления
a, b = map(int, input().split()) # Пока оба числа не равны нулю while a != 0 and b != 0: if a > b: # Если a больше b, вычисляем остаток от деления a на b a = a % b else: # Иначе, если b больше a, вычисляем остаток от деления b на a b = b % a # После выхода из цикла a или b будет равно нулю, а другое число будет НОД. # Выводим сумму a и b, которая и будет значением НОД. print(a + b)
Как расшифровывается аббревиатура НОК?
Наименьшее общее кратное
Чему равен НОК чисел 35 и 5?
35
Чему равен НОК чисел 75 и 120?
600
Даны два натуральных числа A и B. Требуется найти их наименьшее общее кратное (НОК).
# НОК = (A * B) / НОД # A и B в первоначальном виде. a, b = map(int, input().split()) # Создоем переменную для НОК (наименшее общее кратное) z = a * b # Нахоdим НОД (наибольший общий делитель) while b > 0: a, b = b, a % b #Находим НОК print(int(z / a))