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

ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Разработчику

---

Зачем отдельная статья

В введении алгоритм Евклида уже связан с ритмами и НОД. Здесь — чуть больше практики: сложность, применения в коде и соседние «карманные» алгоритмы, которые не требуют графов и сортировок.

---

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

НОД(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