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

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

Урок Циклы научил записывать повторение; этот урок учит записывать его правильно и знать, почему оно правильно. Он начинается с шаблонов, из которых строится большинство циклов (счётчик, накопитель, максимум и минимум, сигнальное значение и флаг), и каждый из них определяется тем, что означает его переменная после каждой итерации. Это наблюдение ведёт к центральному понятию: инварианту, утверждению о переменных, которое верно перед первой итерацией и после каждой из них и которое вместе с условием выхода влечёт результат. Это индукция по числу итераций, и с ней цикл проектируется в обратном порядке: сначала то, что должно быть верно в конце, затем инвариант, и лишь в последнюю очередь тело. Завершение обосновывается вариантом цикла, уже представленным в уроке От задачи к алгоритму, и урок показывает три цикла, которые не завершаются: один с вещественным условием, один со счётчиком без знака и один, чей знаковый счётчик переполняется, а это неопределённое поведение. Завершает урок первое знакомство с отладчиком Visual Studio Code, который останавливает программу на строке и показывает её переменные итерация за итерацией.

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

  1. Распознавать в цикле шаблоны счётчика, накопителя, максимума и сигнального значения и использовать их для проектирования новых циклов.
  2. Формулировать инвариант простого цикла и устанавливать, что он сохраняется на произвольной итерации.
  3. Обосновывать завершение цикла целой величиной, которая убывает и ограничена снизу.
  4. Прослеживать выполнение цикла в отладчике Visual Studio Code с помощью точки останова и панели переменных.

Шаблоны

Что означает переменная

Большинство циклов не изобретаются: они собираются из немногих деталей, которые встречаются во всех программах. Каждая деталь есть переменная с инициализацией перед циклом, обновлением внутри него и, главное, смыслом, который верен после каждой итерации. Знать детали по их смыслу, а не по их форме, и есть то, что позволяет сочетать их без ошибок.

  • Счётчик равен тому, сколько данных обработано (или сколько из них удовлетворяют условию). Он инициализируется нулём, потому что перед первой итерацией не обработано ни одного, и обновляется через ++count, только когда есть что считать.
  • Накопитель равен комбинации обработанных данных: их сумме, их произведению. Он инициализируется нейтральным элементом операции (0 для суммы, 1 для произведения), потому что сумма никаких данных равна 0, а произведение никаких данных равно 1.
  • Максимум равен наибольшему из обработанных данных, а минимум, наименьшему. Максимума пустого набора данных не существует: поэтому его инициализируют первым элементом данных, а не числом, выбранным наугад.
  • Сигнальное значение есть значение во входных данных, которое не является элементом данных, а служит знаком того, что данные закончились. Шаблон требует читать один раз перед циклом и ещё раз в конце тела, как сделал урок Циклы, суммируя до нуля, так что условие рассматривает каждое значение до того, как оно обработано, и сигнальное значение никогда не учитывается как элемент данных.
  • Флаг есть bool, который показывает, произошло ли что-то хотя бы раз среди обработанных данных. Он инициализируется значением false и становится true в первый раз, когда это происходит; никакая последующая итерация не возвращает его к false.

Пример со всеми деталями

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

Программа на C++
#include <iostream>#include <print>​int main(){    double threshold{};    std::cin >> threshold;    int count{0};          // счётчик: обработанные измерения    int aboveCount{0};     // счётчик: измерения выше порога    double total{0.0};     // накопитель: сумма измерений    double largest{0.0};   // максимум: имеет смысл, только если count > 0    bool dryDay{false};    // флаг: был день без дождя    double value{};    std::cin >> value;    while (std::cin && value >= 0.0) {        if (count == 0 || value > largest) {            largest = value;        }        ++count;        total += value;        if (value > threshold) {            ++aboveCount;        }        if (value == 0.0) {            dryDay = true;        }        std::cin >> value;    }    if (count == 0) {        std::println("Нет измерений.");    } else {        std::println("Измерений: {}; среднее: {:.2f} мм", count, total / count);        std::println("Максимум: {:.1f} мм; дней выше {:.1f} мм: {}", largest, threshold, aboveCount);        std::println("Были дни без дождя: {}", dryDay ? "да" : "нет");    }}
Ввод программы
104.5 0 12.5 21.5 7.5 -1
Вывод
Измерений: 5; среднее: 9.20 ммМаксимум: 21.5 мм; дней выше 10.0 мм: 2Были дни без дождя: да

Четыре решения заслуживают комментария. Условие count == 0 || value > largest инициализирует максимум первым элементом данных без отдельного чтения: на первой итерации счётчик равен 0 и присваивание происходит всегда; на последующих, только если элемент данных превосходит максимум. Сравнение value == 0.0 точное, потому что значение было прочитано, а не вычислено: запись 0 превращается в точный ноль, а предостережение урока Числа с плавающей точкой против == относится к результатам операций. Условие цикла включает std::cin, так что ввод, который кончается без сигнального значения, тоже завершает цикл. И среднее вычисляется, только если измерения есть: при count, равном 0, выражение total / count было бы 0/00/0, что в арифметике с плавающей точкой не ошибка, а значение «не число», которое программа вывела бы без предупреждения.

ПримерПеременные итерация за итерацией

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

  1. Перед циклом: порог равен 10, счётчики и накопитель равны 0, флаг ложен, и первое измерение, 4.5, уже прочитано. Максимум равен 0, но это значение ничего не означает, пока count равен 0.

  2. Первая итерация: count равен 0, так что 4.5 становится максимумом; счётчик увеличивается до 1, а сумма до 4.5. Читается 0.

  3. Вторая итерация: 0 не превосходит максимум, но поднимает флаг. Читается 12.5.

  4. Третья итерация: 12.5 есть новый максимум и превышает порог: aboveCount увеличивается до 1. Читается 21.5.

  5. Четвёртая итерация: 21.5 есть новый максимум и тоже превышает порог. Читается 7.5.

  6. Пятая итерация: 7.5 не меняет ни максимум, ни aboveCount; сумма достигает 46. Читается −1-1.

  7. Условие рассматривает −1-1, которое отрицательно: цикл завершается, не обработав его. Среднее равно 46/5=9.246 / 5 = 9.2.

Заметим, что в каждой строке рисунка каждая переменная удовлетворяет своему смыслу относительно измерений, обработанных к этому моменту: total есть их сумма, largest их максимум, dryDay говорит, был ли среди них ноль. Это свойство, верное после каждой итерации, имеет имя.