#хакнем_математика 👈 рубрика, содержащая интересный, познавательный контент по математике как для школьников, так и для взрослых 🥳
Цикл статей "Дроби"
Первая часть Вторая часть Третья часть
Четвертая часть Пятая часть Шестая часть Седьмая часть Восьмая часть
Здравствуйте, уважаемые читатели!
Предлагаю рассмотреть ещё один способ нахождения Наибольшего Общего Делителя (НОД) двух чисел, известный под названием «АЛГОРИТМ ЕВКЛИДА», использование которого в случаях многозначных чисел часто оказывается значительно рациональнее традиционного способа с разложением чисел на простые множители.
Для начала опишем последовательность шагов алгоритма.
На первом шаге необходимо провести деление бОльшего числа на мЕньшее. Если деление удалось, т.е. остаток оказался равен нулю, то меньшее число и будет Наибольшим Общим Делителем этих двух чисел. В случае ненулевого остатка необходимо продолжить выполнение алгоритма.
На втором шаге необходимо разделить мЕньшее из двух данных чисел (первый делитель) на полученный в первом делении остаток. Если при этом делении получится нулевой остаток, то НОД двух данных чисел равен остатку от деления на первом шаге или, что то же, делителю на втором шаге. В случае ненулевого остатка следует продолжить выполнение алгоритма.
На третьем шаге следует разделить предыдущий делитель (остаток от предпоследнего деления) на остаток, полученный на предыдущем шаге. В случае получения нулевого остатка НОД будет равен остатку, полученному на предыдущем шаге или, что тоже, последнему делителю. В случае получения ненулевого остатка повторять действия на этом шаге вплоть до получения нулевого остатка — в этом случае последний ненулевой остаток или, что то же, последний делитель и будет Наибольшим Общим Делителем.
Замечу, что описание Алгоритма Евклида для нахождения НОД двух натуральных чисел значительно «объёмнее» его исполнения. Найдём, например, НОД (1729; 2584) сначала с использованием традиционного метода с разложением чисел на простые множители, а затем с помощью алгоритма Евклида.
Чтобы реально оценить преимущество алгоритма Евклида, рекомендую самостоятельно проделать разложение этих чисел на простые множители и все остальные операции по нахождению НОД данных чисел этим способом.
А теперь используем алгоритм:
ОТВЕТ: НОД (1729; 2584) = 19.
В заключение отмечу, что алгоритм Евклида тем эффективнее (в сравнении с традиционным), чем больше числа, НОД которых следует найти.
Автор: #себихов_александр 71 год, много лет проработал конструктором-технологом микроэлектронных приборов и узлов в одном из НИИ г. Саратова, затем преподавателем математики и физики.
Читайте наш канал в телеграм - по этой ссылке
Другие статьи автора:
- Математический концерт
Цикл статей "Дроби"
1 статья 2 статья 3 статья 4 статья 5 статья 6 статья
7 статья 8 статья 9 статья [Текущая]