Здравствуйте, дорогие читатели! Сегодня мы разберем элементарный способ нахождения НОД. Чаще всего, наибольший общий делитель находят с помощью разложения на простые множители. Так как этот способ самый привычный для нас, то его мы сегодня трогать не будем.
На самом деле, существуют два способа вычисления НОД с помощью алгоритма Евклида. Но, Евклид сформулировал одно единственное правило, с помощью которого находится наибольший общий делитель. Хотя, если уж совсем честно, то Евклид и вовсе этого правила не формулировал. Он просто записал его, но открыто оно было задолго до него.
Звучит это правило так:
Пока числа не равны друг другу, вычитай из большего меньшее. А затем заменяй большее на получившуюся разность.
Почему же два способа, если правило одно? А очень просто, можно пользоваться классической интерпретацией (через разность), а можно несколько усовершенствовать процесс вычисления и перейти к операции деления.
Оба способа просты и понятны. Ниже, рассмотрим первый способ, а в одной из следующих статей я разберу второй.
Классический способ нахождения НОД
В этом случае, будем двигаться точно по правилу, сформулированному выше.
Опробуем этот алгоритм, на таком примере:
Ну что ж, числа не равны друг другу. Поэтому, вычитаем из большего меньшее и заменяем:
Соответственно, теперь у нас в работе числа: 6902 и 2737. Проделываем с ними ту же самую операцию, вычитаем из большего меньшее:
Дальнейшее действие очевидно:
Не буду подробно описывать каждый дальнейший шаг, так как логика вычислений уже ясна. Приведу готовые расчеты:
Таким образом, НОД (9639, 2737)=119. Алгоритм очень простой, хотя и требует большого количества элементарных вычислений. Он очень удобен для программной реализации нахождения НОД.
Как и обещала, в дальнейшем я разберу и другую интерпретацию этого алгоритма.
Если Вам понравилась статья, то обязательно ставьте лайки и комментируйте ее. Это поспособствует тому, чтобы ее увидело много людей! А также, переходите на мой канал, подписывайтесь, и ежедневно читайте интересные статьи.
Самая интересная статья, опубликованная на этой неделе:
Quincy: робот, который обучит Ваших детей математике, английскому и рисованию