Здравствуйте, дорогие читатели! Сегодня мы разберем, как находить НОД чисел, используя усовершенствованную версию алгоритма Евклида. На самом деле, процесс нахождения НОД будет очень простым и довольно быстрым.
В одной из своих предыдущих статей я разбирала классический алгоритм Евклида и пообещала рассмотреть его реализацию не через разность, а через деление. Это более короткий путь. Но, не знаю насколько он проще.
Вы находитесь на канале Trifler, где я ежедневно разбираю интересные математические задачи, а также рассуждаю на некоторые околоматематические темы. Если Вы искренне увлечены математикой, но еще не подписаны на этот канал, то самое время это исправить! Подписаться
Совершенствуем алгоритм Евклида
Наверное, перед тем как его улучшать, нужно вспомнить, как он звучит изначально:
Пока числа не равны друг другу, вычитай из большего меньшее. А затем заменяй большее на получившуюся разность.
Когда числа станут равными, они и будут представлять собой НОД изначальных чисел. На примере, это разобрано вот в этой статье:
Очевидно, что от разности мы можем перейти к делению. Таким образом, мы избежим лишних расчетов. Усовершенствованный алгоритм будет звучать так:
Делим большее число на меньшее. И заменяем большее число остатком от деления. Повторяем процесс для новых чисел. Процесс прекращается, когда остаток равен нулю. Наибольшим общим делителем является последний ненулевой остаток.
Формулировка получилась не самой простой. Но, сам процесс - элементарный. Рассмотрим его на том же примере, что и в предыдущей статье, чтобы сравнить эти подходы.
Пример
Двигаемся точно по алгоритму. Делим большее число на меньшее:
Теперь, заменяем большее число на остаток от деления. Получается, что теперь нужно работать с числами 2737 и 1428. Делим большее из них на меньшее. Удобно записывать так:
Получается такая лесенка. Дальше не буду подробно описывать шаги, так как смысл уже ясен. Прост продемонстрирую готовый результат:
Выделяем последний ненулевой остаток, это число и будет являться НОДом:
Получили тот же ответ, что и по классическому алгоритму. Но, предприняв меньшее число шагов.
Какой способ Вам нравится больше?
Если Вам понравилась статья, то обязательно ставьте лайки и комментируйте ее. Это поспособствует тому, чтобы ее увидело много людей!
Другие интересные статьи, опубликованные на канале: