Перейти к содержимому
Topos Uranos
Русский

Циклы

Краткое содержание

Урок От задачи к алгоритму выделил три способа составлять шаги: следование, ветвление и повторение. У первых двух уже есть своя запись в C++; этот урок даёт её третьему. Он изучает три формы цикла: while, который вычисляет своё условие перед каждой итерацией и может ни разу не выполнить тело; do, который вычисляет его после и выполняет тело хотя бы один раз; и for, который собирает в одной строке инициализацию, условие и приращение переменной, управляющей повторением. Урок показывает, что все три выражают один и тот же механизм, так что каждая форма преобразуется в другие, и учит выбирать самую ясную; знакомит с break и continue, которые меняют ход итерации; и завершается вложенными циклами, внутреннее тело которых выполняется столько раз, сколько даёт некоторая сумма. Инструмент, сопровождающий весь урок, есть таблица трассировки: выполнить цикл вручную, итерация за итерацией, значит предсказать, сколько раз выполнится его тело и что он оставит после выхода.

Цели обучения

  1. Писать цикл while, do или for для заданного повторения, выбирая самую ясную форму.
  2. Выполнять цикл вручную с таблицей трассировки и предсказывать, сколько раз выполнится тело.
  3. Преобразовывать цикл из одной формы в другую, сохраняя его смысл.
  4. Писать вложенные циклы и вычислять, сколько раз выполняется внутреннее тело.

while

Форма цикла while

Цикл while записывается так:

Код на C++
while (условие) {    тело}

Его смысл формулируется в три шага: вычисляется условие; если оно ложно, цикл завершается и выполнение продолжается после закрывающей его фигурной скобки; если истинно, выполняется тело и происходит возврат к первому шагу. Каждое выполнение тела называется итерацией (или проходом). Условие есть логическое выражение вроде тех, что рассматривал урок Отношения и логика, а тело есть блок; правило фигурных скобок, установленное уроком Ветвления, действует и здесь: тело цикла всегда заключается в фигурные скобки, даже если в нём одна инструкция.

Из определения следуют два вывода. Первый: условие вычисляется перед каждой итерацией, так что если оно ложно с самого начала, тело не выполняется ни разу. Второй: чтобы цикл завершился, тело должно менять что-то из того, что читает условие; если ничего не меняется, условие, однажды оказавшееся истинным, будет истинным всегда. Однако менять недостаточно: урок От задачи к алгоритму показал, что нужна натуральная величина, убывающая на каждой итерации, вариант цикла, а урок Проектирование правильных циклов превратит её в метод.

Деление последовательными вычитаниями

Первым алгоритмом с повторением в этом курсе было деление последовательными вычитаниями: пока остаток не меньше делителя, из него вычитается делитель, а к частному прибавляется единица. На C++ этот алгоритм переносится почти слово в слово.

ПримерЧастное и остаток вычитаниями
Программа на C++
#include <iostream>#include <print>​int main(){    int a{};    int b{};    std::cin >> a >> b;    int q{0};    int r{a};    while (r >= b) {        r -= b;        ++q;    }    std::println("{} = {} · {} + {}", a, b, q, r);}
Ввод программы
23 7
Вывод
23 = 7 · 3 + 2

Строки 9 и 10 дают переменным начальные значения: ещё ничего не вычтено, поэтому частное равно 0, а остаток равен всему делимому. Строка 11 есть условие шага 2 алгоритма; строки 12 и 13 образуют тело. Программа предполагает, как и алгоритм, что a≥0a \geq 0 и b>0b > 0: при b=0b = 0 строка 12 не меняла бы r и цикл не завершился бы.

Таблица трассировки

Выполнить цикл вручную значит заполнить таблицу: одна строка на итерацию, один столбец на переменную и ещё один для условия, вычисленного в начале итерации. Строка 0 фиксирует состояние перед первым вычислением условия; последняя строка фиксирует вычисление, которое оказывается ложным и завершает цикл.

ПримерТрассировка деления 23 на 7

Доказательство

  1. Перед циклом выполняются строки 9 и 10: q=0q = 0 и r=23r = 23. Это строка 0 таблицы; условие ещё не вычислялось.

  2. Первая итерация. Условие 23≥723 \geq 7 истинно, поэтому выполняется тело: rr становится равным 16, а qq равным 1. Затем выполнение возвращается к строке 11.

  3. Вторая итерация. Условие 16≥716 \geq 7 истинно: rr становится равным 9, а qq равным 2.

  4. Третья итерация. Условие 9≥79 \geq 7 истинно: rr становится равным 2, а qq равным 3.

  5. Четвёртое вычисление, 2≥72 \geq 7, даёт ложь: тело не выполняется, цикл завершается, и строка 15 выводит 23=7⋅3+223 = 7 \cdot 3 + 2.

Трассировка учит считать. Тело выполнилось три раза, столько же, сколько составляет частное, а условие вычислялось четыре раза: по одному на итерацию и ещё одно, неудачное. Это соотношение верно для любого while, завершающегося по своему условию: если тело выполняется kk раз, условие вычисляется k+1k + 1 раз. И крайний случай это подтверждает: при входных данных 5 7 первое вычисление, 5≥75 \geq 7, уже ложно, тело выполняется ноль раз, и программа выводит 5=7⋅0+55 = 7 \cdot 0 + 5, что верно. Правильно написанный while без дополнительного кода справляется со случаем, когда повторять нечего.