Исполнитель «Робот» и ЕГЭ
Создание: 02.03.2013
До недавнего времени обязательным атрибутом экзамена по информатике был исполнитель «Робот».

В демонстрационном варианте за 2013 г. этой задачи нет, но это не повод не разобрать как решается такой тип задач.

Итак, все задачи имели похожий, текст, например, такой:

Система команд исполнителя РОБОТ, «живущего» в клетках прямоугольного лабиринта на плоскости: вверх, вниз, влево, вправо.
Четыре условия позволяют проверить отсутствие преград у каждой из сторон той клетки, где находится РОБОТ: сверху свободно, снизу свободно, слева свободно, справа свободно.
В цикле ПОКА < условие > команда команда выполняется, пока условие истинно, иначе происходит переход на следующую строку программы.
Если РОБОТ начнет движение в сторону стены, то он разрушится и выполнение программы прервется.
Сколько клеток лабиринта соответствуют требованию, что, выполнив предложенную программу, РОБОТ уцелеет и остановится в той же клетке, с которой он начал движение?

Отличия касались только программы исполнителя и расположения стенок, на поле.

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

 

Для того чтобы нарисовать схему движение не нужно видеть поля исполнителя, достаточно программы. На схеме отображается направление движение исполнителя и условие прекращения движения. Начальная и конечная точка выделена цветом. Переходим к заданному полю.

Так как  последняя клетка исполнителя должна быть ограничена сверху из всех 36 клеток поля для рассмотрения нужно оставить только 12, которые удовлетворяют этому условию (1). Простейший анализ исключает большую часть этих клеток, так как двигаясь по стрелке вниз робот ни где не найдет стены справа - условия прекращения движения, а значит такие клетки нужно исключить из рассмотрения (2). Остается пять клеток, которые нужно рассмотреть внимательней.

 

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

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

Итак, благодаря переводу программного кода в сему, отсечения «лишних» клеток мы смогли в несколько раз уменьшить размер задачи, свести ее к проверки всего лишь нескольких полей.

P.S.

Хочу остановиться на моменте не имеющем отношения к программирования, зато напрямую определяющую результат ученика на экзамене - крайне низком качестве печати задания.

Предложенная задача взята из pdf-файла, скачанного с официального портала ЕГЭ. На предложенном рисунке четыре типа линий (!): толстая, тонкая, пунктирная, и пунктирная прерывистая . Какие из линий воспринимать за стены? Эта проблема может сбить с толку, заставить рассматривать лишние поля...

Если вы столкнетесь с такой проблемой на экзамене не волнуйтесь - подзовите экзаменатора и заявите о своем несогласии с процедурой проведения экзамена, у вас есть такое право. Вы получили материал, который не дает вам возможности выполнить задание. Не смотря на то, что задачи части A проверяются машиной и их нельзя апеллировать, такая процедура даст вам шанс вернуть потерянный балл. Желаю, чтобы такой ситуации с вами не произошло.