В этом уроке представлено 30 типовых алгоритмических задач с подробными математическими обоснованиями без кода на Python.

1. Проверка числа на простоту

Математическое обоснование:

• Число простое, если имеет ровно два делителя: 1 и само себя.
• Достаточно проверять делители только до √n, так как если n = a×b, то хотя бы один из множителей ≤ √n.
• Исключаем числа < 2, отрицательные числа и чётные числа больше 2.
• Оптимизация: проверяем делимость на 2 отдельно, затем на нечётные числа.

2. Разложение числа на простые множители

Математическое обоснование:

• Основная теорема арифметики: каждое натуральное число > 1 единственным образом раскладывается на простые множители.
• Алгоритм: последовательно делим число на наименьший простой делитель, пока оно не станет равным 1.
• Достаточно проверять делители до √n, так как если после проверки всех делителей ≤ √n остаток > 1, то этот остаток — простой множитель.

3. Алгоритм Евклида для НОД

Математическое обоснование:

• Основан на свойстве: НОД(a, b) = НОД(b, a mod b).
• Доказательство: если d делит и a, и b, то d делит и их разность a - b, и наоборот.
• Алгоритм заканчивается, когда остаток становится равным 0, последний ненулевой остаток — НОД.
• Сложность: O(log min(a, b)).

4. Вычисление НОК через НОД

Математическое обоснование:

• Связь НОК и НОД: a × b = НОД(a, b) × НОК(a, b).
• Следует из канонического разложения чисел на простые множители.
• Поэтому НОК(a, b) = |a × b| / НОД(a, b).
• Для избежания переполнения лучше вычислять как: a / НОД(a, b) × b.

5. Быстрое возведение в степень

Математическое обоснование:

• Используем двоичное представление степени: xⁿ можно представить как произведение x^(2^k) для тех k, где соответствующий бит n равен 1.
• Свойство степени: x^(a+b) = x^a × x^b.
• Алгоритм: на каждом шаге возводим основание в квадрат, а если текущий бит степени = 1, умножаем результат.
• Сложность: O(log n) вместо O(n).

6. Решето Эратосфена для поиска простых чисел

Математическое обоснование:

• Принцип: вычеркиваем все числа, кратные найденным простым.
• Начинаем с 2, вычеркиваем все кратные 2, затем переходим к следующему невычеркнутому числу.
• Достаточно проверять до √n, так как любое составное число n имеет делитель ≤ √n.
• Оптимизация: начинаем вычеркивать с p², так как меньшие кратные уже вычеркнуты.

7. Числа Фибоначчи

Математическое обоснование:

• Рекуррентное соотношение: F(n) = F(n-1) + F(n-2), F(0)=0, F(1)=1.
• Золотое сечение: F(n) ≈ φⁿ/√5, где φ = (1+√5)/2.
• Для быстрого вычисления используем матричное представление или метод удвоения.
• Свойство: F(n+m) = F(n)F(m+1) + F(n-1)F(m).

8. Проверка числа на совершенность

Математическое обоснование:

• Совершенное число равно сумме своих собственных делителей.
• Теорема Евклида-Эйлера: чётное совершенное число имеет вид 2^(p-1)(2^p - 1), где 2^p - 1 — простое (простое Мерсенна).
• Для проверки: находим все делители до √n, суммируем их с соответствующими парными делителями.

9. Факториал и его вычисление

Математическое обоснование:

• n! = 1×2×3×...×n (определение).
• Рекуррентное соотношение: n! = n × (n-1)!, 0! = 1.
• Формула Стирлинга: n! ≈ √(2πn) × (n/e)^n.
• Для больших n используем алгоритмы типа Карацубы или преобразование Фурье.

10. Комбинаторные числа (биномиальные коэффициенты)

Математическое обоснование:

• C(n,k) = n!/(k!(n-k)!) (определение).
• Треугольник Паскаля: C(n,k) = C(n-1,k-1) + C(n-1,k).
• Свойство симметрии: C(n,k) = C(n,n-k).
• Для вычисления без переполнения используем рекуррентное соотношение или формулу с умножением и делением.

11. Проверка числа на палиндром

Математическое обоснование:

• Число-палиндром читается одинаково слева направо и справа налево.
• Алгоритм: переворачиваем число и сравниваем с оригиналом.
• Для переворота: последовательно берем последнюю цифру (n mod 10) и добавляем к перевернутому числу.

12. Перевод между системами счисления

Математическое обоснование:

• Основано на позиционной записи числа: число в системе с основанием b = Σ d_i × b^i.
• Из десятичной в другую: последовательное деление на основание с записью остатков.
• Из другой в десятичную: суммирование произведений цифр на степени основания.
• Для быстрого перевода между степенями двойки используем группировку бит.

13. Вычисление суммы цифр числа

Математическое обоснование:

• Используем свойство: последняя цифра числа n равна n mod 10.
• Сумма цифр: последовательно берем n mod 10, добавляем к сумме, затем n = n // 10.
• Повторяем до n = 0.
• Для больших чисел можно использовать свойства делимости на 9.

14. Проверка делимости

Математическое обоснование:

• Признаки делимости основаны на свойствах сравнений по модулю.
• Например, для делимости на 3: сумма цифр делится на 3.
• Для делимости на 4: последние две цифры делятся на 4.
• Общий метод: вычисление остатка от деления.

15. Поиск всех делителей числа

Математическое обоснование:

• Делители идут парами: если d делит n, то n/d тоже делитель.
• Достаточно искать делители до √n, затем добавлять парные.
• Для нахождения всех делителей: факторизуем число и генерируем все комбинации степеней простых множителей.

16. Функция Эйлера (количество взаимно простых чисел)

Математическое обоснование:

• φ(n) = количество чисел ≤ n, взаимно простых с n.
• Мультипликативность: если НОД(a,b)=1, то φ(ab) = φ(a)φ(b).
• Формула: φ(n) = n × Π(1 - 1/p), где произведение по всем простым p, делящим n.
• Для простого p: φ(p) = p-1.

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

Математическое обоснование:

• Находит такие x,y, что ax + by = НОД(a,b) (соотношение Безу).
• Использует ту же итерацию, что и обычный алгоритм Евклида, но сохраняет коэффициенты.
• Коэффициенты обновляются по формулам: x_new = y_old, y_new = x_old - ⌊a/b⌋×y_old.

18. Решение линейных диофантовых уравнений

Математическое обоснование:

• Уравнение ax + by = c имеет решение тогда и только тогда, когда НОД(a,b) делит c.
• Находим частное решение с помощью расширенного алгоритма Евклида.
• Общее решение: x = x₀ + (b/d)t, y = y₀ - (a/d)t, где d = НОД(a,b).

19. Проверка числа на степень двойки

Математическое обоснование:

• Число является степенью двойки, если в двоичной записи ровно одна единица.
• Математически: n > 0 и (n & (n-1)) = 0.
• Доказательство: если n = 2^k, то n-1 имеет все единицы в младших k битах.

20. Быстрое умножение по модулю (modular exponentiation)

Математическое обоснование:

• Использует тот же принцип, что и быстрое возведение в степень, но с учётом модуля.
• Свойство: (a × b) mod m = [(a mod m) × (b mod m)] mod m.
• Позволяет работать с очень большими степенями без переполнения.

21. Генерация всех перестановок

Математическое обоснование:

• Количество перестановок n элементов: n!.
• Алгоритм Хипа: генерирует перестановки с помощью минимального числа транспозиций.
• Рекурсивный метод: на каждом шаге фиксируем один элемент и генерируем перестановки оставшихся.

22. Генерация всех подмножеств

Математическое обоснование:

• Количество подмножеств n-элементного множества: 2^n.
• Битовое представление: каждое подмножество соответствует битовой маске длины n.
• Генерация всех масок от 0 до 2^n - 1 даёт все подмножества.

23. Задача о рюкзаке (0-1)

Математическое обоснование:

• Динамическое программирование: dp[i][w] = максимальная стоимость при использовании первых i предметов и весе w.
• Рекуррентное соотношение: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight_i] + value_i).
• Сложность: O(n×W), где n — количество предметов, W — максимальный вес.

24. Алгоритм Кадана (максимальная сумма подмассива)

Математическое обоснование:

• Основан на идее динамического программирования.
• Пусть dp[i] — максимальная сумма подмассива, заканчивающегося в позиции i.
• Рекуррентное соотношение: dp[i] = max(arr[i], dp[i-1] + arr[i]).
• Оптимизация по памяти: храним только предыдущее значение.

25. Задача о размене монет

Математическое обоснование:

• Динамическое программирование: dp[x] = минимальное количество монет для суммы x.
• Рекуррентное соотношение: dp[x] = min(dp[x-coin] + 1) по всем номиналам coin.
• Начинаем с dp[0] = 0, dp[>0] = ∞.

26. Поиск наибольшей возрастающей подпоследовательности (LIS)

Математическое обоснование:

• Динамическое программирование: dp[i] = длина LIS, заканчивающейся в i.
• Рекуррентное соотношение: dp[i] = 1 + max(dp[j]) для всех j < i, где arr[j] < arr[i].
• Алгоритм с бинарным поиском: O(n log n) с помощью поддержания массива возможных хвостов.

27. Расстояние Левенштейна (редакционное расстояние)

Математическое обоснование:

• Динамическое программирование: dp[i][j] = расстояние между префиксами длины i и j.
• Рекуррентное соотношение: dp[i][j] = min(
  dp[i-1][j] + 1 (удаление),
  dp[i][j-1] + 1 (вставка),
  dp[i-1][j-1] + (0 если символы равны, иначе 1) (замена)
  )

28. Задача о рюкзаке с бесконечными предметами

Математическое обоснование:

• Динамическое программирование: dp[w] = максимальная стоимость для веса w.
• Рекуррентное соотношение: dp[w] = max(dp[w], dp[w-weight_i] + value_i) для всех предметов i.
• Порядок обхода: от 0 до W, позволяя многократное использование предметов.

29. Проверка графа на двудольность

Математическое обоснование:

• Граф двудольный, если его вершины можно раскрасить в два цвета так, что смежные вершины имеют разные цвета.
• Теорема: граф двудольный тогда и только тогда, когда не содержит циклов нечётной длины.
• Алгоритм: поиск в ширину или глубину с раскраской.

30. Алгоритм Дейкстры для кратчайших путей

Математическое обоснование:

• Жадный алгоритм: на каждом шаге выбираем вершину с минимальным текущим расстоянием.
• Принцип оптимальности Беллмана: если кратчайший путь из A в C проходит через B, то его часть от A до B тоже кратчайшая.
• Корректность обеспечивается неотрицательностью весов рёбер.

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