Алгоритм евклида для нахождения нод 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 или 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

Блог про алгоритмы и все что с ними связано. Основной инструмент реализации — Python.

воскресенье, 3 апреля 2011 г.

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

Алгоритм Евклида (описание с Вики)

Пусть a и b — целые числа, не равные одновременно нулю, и последовательность чисел
r_2 > r_3 > r_4 > cdots >r_n" > определена тем, что каждое r_k — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть
a = bq + r₁ b = r₁q₁ + r₂ r₁ = r₂q₂ + r₃ r_{k − 2} = r_{k − 1}q_{k − 1} + r_k r_{n − 1} = r_nq_n Тогда НОД(a,b), наибольший общий делитель a и b , равен r_n , последнему ненулевому члену этой последовательности.

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

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

Конкретная реализация алгоритма:

А вот нормальная его реализация (аналог из видеолекции с применением рекурсии). Тут применена идея поочередного деления, поэтому назовем его , как не трудно догадаться, :)) метод поочередного деления.

Так же существует его реализация в не рекурсивном виде

И должен признаться, что с точки зрения производительности он предпочтительнее. Основные причины — стек рекурсиии (т.е. доп. память на хранение и доп. время на доступ к заранее сохраненным данным), об этом вы так же можете услышать из видео лекции. Там же затронули связь НОД и НОК (наименьшее общее кратное).
Вот что написано в вике на этот счет:

Наименьшее общее кратное (НОК) двух целых чисел m и n — это наименьшее натуральное число, которое делится на m и n. Обозначается НОК(m,n) или [m,n] , а в английской литературе lcm(m,n).
НОК для ненулевых чисел m, n всегда существует и связан с НОД следующим соотношением:

Таким образом поиск НОК выглядит следующим образом

Хочу обратить ваше внимание на то, что сначалы мы делим на НОД а потом умножаем, таким образом мы защищаем себя от переполнения при произведении 2-х больших цифр.

Интересное: Тот факт, что число шагов, затрачиваемых алгоритмом Евклида, растет логарифмически, связан с числами Фибоначчи:

Теорема (Ламэ, 1845 г.). Пусть n О N , и пусть a > b > 0 такие, что алгоритму Евклида для обработки а и b необходимо выполнить точно n шагов (делений с остатком), причем а — наименьшее с таким свойством. Тогда а = F _{n +2} , b = F _{n +1} , где F _k — k- ое число Фибоначчи.

Доказательство можно посмотреть, например, здесь: http://virlib.eunnet.net/books/numbers/text/10.html
С помощью этой теоремы можно оценить порядок роста алгоритма Евклида. Пусть a будет меньшим из двух аргументов процедуры. Если процесс завершается за k шагов, тогда должно выполняться a>=Fib(k), т.е. приблизительно равно f^5/sqrt(5) — золотое сечение. Следовательно, число шагов k растет как логарифм a(по основанию f)!

Теперь по-поводу тестирования. Для этого я использую стандартный python profile.
Само собой 1 запуск любого из 3-х вариантов будет производителен, посему я сделал это по 2000 раз, чтобы увидеть разницу.
Результат, полностью подтвердил теорию:

• Самым медленным оказался метод последовательной разницы 2004 function calls in 3.086 seconds
• Сильно быстрее — метод поочередного деления в рекурсивном виде 13743 function calls (2004 primitive calls) in 0.088 seconds
• Ну и победитель забега — метод поочередного деления в не рекурсивном 2004 function calls in 0.014 seconds

* — небольшое пояснение ко 2-му результату. Кто-то может не понять откуда берётся 13743 вызова ф-ии. Ответ кроется как раз в рекурсии, а именно в стеке рекурсии. Т.е. эта циферка говорит, что при вызове 2000 поисков НОД, было выполнено 13739 рекурсивных запусков.

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

Python

Pascal:

Данная статья не подлежит комментированию, поскольку её автор ещё не является полноправным участником сообщества. Вы сможете связаться с автором только после того, как он получит приглашение от кого-либо из участников сообщества. До этого момента его username будет скрыт псевдонимом.

• 25 ноября 2019 в 15:24 Быстрее ли JavaScript, чем Python?
• 3 декабря 2019 в 14:37 Python List Comprehension
• 13 декабря 2019 в 17:15 Стиллер паролей на python с отправкой на почту
• 15 декабря 2019 в 20:08 C# Entity Framework Wizard crash
• 13 января 2020 в 15:54 theHarvester and Datasploit Comparison of Python OSINT Tools

Ой, у вас баннер убежал!

Это «Песочница» — раздел, в который попадают дебютные посты пользователей, желающих стать полноправными участниками сообщества.

Если у вас есть приглашение, отправьте его автору понравившейся публикации — тогда её смогут прочитать и обсудить все остальные пользователи Хабра.

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