1. Введение
Когда вы только начинаете программировать, массив кажется просто коробкой с числами: положили — достали. Но в реальности массив быстро превращается в «данные», над которыми постоянно нужно делать одно и то же: найти минимум, найти максимум, проверить, есть ли значение, развернуть порядок. И вот эти повторяющиеся приёмы — почти как кулинарные рецепты — и называют алгоритмическими шаблонами.
Главная идея проста: массив фиксированного размера чаще всего обрабатывается одним линейным проходом по индексам 0..N-1. В этом проходе вы либо «улучшаете ответ» (как в min/max), либо «ищете совпадение» (как в поиске), либо «перекидываете элементы» (как в развороте).
Давайте закрепим это в виде маленькой таблицы (не для экзамена, а чтобы мозг не паниковал):
| Операция | Что делаем в цикле | Сколько проходов | Идея результата |
|---|---|---|---|
|
сравниваем текущий элемент с лучшим | 1 | «лучшее значение» |
| линейный поиск | проверяем a[i] == target | 1 | «позиция» или «не найдено» |
| разворот | меняем местами пары элементов | |
массив изменён «на месте» |
2. Минимум и максимум на одном проходе
Минимум и максимум — это идеальный пример того, как цикл становится «машиной по улучшению результата». Сначала у нас нет ответа, поэтому нам нужно взять какое-то стартовое значение. И вот тут новички часто делают ход «давайте начнём с 0» — и получают сюрпризы, если все числа отрицательные или если ноль вообще не встречается. Правильнее и честнее начать с первого элемента массива.
То есть логика такая: «пока что минимум — это a[0]. Теперь посмотрим, не найдётся ли что-то меньше». Поэтому цикл обычно начинается с i = 1, потому что a[0] мы уже использовали как старт.
Пример 1: min/max для C‑массива — мини‑приложение «Температуры»
Представим, что мы пишем маленькую программу «Температуры за неделю»: вводим 7 целых температур и хотим найти минимум и максимум.
#include <cstddef>
#include <iostream>
int main() {
constexpr std::size_t N = 7;
int t[N] = {}; // температуры
for (std::size_t i = 0; i < N; ++i) std::cin >> t[i];
int mn = t[0], mx = t[0];
for (std::size_t i = 1; i < N; ++i) { if (t[i] < mn) mn = t[i]; if (t[i] > mx) mx = t[i]; }
std::cout << "min=" << mn << " max=" << mx << '\n'; // например: min=-3 max=8
}
Обратите внимание на два момента, которые делают код «устойчивым». Мы взяли старт из t[0], поэтому не зависим от того, какие числа лежат в массиве. Мы начали цикл с i = 1, чтобы не сравнивать t[0] с самим собой (это не ошибка, но лишняя работа и лишний шум в голове).
Немного про предусловие
Такой шаблон предполагает, что массив не пустой. В нашем случае это обеспечивается тем, что N фиксирован и больше нуля. Если бы размер мог быть 0, пришлось бы отдельно решать, что делать (но это уже другая история, не сегодня).
3. Линейный поиск и маркер «не найдено»
Линейный поиск — это когда мы честно идём слева направо и спрашиваем у каждого элемента: «ты тот самый?». Компьютер не обижается на такие вопросы, ему нормально. Это один из самых полезных шаблонов для начинающего, потому что он тренирует дисциплину: корректные границы, корректный тип индекса, понятный результат.
Самый важный вопрос здесь даже не «как сравнить», а «как вернуть результат». Часто мы хотим вернуть позицию (индекс), но позиция — это число от 0 до N-1. Тогда как обозначить «не найдено»?
Один из удобных способов (особенно если индекс хранится в std::size_t) — использовать значение N. Это безопасно, потому что N не может быть корректным индексом, ведь последний индекс — N-1.
Пример 2: поиск первого вхождения
Добавим к нашему приложению: пользователь вводит число target, и мы ищем, на каком дне недели оно встречалось.
#include <cstddef>
#include <iostream>
int main() {
constexpr std::size_t N = 7;
int t[N] = {};
for (std::size_t i = 0; i < N; ++i) std::cin >> t[i];
int target = 0;
std::cin >> target;
std::size_t pos = N; // маркер "не найдено"
for (std::size_t i = 0; i < N; ++i)
if (t[i] == target)
{ pos = i; break; }
if (pos != N)
std::cout << "found at day " << pos << '\n'; // например: found at day 3
else
std::cout << "not found\n";
}
Здесь break означает «нам достаточно первого совпадения». Это нормальная стратегия и часто именно её ждут. Но важно понимать: если убрать break, вы получите последнее совпадение, потому что pos будет перезаписываться каждый раз.
Один каркас цикла для разных задач
Если приглядеться, min/max и поиск похожи сильнее, чем кажется. В обоих случаях у нас есть цикл for, и в нём есть if. Отличие только в том, что именно мы делаем внутри if.
Для min/max мы не «прыгаем наружу», а обновляем переменную ответа, продолжая проход. Для поиска мы либо тоже обновляем «ответ» (например, позицию), либо выходим, если выбрали стратегию «первое совпадение».
Чтобы это закрепилось не как магия, а как привычка, можно мысленно держать такую мини-схему:
Идём по i от 0 до N-1
если элемент подходит под условие:
либо улучшаем ответ и идём дальше
либо фиксируем ответ и останавливаемся
Это и есть один из самых полезных «скелетов» в программировании.
4. Разворот массива «на месте»
Разворот массива — это операция, где легко допустить классическую ошибку индекса: перепутать N - i и N - 1 - i. Тут важно помнить железное правило: последний индекс — N - 1.
Смысл разворота такой: первый элемент меняется местами с последним, второй — с предпоследним, и так далее. Если вы будете делать это до конца массива, вы просто дважды всё вернёте обратно. Поэтому нужно делать обмены только до середины: i < N / 2.
Небольшая схема пар при развороте
Для массива из 7 элементов индексы выглядят так:
0 1 2 3 4 5 6
| | | | | | |
6 5 4 3 2 1 0
То есть парный индекс для i — это N - 1 - i.
Пример 3: разворот C‑массива с временной переменной
Добавим в наше приложение разворот температур, чтобы вывести их «с конца недели к началу».
#include <cstddef>
#include <iostream>
int main() {
constexpr std::size_t N = 7;
int t[N] = {};
for (std::size_t i = 0; i < N; ++i) std::cin >> t[i];
for (std::size_t i = 0; i < N / 2; ++i) {
int tmp = t[i];
t[i] = t[N - 1 - i];
t[N - 1 - i] = tmp;
}
for (std::size_t i = 0; i < N; ++i) std::cout << t[i] << ' ';
std::cout << '\n'; // например: 8 6 4 1 0 -2 -3
}
Почему здесь не используется std::swap? Потому что нам сейчас важнее увидеть механику руками: «временно положить один элемент в tmp, потом сделать две записи». Это прозрачно: видно каждое присваивание, и легче отлавливать ошибки.
5. Те же шаблоны на std::array
С std::array приятно то, что он сам умеет говорить свой размер: a.size(). И это сильно снижает количество «магических чисел» и риск рассинхронизации, когда вы поменяли размер массива, а цикл забыли поменять.
Психологически это тоже помогает: вы меньше думаете про «а я точно везде использую 7?», и больше думаете про задачу.
Пример 4: min/max для std::array
#include <array>
#include <cstddef>
#include <iostream>
int main() {
std::array<int, 7> t{}; // 7 температур
for (std::size_t i = 0; i < t.size(); ++i) std::cin >> t[i];
int mn = t[0], mx = t[0];
for (std::size_t i = 1; i < t.size(); ++i)
{ if (t[i] < mn) mn = t[i]; if (t[i] > mx) mx = t[i]; }
std::cout << "min=" << mn << " max=" << mx << '\n';
}
Обратите внимание: логика та же, «рецепт» тот же, поменялась только граница цикла. Это хороший знак: значит, вы не привязаны к конкретной реализации массива, вы мыслите «данными и проходом».
Пример 5: поиск в std::array с маркером «не найдено»
#include <array>
#include <cstddef>
#include <iostream>
int main() {
std::array<int, 7> t{};
for (std::size_t i = 0; i < t.size(); ++i) std::cin >> t[i];
int target = 0;
std::cin >> target;
std::size_t pos = t.size();
for (std::size_t i = 0; i < t.size(); ++i)
if (t[i] == target)
{ pos = i; break; }
std::cout << (pos == t.size() ? "not found\n" : "found\n"); // found / not found
}
Тут маркером становится t.size(). Это ровно та же идея, что и pos = N, просто более «самодокументируемая».
6. Практический сценарий: «температуры за неделю»
Чтобы всё это не осталось набором отдельных трюков, полезно представить, что мы пишем одно мини-приложение, которое делает несколько операций подряд. В реальной жизни так и будет: данные редко обрабатываются одной командой, чаще это цепочка шагов.
Мы уже почти собрали такую программу: вводим 7 температур, находим min/max, ищем конкретную температуру, разворачиваем массив и печатаем. Да, это звучит как «мини‑Excel на минималках», но именно такие упражнения закладывают базовую моторику работы с массивами.
Вот компактная версия, где всё в одном main (и это важно для текущего дня: никаких пользовательских функций).
#include <array>
#include <cstddef>
#include <iostream>
int main() {
std::array<int, 7> t{};
for (std::size_t i = 0; i < t.size(); ++i)
std::cin >> t[i];
int mn = t[0], mx = t[0];
for (std::size_t i = 1; i < t.size(); ++i)
{ if (t[i] < mn) mn = t[i]; if (t[i] > mx) mx = t[i]; }
int target = 0; std::cin >> target;
std::size_t pos = t.size();
for (std::size_t i = 0; i < t.size(); ++i)
if (t[i] == target) { pos = i; break; }
for (std::size_t i = 0; i < t.size() / 2; ++i)
{ int tmp = t[i]; t[i] = t[t.size() - 1 - i]; t[t.size() - 1 - i] = tmp; }
std::cout << "min=" << mn << " max=" << mx << '\n';
std::cout << (pos == t.size() ? "not found\n" : "found\n");
}
Да, здесь строки плотные. Но обратите внимание на структуру: три прохода (min/max, поиск, разворот) и каждый проход — это один и тот же знакомый цикл по индексам. Это и есть цель лекции: чтобы вы видели в коде не хаос, а повторяемые паттерны.
7. Типичные ошибки при min/max, поиске и развороте
Ошибка №1: начинать min/max с “0” или “очень большим числом”.
Новичок часто пишет int mn = 0; и потом удивляется, что минимум массива {-5, -2} внезапно равен 0. Проблема в том, что вы взяли стартовое значение не из массива, а из головы. Надёжнее начинать с a[0], а цикл — с i = 1: тогда ответ всегда основан на реальных данных.
Ошибка №2: цикл для min/max начинается с i = 0, но mn тоже равен a[0], и студент путается.
Формально это не ломает результат: сравнить a[0] с mn, где mn == a[0], не страшно. Но для начинающего это добавляет лишнюю мыслительную нагрузку: «а зачем мы сравниваем элемент сам с собой?». Лучше придерживаться чистого шаблона mn = a[0]; for (i = 1; ...).
Ошибка №3: в поиске нет понятного “не найдено”.
Если вы ищете позицию и забыли договориться, что делать при провале, появляются странные костыли: возвращают 0, возвращают -1 в size_t (а это превращается в огромное число), или печатают мусор. Самый безопасный приём на этом уровне — pos = N (или pos = a.size()), потому что это значение не может быть корректным индексом.
Ошибка №4: потерянный break или, наоборот, лишний break.
Иногда вы хотите найти первое вхождение, но забываете break и получаете последнее. Иногда вы хотите найти последнее (или посчитать все), но ставите break и находите только первое. Это не “ошибка компиляции”, это ошибка постановки задачи. Перед тем как писать цикл, полезно честно решить: «мне нужен первый, последний или все совпадения?».
Ошибка №5: неправильная формула индекса при развороте (N - i вместо N - 1 - i).
Это классика: вы помните, что «в конце массива», но забываете, что индексация начинается с нуля. В результате вы обращаетесь к a[N], а это уже за границей. Лечится одной мантрой: «последний индекс — N - 1».
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ