Анализ циклов

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

1. Как определить число итераций

Сначала установите начальное значение переменной, затем выясните, когда проверяется условие, и только после этого определяйте шаг изменения. Для цикла for границы обычно видны сразу. Например, for i in range(2, 8) в Python принимает значения \(2,3,4,5,6,7\), то есть выполняет тело 6 раз. Правая граница 8 не входит в диапазон.

В формуле \(a\) — начальное значение, \(b\) — граница остановки, \(d\) — шаг при движении к границе. Она подходит для последовательности значений \(a, a+d, a+2d,\ldots\), пока значение остаётся меньше \(b\) при положительном шаге. Для целых значений часто удобнее просто выписать несколько первых значений или применить формулу числа членов арифметической прогрессии.

2. Трассировка переменных

Трассировка особенно полезна, когда в теле цикла несколько присваиваний. Для каждой итерации записывают значения до выполнения тела, затем вычисляют команды строго сверху вниз и получают значения после итерации. Если одна команда меняет переменную, следующая использует уже новое значение.

1. Выпишите начальные значения всех переменных.
2. Определите, разрешён ли вход в цикл.
3. Для каждой итерации выполняйте команды в исходном порядке.
4. Запишите изменившиеся значения в таблицу.
5. После выхода отдельно проверьте итоговое условие и результат.

Если переменная увеличивается на постоянный шаг \(d\), после \(k\) итераций её значение равно \(x_k=x_0+kd\). Если она умножается на постоянный множитель \(q\), используется геометрическая последовательность: \(x_k=x_0q^k\).

3. Накопители и результат цикла

Во многих задачах одна переменная хранит накапливаемый результат: сумму, произведение, количество подходящих элементов или максимум. Такой приём называется накопителем в цикле. Перед началом нужно задать нейтральное начальное значение: 0 для суммы и счётчика, 1 для произведения. Для поиска максимума начальное значение выбирают осторожно: это может быть первый элемент или заведомо подходящая граница.

1s = 0
2for i in range(1, 5):
3    s = s + 2 * i
4print(s)

Здесь s получает добавки \(2,4,6,8\). После четырёх итераций результат равен \(20\). Если в условии есть проверка, например if i % 2 == 0, сначала определяют все значения счётчика, затем оставляют только подходящие и прибавляют их к накопителю. Условие с несколькими частями разбирайте с учётом составного условия.

4. Разобранный пример

1s := 1
2x := 2
3FOR i FROM 1 TO 4:
4    s := s + x
5    x := x * 2
6OUTPUT s

Цикл имеет четыре итерации: \(i=1,2,3,4\). Важно соблюдать порядок команд: сначала текущее значение x прибавляется к s, затем x удваивается.

5. Циклы, условия и досрочный выход

Если внутри цикла есть оператор выхода из цикла, число фактически выполненных итераций может быть меньше числа проходов по счётчику. Аналогично, оператор пропуска итерации завершает текущий проход раньше, но сам цикл продолжается. При анализе нужно отдельно отмечать: вошли ли в тело, встретилась ли команда выхода и какие команды были пропущены.

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