Задачи на алгоритмы с решениями и разбором

Задачи на алгоритмы — это учебные задачи, где нужно не просто получить ответ, а выбрать способ вычисления и оценить, сколько шагов и памяти он потребует. Именно алгоритм, а не язык, отличает решение за секунду от решения, которое не дождаться. Ниже — разбор типовых задач по темам: поиск, сортировка, строки, динамическое программирование и графы.

Каждая задача идет по одной схеме: условие, идея решения, готовый код и оценка сложности O(). Код на Python — полные фрагменты, их можно скопировать и запустить, вывод указан в комментарии рядом. В конце разберем типичную ошибку, из-за которой рабочий на вид код возвращает неверный ответ.

Как подходить к алгоритмической задаче

Перед тем как писать код, полезно пройти четыре шага: понять условие, придумать идею (какая структура данных и какой прием подходят), прикинуть сложность и только потом кодировать. Сложность записывают через O-нотацию: она описывает, как растет число операций при увеличении размера входных данных n.

Ориентиры для оценки: O(1) — число шагов не зависит от n; O(log n) — на каждом шаге отбрасываем половину данных (бинарный поиск); O(n) — один проход по данным; O(n log n) — хорошие сортировки; O(n^2) — вложенный перебор пар; O(2^n) — полный перебор, применим лишь на малых n. Меньшая сложность важна на больших данных: при n = 1 000 000 разница между O(n) и O(n^2) — это секунда против недели.

Поиск: бинарный поиск в отсортированном массиве

Условие: в отсортированном по возрастанию массиве найти индекс числа. Вернуть -1, если числа нет.

Идея: сравниваем цель со средним элементом. Если цель меньше — ищем в левой половине, если больше — в правой. Каждый шаг вдвое сокращает область поиска, поэтому массив обязан быть отсортирован.

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1     # цель правее середины
        else:
            hi = mid - 1     # цель левее середины
    return -1

nums = [1, 3, 5, 7, 9, 11]
print(binary_search(nums, 7))   # 3
print(binary_search(nums, 8))   # -1

Вывод:

3
-1

Сложность — O(log n): область поиска уменьшается вдвое на каждой итерации. Для сравнения, простой перебор по массиву дал бы O(n). Если массив не отсортирован, бинарный поиск неприменим — сначала пришлось бы отсортировать.

Сортировка: сортировка вставками

Условие: отсортировать массив по возрастанию своими руками, без встроенной sorted.

Идея: идем слева направо и каждый новый элемент вставляем на нужное место среди уже отсортированных слева. Полезно проговорить проходы на массиве [5, 2, 4, 1, 3] до кода:

• берем 2, вставляем перед 5: [2, 5, 4, 1, 3]
• берем 4, между 2 и 5: [2, 4, 5, 1, 3]
• берем 1, в начало: [1, 2, 4, 5, 3]
• берем 3, между 2 и 4: [1, 2, 3, 4, 5]

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:  # сдвигаем большие вправо
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key                # ставим key на освободившееся место
    return arr

print(insertion_sort([5, 2, 4, 1, 3]))  # [1, 2, 3, 4, 5]

Вывод:

[1, 2, 3, 4, 5]

Сложность — O(n^2) в среднем и худшем случае (для почти обратного порядка сдвигов много), но O(n) на уже отсортированном массиве: внутренний цикл сразу завершается. Сортировка вставками — учебный прием; в реальном коде берут встроенную sorted, у нее сложность O(n log n).

Строки: палиндром и анаграмма

Условие 1: проверить, читается ли строка одинаково слева направо и справа налево (палиндром).

Идея: сравнить строку с ее разворотом. В Python разворот дает срез s[::-1].

def is_palindrome(s):
    s = s.lower()
    return s == s[::-1]

print(is_palindrome("radar"))   # True
print(is_palindrome("python"))  # False

Вывод:

True
False

Сложность — O(n): разворот и сравнение проходят по всем символам один раз.

Условие 2: проверить, являются ли две строки анаграммами, то есть состоят из одних и тех же символов в разном порядке.

Идея: посчитать, сколько раз встречается каждый символ, и сравнить эти счетчики. Готовый счетчик дает collections.Counter.

from collections import Counter

def is_anagram(a, b):
    return Counter(a) == Counter(b)

print(is_anagram("listen", "silent"))  # True
print(is_anagram("hello", "world"))    # False

Вывод:

True
False

Сложность — O(n): подсчет символов линейный. Сортировка обеих строк дала бы тот же ответ, но за O(n log n) — счетчик экономнее.

Динамическое программирование: Фибоначчи и размен монет

Динамическое программирование (ДП) — это когда задачу разбивают на подзадачи, а ответы на них сохраняют, чтобы не считать одно и то же дважды.

Условие 1: найти n-е число Фибоначчи (каждое следующее — сумма двух предыдущих: 0, 1, 1, 2, 3, 5, 8…).

Идея: наивная рекурсия fib(n) = fib(n-1) + fib(n-2) пересчитывает одни и те же значения и работает за O(2^n). Достаточно идти снизу вверх, храня два последних числа — тогда сложность O(n).

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b   # сдвигаем пару на шаг вперед
    return a

print(fib(10))  # 55

Вывод:

55

Сложность — O(n) по времени и O(1) по памяти: храним только два числа.

Условие 2: набрать заданную сумму минимальным числом монет данных номиналов (номиналы можно повторять).

Идея: для каждой суммы от 1 до нужной считаем минимум монет, опираясь на уже посчитанные меньшие суммы. Это классическая задача ДП.

def min_coins(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount        # dp[s] - минимум монет на сумму s
    for s in range(1, amount + 1):
        for c in coins:
            if c <= s:
                dp[s] = min(dp[s], dp[s - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

print(min_coins([1, 3, 4], 6))  # 2  (это 3 + 3)

Вывод:

2

Для суммы 6 и номиналов 1, 3, 4 ответ — две монеты (3 + 3), а жадный выбор самой крупной монеты дал бы 4 + 1 + 1 = три монеты. Поэтому здесь нужен именно перебор через ДП. Сложность — O(amount * k), где k — число номиналов.

Графы: обход в ширину (BFS)

Условие: обойти все вершины графа, начиная с заданной, по уровням близости к старту.

Идея: обход в ширину (breadth-first search, BFS) использует очередь. Достаем вершину, помечаем ее соседей как увиденных и кладем их в конец очереди. Множество seen защищает от повторов и зацикливания.

from collections import deque

def bfs(graph, start):
    order = []
    seen = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()        # берем из начала очереди
        order.append(node)
        for nb in graph[node]:
            if nb not in seen:
                seen.add(nb)
                queue.append(nb)      # соседи - в конец очереди
    return order

graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}
print(bfs(graph, "A"))  # ['A', 'B', 'C', 'D', 'E', 'F']

Вывод:

['A', 'B', 'C', 'D', 'E', 'F']

Сложность — O(V + E), где V — число вершин, E — число ребер: каждую вершину и каждое ребро обрабатываем один раз. BFS находит кратчайший путь по числу ребер в невзвешенном графе; для взвешенных графов берут алгоритм Дейкстры.

Типичная ошибка: неверное условие цикла в бинарном поиске

Частая ошибка в бинарном поиске — написать while lo < hi вместо while lo <= hi. Тогда при совпадении границ (lo == hi) последний оставшийся элемент не проверяется, и найденное число объявляется отсутствующим.

Неверный код:

def binary_search_bad(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:               # ошибка: пропускаем случай lo == hi
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search_bad([1, 3, 5], 5))  # -1, хотя 5 есть в массиве

Фактический вывод:

-1

Разбор: для [1, 3, 5] и цели 5 после первого шага lo становится равен 2 и hi тоже равен 2. Условие 2 < 2 ложно, цикл прерывается, и элемент с индексом 2 (как раз число 5) остается непроверенным.

Исправление — нестрогое сравнение <=, оно и стоит в рабочей версии из раздела про поиск:

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:             # проверяем и случай lo == hi
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search([1, 3, 5], 5))  # 2

Вывод:

2

Выводы

• Задача на алгоритмы решается по схеме: условие, идея (структура данных и прием), оценка сложности O() и только потом код.
• Бинарный поиск дает O(log n), но требует отсортированного массива; обычный перебор работает всегда, но за O(n).
• Сортировка вставками — учебный прием на O(n^2); в реальном коде берут встроенную sorted с O(n log n).
• Для строк подсчет символов через Counter решает задачу анаграмм за O(n) — экономнее сортировки.
• Динамическое программирование убирает повторный счет: наивный Фибоначчи — O(2^n), итеративный — O(n); жадный выбор в размене монет не всегда оптимален, ДП надежнее.
• Обход графа в ширину (BFS) работает за O(V + E) и находит кратчайший путь по числу ребер в невзвешенном графе.

Где применять на практике

Смежные темы: Виды и характеристики алгоритмов, Массивы в программировании.

FAQ

С каких задач начать новичку? С поиска и простых сортировок: они короткие, легко проверяются на маленьком массиве и знакомят с оценкой сложности. Дальше — строки, затем динамическое программирование и графы.

Обязательно ли знать O-нотацию, чтобы решать задачи? Для рабочего ответа — нет, но именно сложность отличает решение, которое проходит по времени на больших данных, от того, которое падает по таймауту на собеседовании или в проде.

На каком языке решать алгоритмические задачи? Язык вторичен: те же идеи переносятся на C++, Java, Go. Python удобен для обучения из-за коротких срезов, collections и читаемого кода, но на олимпиадах и в высоконагруженных задачах чаще берут C++ ради скорости.