Не работает алгоритм евклида

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

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

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

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

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

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

В цикле в переменную a или 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

Функция вычисления НОД

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

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

Источник

В очередной раз о НОД, алгоритме Евклида и немного об истории алгоритмов вообще. Конечно, с примерами на Swift

Алгоритмы – одна из центральных тем в программировании, они повсюду (особенно на собеседованиях, ха-ха).

(Разве можно обойтись в таком посте без «баяна»?)

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

А Дональд Кнут, небезызвестный автор трактата “Искусство программирования” (и не только), и вовсе считает алгоритм первым в истории (по крайней мере, относительно современных определений). Потому что, не смотря на то, что алгоритм был придуман и использовался еще до, собственно, Евклида, который жил в IV-III вв. до нашей эры (он упоминается уже у Аристотеля, жившего веком ранее), Евклид описывает процесс итеративно, что согласуется с современным значением слова.

Само слово “алгоритм” восходит к имени персидского математика Аль-Хорезми, жившего примерно в VIII-IX вв. уже нашей эры. А началом его использования в смысле, близком современному, считается уже лишь XX век, точнее – его первые десятилетия, восход информационных технологий.

Алгоритм Евклида

Любопытства ради предлагаю ознакомиться с евклидовским описанием алгоритма в редактуре Кнута. Оно довольно длинное, поэтому спрятано под катом:

Предложение. Для данных двух положительных целых чисел найти их наибольший общий делитель.

Пусть A и C – два заданных положительных целых числа; требуется найти их НОД. Если число A делится на C, то число C есть общий делитель чисел C и A, поскольку оно делит самое себя. И очевидно, что оно будет и наибольшим делителем, поскольку нет числа большего, чем число C, которое бы делило C.

Но если C не делит число A, то будем непрерывно вычитать меньшее из чисел A и C из большего до тех пор, пока не получим число, которое нацело делит предыдущее вычитаемое. Это должно рано или поздно произойти, потому что, если разность будет равна единице, то единица будет делить предыдущее вычитаемое.

Теперь положим, что E – положительный остаток от деления числа A на C; пусть F – положительный остаток от деления числа C на число E и пусть F делит E. Так как F делит E, а E делит C — F, F также делит C — F. Но оно делит и самое себя, поэтому F делит C, а C делит A — E; поэтому F делит также A — E, но оно делит и E; поэтому F делит A. Следовательно F является общим делителем чисел A и C.

Теперь я утверждаю, что оно является и НОД. Действительно, если F – не наибольший общий делитель чисел A и C, то найдется большее число, которое будет делить оба этих числа. Пусть таким числом будет G.

Так как число G делит число C, а число C – делит A — E, то G также делит число A — E. Число G делит также все число A, поэтому оно делит и остаток E. Но E делит C — F, поэтому G также делит C — F. А число G также делит все число C, так как оно делит и остаток F; таким образом, большее число делит меньшее, а это невозможно.

Таким образом, нет такого числа, большего, чем F, которое бы делило A и C; значит, число F является НОД.

Следствие. Это рассуждение делает очевидным предположение, что всякое число, делящее два числа, делит и их НОД. Ч.т.д.

Описание приводит два способа нахождения НОД – вычитанием и делением. Собственно, и в наши дни широко известны эти два способа реализации алгоритма.

Вот пример функции, написанной на «Swift», реализации первого способа:

Здесь, переиспользования ради, я вынес в отдельную функцию случаи поиска НОД, когда он известен сразу, без необходимости следования какому-либо алгоритму:

(Если два числа равны, то, естественно, их НОД также равен им. Если какое-то из чисел равно нулю, то НОД будет равняться второму числу, т.к. ноль делится любым числом (с результатом, понятное дело, тоже ноль).)

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

А вот так может выглядеть реализация версии алгоритма делением:

Вторая версия в наши дни считается предпочтительней, так как содержит в себе, в среднем, ощутимо меньшее количество шагов. Тем не менее, во времена, когда компьютеры были большие и медленные, операция деления могла быть сама по себе сложной процедурой. И тогда первая версия алгоритма могла оказаться эффективней.

Чтобы немного их сравнить, я произвел несколько замеров с использованием любимого мной метода measure(_:) класса XCTestCase «нативного» фреймворка для тестирования кода в Xcode-проектах XCTest .

В качестве входных данных я использовал массив пар случайных чисел. Замеры производились, естественно, с использованием одного и того же массива для каждого способа. Разброс чисел для пар я взял от нуля до 9999. Замеры производились на количестве вычислений (пар чисел): одно, десять, 100, 1000, 10000, 100000, 1000000 и 10000000. Последнее заставляло ожидать результата уже несколько минут, поэтому на нем я решил остановиться.

Вот простой код генерации входных данных:

Сам замер выглядит, например, так:

А вот так выглядят результаты запуска на моем компьютере:

(Subtraction – вычитание, division – деление.)

В общем, очень хорошо видно, как сильно на современных компьютерах проигрывает метод вычитания.

«Улучшенная» версия алгоритма Евклида

В литературе можно встретить версию алгоритма, в которой одно из чисел на каждом шаге вместо остатка от деления на второе заменяется на разность между этим отстатком и вторым числом, но только в случае, если остаток от деления больше половины второго числа. Реализация этой версии может выглядеть так:

Такая модификация сокращает количество шагов алгоритма, но, судя по результатам замеров на моем компьютере, дополнительные вычисления и проверки на каждом шаге, нейтрализуют это преимущество и даже более:

(Improved – «улучшенная» версия.)

Еще немного о значимости алгоритма Евклида

Алгоритм имеет также геометрическую версию (для нахождения наибольшей меры двух отрезков).

Алгоритм был, конечно, обощен и для нахождения НОД любого количества чисел, не только двух. В двух словах идея такова: если обозначить функцию поиска НОД двух чисел как gcd(a, b), то, скажем, НОД трех чисел gcd(a, b, c) равен gcd(gcd(a, b), c). И так далее, для любого количества чисел НОД находится последовательным вычислением НОД НОД-а предыдущей пары чисел и следующего числа. Хотя, конечно, это касается поиска НОД вообще, а не только алгоритма Евклида.

Существует также обощение алгоритма для нахождения НОД полиномов. Но это уже выходит за рамки этого несложного поста, а в некоторой степени, и моих познаний в математике.

Сложность алгоритма Евклида

Временная сложность алгоритма исследовалась давно, не быстро и гораздо более учеными мужами, чем ваш покорный слуга. Тем не менее, вопрос давно закрыт и ответ получен. Собственно, еще в середине позапрошлого века. Габриэлем Ламе.

Если коротко, то ответ формулируется, собственно, теоремой Ламе, связанной с этим алгоритмом. Количество шагов алгоритма будет равно порядковому номеру ближайшего большего числа Фибоначчи наименьшему из двух чисел входных параметров минус 2. Оперируя чуть более традиционно-математическими обозначениями, то если u > v (и v > 1), то число проходов алгоритма будет равняться n — 2 при v

Источник

Алгоритм Евклида

Вы будете перенаправлены на Автор24

Существуют разные способы поиска НОД. Одним из наиболее эффективных из них является алгоритм Евклида для вычисления наибольшего общего делителя. Рассмотрим его подробнее.

Алгоритм Евклида для нахождения НОД — это последовательное деление с остатком.

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

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

Пусть даны два числа a=$f_0$ и $b=f_1$, причём $f_0≥f_1$ и оба этих числа не равны нулю. Тогда если предположить, что $f_1$ равно нулю, то НОД этих двух чисел будет равен $f_0$. Рассмотрим теперь случай, когда $f_1$ не равно нулю. В этом случае остаток от деления $f_0$ на $f_1$ пусть будет $f_2$, тогда справедливо равенство:

$НОД(f_0, f_1)= НОД(f_1, f_2)$

Пусть $a$ будет частным от деления $f$ на $g$, тогда при любом целом $a$, числа $f_0$ и $f_1$ имеют те же общие делители, что и числа $f_1$ и $f_2=(f_0-a\cdot f_1)$.

То есть применение алгоритма Евклида для нахождения наибольшего общего делителя есть не что иное, как последовательная цепочка вычислений остатков и частных от деления.

Цепочку вычисления НОД с помощью алгоритма Евклида можно записать так:

$f_0=a_1 \cdot f_1 + f_2$;

$f_1=a_2 \cdot f_2 + f_3$;

Вычисления продолжаются до тех пор пока остаток $f_$ не станет равным нулю, тогда за НОД принимается $f_$.

Каждое последовательное вычисление нового остатка называется итерацией.

Рисунок 1. Алгоритм Евклида: блок-схема. Автор24 — интернет-биржа студенческих работ

Готовые работы на аналогичную тему

Рассмотрим пример на получение НОД через алгоритм Евклида.

Осуществите вычисление НОД с помощью алгоритма Евклида для пары $(39; 15)$

При вычислении НОД получаем последовательно пары чисел:

$НОД(3;0)$ — последняя пара является конечной, так как остаток равен нулю. Значит, наибольшим общим делителем для чисел $39$ и $15$ является число $3$.

Алгоритм Евклида: доказательство

Докажем корректность алгоритма Евклида с помощью двух этапов.

Сначала рассмотрим последний остаток $f_$, не равный нулю.

Этот остаток является делителем обоих чисел $a$ и $b$. Так как этот остаток является общим делителем, то он должен быть меньше или равен некоторому $НОД=g$.

Для того чтобы показать, что $f_$ является делителем $a$ и $b$, запишем предыдущий остаток через $f_$:

Так как последний остаток $f_=0$, то$ f_$ также должен быть делителем $f_$:

$f_=q_f_+f_$, так как он является делителем обоих слагаемых в правой части равенства.

Проведя последующие итерации, получается, что $f_$ является делителем всех предыдущих остатков, включая $a$ и $b$.

При этом ни один из предыдущих остатков не является делителем $a$ и $b$, так как деление на них происходит с остатком.

Поэтому $f_$ является общим делителем $a$ и $b$, при этом меньшим, либо равным $g$.

На втором этапе показываем, что любой общий делитель $a$ и $b$, в том числе и $g$, должен делиться на $f_$.

Возьмём любое число $c$, являющееся делителем $a$ и $b$, также оно должно быть делителем любого получающегося остатка $f_k$.

Соответственно, числа $a$ и $b$ можно представить как $a=mc$ и $b=lc$, причём $l, m$ — натуральные числа.

Получается, что $c$ является делителем $f_1$, так как $f_1=a-q_0lc=(m-q_0l)c$.

Используя аналогичные рассуждения, можно доказать, что $c$ является делителем всех остатков.

Таким образом, получается, что $НОД=g$ должен быть делителем $f_$, что значит, что $g≤f_$.

Также $g$ должен быть меньше или равен $r_$. Это и предыдущее заключение что $f_≤g$ противоречат друг другу во всех случаях, кроме $f=g$, следовательно, $g=f_$.

То есть $f_$ является НОД, полученным через алгоритм Евклида.

НОД: расширенный алгоритм Евклида

Расширенный алгоритм Евклида рассматривает НОД через линейную комбинацию этих чисел с некоторыми целыми коэффициентами.

Здесь остатки вычисляются по следующим формулам:

Источник

Алгоритм Евклида — реализация на Python

Алгоритм Евклида — это алгоритм, который используется для нахождения наибольшего делителя двух целых чисел. Он часто используется как в обучающих целях, так и в прикладных задачах.

Существует несколько видов алгоритма: обычный, расширенный и бинарный. Все виды алгоритма Евклида легко реализуются на языке программирования Python.

Классический алгоритм Евклида

Этот вид алгоритма Евклида является самым простым, он был придуман более 1300 лет назад. С появлением электронно-вычислительных машин расширились возможности по применению алгоритма Евклида, возникли новые более эффективные его реализации.

Алгоритм состоит из определенного количества шагов, количество которых зависит от размера входных данных.

Реализация на Python

Существует несколько реализаций классического алгоритма Евклида, которые основаны на использовании различных операторов и возможностей языка Python (остаток от деления, вычитание, рекурсия). Эти реализации отличаются незначительно, сильные различия в эффективности наблюдаются только при специфических входных данных.

Реализация с помощью остатка от деления

Идея такой реализации достаточна проста, алгоритм уменьшает числа до тех пор, пока одно из них не станет равно нулю, а другое искомому делителю. Для этого используется цикл while , в котором большее число делится на меньшее и становится равным остатку от деления. Таким образом, функция вернёт наибольший общий делитель (НОД) её двух аргументов.

Код алгоритма Евклида на Python:

Так как одно из чисел всегда становится равным нулю, то функция всегда будет возвращать делитель, благодаря логическому оператору или, который используется вместе с return .

В каждой новой итерации большее число становится меньшим и наоборот. Возьмём числа 168 и 105 и распишем работу программы вручную:

• 1 итерация:
  168 % 105 = 63
  105
• 2 итерация:
  63
  105 % 63 = 42
• 3 итерация:
  63 % 42 = 21
  42
• 4 итерация:
  42 % 21 = 0
  21

После 4 итерации алгоритм завершает свою работу, так как одно из чисел равно нулю, второе же число равно наибольшему общему делителю, в нашем случае это 21. Проверим работу программы:

Реализация с помощью вычитания

Идея этой реализации схожа с предыдущей, однако здесь числа уменьшаются до нуля и делителя с помощью вычитания.

Код вычисления НОД на Python:

Также распишем работу программы с числами 168 и 105:

• 1 итерация:
  168 — 105 = 63
  105
• 2 итерация:
  63
  105 — 63 = 42
• 3 итерация:
  63 — 42 = 21
  42
• 4 итерация:
  21
  42 — 21 = 21
• 5 итерация:
  21 — 21 = 0
  21

Видно, что до 4 итерации результаты работы обоих версий алгоритма полностью совпадают. Отличия начинаются, когда в 4 итерации вместо 0 и 21, получается числа 21 и 21, из-за чего в алгоритме с вычитанием добавляется дополнительная итерация, но это не значит, что он работает менее эффективнее.

Проверка работы программы:

Реализация с помощью рекурсии

Суть алгоритма схожа с реализацией через остаток от деления, однако вместо цикла while используется рекурсия.

Код программы на Python нахождения НОД с помощью рекурсии:

Первое, что стоит заметить, на ноль проверяется только num1 . Важно понять, что числа постоянно меняются местами. В качестве первого числа в рекурсивный вызов функции передаётся num2 % num1 , вспомним 4 итерацию в алгоритме через остаток от деления:

• 4 итерация:
  42 % 21 = 0 — num1
  21 — num2

То есть рекурсивный алгоритм проверит число num1 на ноль, получит True и вернёт значение num2 , которое и будет являться наибольшим общим делителем.

Особенности алгоритма: простые числа

Если два переданных числа не имеют общих делителей, то алгоритм возвращает единицу. Действительно, ведь каждое число делится на единицу. Например, числа 35 и 18 не имеют общих делителей:

• 35 = 5 * 7 * 1
• 18 = 2 * 9 * 1 = 3 * 6 * 1

Алгоритм будет возвращать единицу, если оба переданных числа являются простыми и не равны друг другу. Простые числа делятся только на себя и на единицу.

Если алгоритм получает на вход одно простое число, это не значит, что он обязательно вернет единицу:

• 5 и 15: число 5 является простым, а 15 — нет, алгоритм вернет наибольший общий делитель 5.
• 5 и 21: число 5 — простое, а 21 — нет, будет возвращена единица, потому что 21 не делится на 5.
• 3 и 21: число 3 — простое, 21 — нет, будет возвращено число 3, потому что 21 делится на 3.

Расширенный алгоритма Евклида

Расширенным алгоритм называется не из-за более высокой скорости работы или более сложной реализации, а потому что он позволяет извлекать из входных данных дополнительную информацию.

Расширенный алгоритм также находит наибольший общий делитель, а ещё он определяет два коэффициента x и y, такие что:

ax + by = gcd(a,b), где gcd – это функция по нахождения НОД.

Иными словами, алгоритм находит наибольший делитель и его линейное представление.

gcd – это аббревиатура, которую часто используют для обозначения функции по назначению НОД:

• g – Greatest (наибольший);
• c – Common (общий);
• d – Divisor (делитель).

Реализация на Python

Код программы выглядит так:

Проверяем работу кода:

Подставим полученные коэффициенты в формулу, тогда:

Действительно, коэффициенты и делитель найдены правильно. Но как работает алгоритм?

Сначала проверяется, равно ли первое число нулю, если это так, то второе число является делителем, а коэффициенты равны 0 и 1, так как «num1 * x + num2 * y = y» в том случае, если y = 1, а левое произведение равно нулю.

Функция возвращает три числа: делитель, коэффициент x и коэффициент y. Для её реализации используется рекурсия, делитель получается тем же образом, что и в классическом рекурсивным алгоритме, а коэффициенты рекурсивно вычисляются по формулам:

Бинарный алгоритм Евклида

Суть бинарного алгоритма точно такая же — найти наибольший делитель. От классического он отличается только способом реализации.

Сложность алгоритма по прежнему определяется функций O(h 2 ), однако реальные тесты показывают, что бинарный алгоритм эффективнее классического на 60%, это обусловлено различиями в реализациях обычных арифметических операций и сдвигов.

Реализация на Python

Бинарный алгоритм имеет довольно сложную реализацию по сравнению со всеми предыдущими, однако это окупается его эффективностью.

Код на Python:

Результат выполнения не будет отличаться от результатов, полученных другими реализациями.

Тест скорости выполнения

Для выполнения теста воспользуемся функцией monotonic модуля time. Подробнее про неё и про то, как засечь время выполнения программы описано здесь.

Мы будем делать проверку, используя функцию выше описанного бинарного алгоритма Евклида и описанную в самом начале функцию классического.

Код проверки следующий:

Результат теста выглядит следующим образом:

Из результатов видно, что реализация классического алгоритма на Python быстрее, чем бинарного. Так что лучше на Python использовать классический алгоритм Евклида, а если программировать на C++ и важна скорость выполнения, то тогда использовать бинарный.

Заключение

Алгоритм Евклида позволяет эффективно находить общие делители чисел. За много лет его существования было придумано несколько различных видов, которые могут отличаться по способу реализации и эффективности.

Любой вид алгоритма Евклида можно реализовать на языке Python без использования сторонних библиотек.

Источник