Циклы

Цикл (loop) — оператор, который организует повторяющееся выполнение другого оператора. В C++ их три: while, do-while и for.

Зачем нужно

Ввести n, затем n целых чисел и найти их сумму. Для трёх или десяти чисел можно выписать все строки руками или даже сгенерировать код скриптом. Но если n неизвестно на этапе компиляции, без цикла не обойтись.

Как работает

while

while (<condition>) <statement>

• condition — выражение либо объявление переменной с инициализатором. В любом случае значение должно приводиться к bool.
• statement — оператор, может быть составным (блоком).

Условие проверяется перед каждой итерацией:

int n;
std::cin >> n;
 
int sum = 0;
while (n > 0) {
  int x;
  std::cin >> x;
  sum += x;
  --n;
}
 
std::cout << sum << '\n';

В условии можно объявить переменную:

x = -5;
while (int sqr = x * x) {
  ++x;
  std::cout << sqr << '\n';
}

Цикл остановится, когда x дойдёт до нуля и sqr станет 0, то есть false. Так же устроено объявление в условии if.

do-while

do <statement> while (<condition>);

Тело выполняется до проверки условия, поэтому хотя бы одна итерация гарантирована. Естественный случай — читать числа до первого нуля: до первого чтения проверять нечего.

int x = 0;
int sum = 0;
 
do {
  std::cin >> x;
  sum += x;
} while (x != 0);
 
std::cout << sum << '\n';

for

for ([init]; [condition]; [expression]) <statement>

• init — выражение либо объявление; область действия объявленной сущности совпадает с областью оператора for;
• condition — как у while, пустое означает true;
• expression — произвольное выражение, выполняется в конце итерации;
• statement — тело цикла.

for эквивалентен такому while:

{
  [init];
  while ([condition]) {  // while (true), если condition пуст
    <statement>
    [expression];
  }
}

Внешние фигурные скобки — не для красоты: они и делают так, что счётчик не виден после цикла (см. Область действия). Сравните с вариантом на while, где int i = 0; стоит перед циклом: счётчик виден снаружи, сколько будет итераций — неясно, а ++i легко забыть или не найти в теле. for собирает всё это в одну строку, поэтому на практике используется чаще.

for (int i = 0; i < n; ++i) std::cout << i << '\n';
 
for (int i = 0; i < n; i += 2) {
  std::cout << i << '\n';
}
 
for (std::cin >> x; x != 0; std::cin >> x) {
  std::cout << x * x << '\n';
}
 
for (;;) ...     // бесконечный цикл
for (; x;) ...   // аналог while
 
for (int i = 0, j = 0; i < n && j < m; ++i, ++j) ...

break и continue

• break досрочно завершает весь цикл;
• continue досрочно завершает текущую итерацию, цикл идёт дальше.

for (int i = 0; i < n; ++i) {
  int x;
  std::cin >> x;
  if (x == 0) {
    std::cout << "Division by zero\n";
    break;  // с continue — перейдёт к следующему числу
  }
  std::cout << y / x << '\n';
}

Тонкости

• Условие входа или условие выхода? while и for могут не выполнить тело ни разу, если условие ложно с самого начала. do-while выполнит хотя бы одну итерацию. От этого и зависит выбор.
• while (true) ... и for (;;) ... — бесконечные циклы; выходят из них через break.
• Пустой цикл while (x); — Неопределённое поведение, если x не меняет своего результата и не имеет побочных действий.
• Вместо goto для повторения и досрочного выхода используют циклы, break и continue — goto в курсе запрещён, см. Кодстайл курса.

Частые ошибки

• Забыть изменить переменную условия в теле while — цикл станет бесконечным.
• Ставить ; сразу после while (...) или for (...): телом цикла станет пустой оператор.
• Путать break и continue.

Углубление — АиСД L01

Сколько стоит цикл

На АиСД время работы считают в тактах — простейших действиях вроде сравнения и присвоения, см. Время работы алгоритма. Цикл стоит столько, сколько стоит его тело, умноженное на число итераций.

Проверка числа $p$ на простоту перебором всех делителей:

counter = 0            // 1 такт
for i = 1 ... p
    если p ⋮ i         // тело — не больше 2 тактов,
        counter += 1   // выполняется N раз
если counter = 2       // 2 такта
    число простое
иначе
    не простое

$\Sigma =2+1+2\cdot N=3+2N$ тактов, то есть $O(N)$ — см. Асимптотические оценки. Здесь N — само число $p$, а не длина входа.

break и оценка

Если перебирать делители от 2 до $p-1$ и выходить через break на первом найденном, оценка на лекции осталась прежней: $O(N)$. Быстрее стало только при переборе до $\sqrt{N}$: $O(\sqrt{N})$.

Не из лекции: почему break не помог

Для простого $p$ делителя нет, break не срабатывает, и цикл проходит все итерации. Оценку определяет такой, самый долгий случай.