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

Напишите функцию которая вычисляет наибольший общий делитель двух чисел

  • автор:

Наибольший общий делитель двух чисел

Author24 — интернет-сервис помощи студентам

Вычислите наибольший общий делитель чисел A и B согласно алгоритму Евклида
Задание на рекурсивный алгоритме: Вычислите наибольший общий делитель чисел A и B согласно.

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

Наибольший общий делитель прямоугольников
Будем говорить, что прямоугольник PP является делителем прямоугольника QQ, если прямоугольник QQ.

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

Найдите наибольший общий делитель двух натуральных чисел
Найдите наибольший общий делитель двух натуральных чисел. Целые числа могут быть большими, поэтому.

Эксперт Python

1355 / 652 / 207
Регистрация: 23.03.2014
Сообщений: 3,057

Лучший ответ

Сообщение было отмечено mik-a-el как решение

Решение

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
# ввод целых чисел a = int(input()) b = int(input()) # Пока какое-нибудь из двух числе не будет равно 0, while a != 0 and b != 0: # сравнивать их между собой. # Если первое число больше второго, if a > b: # то находить остаток от деления его на второе число # и присваивать его первой переменной a = a % b # Иначе (когда второе число больше первого) else: # присваивать второй переменной остаток от деления # нацело второго числа на первое b = b % a # Одно из чисел содержит 0, а другое - НОД, но какое - неизвестно. # Проще их сложить, чем писать конструкцию if-else gcd = a + b print(gcd)

Алгоритм Евклида — нахождение наибольшего общего делителя

Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел.

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

Решение задачи на языке программирования Python

Алгоритм нахождения НОД делением

  1. Большее число делим на меньшее.
  2. Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).
  3. Если есть остаток, то большее число заменяем на остаток от деления.
  4. Переходим к пункту 1.

Пример:
Найти НОД для 30 и 18.
30 / 18 = 1 (остаток 12)
18 / 12 = 1 (остаток 6)
12 / 6 = 2 (остаток 0)
Конец: НОД – это делитель 6.
НОД (30, 18) = 6

a = int(input()) b = int(input()) while a != 0 and b != 0: if a > b: a = a % b else: b = b % a print(a + b)

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

Если условием завершения цикла является равенство хотя бы одной из переменных нулю ( a == 0 or b == 0 ), то условием продолжения его работы является обратное этому условие — обе переменные должны иметь отличные от нуля значения ( a != 0 and b != 0 ).

Блок-схема алгоритма Евклида

Для того, чтобы вышеприведенная программа могла обрабатывать отрицательные числа, в логическом выражении при if должны сравниваться модули значений переменных: if abs ( a ) > abs ( b ) : . Иначе большим числом может оказаться меньшее по модулю. В этом случае интерпретатор Питона в качестве остатка от деления выдает вещественное число. В результате это приводит к зацикливанию, так как низвести переменные до нуля становится как минимум маловероятным.

Алгоритм нахождения НОД вычитанием

  1. Из большего числа вычитаем меньшее.
  2. Если получается 0, значит, числа равны друг другу и являются НОД (следует выйти из цикла).
  3. Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.
  4. Переходим к пункту 1.

Пример:
Найти НОД для 30 и 18.
30 — 18 = 12
18 — 12 = 6
12 — 6 = 6
6 — 6 = 0
Конец: НОД – это уменьшаемое или вычитаемое.
НОД (30, 18) = 6

a = int(input()) b = int(input()) while a != b: if a > b: a = a - b else: b = b - a print(a)

Функция, вычисляющая НОД

def gcd(m, n): while m != n: if m > n: m = m - n else: n = n - m return n a = int(input()) b = int(input()) print(gcd(a, b))

Функция gcd модуля math

В модуле math языка программирования Python есть функция gcd , вычисляющая наибольший общий делитель двух чисел.

>>> import math >>> math.gcd(30, 18) 6

X Скрыть Наверх

Решение задач на Python

Найти наибольший общий делитель двух чисел. Python

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

Не нужно беспокоиться о правильной формуле или о том, как её применять. Нейросеть пишет текст самостоятельно и быстро. Без лишних затрат времени и усилий ты получишь ответ, который требуется. Просто загрузи числа и нажми на кнопку «решить». Довольно просто, не правда ли?

Не откладывай на потом решение задачи, воспользуйся нейросетью онлайн и экономь своё время и нервы. Будь профессионалом в решении задач — стань пользователем нашей нейросети!

Нахождение НОД нескольких чисел на Python

Всем привет! Занимаюсь изучением языка Python. Никак не могу решить задачу с академии яндекса по нахождению НОДа нескольких чисел :(. Задача из раздела «Вложенные Циклы». Суть заключается в следующем: «В одном из местных НИИ часто требуется находить наибольший общий делитель (НОД) нескольких чисел. Вам уже доверяют, так что вновь пришли с этой задачей. Формат ввода В первой строке записано одно число NN — количество данных. В каждой из последующих NN строк записано по одному натуральному числу. Формат вывода Требуется вывести одно натуральное число — НОД всех данных чисел (кроме NN)» Но, решить надо, как я понял, без использования списков, словарей, готовых функций (типа math.gcd()) и т.д., т.к. тема вложенные циклы идет после тем: Ввод и вывод данных. Операции с числами, строками. Форматирование Условный оператор Циклы. Т.е. предполагается, что я владею только перечисленными выше темами. Даже не знаю с какой стороны подойти. Конечно, можно использовать уже готовую функцию math.gcd(), но очень хочется понять алгоритм решения. Спасибо всем откликнувшимся ☻

Отслеживать
задан 12 фев 2023 в 16:40
21 1 1 серебряный знак 3 3 бронзовых знака
12 фев 2023 в 16:41
12 фев 2023 в 16:48
@Nowhere Man Первый линк — неудачные ответы
12 фев 2023 в 16:57

но очень хочется понять алгоритм решения — Неужели он нигде не описан, и здесь на сайте нет реализаций?

12 фев 2023 в 17:07

Есть реализация только для 2х чисел, либо с использованием уже готовой функции math.gcd(). Другого я не нашел.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *