Алгоритмы и блок-схемы

Первая блок-схема в жизни почти каждого школьника выглядит одинаково: прямоугольник, от него стрелка, второй прямоугольник. В первом написано «встать», во втором «умыться», и рисунок занимает полстраницы тетради. Учитель ставит галочку, ученик не понимает, чем это лучше строчки «встать, умыться», — и в этом месте он, как ни странно, прав. Что такое алгоритм вообще, здесь не объясняется: это есть в статье про порядок тем школьного курса. Речь пойдёт только о записи схемой: когда она выигрывает у записи словами, когда проигрывает и чем её тогда заменить.

Четыре фигуры, которых хватает

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

• овал: начало или конец, внутри одно слово
• прямоугольник: действие, например «налить воду» или «прибавить единицу к счётчику»
• ромб: вопрос, на который отвечают «да» или «нет»; выходят из него ровно две стрелки, и обе подписаны
• параллелограмм: ввод и вывод, «ввести длину», «вывести ответ»

Про стрелки обычно забывают, а у них тоже есть правило: из любого прямоугольника выходит ровно одна стрелка. Если из «налить воду» выходят две, то в этом месте спрятан вопрос, который вы забыли оформить ромбом. Входить в прямоугольник может сколько угодно стрелок, но хотя бы одна обязана: если не входит ни одной, он недостижим, и работа, которую вы в него вписали, не будет выполнена никогда. Это проверяется взглядом, и многие ошибки в школьных схемах находятся именно этим правилом, без разбора смысла.

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

Один маршрут, записанный дважды

Маршрут до школы словами: «Идите по набережной до моста. Если мост открыт, перейдите его и поверните налево. Иначе идите вдоль реки до пешеходного перехода и поверните налево после него. Если идёт дождь, зайдите на остановку и доезжайте на автобусе». Прочитайте последнюю фразу ещё раз. Она относится к обоим вариантам или только к тому, где мост закрыт? Грамматика не подскажет, ответ зависит от того, как читатель расставил скобки у себя в голове.

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

В программировании это знакомая ловушка: вложенное «если», к которому приписано «иначе», и «иначе» цепляется не к тому условию, к которому задумывалось (подробнее о ветвлениях — в статье про условия и ветвления). В коде на Python вопрос решает отступ, на схеме — стрелка. В обоих случаях глазами по тексту ошибка проскакивает, а на рисунке находится за секунду.

Пустая петля у автобусной остановки

Это самая ходовая находка, ради которой рисовать стоит. Задача: дождаться автобуса нужного номера. Словами: «Смотрите на подъехавший автобус. Если номер не тот, ждите дальше». Записано связно, придраться не к чему.

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

В тексте этого не видно из-за слова «дальше»: оно молча предполагает, что мир за время ожидания изменится. Схема ничего не предполагает: между «нет» и ромбом нет ни одного прямоугольника, и на рисунке это видно глазом. Как такая петля записывается в коде и чем она кончается, разобрано в статье про циклы.

Есть у петель и второй подвох, который текст скрывает почти целиком. Фраза «повторять, пока не придёт нужный автобус» не говорит, где стоит проверка: перед первым взглядом на дорогу или после него. На схеме разница видна сразу, ромб стоит либо над прямоугольником «посмотреть», либо под ним. В первом случае тело петли может не выполниться ни разу, во втором выполнится минимум один раз, и для задач, где «ни разу» невозможно или недопустимо, это решает всё. В Паскале для двух вариантов есть две разные конструкции, в Python одна, а различие в голове всё равно надо держать.

Прогон пальцем

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

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

Проведите пальцем по схеме для каждого случая. На третьем выяснится, что у схемы нет выхода «автобусы кончились»: ромб спрашивает только про номер. Это уже не ошибка рисунка, а дыра в самом алгоритме. Ждать можно бесконечно долго даже с исправной петлёй, и в программе такой дыре соответствует цикл, который никто не умеет остановить снаружи. Закрывается она новым ромбом со своим выходом («время вышло?»), и на листе это пять секунд работы, а в готовой программе — полчаса поисков.

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

Где схема проигрывает

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

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

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

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

Экзамен, камера и чат

На ЕГЭ по информатике схема нигде не оценивается: работа проверяется по введённым ответам, а черновик остаётся бумажным и в проверку не идёт. Устройство экзамена описано в статье про структуру ЕГЭ по информатике. Тем не менее в первой части встречаются задания, где задан алгоритм исполнителя с ветвлением и повторением, и там быстрая схема на полях — самый надёжный способ не потеряться в «если» и «пока». Какие это задания и как их распознать, показано в карте первой части.

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

Занятия идут в видеокомнате без общей доски и показа экрана, поэтому схему рисуют на бумаге и поднимают к камере; проверить камеру и микрофон можно заранее, не входя в комнату. Если рисунок нужно сохранить, его пересказывают в чат по стрелкам: «ромб А: да, идём к Б; нет, идём к В». Такой пересказ скучен, зато его можно скопировать и поправить прямо в тексте.

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

Начать поиск:

• репетиторы по информатике, все направления
• репетиторы по информатике для 5–8 класса
• репетиторы по информатике для 9 класса
• репетиторы по информатике с пробным занятием

Вопросы и ответы

Нужно ли соблюдать стандарт, если схема рисуется для себя? Нет. Ромбы с подписанными выходами и стрелки — этого хватает. Стандарт пригодится, когда схему сдают учителю: тогда спросите, какие фигуры он требует.

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

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

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