Евклид и классические алгоритмы на числах
Зачем отдельная статья
В введении алгоритм Евклида уже связан с ритмами и НОД. Здесь — чуть больше практики — сложность, применения в коде и соседние "карманные" алгоритмы, которые не требуют графов и сортировок.
Алгоритм Евклида
НОД(a, b) — наибольшее число, делящее оба аргумента без остатка.
АЛГОРИТМ НОД(a, b)
пока b ≠ 0
(a, b) := (b, остаток a от деления на b)
конец пока
вернуть |a|
КОНЕЦ
| Свойство | Значение |
|---|---|
| Время | O(log min(a, b)) — число шагов ограничено логарифмом меньшего аргумента |
| Память | O(1) в итеративной версии |
| История | "Начала" Евклида, ~300 г. до н. э. |
Расширенный алгоритм Евклида дополнительно находит коэффициенты x, y в тождестве Безу: a·x + b·y = НОД(a, b). Это нужно в криптографии (обратимые элементы по модулю).
Где применяется
- Сокращение дробей
p/q— делить числитель и знаменатель наНОД(p, q). - Периодичность событий с циклами разной длины — НОК через
НОК(a,b) = |a·b| / НОД(a,b). - Криптография (RSA и др.) — см. информационная безопасность.
Жадный выбор на каждом шаге
Евклид жадный — на каждом шаге заменяет пару на "меньшую" пару (b, a mod b), не откатываясь назад. Для НОД это даёт оптимум.
Жадный алгоритм в общем случае берёт локально лучший шаг. Локальный оптимум не всегда глобальный — контрпример задача коммивояжёра в тренировке мышления. Для кратчайших путей с неотрицательными весами жадность работает в алгоритме Дейкстры.
Другие классические приёмы
| Алгоритм | Задача | Сложность |
|---|---|---|
| Двоичное возведение в степень | aⁿ mod m для больших n | O(log n) умножений |
| Решето Эратосфена | Все простые до N | O(N log log N) |
| Проверка простоты (наивная) | Делители до √n | O(√n) |
Эти алгоритмы часто встречаются в олимпиадной и прикладной математике; в промышленном коде чаще вызывают готовые библиотеки, но понимание шагов помогает отлаживать граничные случаи.
Связь с музыкой и ритмом
Равномерное размещение ударов между паузами — та же схема "вычитания остатка", что и НОД. Один алгоритмический каркас объединяет:
- древнегреческую теорию чисел;
- африканские и балканские ритмы;
- современный анализ данных, где периодичность ищут через делимость длин циклов.
Подробнее контекст — в статье "Алгоритмы" (раздел про алгоритм Евклида).
Связанные материалы
- Нотация Большое O
- Графы — когда задача уже не про одно число, а про сеть
- Базовая информатика, глава 4
- Алгоритмы на Python — ЕГЭ и олимпиадка —
math.gcd, решето Эратосфена, быстрая степень по модулю - Big-O — шпаргалка — почему наивный Фибоначчи O(2ⁿ), а с циклом — O(n)
- Pascal / Free Pascal — типовые программы — НОД, решето, быстрая степень (
mod,int64)