Краткое содержание
Этот урок открывает четвёртый раздел курса, посвящённый управлению потоком. Он объясняет, для чего нужен раздел: научить управлять порядком, в котором выполняются инструкции программы, с помощью ветвлений и циклов, и рассуждать об их правильности, то есть добиваться того, чтобы каждый случай был обработан, чтобы каждый цикл делал то, что должен, и чтобы он завершался; представляет четыре урока раздела и связывающую их нить; напоминает то, что раздел считает известным, прежде всего составные условия из раздела 3; формулирует задачу, которую решает раздел, задачу программы, которая вычисляет наибольший общий делитель за фиксированное число шагов и в зависимости от данных отвечает неверно или останавливается на делении на нуль; заранее представляет инвариант как инструмент, которым раздел будет обосновывать свои циклы; и показывает, куда он ведёт, в следующих разделах и в курсе «Программирование на C++ II».
Цели обучения
- Описывать последовательность содержания раздела и объяснять, что каждый урок даёт тому, который идёт за ним.
- Вспомнить составные условия из раздела 3 (логические связки, вычисление по короткой схеме и отрицание по законам де Моргана) и при необходимости повторить их.
- Заранее, на примере, представить инвариант как инструмент рассуждения: соотношение между переменными, которое повторение сохраняет и которое по окончании даёт результат.
- Понимать, что ожидается уметь по окончании раздела, и отличать это от того, чему предстоит научиться в следующих разделах.
Входная проверка
Прежде чем проходить раздел, полезно определить исходный уровень. Эта проверка является самопроверкой: она не оценивается, и её единственная цель состоит в том, чтобы направить занятия. Первые четыре вопроса касаются того, что раздел считает известным: отрицания составного условия, вычисления по короткой схеме, трассировки повторения из урока 1.1 и предела int. Следующие семь в порядке уроков касаются центральных идей раздела, и некоторые из них исходят из школьной математики: наибольшего общего делителя, записи суммы со знаком суммирования, завершения процедуры. Никто не обязан пока отвечать на них верно, а в некоторых из них «пока не знаю» является честным ответом: каждый ответ, верный или нет, объясняет суть дела и называет урок, где она разбирается. Те же умения измеряются снова в конце, в уроке итогов.
Перед началом раздела оцени свою отправную точку. Это короткая самопроверка: она не оценивается, а результат хранится только в твоём браузере.
Вопрос 1Из предыдущих разделовКаково отрицание условия
1 <= n && n <= 10?Отрицает каждую часть, но сохраняет конъюнкцию: забывает де Моргана. Кроме того, никакое число не бывает одновременно меньше 1 и больше 10, так что это условие всегда ложно.Связку меняет верно, но отношения отрицает неверно: лишний раз исключает границы 1 и 10, которые удовлетворяют исходному условию.Отрицает только первую часть.По де Моргану отрицание конъюнкции есть дизъюнкция отрицаний, а отрицание1 <= nестьn < 1, а неn <= 1. Разделу оно нужно в каждой цепочке ветвлений, потому что ветвьelseобрабатывает в точности отрицание предшествующих условий, и в каждом цикле, потому что при выходе верно отрицание его условия.Повторить: Отношения и логика
Вопрос 2Из предыдущих разделовПри
int d{0};иint n{5};что происходит при вычисленииd != 0 && n / d > 2?Не учитывает короткую схему: деление вообще не вычисляется.Конъюнкция с ложным операндом никак не может быть истинной.Выражение правильное; компилятор не знает значенияdво время выполнения.Первый операнд ложен, и короткая схема не вычисляет второй: страж слева защищает деление. Раздел превращает этого стража в явные ветвления и в условия циклов, которые защищают своё тело.Повторить: Отношения и логика
Вопрос 3Из предыдущих разделовДеление последовательными вычитаниями из урока 1.1 начинается с и и повторяет «пока , вычесть из и прибавить 1 к ». Сколько раз при и выполняется тело повторения?
Считает вычисления условия, которых на одно больше, чем итераций.Останавливает повторение при : читает как .Путает число итераций с начальным значением .Трассировка даёт : тело выполняется четыре раза, а условие вычисляется пять раз, потому что последнее вычисление и есть то, которое даёт ложь. Урок 4.2 записывает это повторение на C++ и превращает трассировку в таблицу.Повторить: От задачи к алгоритму
Вопрос 4Из предыдущих разделовЧто гарантирует стандарт о значении
46341 * 46341для 32-битногоint?Не учитывает диапазон типа: это число не помещается вint.Считает, что переполнение останавливается на границе; стандарт ничего не обещает.Тип результата определяют операнды, которые имеют типint, а не значение результата.Максимум равен . Раздел встречает это произведение там, где его не ищут: в условииd * d <= nцикла, перебирающего делители, которое переполняется как раз тогда, когда близко к максимуму.Повторить: Целые числа и их представление
Вопрос 5Программа содержит цепочку ветвлений:
if (score >= 50), которая выводит «Зачтено»;else if (score >= 90), которая выводит «Отлично»; иelse, которая выводит «Не зачтено». Что она выводит, еслиscoreравно 95?Считает, что побеждает самое строгое условие; побеждает первое выполненное.Считает, что выполняются все истинные ветви; в цепочке выполняется только одна.Это честный ответ: урок 4.1 это объясняет, и итоговая проверка вернётся к границам цепочки.В цепочке выполняется первая ветвь, условие которой истинно, а . Ветвь «Отлично» не выполняется никогда: её настоящий случай есть и , а он пуст. Урок 4.1 учит читать настоящий случай каждой ветви и упорядочивать условия.Повторить: Ветвления
Вопрос 6Какое из выражений ниже обозначает сумму ?
Складывает раз число , то есть получает : путает слагаемое с верхним пределом.Складывает : сдвигает пределы и теряет последнее слагаемое, это ошибка на единицу, типичная для циклов.Верхний предел не может быть самим индексом: выражение не имеет смысла.Индекс пробегает целые числа от 1 до , и каждое слагаемое есть само . Циклfor, который накапливает сумму, есть прямой перевод этой записи: переменная цикла есть индекс, её пределы суть пределы суммы, а тело прибавляет слагаемое.Повторить: Циклы
Вопрос 7При
int total{0};что выводитstd::println("{}", total);послеfor (int i{0}; i < 5; ++i) { total += i; }?Считает, чтоiдоходит до 5: читает<как<=.Путает накопитель со счётчиком: пять есть число итераций, а не сумма.Это честный ответ: урок 4.2 учит формеforи тому, как считать его итерации.Переменнаяiпринимает значения 0, 1, 2, 3 и 4, и ; когдаiравно 5, условие ложно и тело не выполняется. Это сумма из предыдущего вопроса с пределами 0 и 4.Повторить: Циклы
Вопрос 8Какое соотношение между переменными выполняется всякий раз, когда вычисляется условие, в делении последовательными вычитаниями (, ; пока , переходит в , а в )?
Верно только при выходе: пока повторение идёт, условие утверждает обратное.Верно только по окончании; до этого меньше частного.Это честный ответ: урок 4.3 учит находить и проверять это соотношение, и итоговая проверка спросит об этом снова.Оно верно в начале, потому что ; и если оно верно перед итерацией, то верно и после неё, потому что . При выходе к нему добавляется отрицание условия, , и вместе они дают результат. Такое соотношение называется инвариантом, и урок 4.3 превращает его в метод проектирования циклов и их обоснования.Повторить: Проектирование правильных циклов
Вопрос 9Процедура начинает с произвольного целого (положительного, нулевого или отрицательного) и повторяет «пока , вычесть 2 из ». Завершается ли она для всякого ?
Так бывает с условием ; с повторение останавливается, как только становится равным 0 или .При отрицательном условие ложно с самого начала, и тело не выполняется.Заключение верно, но довод нет: быть целым недостаточно; нужно, чтобы величина была натуральной, пока повторение идёт, и чтобы она убывала.Величина есть натуральное число, пока повторение идёт (это обеспечивает условие), и строго убывает: это вариант цикла, инструмент урока 1.1, которым урок 4.3 пользуется в каждом цикле. С «пока » ответ был бы другим: нечётное перескакивает через нуль.Повторить: Проектирование правильных циклов
Вопрос 10Каков наибольший общий делитель чисел 84 и 36?
Это общий делитель, но не наибольший.Это общий делитель, но не наибольший: не хватает множителя 3, который у них тоже общий.Это наименьшее общее кратное, а не наибольший общий делитель.Общие делители суть 1, 2, 3, 4, 6 и 12. Алгоритм Евклида получает его без поиска делителей: и , так что . Урок 4.4 записывает его в виде цикла и доказывает, почему он работает.Повторить: Численные алгоритмы
Вопрос 11До какого делителя достаточно дойти, чтобы, перебирая делители, решить, простое ли число 101?
Берёт половину: это верно, но в пять раз дольше, чем нужно.Перебирает всех кандидатов: это верно, но не использует того, что делители идут парами.Это честный ответ: урок 4.4 это доказывает.Если бы у 101 был делитель с , то делителем было бы и , и одно из двух было бы не больше . Достаточно проверить числа от 2 до 10: ни одно не делит 101, и оно простое. Урок 4.4 доказывает это правило и записывает его без корней и без произведений, которые переполняются.Повторить: Численные алгоритмы
Загрузка содержимого…