Раздел 6 — Циклы

Цикл повторяет инструкции, пока выполняется условие. while — цикл с предусловием из раздела 2: условие проверяется до каждого повторения. Одно выполнение тела называют итерацией.

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

/* Сумма 1 + 2 + ... + n */
#include <stdio.h>

int main(void)
{
    int n = 0;
    printf("n: ");
    if (scanf("%d", &n) != 1 || n < 1 || n > 100000) {
        printf("Error: n must be 1..100000\n");
        return 1;
    }

    long long sum = 0;
    int i = 1;                 /* 1. начальное значение */
    while (i <= n) {           /* 2. условие продолжения */
        sum += i;
        i++;                   /* 3. изменение переменной цикла */
    }
    printf("1 + ... + %d = %lld\n", n, sum);
    return 0;
}

n: 4      ->  1 + ... + 4 = 10
n: 100    ->  1 + ... + 100 = 5050

У цикла три части, и ошибка в любой из них — самая частая ошибка раздела: начальное значение (i = 1), условие продолжения (i <= n) и изменение переменной цикла в теле (i++). Трассировка для n = 4:

Условие проверяется на один раз больше, чем выполняется тело. После цикла i равно 5, а не 4. Сумма — long long: при n = 100 000 она равна 5 000 050 000 и в int не помещается.

Алгоритм Евклида из раздела 2 — цикл, число повторений которого заранее неизвестно:

/* НОД двух натуральных чисел — алгоритм Евклида */
#include <stdio.h>

int main(void)
{
    int a = 0, b = 0;
    printf("a b: ");
    if (scanf("%d %d", &a, &b) != 2 || a < 1 || b < 1) {
        printf("Error: need two natural numbers\n");
        return 1;
    }

    int x = a, y = b;
    while (y != 0) {
        int r = x % y;
        x = y;
        y = r;
    }
    printf("gcd(%d, %d) = %d\n", a, b, x);
    return 0;
}

a b: 48 18    ->  gcd(48, 18) = 6
a b: 18 48    ->  gcd(18, 48) = 6
a b: 17 5     ->  gcd(17, 5) = 1

Цикл идёт по копиям x и y: после цикла y равно 0, а в выводе нужны исходные числа. Почему цикл закончится: остаток r всегда меньше делителя y и не меньше 0, значит, y уменьшается на каждой итерации хотя бы на 1 и за конечное число шагов станет 0. Это рассуждение — обязательная часть решения каждой задачи с циклом while в практических работах.

Цифры числа. n % 10 — последняя цифра, n / 10 — число без неё (раздел 4). Повторяя их, пока от числа что-то осталось, проходим все цифры:

/* Количество и сумма цифр целого числа */
#include <stdio.h>

int main(void)
{
    int number = 0;
    printf("Number: ");
    if (scanf("%d", &number) != 1 || number < -1000000000) {
        printf("Error: integer from -1000000000 expected\n");
        return 1;
    }

    int rest = number < 0 ? -number : number;
    int count = 0, digit_sum = 0;
    while (rest > 0) {
        digit_sum += rest % 10;
        rest /= 10;
        count++;
    }
    printf("%d: digits %d, sum %d\n", number, count, digit_sum);
    return 0;
}

Number: 30572    ->  30572: digits 5, sum 17
Number: -408     ->  -408: digits 3, sum 12
Number: 0        ->  0: digits 0, sum 0         <- неверно: у нуля одна цифра

Для нуля условие rest > 0 ложно с первой проверки: тело цикла с предусловием может не выполниться ни разу. Сумма цифр нуля верна, количество — нет. Это исправит цикл с постусловием (пункт 04). Почему ограничение снизу: -number для наименьшего int (−2 147 483 648) не помещается в int — переполнение.

Сколько чисел введёт пользователь, заранее неизвестно; конец обозначается особым значением — признаком конца, например нулём. Сам признак не обрабатывается:

/* Сумма и среднее чисел, ввод до нуля */
#include <stdio.h>

int main(void)
{
    printf("Numbers, 0 - end: ");
    int value = 0;
    int count = 0;
    long long sum = 0;
    while (scanf("%d", &value) == 1 && value != 0) {
        sum += value;
        count++;
    }

    if (count == 0) {
        printf("No numbers\n");
    } else {
        printf("Count %d, sum %lld, average %.2f\n", count, sum, (double)sum / count);
    }
    return 0;
}

Numbers, 0 - end: 5 8 -3 10 0     ->  Count 4, sum 20, average 5.00
Numbers, 0 - end: 7 2 0           ->  Count 2, sum 9, average 4.50
Numbers, 0 - end: 0               ->  No numbers
Numbers, 0 - end: 5 8 x 3 0       ->  Count 2, sum 13, average 6.50

Чтение — в условии цикла: scanf(…) == 1 && value != 0. Сокращённое вычисление (раздел 5) гарантирует, что value проверяется, только если число прочитано. Цикл заканчивается по любой из двух причин: введён 0 или ввод не число. Последний пример показывает, что программа не отличает их: на x она молча закончила, как будто введён признак конца. Если это важно, после цикла проверяют, что именно его остановило, — так сделано в практической работе №4.

Условие проверяется после тела, поэтому тело выполняется хотя бы один раз. После while (…) — точка с запятой.

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

Количество цифр с do while верно и для нуля: одна итерация выполнится всегда, а у любого числа хотя бы одна цифра:

int rest = number < 0 ? -number : number;
int count = 0;
do {
    rest /= 10;
    count++;
} while (rest > 0);          /* 0 -> 1 цифра, 7 -> 1, 30572 -> 5 */

В разделе 5 программа при ошибке ввода завершалась. В диалоговой программе вежливее спросить ещё раз. Трудность: если scanf("%d") встретил abc, эти символы остаются во вводе, и следующий scanf снова споткнётся о них — цикл станет бесконечным. Перед повтором остаток строки нужно прочитать и выбросить:

/* Запрашивать число от 1 до 10, пока не введут верное */
#include <stdio.h>

int main(void)
{
    int n = 0;
    int ok = 0;
    do {
        printf("Number 1..10: ");
        int read = scanf("%d", &n);
        if (read == EOF) {                     /* ввод закончился (Ctrl+Z / Ctrl+D) */
            printf("\nError: no input\n");
            return 1;
        }
        int ch;
        while ((ch = getchar()) != '\n' && ch != EOF) {
            /* выбросить остаток строки */
        }
        ok = read == 1 && n >= 1 && n <= 10;
        if (!ok) {
            printf("Wrong input, try again\n");
        }
    } while (!ok);

    printf("You entered %d\n", n);
    return 0;
}

Number 1..10: abc
Wrong input, try again
Number 1..10: 15
Wrong input, try again
Number 1..10: 7
You entered 7

• getchar() читает один символ и возвращает его код, а в конце ввода — константу EOF (обычно −1). Поэтому ch — int, а не char: в char значение EOF может не отличиться от обычного символа.
• (ch = getchar()) != '\n' — присваивание внутри условия, взятое в скобки: сначала прочитать, потом сравнить. Это одно из немногих мест, где так пишут намеренно.
• scanf возвращает EOF, если ввод закончился (пользователь нажал Ctrl+Z в Windows или Ctrl+D в Linux, или кончился файл, перенаправленный на вход). Без этой проверки цикл стал бы бесконечным.

Когда число повторений известно до начала цикла, три части цикла собирают в одну строку:

for (начальное значение; условие; изменение) {
    тело цикла
}

Порядок: начальное значение — один раз; затем проверка условия, тело, изменение, снова проверка. Любой for переписывается через while и наоборот. Переменная, объявленная в заголовке for, существует только внутри цикла (с C99):

/* Степени двойки */
#include <stdio.h>

int main(void)
{
    int n = 0;
    printf("n (0..62): ");
    if (scanf("%d", &n) != 1 || n < 0 || n > 62) {
        printf("Error: n must be 0..62\n");
        return 1;
    }
    long long power = 1;
    for (int i = 0; i <= n; i++) {
        printf("2^%d = %lld\n", i, power);
        if (i < n) {
            power *= 2;
        }
    }
    return 0;
}

n (0..62): 4
2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16

Почему if (i < n) перед умножением: без него на последней итерации power стал бы 2⁶³ — больше наибольшего long long. Значение не выводится, но переполнение знакового типа — неопределённое поведение (раздел 3), даже когда результат не используется. Шаг может быть любым: for (int i = 10; i > 0; i -= 3) даёт 10, 7, 4, 1.

Большинство задач с циклом сводится к нескольким типовым алгоритмам. У каждого — переменная-накопитель и правило, каким значением её начинать:

/* n чисел: сумма, среднее, максимум и его номер, количество положительных */
#include <stdio.h>

int main(void)
{
    int n = 0;
    printf("How many: ");
    if (scanf("%d", &n) != 1 || n < 1) {
        printf("Error: n must be >= 1\n");
        return 1;
    }
    printf("Numbers: ");
    long long sum = 0;
    int max = 0, max_pos = 0, positive = 0;
    for (int i = 1; i <= n; i++) {
        int value = 0;
        if (scanf("%d", &value) != 1) {
            printf("Error: number %d is not an integer\n", i);
            return 1;
        }
        sum += value;
        if (i == 1 || value > max) {      /* первое значение — начальный максимум */
            max = value;
            max_pos = i;
        }
        if (value > 0) {
            positive++;
        }
    }
    printf("Sum %lld, average %.2f\n", sum, (double)sum / n);
    printf("Max %d (number %d), positive %d\n", max, max_pos, positive);
    return 0;
}

How many: 6                          How many: 3
Numbers: 4 -2 9 0 9 -5               Numbers: -7 -2 -9
Sum 15, average 2.50                 Sum -18, average -6.00
Max 9 (number 3), positive 3         Max -2 (number 2), positive 0

• Максимум начинается с первого числа, а не с нуля: с max = 0 второй пример выдал бы максимум 0 — числа, которого не было.
• > или >= решает, какой из равных максимумов запомнится: со строгим > — первый (номер 3), с >= — последний (номер 5).
• Сумма — long long: каждое число помещается в int, а сумма многих — не обязательно.

Поиск перебирает кандидатов, пока не найдёт подходящего. Обе причины остановки — «кандидаты кончились» и «найдено» — удобно вписать в условие цикла. Простое ли число n — есть ли у него делитель от 2 до √n:

int divisor = 2;
while (divisor <= n / divisor && n % divisor != 0) {
    divisor++;
}
if (divisor > n / divisor) {
    printf("%d is prime\n", n);               /* 97 is prime */
} else {
    printf("%d = %d * %d\n", n, divisor, n / divisor);   /* 91 = 7 * 13 */
}

После цикла выясняется, почему он закончился. Почему до √n: если n = a · b и a ≤ b, то a ≤ √n — меньший делитель пары найдётся до корня. Для простого числа около двух миллиардов это около 44 700 проверок вместо двух миллиардов. Условие записано как divisor <= n / divisor, а не divisor * divisor <= n: квадрат при n около INT_MAX переполнил бы int.

break немедленно завершает ближайший цикл (или switch). continue пропускает остаток тела и переходит к следующей итерации (в for — к изменению счётчика):

/* Сумма положительных из введённых, ввод до нуля; отрицательные пропускаются */
long long sum = 0;
int value = 0;
while (1) {
    if (scanf("%d", &value) != 1 || value == 0) {
        break;                /* конец ввода */
    }
    if (value < 0) {
        continue;             /* отрицательное — пропустить */
    }
    sum += value;
}                              /* 5 -3 8 -1 0 -> 13 */

while (1) с break внутри — «цикл с выходом из середины»; он оправдан, когда условие выхода естественно проверять в середине тела. Если условие можно записать в заголовке — пишите в заголовке: по нему сразу видно, когда цикл заканчивается. break во вложенном цикле выходит только из внутреннего.

Внутренний цикл выполняется целиком на каждой итерации внешнего. Таблица умножения — внешний цикл по строкам, внутренний по столбцам:

for (int row = 1; row <= n; row++) {
    for (int col = 1; col <= n; col++) {
        printf("%4d", row * col);
    }
    printf("\n");
}

n = 4:
   1   2   3   4
   2   4   6   8
   3   6   9  12
   4   8  12  16

Граница внутреннего цикла может зависеть от переменной внешнего: for (int k = 1; k <= row; k++) — в строке row выводится row символов, получается треугольник.

Таблица значений функции на отрезке [a; b] с шагом h. Вещественный счётчик напрашивается, но ошибается:

for (double x = 0; x <= 0.3; x += 0.1) {
    printf("%g\n", x);         /* 0  0.1  0.2 — точки 0.3 нет */
}

После трёх сложений x равно 0.30000000000000004 — чуть больше 0.3 (раздел 3). Надёжно — заранее посчитать число шагов и вести целый счётчик, а x вычислять от начала отрезка:

const double EPS = 1e-9;
int steps = (int)((b - a) / h + EPS);      /* число шагов с допуском */
for (int i = 0; i <= steps; i++) {
    double x = a + i * h;
    printf("%6.2f %10.4f\n", x, x * x - 2 * x);
}

a b h = 0 0.3 0.1:              a b h = 0 1 0.25:
  0.00     0.0000                 0.00     0.0000
  0.10    -0.1900                 0.25    -0.4375
  0.20    -0.3600                 0.50    -0.7500
  0.30    -0.5100                 0.75    -0.9375
                                  1.00    -1.0000