Алгоритм Евклида: различия между версиями
(Написала про НОК, НОД, начала сам алгоритм) |
м |
||
Строка 52: | Строка 52: | ||
===Обычный алгоритм Евклида=== | ===Обычный алгоритм Евклида=== | ||
− | Легко проверить, что $(a, b) = (a - b, b), \ a \ge b$. Отсюда будет следовать, что $(a, b) = (a % b, b)$, где $a % b$ означает взятие остатка от деления $a$ на $b$. | + | Легко проверить, что $(a, b) = (a - b, b), \ a \ge b$. Отсюда будет следовать, что $(a, b) = (a % b, b)$, где $a % b$ означает взятие остатка от деления $a$ на $b$. Это верно, так как взятие остатка это то же самое, что многократное вычитание из $a$ $b$, пока результат не станет меньше $b$. |
+ | |||
+ | Алгоритм Евклида заключается в том, чтобы подаваемые на вход числа, пока одно из них не станет равно нулю. Заметим, что $(0, x) = x, \ \ x \neq 0$. В данном случае ответ очевиден. Для уменьшения чисел используется приведенное выше соотношение. | ||
+ | |||
+ | Алгоритм будет выглядеть так: | ||
+ | |||
+ | <syntaxhighlight lang="C++" line=true> | ||
+ | int gcd(int a, int b) { | ||
+ | while (b != 0) { | ||
+ | int c = a % b; | ||
+ | a = b; | ||
+ | b = c; | ||
+ | } | ||
+ | return a; | ||
+ | } | ||
+ | </syntaxhighlight>> | ||
===Расширенный алгоритм Евклида=== | ===Расширенный алгоритм Евклида=== | ||
+ | От алгоритма Евклида можно получить больше, чемм просто нахождение НОД. <em>Расширенный алгоритм Евклида</em> позволяет найти такие два числа $x, \ y$, что $ax + by = (a, b)$. | ||
+ | |||
+ | Почему такое представление НОДа в виде линейной комбинации $a$ и $b$ возможно? Это будет следовать непосредственно из приведенного ниже алгоритма. | ||
+ | |||
+ | Для ясности будем работать с рекурсивной реализацией алгоритма Евклида. Пусть функция <tt>gcd(a, b)</tt> возвращает три числа - найденный НОД и два коэффициента $x, \ y$. Если $b = 0$, то линейная комбинация определяется легко: | ||
+ | $$(a, b) = (a, 0) = a = 1\cdot a + 0 \cdot b$$ | ||
+ | из <tt>gcd(a,b)</tt> | ||
+ | |||
{{Автор|Полина Романченко|Romanchenko}} | {{Автор|Полина Романченко|Romanchenko}} | ||
[[Категория:Конспект]] | [[Категория:Конспект]] | ||
[[Категория:Теория чисел]] | [[Категория:Теория чисел]] |
Версия 12:38, 3 сентября 2019
Содержание
Алгоритм Евклида
НОК и НОД
Теория
Определение:
Наибольший общий делитель(GCD, НОД) набора чисел $a_n$ —это максимальное число $x$ такое, что на него делятся все $a_i$.
Определение:
Наименьшее общее кратное(LCM, НОК) набора чисел $a_n$ —это минимальное число $x$ такое, что оно делит все $a_i$.
Примеры:
- $НОД(18, 30) = 6$
- $НОД(60, 180, 315) = 15$
- $НОД(1, N) = 1$
- $НОК(12, 30) = 6$
- $НОК(1, 2, 3, 4) = 12$
- $НОК(1, N) = N$
Для краткости обыкновенно используют следующие обозначения: $$(a,b) = НОД(a, b) \ \ \ [a, b] = НОК(a, b)$$
Утверждение:
$[a,b] = \frac{ab}{(a,b)}$
Доказательство:
рассмотрим мультимножество простых делителей чисел $a$ и $b$. То есть если число делится на $5^2$, то пятерка войдет дважды в это множество. Осталось понять, что НОД - пересечение этих двух мультимножеств, а НОК - объединение. Чтобы получить объединение мы берем элементы из обоих мультимножеств (умножаем $a$ на $b$), а потом убираем из этого множества пересечение исходных (делим на НОД)
Задача-пример 1
Есть $n$ шестеренок, каждая $i$-ая зацеплена с $(i-1)$-ой. $i$-ая шестеренка имеет $a_i$ зубчиков. Сколько раз нужно повернуть полностью первую шестеренку, чтобы все остальные шестеренки тоже вернулись на изначальное место?
Решение: Когда одна шестеренка крутится на 1 зубчик, все остальные тоже крутятся на один зубчик. Нужно найти минимальное такое число зубчиков $x$, что при повороте на него все шестеренки вернутся в изначальное положение, то есть $x$ делится на все $a_i$, то есть это $[a_1, a_2, \ldots, a_n]$. Ответом будет $\frac{x}{a_1}$.
Задача-пример 2
Город — это прямоугольник $n$ на $m$, разделенный на квадраты единичного размера. Вертолет летит из нижнего левого угла в верхний правый по прямой. Вертолет будит людей в квартале, когда он пролетает строго над его внутренностью (границы не считаются). Сколько кварталов разбудит вертолёт?
Решение: Вертолет пересечет по вертикали $(m-1)$ границу. С этим ничего не поделать — каждое пересечение считается как новое посещение какого-то квартала. По горизонтали то же самое — $(n-1)$ переход в новую ячейку будет сделан.
Однако еще есть случай, когда он пересекает одновременно обе границы (то есть пролетает над каким-нибудь углом) — ровно тот случай, когда нового посещения квартала не происходит. Сколько таких будет? Ровно столько, сколько есть целых решений уравнения: $$\dfrac{n}{m} = \dfrac{x}{y}$$ Мы как бы составили уравнение движения вертолёта и ищем, в скольки целых точках оно выполняется.
Пусть $t = (n, m)$, тогда $n = at, m = bt \ \Rightarrow \ \dfrac{n}{m} = \dfrac{a}{b} = \dfrac{x}{y}$.
Любая дробь с натуральными числителем и знаменателем имеет ровно одно представление в виде несократимой дроби, так что $x$ должно делиться на $a$, а $y$ должно делиться на $b$. А значит, как ответ подходят пары: $$(a, b), (2a, 2b), (3a, 3b), \cdots, ((t-1)a, (t-1)b)$$ Таких ответов ровно $t - 1 = (n, m) - 1$ Значит, итоговый ответ: $(n-1) + (m-1) - (t-1)$.
Обычный алгоритм Евклида
Легко проверить, что $(a, b) = (a - b, b), \ a \ge b$. Отсюда будет следовать, что $(a, b) = (a % b, b)$, где $a % b$ означает взятие остатка от деления $a$ на $b$. Это верно, так как взятие остатка это то же самое, что многократное вычитание из $a$ $b$, пока результат не станет меньше $b$.
Алгоритм Евклида заключается в том, чтобы подаваемые на вход числа, пока одно из них не станет равно нулю. Заметим, что $(0, x) = x, \ \ x \neq 0$. В данном случае ответ очевиден. Для уменьшения чисел используется приведенное выше соотношение.
Алгоритм будет выглядеть так:
1 int gcd(int a, int b) {
2 while (b != 0) {
3 int c = a % b;
4 a = b;
5 b = c;
6 }
7 return a;
8 }
>
Расширенный алгоритм Евклида
От алгоритма Евклида можно получить больше, чемм просто нахождение НОД. Расширенный алгоритм Евклида позволяет найти такие два числа $x, \ y$, что $ax + by = (a, b)$.
Почему такое представление НОДа в виде линейной комбинации $a$ и $b$ возможно? Это будет следовать непосредственно из приведенного ниже алгоритма.
Для ясности будем работать с рекурсивной реализацией алгоритма Евклида. Пусть функция gcd(a, b) возвращает три числа - найденный НОД и два коэффициента $x, \ y$. Если $b = 0$, то линейная комбинация определяется легко: $$(a, b) = (a, 0) = a = 1\cdot a + 0 \cdot b$$ из gcd(a,b)
Автор конспекта: Полина Романченко
По всем вопросам пишите в telegram @Romanchenko