От задачи к алгоритму

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

В этом уроке нет кода, и не по недосмотру: алгоритм предшествует программе, и тот, кто не умеет точно описать, что нужно сделать, не сумеет сказать этого и на C++. Сначала мы учимся специфицировать задачу, то есть объявлять, какие данные она получает, какой результат должна выдать и какое отношение их связывает, и видим, что одна и та же формулировка допускает разные спецификации. Затем алгоритм определяется как конечная, определённая и массовая процедура, и в пронумерованных шагах записывается алгоритм деления последовательным вычитанием. Мы учимся выполнять алгоритм вручную с таблицей трассировки, которая на протяжении всего курса будет первым инструментом, чтобы понимать и чтобы отлаживать. Вводятся три способа соединять шаги (следование, ветвление и повторение), которыми записывается любой алгоритм, и мы учимся обосновывать, что повторение завершается, с помощью величины, которая уменьшается на каждой итерации и не может убывать бесконечно.

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

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

Что такое вычислительная задача

Вычислительная задача есть отношение между двумя видами данных: теми, что получены, которые называются входом, и теми, что должны быть выданы, которые называются выходом. Решить её значит не получить ответ для одного случая, а располагать методом, который для каждого допустимого входа выдаёт выход, удовлетворяющий отношению. «Сколько будет 17, делённое на 5?» есть вопрос; «даны два целых числа, найти их частное и остаток» есть задача, потому что она говорит обо всех парах целых чисел сразу.

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

ПримерМаксимум трёх чисел

Обыденная формулировка: «найти наибольшее из трёх чисел». Спецификация:

Вход: три числа $x$ , $y$ , $z$ (целые или десятичные, без других условий).
Выход: число $m$ .
Отношение: $m$ есть одно из трёх данных, и ни одно из них не больше $m$ ; то есть $m \geq x$ , $m \geq y$ и $m \geq z$ .

Отношение не говорит «наибольшее из трёх», ведь именно это и требовалось уточнить, а даёт два проверяемых условия. Первое требует, чтобы $m$ было одним из данных (без него число 1000 удовлетворяло бы второму почти для любого входа); второе требует, чтобы ни одно из данных его не превосходило. И спецификация попутно снимает сомнение, которое формулировка оставляла открытым: если два данных вместе достигают максимума, как в $(4, 9, 9)$ , выход равен $9$ , и никакой ошибки в этом нет.

Одна и та же формулировка допускает разные спецификации, и выбор между ними есть решение, а не недосмотр. Самый поучительный случай связан с целочисленным делением. Для целых $a \geq 0$ и $b > 0$ все согласны: частное $q$ и остаток $r$ суть единственные целые числа, удовлетворяющие условиям

a = b \cdot q + r, \quad 0 \leq r < b

Так, для $a = 17$ и $b = 5$ получаем $q = 3$ и $r = 2$ , потому что $17 = 5 \cdot 3 + 2$ . Но формулировка «разделить два целых числа» не говорит, что делать, если $a$ отрицательно, и вопрос не праздный: для $a = -7$ и $b = 2$ есть два разумных ответа.

ПримерДве спецификации деления с отрицательным делимым

Первая спецификация: остаток никогда не бывает отрицательным, $0 \leq r < b$ . Тогда $-7 = 2 \cdot (-4) + 1$ , и выход таков: $q = -4$ , $r = 1$ . Именно её изучает математика, в уроке «Делимость и деление с остатком» курса «Алгебра и геометрия I».

Вторая спецификация: частное есть результат деления с десятичными знаками, у которого отброшена дробная часть, то есть округлённый к нулю; остаток есть то, чего недостаёт, и он имеет знак делимого. Тогда $-7 / 2 = -3{,}5$ усекается до $-3$ , и $-7 = 2 \cdot (-3) + (-1)$ : выход таков: $q = -3$ , $r = -1$ .

Обе удовлетворяют равенству $a = b \cdot q + r$ ; они различаются условием, наложенным на остаток. Ни одна из них не ошибочна, но программа, которая пользуется одной, полагая, что пользуется другой, будет давать неверные результаты для отрицательных чисел. Забежим вперёд: C++ принимает вторую, как будет видно в уроке Арифметические операции; кто ждёт первую, будет неприятно удивлён.

Есть и третий вариант, самый частый на практике: исключить этот случай предусловием. Если спецификация требует $a \geq 0$ , проблема отрицательных чисел исчезает, не потому что она решена, а потому что тот, кто пользуется решением, обязался её не ставить. Чего нельзя делать, так это оставлять вопрос нерешённым. И по той же причине спецификация требует $b > 0$ : при $b = 0$ не существует $q$ и $r$ , удовлетворяющих отношению, и контракт должен это оговаривать.

Частая ошибка состоит в том, чтобы специфицировать примером: «выход для 17 и 5 равен 3 и 2». Пример иллюстрирует, но не специфицирует, потому что не говорит, что происходит с остальными входами; бесконечно много разных отношений совпадают в одном случае. Спецификация записывается как общее условие, а примеры служат затем для того, чтобы её проверить.

Алгоритмы

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

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

С некоторой вольностью алгоритмом называют и процедуру, которая определённа и завершается, но для какого-то допустимого входа не удовлетворяет постусловию: строго говоря, это алгоритм для другой задачи, и мы будем говорить, что он неправилен для специфицированной задачи. Так мы будем говорить в задачах этого урока, которые опровергают неправильные алгоритмы контрпримером.

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

Алгоритмы этого курса записываются сначала пронумерованными шагами, по-русски, с некоторыми соглашениями. Данные, которые меняются во время работы алгоритма, обозначаются буквами или словами, как $q$ или $r$ , и называются переменными. Пишут « $r$ принимает значение $r - b$ », чтобы сказать, что вычисляется $r - b$ при текущем значении $r$ и результат становится новым значением $r$ ; прежнее значение теряется. В сокращённой записи, которая используется в заметках, та же инструкция записывается стрелкой влево, которая на клавиатуре набирается как r <- r - b. Инструкции выполняются в порядке их номеров, если только одна из них не предписывает иное.

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

Задача та, что специфицирована в предыдущем параграфе: вход, два целых числа $a \geq 0$ и $b > 0$ ; выход, два целых числа $q$ и $r$ , для которых $a = b \cdot q + r$ и $0 \leq r < b$ . Идея в том, чтобы раздавать: из $a$ отнимают группы по $b$ , пока это возможно, считают отнятые группы, и то, что осталось, есть остаток.

$q$ принимает значение $0$ , и $r$ принимает значение $a$ .
Пока выполняется $r \geq b$ , повторять шаги 3 и 4; когда это перестанет выполняться, перейти к шагу 5.
$r$ принимает значение $r - b$ .
$q$ принимает значение $q + 1$ ; вернуться к шагу 2.
Выдать $q$ и $r$ и завершить работу.

Шаг 2 есть вопрос, который задаётся каждый раз: перед первой итерацией и после каждой. Шаги 3 и 4 образуют тело повторения, то, что повторяется. Ничто не оставлено на усмотрение исполнителя: в каждый момент есть ровно одна следующая инструкция.

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

Наконец, стоит отделить алгоритм от его записи. Алгоритм деления вычитанием один и тот же, записан ли он по-русски, в виде схемы, на C++ или на любом другом языке программирования: его определяет последовательность операций, а не слова. Программа есть запись алгоритма на языке, который может исполнить машина, и урок Программы, компиляторы и C++ объяснит, как происходит это исполнение. Если это так, программа может быть неверной двумя совершенно разными способами: потому что алгоритм неправилен, и тогда никакой язык его не спасёт, или потому что алгоритм правилен, но записан неверно. Различать эти два случая значит сделать половину работы по отладке, и поэтому курс всегда сначала записывает алгоритм.

Выполнение алгоритма вручную

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

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

ПримерТрассировка деления 17 на 5

Выполним деление последовательным вычитанием при $a = 17$ и $b = 5$ . Стрелка на рисунке указывает шаг, который только что выполнен; пунктирная линия напоминает, что шаг 4 возвращает к шагу 2.

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

$(q, r) = (0, 17)$
Шаг 1: задаются начальные значения. Вход удовлетворяет предусловию, потому что $17 \geq 0$ и $5 > 0$ .
$(q, r) = (1, 12)$
Первая итерация. На шаге 2 проверяется, что $17 \geq 5$ , поэтому выполняется тело: шаг 3 отнимает группу из пяти, а шаг 4 её считает.
$(q, r) = (2, 7)$
Вторая итерация: $12 \geq 5$ , и тело выполняется снова.
$(q, r) = (3, 2)$
Третья итерация: $7 \geq 5$ , и тело выполняется снова.
$17 = 5 \cdot 3 + 2, \quad 0 \leq 2 < 5$
На шаге 2 условие не выполняется, потому что $2 < 5$ : алгоритм переходит к шагу 5 и выдаёт $q = 3$ и $r = 2$ . Выход удовлетворяет постусловию.

Полная таблица имеет двенадцать строк: шаг 1, три итерации по три строки (шаги 2, 3 и 4), вычисление условия, давшее ложь, и выдача результата.

Два замечания о таблице. Первое: число итераций равно частному, $3$ , а шаг 2 выполнился на один раз больше, чем тело, $4$ раза; так бывает всегда в повторении такого вида, потому что именно при последнем вычислении условие не выполняется. Второе: трассировка показывает то, чего текст алгоритма не говорит с первого взгляда; если $a < b$ , например $a = 3$ и $b = 5$ , условие не выполняется с первого же раза, тело не выполняется ни разу, и выход таков: $q = 0$ , $r = 3$ , что правильно, потому что $3 = 5 \cdot 0 + 3$ . Забыть случай, когда повторение не выполняется, есть одна из самых частых ошибок при проектировании алгоритмов, и трассировка на маленьких входах её обнаруживает.

Трассировка одного случая не доказывает, что алгоритм правилен: она проверяет один случай. Но хорошо выбранная трассировка (обычный случай, граничный случай, случай, когда повторение не выполняется) обнаруживает большую часть ошибок, а та, что не проходит, показывает, где они. Урок Проектирование правильных циклов научит переходить от случаев к доказательству.

Следование, ветвление и повторение

Если присмотреться, алгоритмы строятся из очень немногих деталей. Есть элементарные инструкции (присвоить значение переменной, выдать результат) и три способа их соединять.

Следование: одна инструкция за другой, по порядку. Шаги 3 и 4 деления образуют следование: сначала вычитают, потом считают.
Ветвление: в зависимости от того, выполняется ли условие, выполняется одна часть или другая (или одна часть или ничего). «Если $y > m$ , то $m$ принимает значение $y$ » есть ветвление.
Повторение: пока выполняется условие, некоторая часть выполняется снова и снова. Шаг 2 деления вместе со своим телом есть повторение.

Каждая форма имеет один вход и один выход, и её внутренность в свою очередь может быть любой из трёх: тело повторения может содержать ветвления, ветвь ветвления может содержать повторение, и так далее. Если это так, тремя формами строятся алгоритмы любой сложности, подобно тому как из немногих деталей, подходящих друг к другу, строится любое здание. То, что их достаточно для выражения любого алгоритма, есть известный результат теории программирования (его доказали Коррадо Бём и Джузеппе Якопини в 1966 году); здесь он не доказывается, но весь курс его подтверждает: программы, которые будут в нём написаны, сколь бы длинными они ни были, не будут использовать ничего, кроме этих трёх форм, записанных на C++ как if для ветвления и while или for для повторения, в уроках Ветвления и Циклы.

Удобная нотация, чтобы видеть форму алгоритма, есть блок-схема: каждая инструкция изображается прямоугольником, каждое условие ромбом с двумя выходами (выполнено, что на рисунке помечено $1$ , и не выполнено, $0$ ), а стрелки указывают, какой шаг следующий. Это нотация, а не цель: она помогает охватить взглядом небольшой алгоритм, но не масштабируется, и никто не пишет большую программу, рисуя её.

ПримерТри формы и их композиция

Рисунок изображает три формы с обобщёнными инструкциями $A$ и $B$ и условием $c$ , а затем соединяет их в блок-схему деления последовательным вычитанием.

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

$A ; B$
Следование: выполняется $A$ , а затем $B$ ; есть один вход и один выход.
$c = 1 \Rightarrow A, \quad c = 0 \Rightarrow B$
Ветвление: если $c$ выполнено, выполняется $A$ ; иначе $B$ . Обе ветви сходятся в один выход.
$c, A, c, A, \ldots, c$
Повторение: вычисляется $c$ ; если оно выполнено, выполняется $A$ и снова вычисляется $c$ ; иначе происходит выход. Условие вычисляется на один раз больше, чем тело.
$a = b \cdot q + r, \quad 0 \leq r < b$
Композиция: деление последовательным вычитанием есть следование (начальные значения, повторение, выдача результата), у которого повторение имеет телом другое следование (вычесть, сосчитать).

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

Завершается ли?

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

Чтобы обосновать, что повторение завершается, ищут величину, вычисляемую по переменным, которая удовлетворяет двум условиям: она есть натуральное число (целое и неотрицательное), пока повторение продолжается, и строго убывает на каждой итерации. Если это так, повторение завершается: строго убывающая последовательность натуральных чисел не может быть бесконечной, потому что каждая итерация уменьшает её хотя бы на единицу, а от натурального $n$ до нуля не больше $n$ ступенек. Такую величину называют вариантом цикла или ограничивающей функцией, и урок Проектирование правильных циклов будет использовать её систематически.

ПримерВариант цикла в делении вычитанием

В делении последовательным вычитанием вариантом цикла служит $r$ . Пока повторение продолжается, $r \geq b > 0$ , так что $r$ есть натуральное число. На каждой итерации $r$ принимает значение $r - b$ , и поскольку $b > 0$ (предусловие), новое значение строго меньше. Следовательно, повторение завершается, и происходит это не более чем через $a$ итераций (на самом деле ровно через $q$ итераций, по частному).

Обратите внимание, где использовано предусловие $b > 0$ . Если выполнить алгоритм при $b = 0$ , шаг 3 оставляет $r$ неизменным, условие $r \geq 0$ выполняется всегда, и повторение не завершается никогда: алгоритм не ошибочен, просто ему дали вход, который контракт исключал. А если бы $b$ было отрицательным, $r$ возрастало бы на каждой итерации. Предусловие не есть украшение: это ровно то, что нужно, чтобы рассуждение работало.

Оба условия варианта необходимы, и ошибиться легко в любом из них. Рассмотрим процедуру, которая должна решать, чётно ли натуральное $n$ : «пока $n \neq 0$ , $n$ принимает значение $n - 2$ ; если дошли до нуля, $n$ было чётным». Величина $n$ убывает на каждой итерации, и всё же процедура не завершается, если $n$ нечётно: при $n = 5$ она проходит через $3$ , $1$ , $-1$ , $-3$ , и условие $n \neq 0$ никогда не перестаёт выполняться. Не выполняется другое условие: $n$ перестаёт быть натуральным, потому что условие повторения не мешает ему опуститься ниже нуля. Исправление состоит в том, чтобы повторять, пока $n \geq 2$ , и в конце решать по оставшемуся значению, $0$ или $1$ ; теперь $n$ натурально на каждой итерации, потому что вычитание происходит только при $n \geq 2$ , и убывает: процедура завершается.

Решить, завершается ли повторение, не всегда легко. Знаменитый пример: начиная с натурального $n \geq 1$ , пока $n \neq 1$ , если $n$ чётно, его делят на два, а если нечётно, заменяют на $3n + 1$ . При $n = 6$ последовательность такова: $6, 3, 10, 5, 16, 8, 4, 2, 1$ , и она завершается. Никто не нашёл $n$ , для которого она не завершалась бы, и это проверено на компьютерах для огромного количества значений; но никому не удалось доказать, что она завершается всегда: это гипотеза Коллатца, открытая проблема математики. Ни одна известная величина не убывает на каждой итерации. Мораль для программиста скромна и тверда: алгоритм, завершение которого не удаётся обосновать, не закончен.

Частые ошибки

Двусмысленные шаги. «Повторить несколько раз», «пока не станет хорошо», «взять подходящее число». Каждый шаг должен быть выполним без понимания задачи; иначе он записан плохо.
Забытый случай, когда повторение не выполняется. Любое повторение с условием в начале может выполнить своё тело ноль раз. Всегда нужно спрашивать себя, что выдаёт алгоритм в этом случае, и трассировка на минимальном входе на это отвечает.
Спецификация примером. «Для 17 и 5 даёт 3 и 2» не есть спецификация; отношение записывается как общее условие, а пример его иллюстрирует.
Смешение алгоритма с его программой. В программе, которая работает неверно, может быть ошибочен алгоритм или ошибочна его запись. Кто не записал алгоритм заранее, не знает, что из двух искать.
Завершение, принятое на веру. Недостаточно, чтобы величина убывала: она должна, кроме того, оставаться натуральной, пока продолжается повторение.

Решённые задачи

Решённая задача 1Наибольшее из трёх чисел при равенствах

Написать алгоритм, удовлетворяющий спецификации максимума трёх чисел из первого параграфа, и выполнить его вручную для входов $(7, 2, 5)$ и $(4, 9, 9)$ .

Решение

$m = x$
Идея: просматривать вход, храня наибольшее из уже просмотренных в переменной $m$ . Первый шаг: $m$ принимает значение $x$ . После него $m$ есть максимум просмотренных данных, а это только $x$ .
$m = \max(x, y, z)$
Второй шаг: если $y > m$ , то $m$ принимает значение $y$ . Третий шаг: если $z > m$ , то $m$ принимает значение $z$ . Четвёртый шаг: выдать $m$ . Это три инструкции в следовании, две из них ветвления без альтернативной ветви.
$(x, y, z) = (7, 2, 5) \Rightarrow m = 7$
Трассировка для $(7, 2, 5)$ : после первого шага $m = 7$ ; на втором $2 > 7$ ложно, и $m$ не меняется; на третьем $5 > 7$ ложно, и $m$ не меняется. Выдаётся $7$ .
$(x, y, z) = (4, 9, 9) \Rightarrow m = 9$
Трассировка для $(4, 9, 9)$ : после первого шага $m = 4$ ; на втором $9 > 4$ , и $m$ становится равным $9$ ; на третьем $9 > 9$ ложно, и $m$ не меняется. Выдаётся $9$ , и это правильно: равенство не требует особой обработки.
$m \geq x, \quad m \geq y, \quad m \geq z$
Обоснование: после каждого шага $m$ есть одно из просмотренных данных, и ни одно из них его не превосходит. Это верно после первого шага, и каждое ветвление это сохраняет: если новое данное больше, оно становится $m$ ; если нет, оно не превосходит $m$ . В конце просмотрены все три, и $m$ удовлетворяет постусловию.
$(x, y, z) = (4, 9, 9) \Rightarrow p \in \{2, 3\}$
Если бы было написано $y \geq m$ вместо $y > m$ , результат был бы тем же, потому что при равенстве присваивается равное значение. Выбор между $>$ и $\geq$ был бы важен, если бы требовалась ещё и позиция максимума: с $>$ выдаётся первая из равных позиций, а с $\geq$ последняя, которую формула обозначает $p$ .

Решённая задача 2Високосный год, исправленный контрпримером

В григорианском календаре год високосный, если он делится на $4$ , за исключением делящихся на $100$ , которые високосны, только если делятся ещё и на $400$ . Студент предлагает алгоритм «если год делится на $4$ , выдать да; иначе выдать нет». Найти год, на котором он ошибается, и написать правильный алгоритм с его спецификацией.

Решение

$(4 \mid n \wedge \neg (100 \mid n)) \vee 400 \mid n$
Спецификация. Вход: целое число $n \geq 1583$ (григорианский календарь действует с октября 1582 года). Выход: да или нет. Отношение: выход равен да ровно тогда, когда $n$ делится на $4$ и не делится на $100$ или делится на $400$ .
$1900 = 4 \cdot 475, \quad 1900 = 400 \cdot 4 + 300$
Предложенный алгоритм прав для большинства лет, и поэтому кажется правильным. Чтобы его опровергнуть, достаточно года, делящегося на $100$ и не делящегося на $400$ : $1900$ делится на $4$ , и алгоритм говорит да; но $1900$ не был високосным.
$400 \mid n, \quad 100 \mid n, \quad 4 \mid n$
Исправленный алгоритм из трёх ветвлений, следующих цепочкой. Шаг 1: если $n$ делится на $400$ , выдать да и завершить работу. Шаг 2: если $n$ делится на $100$ , выдать нет и завершить работу. Шаг 3: если $n$ делится на $4$ , выдать да; иначе выдать нет.
$2000, \quad 1900, \quad 2024, \quad 2023$
Порядок вопросов существен: они идут от самого частного правила к самому общему. Если сначала спросить о числе $4$ , год $1900$ получит да, не дойдя до исключения. Трассировка для четырёх лет, по одному на каждый случай: $2000$ (шаг 1: да), $1900$ (шаг 2: нет), $2024$ (шаг 3: да), $2023$ (шаг 3: нет).
$4 \mid 1900 \wedge \neg (400 \mid 1900)$
Урок здесь не только о календарях: алгоритм опровергается одним-единственным контрпримером, и контрпримеры ищут на границах правил, а не в обычных случаях. Испытания на $2024$ , $2020$ и $2016$ ничего бы не обнаружили.

Решённая задача 3Сколько итераций делает деление вычитанием

Выполнить вручную деление последовательным вычитанием при $a = 20$ и $b = 5$ , а также при $a = 0$ и $b = 7$ . Затем обосновать, что для любого допустимого входа алгоритм завершается ровно через $q$ итераций и что его выход удовлетворяет постусловию.

Решение

$20 = 5 \cdot 4 + 0$
Трассировка при $a = 20$ , $b = 5$ : $r$ проходит значения $20$ , $15$ , $10$ , $5$ , $0$ , а $q$ значения $0$ , $1$ , $2$ , $3$ , $4$ . При пятом вычислении условие $0 \geq 5$ не выполняется. Выход: $q = 4$ , $r = 0$ . Здесь граничный случай есть деление нацело: четвёртая итерация выполняется, потому что $5 \geq 5$ , и поэтому условие должно быть $\geq$ , а не $>$ .
$0 = 7 \cdot 0 + 0$
Трассировка при $a = 0$ , $b = 7$ : при первом же вычислении условие $0 \geq 7$ не выполняется; тело не выполняется ни разу. Выход: $q = 0$ , $r = 0$ , и это правильно.
$\dato{conserva}{b \cdot (q + 1) + (r - b) = b \cdot q + r = a}$
Отношение, которое сохраняется. Перед первой итерацией $b \cdot q + r = b \cdot 0 + a = a$ . На каждой итерации $r$ уменьшается на $b$ , а $q$ увеличивается на $1$ , так что величина $b \cdot q + r$ не меняется. Следовательно, равенство верно после каждой итерации.
$r_0 > r_1 > r_2 > \cdots \geq 0$
Завершение. Пока продолжается повторение, $r \geq b > 0$ , и $r$ есть натуральное число; на каждой итерации оно уменьшается на $b \geq 1$ . Строго убывающая последовательность натуральных чисел конечна: повторение завершается.
$a = b \cdot q + r, \quad 0 \leq r < b$
По завершении условие не выполнилось: $r < b$ . Кроме того, $r \geq 0$ , потому что $b$ вычитается только при $r \geq b$ . Вместе с сохраняющимся отношением это даёт, что выход удовлетворяет постусловию; а поскольку $q$ считает итерации, число итераций равно частному.

Упражнения онлайн

Упражнение 1Сосчитать итерации

Выполнить вручную следующий алгоритм и записать в поле значение, которое он выдаёт, только число.

$n$ принимает значение $29$ , и $k$ принимает значение $0$ .
Пока выполняется $n > 1$ , повторять шаги 3 и 4; когда это перестанет выполняться, перейти к шагу 5.
Если $n$ чётно, $n$ принимает значение $n / 2$ ; если нечётно, $n$ принимает значение $n + 1$ .
$k$ принимает значение $k + 1$ ; вернуться к шагу 2.
Выдать $k$ .

Браузер сразу проверяет твой ответ, не оценивая его.

Напиши здесь свой ответ

Подсказка

Составь таблицу: на первой итерации $n$ переходит от $29$ к $30$ . Считай одну итерацию на каждое изменение $n$ , пока $n$ не станет равным $1$ .

Упражнение 2Недостающее условие

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

Браузер сразу проверяет твой ответ, не оценивая его.

Напиши здесь свой ответ

Подсказка

Выполни алгоритм вручную при $a = 10$ и $b = 5$ : вторая итерация должна произойти, хотя остаток равен ровно $5$ .

Задачи для самостоятельного решения

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

Задача для самостоятельного решения 1Спецификация упорядочения трёх чисел

Написать спецификацию задачи «упорядочить три числа» (вход, выход и отношение) и указать, какие решения она заставляет принять, которых формулировка не принимала. Затем проверить, что спецификация отвергает для входа $(5, 2, 5)$ два таких выхода: $(2, 5, 6)$ и $(2, 5, 5, 5)$ , и допускает $(2, 5, 5)$ .

Подсказка

«Упорядоченный» выход может не иметь ничего общего со входом. Какое условие связывает числа выхода с числами входа, включая повторяющиеся? По возрастанию или по убыванию? Строго или нет?

Ответ

Вход: три числа $x$ , $y$ , $z$ . Выход: три числа $u$ , $v$ , $w$ . Отношение: $u \leq v \leq w$ , и $(u, v, w)$ есть перестановка $(x, y, z)$ , то есть содержит те же значения с теми же повторениями. Решения, которых формулировка не принимала: направление (здесь от меньшего к большему); то, что порядок нестрогий ( $\leq$ , а не $<$ , потому что при повторяющихся значениях строгий порядок невозможен); и то, что выход должен быть перестановкой. Выход $(2, 5, 6)$ упорядочен, но содержит число $6$ , которого не было; в $(2, 5, 5, 5)$ четыре значения; $(2, 5, 5)$ удовлетворяет обоим условиям. Без условия перестановки $(0, 0, 0)$ было бы правильным выходом для любого входа.

Задача для самостоятельного решения 2Цифры числа справа налево

Написать алгоритм пронумерованными шагами, который получает натуральное $n$ и выдаёт его цифры от последней к первой (для $4072$ выдаёт $2$ , $7$ , $0$ , $4$ ), используя только частное и остаток от деления на $10$ . Выполнить его вручную для $4072$ и для $0$ и обосновать, что он завершается для любого $n$ .

Подсказка

Остаток от деления на $10$ есть последняя цифра, а частное есть число без неё. Реши, задаётся ли условие до или после выдачи цифры, и посмотри, что происходит при $n = 0$ , у которого одна цифра.

Ответ

Правильный алгоритм: (1) выдать остаток от деления $n$ на $10$ ; (2) $n$ принимает значение частного от деления $n$ на $10$ ; (3) если $n > 0$ , вернуться к шагу 1; иначе завершить работу. Вопрос стоит после тела, так что тело выполняется хотя бы один раз: при $n = 0$ выдаётся $0$ , его единственная цифра. Если бы вопрос задавался в начале («пока $n > 0$ »), при $n = 0$ ничего не было бы выдано; это ошибка забытого случая, когда повторение не выполняется. Трассировка для $4072$ : выдаются $2$ , $7$ , $0$ , $4$ , а $n$ проходит значения $407$ , $40$ , $4$ , $0$ . Завершение: вариант цикла есть $n$ , натуральное число; если происходит возврат к шагу 1, значит, $n > 0$ , а при $n \geq 1$ частное от деления на $10$ строго меньше $n$ , так что $n$ строго убывает на каждой итерации.

Задача для самостоятельного решения 3Сдача монетами

Имеются монеты в $50$ , $10$ и $1$ единиц, в неограниченном количестве. Спецификация: вход, натуральное $m$ ; выход, три натуральных числа $c_{50}$ , $c_{10}$ , $c_1$ , для которых $50 c_{50} + 10 c_{10} + c_1 = m$ и наименьшее возможное количество монет, $c_{50} + c_{10} + c_1$ . Некто предлагает следующий алгоритм. Найти вход, на котором он ошибается, объяснить каждый дефект и исправить его.

$c_{50}$ , $c_{10}$ и $c_1$ принимают значение $0$ .
Если $m \geq 50$ , то $c_{50}$ принимает значение $c_{50} + 1$ , и $m$ принимает значение $m - 50$ .
Пока $m > 10$ : $c_{10}$ принимает значение $c_{10} + 1$ , и $m$ принимает значение $m - 10$ .
Пока $m > 0$ : $c_1$ принимает значение $c_1 + 1$ , и $m$ принимает значение $m - 1$ .
Выдать $c_{50}$ , $c_{10}$ и $c_1$ .

Подсказка

Сумма монет всегда равна $m$ ; ошибиться может их количество. Попробуй точное кратное $10$ и сумму больше $100$ и спроси себя, какой способ соединения шагов использует шаг 2 и какой он должен был бы использовать.

Ответ

Дефектов два. Во-первых, шаг 3 использует $m > 10$ : при $m = 10$ он не выдаёт ни одной монеты в $10$ и выдаёт десять монет в $1$ вместо одной. Во-вторых, шаг 2 есть ветвление там, где нужно повторение: при $m = 120$ алгоритм в том виде, как он записан, выдаёт одну монету в $50$ , шесть в $10$ и десять в $1$ (семнадцать монет), и даже с уже исправленным шагом 3 он выдал бы одну в $50$ и семь в $10$ (восемь) вместо двух в $50$ и двух в $10$ (четырёх). Вход $m = 100$ показывает оба дефекта: алгоритм выдаёт одну монету в $50$ , четыре в $10$ и десять в $1$ , пятнадцать монет, вместо двух. Исправление: шаг 2, «пока $m \geq 50$ , …»; шаг 3, «пока $m \geq 10$ , …». После такого исправления алгоритм всегда берёт самую крупную монету, которая помещается, и с этими тремя монетами это даёт наименьшее количество: цифру единиц числа $m$ можно оплатить только монетами в $1$ , а то, что остаётся, выгодно оплачивать монетами в $50$ насколько возможно, потому что пять монет в $10$ стоят столько же, сколько одна в $50$ . С другими монетами, например в $1$ , $3$ и $4$ при $m = 6$ , правило всегда брать самую крупную уже не даёт минимума ( $4 + 1 + 1$ против $3 + 3$ ).