Алгоритмические структуры: от теории к практике
Представь: ты открываешь YouTube, и алгоритм моментально подбирает видео, которые тебя заинтересуют. Ты пишешь сообщение в Telegram, и оно мгновенно шифруется. Ты играешь в игру, и NPC реагируют на твои действия. За всем этим стоят алгоритмические структуры — фундаментальные паттерны, из которых собирается любая программа.
Введение: Код, который управляет миром
В этом разделе мы разберём три базовые конструкции, которые составляют 99% всего кода: последовательность, ветвление и цикл. Звучит просто? На деле именно их комбинации создают Netflix, Discord, беспилотные авто и нейросети.
🎯 Что ты узнаешь
- Как три простые структуры создают сложные системы
- Почему последовательность команд критична
- Как работают условия и циклы в реальных приложениях
- Практические приёмы оптимизации алгоритмов
1. Последовательная структура: один шаг за другим
Последовательная алгоритмическая конструкция — это когда команды выполняются строго по порядку, одна за другой, без пропусков и повторений. Каждая инструкция выполняется ровно один раз.
Последовательность как падающее домино — каждый шаг зависит от предыдущего
💡 Определение
Алгоритм реализован через последовательную алгоритмическую конструкцию, если все команды алгоритма выполняются один раз, причём в том порядке, в котором они записаны в тексте программы.
🔄 Аналогия из жизни
Рецепт приготовления пасты:
- Вскипяти воду
- Добавь соль
- Засыпь макароны
- Вари 10 минут
- Слей воду
Если поменять порядок (например, слить воду до варки), результат будет неожиданным. Так же и в коде: последовательность имеет значение.
Пример: эффективное возведение в степень
Задача: вычислить x⁵ (число в пятой степени).
❌ Наивный подход
Умножить x на себя 5 раз:
результат = x * x * x * x * x
// 5 операций умножения✅ Умный подход
Использовать промежуточные результаты:
REZ := X * X // X²
REZ := REZ * REZ // X⁴
REZ := REZ * X // X⁵
// Всего 3 операции!🔐 Применение в реальном мире
В криптографии RSA возведение в степень огромных чисел происходит миллионы раз в секунду. Каждая сэкономленная операция критична! Например, для вычисления x¹⁵² (из задания учебника) можно использовать двоичное разложение:
152 = 128 + 16 + 8
x¹⁵² = x¹²⁸ × x¹⁶ × x⁸
// Вычисляем степени двойки последовательно:
x² → x⁴ → x⁸ → x¹⁶ → x³² → x⁶⁴ → x¹²⁸
// Всего 7 возведений в квадрат + 2 умножения = 9 операций
// вместо 151 операции наивным способом!Дерево решений: визуализация вариантов
Когда у исполнителя есть несколько команд, возникает вопрос: сколько разных программ можно составить и сколько уникальных результатов получить?
Дерево решений показывает все возможные пути выполнения программы
📊 Пример: Исполнитель Вычислитель
Команды:
- Прибавь 2
- Умножь на 3
Вопрос: Сколько разных программ из 3 команд можно составить? Сколько уникальных результатов из начального числа 2?
🔢 Подсчёт программ
Каждую команду можно выбрать одним из двух способов, всего команд три:
N = 2³ = 8 программ
Все варианты:
1-1-1, 1-1-2, 1-2-1, 1-2-2
2-1-1, 2-1-2, 2-2-1, 2-2-2🎯 Уникальные результаты
Из числа 2 получаем 8 различных значений:
Уровень 3 дерева:
8, 10, 14, 18, 20, 24, 36, 54
Все результаты различны!🎮 Практическое применение
Алгоритмы поиска в играх (например, шахматные движки) строят такие деревья решений, оценивая миллионы возможных ходов. Глубина дерева = количество ходов вперёд, которые просчитывает программа.
Минимальное число команд: Номер уровня, на котором впервые появляется нужное число, равен минимальному количеству команд для его получения. Например, число 8 в примере появляется на уровне 2, значит, минимум 2 команды.
🔄 Обратное дерево решений
Для некоторых задач удобнее строить обратное дерево: команды меняются на «обратные», пути строятся от результата к начальному значению.
Пример: Из числа 8 получить число 2
Обратные команды:
1) вычти 2
2) раздели на 3
Дерево: 8 → 6 → 4 → 2
8 → 6 → 2 (деление на 3 невозможно)
Минимум команд: 3Этот приём полезен, когда обратные команды неприменимы ко всем числам (например, нельзя разделить нечётное на 3).
2. Ветвление: выбор пути
Ветвление (условная конструкция) — это когда программа принимает решение: какой блок кода выполнить в зависимости от условия.
Ветвление как развилка — программа выбирает путь на основе условия
💡 Определение
Алгоритм реализован через алгоритмическую конструкцию «ветвление», если от входных данных зависит, какие команды алгоритма будут выполняться. При каждом конкретном наборе входных данных ветвление сводится к выполнению последовательной конструкции.
🗺️ Аналогия: навигатор прокладывает маршрут
ЕСЛИ пробка → выбрать объезд
ИНАЧЕ → ехать по прямойПример: модерация контента
Алгоритм автомодерации сообщений в чате:
if message.contains_forbidden_words():
delete_message()
warn_user()
elif message.length > 1000:
send_to_manual_review()
else:
publish_message()🚫 Сценарий 1
Запрещённые слова → удалить и предупредить пользователя
⚠️ Сценарий 2
Слишком длинное сообщение → отправить на ручную проверку модератору
✅ Сценарий 3
Всё в порядке → опубликовать сообщение
🤖 Реальное применение
Системы типа OpenAI Moderation API используют именно такие ветвления, но с тысячами проверок: токсичность, спам, NSFW, политический контент, дезинформация и т.д. Каждая проверка — это условие, которое может запустить свою цепочку действий.
Вложенные условия: сложность нарастает
Рассмотрим пример из учебника:
if X < 1:
Y = -X
else:
if X < 4:
Y = -1
else:
Y = X - 5📊 Анализ условий
Три ветки выполнения:
- X < 1 → Y = -X
- 1 ≤ X < 4 → Y = -1
- X ≥ 4 → Y = X - 5
🧪 Проверка на примерах
X = -10 → Y = 10
X = 2 → Y = -1
X = 10 → Y = 5⚠️ Проблема сложности
Чем больше вложенных if-else, тем труднее отлаживать код. Программисты стремятся к упрощению логики:
- Раннее возвращение: выходить из функции сразу после выполнения условия
- Таблицы решений: использовать словари/массивы вместо цепочек if-else
- Полиморфизм: заменять условия на объектно-ориентированные паттерны
3. Циклы: сила повторения
Циклическая конструкция — это когда группа команд выполняется многократно, пока выполняется условие.
Цикл как спираль — повторяющиеся действия с накоплением результата
💡 Определение
Алгоритм реализован с использованием циклической алгоритмической конструкции, если некая группа подряд идущих шагов алгоритма может выполняться многократно в зависимости от входных данных. Любая циклическая структура содержит в себе элементы конструкции «ветвление».
🔄 Цикл с предусловием (while)
Проверка условия → тело цикла
while условие:
выполнить_команды()Может не выполниться ни разу
🔁 Цикл с постусловием (do-while)
Тело цикла → проверка условия
do:
выполнить_команды()
while условиеВыполнится минимум один раз
🔢 Цикл с параметром (for)
Фиксированное число повторений
for i in range(n):
выполнить_команды()Известно количество итераций
Пример 1: Подсчёт цифр числа
Задача: сколько цифр в числе X?
📝 Алгоритм
A = 0
while X > 0:
A = A + 1
X = X // 10
// A — количество цифр🔍 Трассировка
X = 12345
Итерация 1: A=1, X=1234
Итерация 2: A=2, X=123
Итерация 3: A=3, X=12
Итерация 4: A=4, X=1
Итерация 5: A=5, X=0 → стоп💳 Применение
Валидация номеров банковских карт, паролей, ISBN-кодов — везде, где нужно проверить количество символов/цифр. Например, номер карты должен содержать ровно 16 цифр.
Пример 2: Сумма цифр числа
Задача из учебника (левая блок-схема на рис. 2.9)
S = 0
while X > 0:
B = X mod 10 # Последняя цифра
S = S + B # Добавляем к сумме
X = X div 10 # Убираем последнюю цифру
# S — сумма всех цифр числа🧮 Пример расчёта
X = 9575
Итерация 1: B=5, S=5, X=957
Итерация 2: B=7, S=12, X=95
Итерация 3: B=5, S=17, X=9
Итерация 4: B=9, S=26, X=0 → результат: 26Сложный кейс: Алгоритм Редактора
Мощный пример из учебника, демонстрирующий работу циклов со строками.
Алгоритм обработки строк как конвейер с роботами-операторами
🤖 Исполнитель Редактор
Команды:
нашлось(v)— проверить наличие подстроки v (возвращает true/false)заменить(v, w)— заменить первое вхождение v на w
Программа обработки
НАЧАЛО
ПОКА нашлось(22) ИЛИ нашлось(333)
ЕСЛИ нашлось(22)
ТО заменить(22, 3)
ИНАЧЕ заменить(333, 2)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ🔍 Анализ: строка из 21 тройки
333 333 333 333 333 333 333 (21 тройка)
→ 2 333 333 333 333 333 ... (заменили 333 → 2)
→ 2 2 333 333 333 ... (ещё раз)
→ 3 333 333 333 ... (заменили 22 → 3)
→ 2 333 333 ... (снова 333 → 2)
...
Паттерн: каждые 3 замены убирают 5 троек!
21[3] → 16[3] → 11[3] → 6[3] → 1[3] = "3"🔍 Анализ: строка из 25 троек
25[3] → 20[3] → 15[3] → 10[3] → 5[3] → 1[2]2[3]
Результат: "233"
Почему остановились:
- Осталось менее 6 троек
- 5[3] → 2[3]3 → 2[2]2[3] → 3[3]3 → 2[3]3 → 233Универсальное правило
Для строки из N подряд идущих цифр 3:
1. ЕСЛИ N mod 5 = 0, ТО N := 5
ИНАЧЕ N := N mod 5
2. Исполнить алгоритм для новой строки из N троек
Примеры:
- 2017 троек: 2017 mod 5 = 2 → "233"
- 12345 троек: 12345 mod 5 = 0 → N=5 → "233"
- 2015 троек: 2015 mod 5 = 0 → N=5 → "233"🗜️ Применение: компрессия данных
Алгоритмы сжатия типа LZ77 (используется в ZIP, PNG) работают по схожему принципу — заменяют повторяющиеся фрагменты ссылками.
Парсинг текста: Markdown-процессоры, подсветка синтаксиса — всё это циклы с заменами паттернов по регулярным выражениям.
🤔 Задача для размышления
Что получится, если применить эту же программу к строке из двоек вместо троек?
Программа та же:
ПОКА нашлось(33) ИЛИ нашлось(22)
ЕСЛИ нашлось(33)
ТО заменить(33, 2)
ИНАЧЕ заменить(22, 3)
Строка: 2015 двоек
Подсказка: паттерн будет другой!
Попробуй проследить первые несколько итераций.Ключевые выводы
Давайте подведём итоги и систематизируем полученные знания.
Из трёх простых структур строится вся сложность программирования
🤔 Проверь себя
Практические вопросы и задачи для закрепления материала.
Задача 1: Обратное дерево решений
Исполнитель может:
- Вычесть 2
- Разделить на 3
Вопрос: Какими командами из числа 8 можно получить число 2? Построй обратное дерево решений.
Подсказка: Если обычные команды неприменимы ко всем числам (нельзя разделить нечётное на 3), обратное дерево помогает отсечь невозможные пути.
Задача 2: Модификация алгоритма Редактора
Дана та же программа Редактора, но применяется к строке из двоек:
ПОКА нашлось(33) ИЛИ нашлось(22)
ЕСЛИ нашлось(33)
ТО заменить(33, 2)
ИНАЧЕ заменить(22, 3)Вопрос: Что получится из 2015 двоек?
Hint: Паттерн будет другой! Проследи первые итерации.
Задача 3: Оптимизация возведения в степень
Напиши последовательный алгоритм возведения x в степень 152 за минимальное число операций.
Подсказка:
152 = 128 + 16 + 8
152 в двоичной системе: 10011000
Используй двоичное разложение и
последовательное возведение в квадрат!Задача 4: Реальный кейс — автокорректор
Опиши алгоритм работы автокорректора (как в клавиатуре смартфона) через три структуры:
- Последовательность: какие этапы? (ввод → анализ → предложение → замена)
- Ветвление: какие проверки? (есть ли в словаре? похоже на известное слово? контекст подходит?)
- Циклы: где повторения? (перебор вариантов, анализ каждого символа)
Задача 5: Анализ алгоритмов из учебника
Известно, что X, A, B, S — целые положительные числа. Две блок-схемы из рис. 2.9:
Левый алгоритм: S = 0; while X > 0: B = X mod 10; S = S + B; X = X div 10
Правый алгоритм: A = 0; while X > 0: A = A + 1; X = X div 10
Вопросы:
- Какую задачу решает каждый алгоритм?
- При каких X оба алгоритма дают результат 3?
Ответ:
- Левый: сумма цифр числа
- Правый: количество цифр в числе
- Для результата 3: левый — любое число с суммой цифр 3 (например, 12, 21, 111, 300); правый — любое трёхзначное число (100-999)
Задача 6: Автомат обработки четырёхзначных чисел
Из учебника (стр. 76): автомат получает четырёхзначное число и создаёт суммы соседних пар цифр. Выбирает минимальную сумму и записывает две другие в порядке неубывания.
Пример: 9575 → суммы: 9+5=14, 5+7=12, 7+5=12 → минимум 12 → результат: 1214
Вопросы:
- Могут ли быть результатами 1610, 1010, 1019?
- Минимальное и максимальное значения результата?
- При каких x результат 1418?
🎯 Практические задания
Применяй полученные знания на практике!
💻 Задание 1: Написать код
Реализуй на Python три алгоритма:
- Подсчёт цифр в числе
- Сумма цифр числа
- Проверка: все ли цифры различны?
Используй: циклы while, операторы mod и div
🎮 Задание 2: Игровая логика
Спроектируй алгоритм поведения NPC в игре:
- Последовательность: патрулирование маршрута
- Ветвление: реакция на игрока (друг/враг)
- Цикл: повторение действий
🔐 Задание 3: Валидация пароля
Напиши алгоритм проверки сложности пароля:
- Длина ≥ 8 символов
- Есть заглавные и строчные буквы
- Есть цифры и спецсимволы
- Нет простых последовательностей (123, abc)
📊 Задание 4: Анализ производительности
Сравни время выполнения:
- x⁵⁰ за 49 умножений
- x⁵⁰ через двоичное разложение
Напиши оба варианта и замерь время для x = 2.
📚 Дополнительные материалы
📖 Для углублённого изучения
- Теорема Бёма-Джакопини (1966) — доказательство достаточности трёх структур
- Проблема останова — почему невозможно создать универсальный анализатор циклов
- Временная сложность — анализ O(n), O(log n), O(n²)
🔬 Исследуй дальше
- Изучи алгоритмы сортировки (QuickSort, MergeSort)
- Попробуй рекурсивные структуры (следующий уровень!)
- Реши задачи на Codeforces или LeetCode
