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

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

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

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

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

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

Термины:

Заметка

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

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

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

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

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

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

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

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

// обход 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#

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

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

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

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

Внимание

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

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

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

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

// сумма и количество чисел до первого нуля
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. Вложенные циклы и полный перебор#

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

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

1 2 3
2 4 6
3 6 9

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

// все пары (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. Шаблоны задач#

Сумма#

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

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

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

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

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

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

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;
}

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

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

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

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++;
    }
}

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

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;
    }
}

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

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. Последовательность, которая заканчивается нулём#

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

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

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

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

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

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

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

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

// формулой — одна операция
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.

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. Шаблон программы#

#include <iostream>
using namespace std;

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

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

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

    return 0;
}