📘 Тема 1.4. Необходимый материал#

Шпаргалка по циклам и перебору вариантов.

1. Что такое цикл#

Цикл — конструкция, которая повторяет один и тот же блок кода много раз: пока выполняется условие или для каждого элемента набора данных.

Зачем нужны циклы:

• Меньше кода. Вместо миллиона одинаковых строк — один цикл.
• Работа с последовательностями. Сумма, максимум, подсчёт — всё это делается в цикле.
• Перебор вариантов. Можно проверить все возможные пары, тройки, комбинации.

Термины:

Заметка

В олимпиадных задачах цикл выполняется 10⁵–10⁶ раз — это нормально. А вот 10⁹ итераций программа будет считать секунды и не уложится в лимит времени.

2. Цикл со счётчиком for#

Используется, когда количество повторений известно.

'''cpp
for (инициализация; условие; шаг) {
// тело цикла
}
'''

Порядок работы:

1. Инициализация — выполняется один раз перед циклом. Здесь создаётся счётчик: int i = 0.
2. Условие — проверяется перед каждой итерацией. Истинно — тело выполняется, ложно — цикл завершается.
3. Тело цикла — то, что повторяется.
4. Шаг — выполняется после каждой итерации. Обычно i++.

'''cpp
// числа от 1 до 5
for (int i = 1; i <= 5; i++) {
cout << i << " ";
}
cout << endl; // 1 2 3 4 5
'''

Три частых варианта границ#

'''cpp
// обход n элементов: i = 0, 1, ..., n - 1 — ровно n итераций
for (int i = 0; i < n; i++) { ... }

// числа от 1 до n включительно — тоже n итераций
for (int i = 1; i <= n; i++) { ... }

// обратный обход: n, n - 1, ..., 1
for (int i = n; i >= 1; i--) { ... }
'''

Предупреждение

i < n и i <= n — это разное число итераций. Для for (int i = 0; i < n; i++) итераций ровно n, а для for (int i = 0; i <= n; i++) — уже n + 1. Это самая частая ошибка на олимпиадах.

3. Цикл с пред-условием while#

Используется, когда количество повторений заранее неизвестно, но есть условие продолжения.

'''cpp
while (условие) {
// тело цикла
}
'''

Порядок работы: проверяется условие → если истинно, выполняется тело → условие проверяется снова → если ложно, цикл завершается.

'''cpp
// сумма чисел от 1 до n
int s = 0;
int i = 1;
while (i <= n) {
s += i;
i++;
}
'''

Внимание

В while счётчик меняется вручную внутри тела цикла. Если забыть i++, условие никогда не станет ложным и программа зависнет — получится бесконечный цикл.

4. Цикл с пост-условием do-while#

Похож на while, но условие проверяется после тела, поэтому тело выполняется хотя бы один раз.

'''cpp
do {
// тело цикла
} while (условие);
'''

'''cpp
// сумма и количество чисел до первого нуля
double sum = 0;
int count = 0;
double number;

do {
cin >> number;
if (number != 0) {
sum += number;
count++;
}
} while (number != 0);
'''

Заметка

do-while нужен там, где действие должно произойти хотя бы раз: например, «запросить пароль, потом проверить». В олимпиадных задачах он встречается редко, чаще хватает while.

5. Какой цикл выбрать#

Правило выбора:

• знаете, сколько раз повторять — for;
• повторяете, пока что-то истинно — while;
• нужно выполнить тело хотя бы раз — do-while.

6. Вложенные циклы и полный перебор#

Вложенный цикл — цикл внутри цикла. Внешний цикл делает одну итерацию, а внутренний за это время полностью проходит все свои.

'''cpp
// таблица умножения 3 × 3
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
cout << i * j << " ";
}
cout << endl;
}
'''

'''text
1 2 3
2 4 6
3 6 9
'''

Полный перебор — стратегия, при которой мы проверяем все возможные варианты и выбираем подходящий. Обычно реализуется вложенными циклами.

'''cpp
// все пары (i, j), такие что i + j = 5
for (int i = 0; i <= 5; i++) {
for (int j = 0; j <= 5; j++) {
if (i + j == 5) {
cout << i << " " << j << endl;
}
}
}
'''

Предупреждение

Два вложенных цикла по n итераций дают n² операций — сложность O(n²). Для n = 1000 это миллион операций (быстро), а для n = 100000 — уже 10¹⁰ (слишком долго). Если перебор не укладывается в лимит времени, ищите формулу или другой алгоритм.

7. Шаблоны задач#

Сумма#

'''cpp
int sum = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
sum += x;
}
'''

Сумма с условием#

'''cpp
int sum = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x > 0) { // только положительные
sum += x;
}
}
'''

Подсчёт количества#

'''cpp
int cnt = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x == 5) {
cnt++;
}
}
'''

Максимум и минимум#

'''cpp
int mx = -1000000000; // «минус бесконечность»
int mn = 1000000000; // «плюс бесконечность»

for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x > mx) mx = x;
if (x < mn) mn = x;
}
'''

Поиск первого подходящего#

'''cpp
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x >= h) {
cout << i + 1 << endl; // номер с единицы
return 0; // нашли — выходим сразу
}
}
cout << 0 << endl; // не нашли
'''

Количество максимальных элементов#

'''cpp
int mx = -1000000000;
int cnt = 0;

for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x > mx) {
mx = x;
cnt = 1; // новый максимум встретился впервые
} else if (x == mx) {
cnt++;
}
}
'''

Второй максимум#

'''cpp
int mx1 = -1000000000; // максимум
int mx2 = -1000000000; // наибольшее число, меньшее максимума

for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x > mx1) {
mx2 = mx1;
mx1 = x;
} else if (x < mx1 && x > mx2) {
mx2 = x;
}
}
'''

Длина самой длинной серии#

'''cpp
int current = 0, best = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x > 0) {
current++;
if (current > best) best = current;
} else {
current = 0;
}
}
'''

Важно

Переменные sum, cnt, mx, mn обязательно инициализируются до цикла. Иначе там будет «мусор» и ответ окажется неверным.

8. Последовательность, которая заканчивается нулём#

Если количество чисел заранее неизвестно, а последовательность завершается нулём (ноль в неё не входит), удобно писать так:

'''cpp
int x;
while (cin >> x && x != 0) {
// обработка x
}
'''

Условие cin >> x && x != 0 читается так: «считать число, и если оно не ноль — продолжить». Как только встречается 0, цикл завершается.

'''cpp
// максимум последовательности до нуля
int mx = -1000000000;
int x;
while (cin >> x && x != 0) {
if (x > mx) mx = x;
}
cout << mx << endl;
'''

9. Формула вместо цикла#

Сумму арифметической прогрессии можно посчитать без цикла:

'''text
1 + 2 + 3 + ... + n = n * (n + 1) / 2
'''

'''cpp
// циклом — n итераций
int s = 0;
for (int i = 1; i <= n; i++) {
s += i;
}
'''

'''cpp
// формулой — одна операция
long long s = (long long)n * (n + 1) / 2;
'''

Пример: задача «Ёлочки». Ёлка красоты n состоит из 2n ветвей длины 1, 2, ..., n и ствола длины 2n + 1. Площадь равна 2 * (1 + 2 + ... + n) + 2n + 1, то есть n * (n + 1) + 2n + 1.

'''cpp
long long n;
cin >> n;
cout << n * (n + 1) + 2 * n + 1 << endl;
'''

Совет

Если задачу можно решить формулой — решайте формулой. Цикл на 2·10⁹ итераций работает десятки секунд и не проходит по времени, а формула — мгновенно.

И следите за типом: при n до 2·10⁹ произведение n * (n + 1) достигает 4·10¹⁸ и в int не помещается — нужен long long.

10. Типичные ошибки#

11. Шаблон программы#

'''cpp
#include
using namespace std;

int main() {
// ввод данных

// цикл: обработка последовательности

// вывод ответа

return 0;

}
'''