A18 (базовый уровень, время – 2 мин)
Тема: Выполнение алгоритмов для исполнителя.
Что нужно знать:
· правила выполнения линейных, разветвляющихся и циклических алгоритмов
· основные операции с символьными строками (определение длины, выделение подстроки, удаление и вставка символов, «сцепка» двух строк в одну)
· исполнитель – это человек, группа людей, животное, машина или другой объект, который может понимать и выполнять некоторые команды
· в школьном алгоритмическом языке нц обозначает «начало цикла», а кц – «конец цикла»; все команды между нц и кц – это тело цикла, они выполняются несколько раз
· запись нц для i от 1 до n обозначает начало цикла, в котором переменная i (она называется переменной цикла) принимает последовательно все значения от 1 до n с шагом 1
Пример задания:
Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:
вверх вниз влево вправо.
При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:
сверху свободно снизу свободно
слева свободно справа свободно
Цикл ПОКА <условие> команда выполняется, пока условие истинно, иначе происходит переход на следующую строку. Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ остановится в той же клетке, с которой он начал движение?
| A | B | C | D | E | F |
1) 1 2) 2 3) 3 4) 0
НАЧАЛО
ПОКА <снизу свободно> вниз
ПОКА <слева свободно> влево
ПОКА <сверху свободно> вверх
ПОКА <справа свободно> вправо
КОНЕЦ
 
|  
| |||||
| ||||||
Решение:
1) легко понять, что для того, чтобы исполнитель вернулся обратно в ту клетку, откуда он начал движения, четыре стенки должны быть расставлены так, чтобы он упирался в них сначала при движении вниз, затем – влево, вверх и, наконец, вправо:
на рисунке красная точка обозначает клетку, начав с которой РОБОТ вернется обратно;
2) кроме этих четырех стенок, необходимо, чтобы коридор, выделенный на рисунке справа зеленым фоном, был свободен для прохода
3) итак, мы выяснили, что нужно рассматривать лишь те клетки, где есть стенка справа; отметим на исходной карте клетки-кандидаты:
| · | · | |||||
| · | · | |||||
| · | ||||||
| · | ||||||
| · | · | |||||
| · | ||||||
| A | B | C | D | E | F |
4) этих «подозрительных» клеток не так много, но можно еще сократить количество рассматриваемых вариантов: если РОБОТ начинает движение с любой клетки на вертикали F, он все равно приходит в клетку F4, которая удовлетворяет заданному условию, таким образом, одну клетку мы нашли, а остальные клетки вертикали F условию не удовлетворяют:
| · | ||||||
| · | ||||||
| · | ||||||
| · | ||||||
| · | ||||||
| · | ||||||
| A | B | C | D | E | F |
5) проверяем оставшиеся три клетки-кандидаты, но для них всех после выполнения алгоритма РОБОТ не приходит в ту клетку, откуда он стартовал:
| 
| 
|
6) итак, условию удовлетворяет только одна клетка – F4
7) таким образом, правильный ответ – 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) ‘АДЗОТ’
Решение:
1) эта задача более близка к классическому программированию, здесь выполняется обработка символьных строк; вся информация для успешного решения, вообще говоря, содержится в условии, но желательно иметь хотя бы небольшой опыт работы с символьными строками на Паскале (или другом языке)
2) заметим, что последняя команда алгоритма, b:=Склеить(b,'Т'), добавляет букву 'Т' в конец строки b, поэтому ответ 2 – явно неверный (строка должна оканчиваться на букву 'Т', а не на 'П')
3) для решения будем использовать ручную прокрутку; здесь пять переменных: a, b, c, i, k, для каждой из них выделим столбец, где будем записывать изменение ее значения
4) перед выполнением заданного фрагмента мы знаем только значение a, остальные неизвестны (обозначим их знаком вопроса):
| a | b | c | i | k | |
| 'ПОЕЗД' | ? | ? | ? | ? |
5) в первой команде длина строки a (она равна 5 символам) записывается в переменную i:
| a | b | c | i | k | |
| 'ПОЕЗД' | ? | ? | ? | ? | |
| i:=Длина(a) |
6) следующие два оператора записывают начальные значения в k и b:
| a | b | c | i | k | |
| 'ПОЕЗД' | ? | ? | ? | ? | |
| i:=Длина(a) | |||||
| k:=2 | |||||
| b:='А' | 'A' |
7) далее следует цикл пока с проверкой условия i>0 в начале цикла; сейчас i=5>0, то есть, условие выполняется, цикл начинает работать и выполняются все операторы в теле цикла:
| a | b | c | i | k | |
| 'ПОЕЗД' | ? | ? | ? | ? | |
| i:=Длина(a) | |||||
| k:=2 | |||||
| b:='А' | 'A' | ||||
| i > 0? | да | ||||
| c:=Извлечь(a,i) | i:=Длина(a) | ||||
| b:=Cклеить(b,c) | k:=2 | ||||
| i:=i–k |
· поскольку i=5, вызов функции Извлечь(a,i) выделяет из строки a символ с номером 5, это 'Д';
· следующей командой этот символ приписывается в «хвост» строки b, теперь в ней хранится цепочка 'АД';
· в команде i:=i-k значение переменной i уменьшается на k (то есть, на 2)
8) далее нужно перейти в начало цикла и снова проверить условие i>0, оно опять истинно, поэтому выполняется следующий шаг цикла, в котором к строке b добавляется 3-й символ строки a, то есть 'Е':
| a | b | c | i | k | |
| ... | 'ПОЕЗД' | 'АД' | … | ||
| i > 0? | да | ||||
| c:=Извлечь(a,i) | 'Е' | ||||
| b:=Cклеить(b,c) | 'АДЕ' | ||||
| i:=i–k |
9) условие i>0 истинно, поэтому тело цикла выполняется еще один раз, к строке b добавляется 1-й символ строки a, то есть 'П':
| a | b | c | i | k | |
| ... | 'ПОЕЗД' | 'АДЕ' | … | ||
| i > 0? | да | ||||
| c:=Извлечь(a,i) | 'П' | ||||
| b:=Cклеить(b,c) | 'АДЕП' | ||||
| i:=i–k | –1 |
10) теперь i=-1, поэтому при очередной проверке условие i>0 в начале цикла оказывается ложным, выполнение цикла заканчивается, и исполнителю остается выполнить единственную строчку после цикла, которая дописывает в конец строки b букву 'Т':
| a | b | c | i | k | |
| ... | 'ПОЕЗД' | 'АДЕП' | … | –1 | |
| i > 0? | нет | ||||
| b:=Склеить(b,'Т') | 'АДЕПТ' |
11) у нас получилось, что в конце выполнения фрагмента алгоритма в переменной b будет записана последовательность символов 'АДЕПТ'
12) таким образом, правильный ответ – 1.
| Возможные проблемы: · таблица получилась достаточно громоздкая, однако она позволяет наиболее наглядно решить задачу |
Задачи для тренировки [1]:
1) Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости: