Рассмотрим ряд задач по теме выполнение алгоритмов для исполнителей с решениями и разбором типичных ошибок. Для начала вспомним необходимые сведения по этой теме.

Справочные сведения

Исполнитель алгоритма - это тот объект или субъект, для управления которым составлен алгоритм.

Система команд исполнителя – это вся совокупность команд, которые исполнитель умеет выполнять.

Среда исполнителя - обстановка, в которой функционирует исполнитель.

Определённая последовательность действий исполнителя всегда применяется к некоторым исходным данным.

Примеры исполнителей: Черепашка , Робот, Калькулятор и другие.

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

Приведём примеры решения типичных задач этого раздела:

ПРИМЕР 1 (А18)

Что нужно знать:

1. правила выполнения линейных, разветвляющихся и циклических алгоритмов
2. основные операции с символьными строками (определение длины, выделение подстроки, удаление и вставка символов, «сцепка» двух строк в одну)
3. исполнитель – это человек, группа людей, животное, машина или другой объект, который может понимать и выполнять некоторые команды
4. в школьном алгоритмическом языке нц обозначает «начало цикла», а кц – «конец цикла»; все команды между нц и кц – это тело цикла, они выполняются несколько раз
5. запись нц для i от 1 до n обозначает начало цикла, в котором переменная i (она называется переменной цикла) принимает последовательно все значения от 1 до n с шагом 1

Пример задания:

Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:

вверх                 вниз                 влево         вправо.

При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:

сверху свободно                снизу свободно

слева свободно                 справа свободно 

 Цикл ПОКА <условие> команда выполняется, пока условие истинно, иначе происходит переход на следующую строку. Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ остановится в той же клетке, с которой он начал движение?

 1) 1         2) 2         3) 3         4) 0

НАЧАЛО

ПОКА <снизу свободно> вниз

ПОКА <слева свободно> влево

ПОКА <сверху свободно> вверх

ПОКА <справа свободно> вправо

КОНЕЦ

 Решение:

1. легко понять, что для того, чтобы исполнитель вернулся обратно в ту клетку, откуда он начал движения, четыре стенки должны быть расставлены так, чтобы он упирался в них сначала при движении вниз, затем – влево, вверх и, наконец, вправо:

на рисунке красная точка обозначает клетку, начав с которой РОБОТ вернется обратно;

2. кроме этих четырех стенок, необходимо, чтобы коридор, выделенный на рисунке справа зеленым фоном, был свободен для прохода
3. обратим внимание, что возможны еще «вырожденные» варианты, вроде таких:

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

6. этих «подозрительных» клеток не так много, но можно еще сократить количество рассматриваемых вариантов: если РОБОТ начинает движение с любой клетки на вертикали F, он все равно приходит в клетку F4, которая удовлетворяет заданному условию, таким образом, одну клетку мы нашли, а остальные клетки вертикали F условию не удовлетворяют:

7. проверяем оставшиеся три клетки-кандидаты, но для каждой из них после выполнения алгоритма РОБОТ не приходит в ту клетку, откуда он стартовал:

8. итак, условию удовлетворяет только одна клетка – F4
9. таким образом, правильный ответ – 1.

Еще пример задания:

Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:

вверх                 вниз                 влево         вправо.

При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:

сверху свободно                снизу свободно

слева свободно                 справа свободно 

 Цикл ПОКА <условие> команда выполняется, пока условие истинно, иначе происходит переход на следующую строку. Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ уцелеет (не врежется в стену) и остановится в той же клетке, с которой он начал движение?

 1) 1         2) 2         3) 3         4) 0

НАЧАЛО

ПОКА <слева свободно> вверх

ПОКА <сверху свободно> вправо

ПОКА <справа свободно> вниз

ПОКА <снизу свободно> влево

КОНЕЦ

Решение:

1. особенность этой задач в том, что РОБОТ проверяет стенку в одном направлении, а движется в другом
2. рассмотрим первый цикл:

ПОКА <слева свободно> вверх

понятно, что при движении вверх РОБОТ остановится в первой же клетке, где слева будет стена

3. рассуждая аналогично, находим, что во втором цикле при движении вправо РОБОТ останавливается в клетке, где есть стена сверху; в третьем цикле (движение вниз) РОБОТ останавливается в клетке, где есть стена справа;
4. наконец, в четвертом цикле РОБОТ останавливается в клетке, где есть стена снизу; при этом он должен попасть обратно в исходную клетку, обозначенную на рисунке красной точкой;
5. кроме этих четырех стенок, необходимо, чтобы коридор, выделенный на рисунке зеленым фоном, был свободен для прохода, иначе РОБОТ врежется в стенку
6. теперь отметим на карте все клетки-кандидаты, где снизу есть стена:
7. при движении из клеток B5, D1, E1, E6, F1 и F3 РОБОТ врежется в стенку, потому что слева стены нет и условие «слева свободно» всегда истинно:

8. начав движение с клетки A1, C1 или C2, РОБОТ также врезается в стенку и разрушается:

10. и только путь, начатый в клетке B1, приводит РОБОТА обратно в точку старта:

11. таким образом, только клетка B1 удовлетворяет условию задачи, поэтому …
12. правильный ответ – 1.

ПРИМЕР 2 (В 5)

Что нужно знать:

1. каких-либо особых знаний из курса информатики не требуется, задача решаема на уровне 6-7 класса простым перебором вариантов, просто его нужно организовать оптимальным образом
2. исполнитель – это человек, группа людей, животное, машина или другой объект, который может понимать и выполнять некоторые команды

Пример задания:

У исполнителя Калькулятор две команды, которым присвоены номера:

1. прибавь 3

2. умножь на 4

Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя вторую, умножает его на 4. Запишите порядок команд в программе получения из числа 3 числа 57, содержащей не более 6 команд, указывая лишь номера команд.

 (Например, программа 21211 это программа

умножь на 4

прибавь 3

умножь на 4

прибавь 3

прибавь 3

которая преобразует число 2 в 50.)

Решение (вариант 1, «прямой ход»):

1. обратим внимание, что в условии ограничено число команд, поэтому неявно ставится задача написать самую короткую программу для решения задачи
2. начнем решать задачу, «отталкиваясь» от начального числа
3. на первом шаге с помощью имеющихся команд из числа 3 можно получить 6 или 12;
4. на втором шаге из 6 можно получить 9 и 12, а из 12 – 15 и 48, и т.д., получается такая схема (структура «дерево»), цифры около стрелок показывает номер выполненной команды:

3

6

24

9

12

48

15

1

1

1

2

2

2

48

51

54

57

1

1

1

5. уже чувствуется, что дерево сильно разрастается, на следующем уровне будет уже 8 вариантов, потом – 16 и т.д. (на каждом следующем уровне – в 2 раза большем, чем на предыдущем)нужно выбрать такой план дальнейшего перебора вариантов, который может быстрее всего привести к цели (числу 57)
6. видим, что после второй операции ближе всего к результату оказалось число 48, попробуем начать анализ с этой ветки; если не получится – возьмем число 24 и т.д.
7. ветка дерева, начиная от числа 48, построена на рисунке справа; красный крестик показывает, что полученное значение превышает 57
8. итак, мы вышли на число 57 в результате такой последовательности команд: 22111, ее длина равна 5, что удовлетворяет условию задачи.
9. таким образом, правильный ответ – 22111.

Решение (вариант 2, «обратный ход»):

1. нам нужно увеличить число (с 3 до 57), для этого в большинстве случаев умножение эффективнее сложения, поэтому нужно постараться максимально использовать умножение, а сложение – только в крайних случаях
2. попробуем решить задачу «обратным ходом», начав с числа 57;
3. очевидно, что последней командой не может быть умножение на 4 (57 на 4 не делится), поэтому последняя команда – сложение (прибавь 3), над стрелкой записан номер команды:

4. число 54 также не делится на 4, поэтому предыдущая команда – тоже сложение:

5. аналогично для числа 51:

6. число 48 делится на 4, поэтому используем умножение:

7. наконец, добавив в начало программы еще одно умножение, получаем полную цепочку:

8. таким образом, правильный ответ – 22111, эта программа состоит из 5 команд.

ПРИМЕР 3

У исполнителя, который работает с положительными однобайтовыми двоичными числами, две команды, которым присвоены номера:

1. сдвинь влево

2. вычти 1

Выполняя первую из них, исполнитель сдвигает число на один двоичный разряд влево, а выполняя вторую, вычитает из него 1. Исполнитель начал вычисления с числа 104 и выполнил цепочку команд 11221. Запишите результат в десятичной системе.

Решение:

1. важно, что числа однобайтовые – на число отводится 1 байт или 8 бит
2. главная проблема в этой задаче – разобраться, что такое «сдвиг влево»; так называется операция, при которой все биты числа в ячейке (регистре) сдвигаются на 1 бит влево, в младший бит записывается нуль, а старший бит попадает в специальную ячейку – бит переноса:

             бит
               переноса

можно доказать, что в большинстве случаев результат этой операции – умножение числа на 2, однако есть исключение: если в старшем (7-ом) бите исходного числа x была 1, она будет «выдавлена» в бит переноса, то есть потеряна, поэтому мы получим остаток от деления числа 2x на 28=256

3. попутно заметим, что при сдвиге вправо в старший бит записывается 0, а младший «уходит» в бит переноса; это равносильно делению на 2 и отбрасыванию остатка
4. таким образом, фактически команда сдвинь влево означает умножь на 2
5. поэтому последовательность команд 11221 выполняется следующим образом

6. правильный ответ – 60.

ПРИМЕР 4

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

            3233241

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

Решение:

1. фактически заданная программа движения Робота, которую он успешно выполнил, показывает нам свободный путь, на котором стенок нет
2. поэтому для того, чтобы не разрушиться на обратном пути, Робот должен идти точно по тому же пути в обратном направлении
3. нарисуем путь Робота, который выполнил программу 323341:

Робот начал движение из клетки, отмеченной красной точкой, и закончил в клетке, где стоит синяя точка

4. чтобы вернуться в исходную клетку (с красной точкой) по пройденному пути, Роботу нужно сделать шаг влево (команда 4), затем шаг вверх (команда 1) и еще один шаг влево (команда 4)
5. таким образом, ответ – 414.

ПРИМЕР 5

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

вправо

вверх

влево

влево

вниз

вниз

вправо

вправо

вправо

вниз

влево

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

Решение (способ 1, моделирование движения Робота):

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

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

4. есть и другие варианты (попробуйте их найти!), но все они содержат 3 команды: одну команду вправо и две команды вниз
5. таким образом, ответ – 3.

Решение (способ 2, анализ программы):

1. можно решить задачу без повторения движений Робота
2. обратим внимание, что пары команд «вперед-назад» и «влево-вправо» дают нулевой эффект, то есть, не перемещают  Робота, поэтому все такие пары можно выкинуть из программы
3. поскольку стенок нет, все равно где стоят парные команды в программе, вычеркиваем их:

вправо

вверх

влево

влево

вниз

вниз

вправо

вправо

вправо

вниз

влево

4. смотрим, какие команды остались (они отмечены желтым маркером), их всего 3
5. таким образом, ответ – 3.

 ПРИМЕР 6

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

Вперёд  n – вызывает  передвижение Черепашки на n шагов в направлении движения.

Направо m - вызывает направления движения на m градусов по часовой стрелке ( 0≤ m ≤180).

Вместо n и m должны стоять целые числа.

Запись

Повтори 5 [ команда1  команда 2]

Означает, что последовательность команд в квадратных скобках повториться 5 раз.

Какое число необходимо записать вместо n в следующем алгоритме

Повтори  6[ вперёд 40  направо  n] чтобы на экране появился правильный пятиугольник?

Решение:

Сумма внутренних углов любого правильного многоугольника вычисляется по формуле , где p- количество углов выпуклого многоугольника. Поэтому величина одного внутреннего угла будет равна . А угол поворота Черепашки в вершине пятиугольника будет равен углу, смежному с внутренним углом, т.е. .

 Ответ: 72.

Возможные ловушки и проблемы:

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

ПРИМЕР 7

Имеется исполнитель Кузнечик, который живет на числовой оси. Система команд Кузнечика:

“Вперед N” (Кузнечик прыгает вперед на N единиц);

“Назад M” (Кузнечик прыгает назад на M единиц).

Переменные N и M могут принимать любые целые положительные значения. Известно, что Кузнечик выполнил программу из 50 команд, в которой команд “Назад 2” на 12 больше, чем команд “Вперед 3”. Других команд в программе не было. На какую одну команду можно заменить эту программу, чтобы Кузнечик оказался в той же точке, что и после выполнения программы?

Решение(математический способ решения) :

1. Определим количество команд Вперёд 3 и количество команд Назад 2. Обозначим через Х количество команд Вперёд 3, тогда количество команд Назад 2 равно Х+ 12.
2. Составим уравнение:

Х+ Х +12 =5 0.

Решая это уравнение, получаем: Х=19.

3)Таким образом, Кузнечик выполнил 19 команд Вперёд 3 и 31 команду Назад 2.

4) Определим положение Кузнечика после выполненных команд, считая, что его начальное положение соответствует значению 0.

Для этого не требуется знать, в каком порядке выполняются команды; достаточно учитывать, что выполнении команды Вперёд 3 позиция Кузнечика увеличивается на 3 единицы, а при выполнении команды Назад 2 – уменьшается на 2 единицы: 3*19-2*31= -5.

5)Следовательно, все команды можно заменить одной: Назад 5.

Ответ: Назад 5.

Заключение

Таким образом, мы рассмотрели ряд задач по теме  ИСПОЛНИТЕЛИ (некоторые из них решены двумя способами), а ученик должен лишь выбрать доступный ему. Исходя из ряда задач очевидно, что все вышеперечисленные умения должны формироваться при изучении математики в основной школе, а их отсутствие сказывается на результатах ЕГЭ в силу высокой роли межпредметных связей в курсе информатики.

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

Литература

1. Демонстрационный материал ЕГЭ (2009,2010,2011 г.г.)
2. М.Э. Абрамян, С.С. Михалкович  ЕГЭ шаг за шагом-  Москва НИИ школьных технологий , 2010 г.
3. С.М. Окулов Основы программирования.- М.: бином. Лаборатория знаний.
4. И.Г. Семакин, А.П. Шестаков Основы алгоритмизации и программирования. – М.: Академия, 2008 г.

Сведения об авторе

Киселева Татьяна Александровна

Учитель информатики и ИКТ 1 квалификационная технология

352142

Краснодарский край Кавказский район

п.им. М. Горького , ул. Набережная, 27