Реферат: Тема : Выполнение алгоритмов для исполнителя

© К. Поляков, 2009-2011
A18 (высокий уровень, время – 6 мин)
Тема: Выполнение алгоритмов для исполнителя.

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

правила выполнения линейных, разветвляющихся и циклических алгоритмов

основные операции с символьными строками (определение длины, выделение подстроки, удаление и вставка символов, «сцепка» двух строк в одну)

исполнитель – это человек, группа людей, животное, машина или другой объект, который может понимать и выполнять некоторые команды

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

запись нц для i от 1 до n обозначает начало цикла, в котором переменная i (она называется переменной цикла) принимает последовательно все значения от 1 до n с шагом 1
^ Пример задания:
Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:

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

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

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

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




















6



















5



















4



















3



















2



















1

A

B

C

D

E

F



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

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

^ НАЧАЛО

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

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

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

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

КОНЕЦ




















































































































































Решение:

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

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

кроме этих четырех стенок, необходимо, чтобы коридор, выделенный на рисунке справа зеленым фоном, был свободен для прохода

обратим внимание, что возможны еще «вырожденные» варианты, вроде таких:
































































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

















6

















5


















4


















3

















2

















1

A

B

C

D

E

F









































































































































































6


















5


















4


















3


















2


















1

A

B

C

D

E

F



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




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





















6



















5



















4



















3


















2



















1

A

B

C

D

E

F





















6



















5



















4



















3



















2



















1

A

B

C

D

E

F






















6


















5



















4



















3



















2



















1

A

B

C

D

E

F

























6



















5



















4



















3



















2


















1

A

B

C

D

E

F







итак, условию удовлетворяет только одна клетка – F4

таким образом, правильный ответ – 1.

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

вариантов может быть достаточно много, важно не пропустить ни один из них

можно попытаться выполнить алгоритм для каждой клетки лабиринта, но это займет много времени; поэтому лучше ограничиться только клетками-кандидатами

нужно правильно определить свойства, по которым клетку можно считать «кандидатом»

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

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

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

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

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




















6



















5



















4



















3



















2



















1

A

B

C

D

E

F



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

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

^ НАЧАЛО

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

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

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

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

КОНЕЦ



















































































































































Решение:

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

рассмотрим первый цикл:

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

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

рассуждая аналогично, находим, что во втором цикле при движении вправо РОБОТ останавливается в клетке, где есть стена сверху; в третьем цикле (движение вниз) РОБОТ останавливается в клетке, где есть стена справа;

наконец, в четвертом цикле РОБОТ останавливается в клетке, где есть стена снизу; при этом он должен попасть обратно в исходную клетку, обозначенную на рисунке красной точкой;

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

теперь отметим на карте все клетки-кандидаты, где снизу есть стена:




















6


















5



















4


















3


















2













1

A

B

C

D

E

F






при движении из клеток B5, D1, E1, E6, F1 и F3 РОБОТ врежется в стенку, потому что слева стены нет и условие «слева свободно» всегда истинно:


















6


















5



















4


















3


















2













1

A

B

C

D

E

F




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



















6



















5



















4



















3


















2
















1

A

B

C

D

E

F







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



















6



















5



















4



















3



















2


















1

A

B

C

D

E

F






таким образом, только клетка B1 удовлетворяет условию задачи, поэтому …

правильный ответ – 1.
^ Еще пример задания:
В приведенном ниже фрагменте алгоритма, записанном на алгоритмическом языке, переменные a, b, c имеют тип «строка», а переменные i, k – тип «целое». Используются следующие функции:

Длина(a) – возвращает количество символов в строке a. (Тип «целое»)

Извлечь(a,i) – возвращает i-тый (слева) символ в строке a. (Тип «строка»)

Склеить(a,b) – возвращает строку, в которой записаны сначала все символы
строки a, а затем все символы строки b. (Тип «строка»)

Значения строк записываются в одинарных кавычках (Например, a:='дом'). Фрагмент алгоритма:

i := Длина(a)

k := 2

b := 'А'

пока i > 0

нц

c := Извлечь(a,i)

b := Склеить(b,c)

i := i – k

кц

b := Склеить(b,'Т')

Какое значение будет у переменной b после выполнения вышеприведенного фрагмента алгоритма, если значение переменной a было ‘ПОЕЗД’?

1) ‘АДЕПТ’ 2) ‘АДЗЕОП’ 3) ‘АДТЕТПТ’ 4) ‘АДЗОТ’

Решение:

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

заметим, что последняя команда алгоритма, b:=Склеить(b,'Т'), добавляет букву 'Т' в конец строки b, поэтому ответ 2 – явно неверный (строка должна оканчиваться на букву 'Т', а не на 'П')

для решения будем использовать ручную прокрутку; здесь пять переменных: a, b, c, i, k, для каждой из них выделим столбец, где будем записывать изменение ее значения

перед выполнением заданного фрагмента мы знаем только значение a, остальные неизвестны (обозначим их знаком вопроса):




a

b

c

i

k




'ПОЕЗД'

?

?

?

?

в первой команде длина строки a (она равна 5 символам) записывается в переменную i:




a

b

c

i

k




'ПОЕЗД'

?

?

?

?

i:=Длина(a)










5




следующие два оператора записывают начальные значения в k и b:




a

b

c

i

k




'ПОЕЗД'

?

?

?

?

i:=Длина(a)










5




k:=2













2

b:='А'




'A'










далее следует цикл пока с проверкой условия i>0 в начале цикла; сейчас i=5>0, то есть, условие выполняется, цикл начинает работать и выполняются все операторы в теле цикла:




a

b

c

i

k




'ПОЕЗД'

?

?

?

?

i:=Длина(a)










5




k:=2













2

b:='А'




'A'










i > 0?

да

c:=Извлечь(a,i)

i:=Длина(a)










5

b:=Cклеить(b,c)

k:=2













i:=i–k










3




поскольку i=5, вызов функции Извлечь(a,i) выделяет из строки a символ с номером 5, это 'Д';

следующей командой этот символ приписывается в «хвост» строки b, теперь в ней хранится цепочка 'АД';

в команде i:=i-k значение переменной i уменьшается на k (то есть, на 2)

далее нужно перейти в начало цикла и снова проверить условие i>0, оно опять истинно, поэтому выполняется следующий шаг цикла, в котором к строке b добавляется 3-й символ строки a, то есть 'Е':




a

b

c

i

k

...

'ПОЕЗД'

'АД'

…

3

2

i > 0?

да

c:=Извлечь(a,i)







'Е'







b:=Cклеить(b,c)




'АДЕ'










i:=i–k










1




условие i>0 истинно, поэтому тело цикла выполняется еще один раз, к строке b добавляется 1-й символ строки a, то есть 'П':




a

b

c

i

k

...

'ПОЕЗД'

'АДЕ'

…

1

2

i > 0?

да

c:=Извлечь(a,i)







'П'







b:=Cклеить(b,c)




'АДЕП'










i:=i–k










–1




теперь i=-1, поэтому при очередной проверке условие i>0 в начале цикла оказывается ложным, выполнение цикла заканчивается, и исполнителю остается выполнить единственную строчку после цикла, которая дописывает в конец строки b букву 'Т':




a

b

c

i

k

...

'ПОЕЗД'

'АДЕП'

…

–1

2

i > 0?

нет

b:=Склеить(b,'Т')




'АДЕПТ'










у нас получилось, что в конце выполнения фрагмента алгоритма в переменной b будет записана последовательность символов 'АДЕПТ'

таким образом, правильный ответ – 1.

Возможные проблемы:

таблица получилась достаточно громоздкая, однако она позволяет наиболее наглядно решить задачу


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

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

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

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

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

Цикл ПОКА <условие> команда выполняется, пока условие истинно, иначе происходит переход на следующую строку.































































































































































































































































































































































































































































































































^ Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ уцелеет (не врежется в стену)?

1) 1 2) 13 3) 21 4) 39

^ НАЧАЛО

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

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

вверх

вправо

КОНЕЦ


Решение:

нарисуем примерный путь Робота в соответствии с программой; вот три варианта, когда Робот не разбивается:




1)

?

?

?

?




2)

?

?




?

3)

?




?

?




?

?

?

?







?

?




?




?




?

?




?







?







?







?




?







?































?










?

?




?

?

?

?







?

?




?




?




?

?

здесь ключевые клетки – две стенки (слева и снизу) и три ярко-зеленых клетки, которые должны быть свободны

теперь ищем на карте участки, где есть все ключевые клеток (они выделены на рисунке):


































































































































































































































































































































































































































































































































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

теперь осталось подсчитать все клетки, спускаясь из которых Робот упирается в темно-коричневые стенки:































































































































































































































































































































































































































































































































подсчет показывает, что их 39 штук;

поэтому правильный ответ – 4.


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

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

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

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

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




















6



















5



















4



















3



















2



















1

A

B

C

D

E

F



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

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

^ НАЧАЛО

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

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

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

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

КОНЕЦ


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

Вперед n, где n – целое число, вызывающая передвижение черепашки на n шагов в направлении движения.

Направо m, где m – целое число, вызывающая изменение направления движения на m градусов по часовой стрелке.

Запись ^ Повтори 5 [Команда1 Команда2] означает, что последовательность команд в скобках повторится 5 раз.

Черепашке был дан для исполнения следующий алгоритм:

^ Повтори 5 [Вперед 10 Направо 72]

Какая фигура появится на экране?

1) Незамкнутая ломаная линия

2) Правильный треугольник

3) Квадрат

4) Правильный пятиугольник

Имеется фрагмент алгоритма, записанный на алгоритмическом языке:

n := Длина(а)

m := 6

b := Извлечь(а, m)

с := Извлечь(а, m-4)

b := Склеить(b, с)

с := Извлечь(а, m+2)

b := Склеить(b, с)

нц для i от 10 до n

с := Извлечь(а, i)

b := Склеить(b, с)

кц

Здесь переменные a, b и с - строкового типа; переменные n, m, k – целые. В алгоритме используются следующие функции:

Длина(х) – возвращает количество символов в строке х. Имеет тип «целое».

Извлечь(х,i) – возвращает i-й символ слева в строке х. Имеет строковый тип.

Склеить(х,у) – возвращает строку, в которой записаны подряд сначала все символы
строки х, а затем все символы строки у. Имеет строковый тип.

Значения строк записываются в кавычках (одинарных), например x='школа'.

Какое значение примет переменная b после выполнения этого фрагмента алгоритма,

если переменная а имела значение 'КИБЕРНЕТИКА'?

1) ‘БЕРЕТ’ 2) ‘НИТКА’ 3) ‘ТИБЕТ’ 4) ‘НЕРКА’

Имеется фрагмент алгоритма, записанный на алгоритмическом языке:

m := 10

b := Извлечь(а, m)

нц для k от 4 до 5

с := Извлечь(а, k)

b := Склеить(b, с)

кц

нц для k от 1 до 3

с := Извлечь(а, k)

b := Склеить(b, с)

кц

Здесь переменные a, b и с - строкового типа; переменные n, m, k – целые. В алгоритме используются следующие функции:

Извлечь(х,i) – возвращает i-й символ слева в строке х. Имеет строковый тип.

Склеить(х,у) – возвращает строку, в которой записаны подряд сначала все символы
строки х, а затем все символы строки у. Имеет строковый тип.

Значения строк записываются в кавычках (одинарных), например x='школа'.

Какое значение примет переменная b после выполнения этого фрагмента алгоритма,

если переменная а имела значение 'ИНФОРМАТИКА'?

1) ‘ФОРМАТ’ 2) ‘ФОРИНТ’ 3) ‘КОРТИК’ 4) ‘КОРИНФ’

Некий исполнитель умеет выполнять три команды:

FD<число шагов> – движение вперед на указанное число шагов

RT<число градусов> – поворот направо на указанное число градусов

REPEAT<число повторений>[<повторяющиеся действия>] – команда повторения

Например, ^ REPEAT 4[FD 20 RT 90] строит квадрат со стороной 20. Какую фигуру будет представлять собой траектория движения данного исполнителя в результате выполнения команды

^ REPEAT 8 [FD 60 RT 45]

1) Равносторонний треугольник

2) Ромб

3) Правильный шестиугольник

4) Правильный восьмиугольник


Некий исполнитель умеет строить лесенки. Каждая ступенька такой лесенки имеет одну единицу по высоте и целое количество единиц в длину. Одна из возможных лесенок показана на рисунке.
Исполнитель умеет выполнять команды ВВЕРХ и ВПРАВО N, где N – длина ступеньки, причем алгоритм всегда начинается командой ВВЕРХ и заканчивается командой ВПРАВО. Необходимо, выполнив 8 команд, построить лесенку из четырех, ступенек, ведущую из точки А в точку В. Точка А имеет координаты (0,0) на координатной плоскости, а точка В – координаты (5,4). Сколько различных последовательностей команд могут привести к требуемому результату?

1) 5 2) 6 3) 3 4) 4


A































B
























Исполнитель Робот действует на клетчатом поле, между соседними клетками которого могут стоять стены. Робот передвигается по клеткам поля и может выполнять следующие команды: Вверх (1), Вниз (2), Вправо (3), Влево (4).
При выполнении каждой такой команды Робот перемещается в соседнюю клетку в указанном направлении. Если же в этом направлении между клетками стоит стена, то робот разрушается.
Какую последовательность из 5 команд выполнил Робот, чтобы переместиться из клетки А в клетку В, не разрушившись от встречи со стенами? Ответы записаны в виде последовательности цифр, соответствующих командам.

1) 32323 2) 23324 3) 32324 4) 22211

Имеется фрагмент алгоритма, записанный на алгоритмическом языке:

n := Длина(а)

m := 1

b := Извлечь(а, m)

нц для i от 7 до n

с := Извлечь(а, i)

b := Склеить(b, с)

кц

Здесь переменные a, b и с - строкового типа; переменные n, m – целые. В алгоритме используются следующие функции:

Длина(х) – возвращает количество символов в строке х. Имеет тип «целое».

Извлечь(х,i) – возвращает i-й символ слева в строке х. Имеет строковый тип.

Склеить(х,у) – возвращает строку, в которой записаны подряд сначала все символы
строки х, а затем все символы строки у. Имеет строковый тип.

Значения строк записываются в кавычках (одинарных), например x='школа'.

Какое значение примет переменная b после выполнения этого фрагмента алгоритма,

если переменная а имела значение 'ЭНЕРГЕТИКА'?

1) ‘РАНЕТ’ 2) ‘ЭТИКА’ 3) ‘ЭРКЕР’ 4) ‘РЕНТА’

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

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

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

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

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

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

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

^ НАЧАЛО

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

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

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

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

КОНЕЦ





















6



















5



















4



















3



















2



















1

A

B

C

D

E

F







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

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

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

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

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