12. Сложные исполнители и алгоритмы

Другие исполнители

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела 12. Сложные исполнители и алгоритмы:

Это старая версия каталога задач

Нажмите для перехода на новую версию

Решаем задачи
Задание 1 #12768

Исполнитель МАШИНКА “живет” в ограниченном прямоугольном лабиринте на клетчатой плоскости, изображенном на рисунке. Серые клетки — возведенные стены, светлые — свободные клетки, по которым МАШИНКА может свободно передвигаться. По краю поля лабиринта также стоит возведенная стенка с нанесенными номерами и буквами для идентификации клеток в лабиринте.

Система команд исполнителя МАШИНКА:

\[\begin{array}{| l | l | l | l |} \hline \text{вверх} & \text{вниз} & \text{влево} & \text{вправо} \\ \hline \end{array}\]

При выполнении любой из этих команд МАШИНКА перемещается на одну клетку соответственно (по отношению к наблюдателю): вверх, вниз, влево, вправо. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится МАШИНКА (также по отношению к наблюдателю):

\[\begin{array}{| l | l | l | l |} \hline \text{сверху} & \text{снизу} & \text{слева} & \text{справа} \\ \text{свободно} & \text{свободно} & \text{свободно} & \text{свободно} \\ \hline \end{array}\]

Цикл

ПОКА < условие > команда

выполняется, пока условие истинно, иначе происходит переход на следующую строку.

При попытке передвижения на любую серую клетку МАШИНКА разбивается о стенку.

Сколько клеток приведенного лабиринта соответствуют требованию, что, стартовав в ней и выполнив предложенную ниже программу, МАШИНКА не разобьется?

НАЧАЛО

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

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

вверх

вправо

КОНЕЦ

Показать решение

Начав движение из любой клетки столбца А, клеток В7, В8, С7, С8 Машинка разобьется, выполняя команду вправо. Стартовав из клеток В1 — В3, Машинка уцелеет. Начав движение из любой клетки первых двух строк, начиная со столбца С и до столбца I, Машинка разобьется. Стартовав из любой клетки столбца J, Машинка разобьется, выполняя команду вверх. Начав движение из любой клетки столбца K, L, M, N Машинка разобьется, выполняя команду вправо.

Проанализировав “пещеру” (участок лабиринта в центре, из которого только один выход), приходим к выводу, что Машинка не разобьется, стартовав из столбцов D и E, H, I. В каждом из них по три клетки, а в столбце I — 2. Следовательно, ответ 3 + 9 + 2 = 14.

Ответ: 14
Задание 2 #12769

Исполнитель КОРАБЛИК «живет» в ограниченном прямоугольном водоеме-лабиринте, разделенном на клетки и изображенном на рисунке (вид сверху). Серые клетки — скалистые берега, светлые — свободное пространство, безопасное для передвижения КОРАБЛИКА. По краю водоема-лабиринта также находятся скалы с нанесенными на них номерами и буквами для удобства идентификации клеток.

Система команд исполнителя КОРАБЛИК:

\[\begin{array}{| l | l | l | l |} \hline \text{вверх} & \text{вниз} & \text{влево} & \text{вправо} \\ \hline \end{array}\]

При выполнении любой из этих команд КОРАБЛИК перемещается на одну клетку соответственно (по отношению к наблюдателю): вверх, вниз, влево, вправо. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится КОРАБЛИК (также по отношению к наблюдателю):

\[\begin{array}{| l | l | l | l |} \hline \text{сверху} & \text{снизу} & \text{слева} & \text{справа} \\ \text{свободно} & \text{свободно} & \text{свободно} & \text{свободно} \\ \hline \end{array}\]

Цикл

ПОКА <условие> команда

выполняется, пока условие истинно, иначе происходит переход на следующую строку.

При попытке передвижения на любую серую клетку КОРАБЛИК разбивается о скалы.

Сколько клеток приведенного лабиринта соответствуют требованию, что, стартовав в ней и выполнив предложенную ниже программу, КОРАБЛИК не разобьется?

НАЧАЛО

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

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

вверх

вправо

КОНЕЦ

Показать решение

Стартовав из любой клетки столбцов A, B, D, I, K, M, N, O и клеток F1—F2, G1—G2, I2—N2 кораблик разобьётся, выполнив команду вверх. Начав из любой клетки столбца С клетки E8 и клеток F4-F8, I4-I8, J4, G4 и H4, кораблик не разобьётся. Таким образом, число клеток, стартовав из которых кораблик не разбивается, равно 17.

Ответ: 17
Задание 3 #12770

Исполнитель КОРАБЛИК «живет» в ограниченном прямоугольном водоеме-лабиринте, разделенном на клетки и изображенном на рисунке (вид сверху). Серые клетки — скалистые берега, светлые — свободное пространство, безопасное для передвижения КОРАБЛИКА. По краю водоема-лабиринта также находятся скалы с нанесенными на них номерами и буквами для удобства идентификации клеток.

Система команд исполнителя КОРАБЛИК:

\[\begin{array}{| l | l | l | l |} \hline \text{вверх} & \text{вниз} & \text{влево} & \text{вправо} \\ \hline \end{array}\]

При выполнении любой из этих команд КОРАБЛИК перемещается на одну клетку соответственно (по отношению к наблюдателю): вверх, вниз, влево, вправо. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится КОРАБЛИК (также по отношению к наблюдателю):

\[\begin{array}{| l | l | l | l |} \hline \text{сверху} & \text{снизу} & \text{слева} & \text{справа} \\ \text{свободно} & \text{свободно} & \text{свободно} & \text{свободно} \\ \hline \end{array}\]

Цикл

ПОКА <условие> команда

выполняется, пока условие истинно, иначе происходит переход на следующую строку. При попытке передвижения на любую серую клетку КОРАБЛИК разбивается о скалы.

Сколько клеток приведенного лабиринта соответствуют требованию, что, стартовав в ней и выполнив предложенную ниже программу, КОРАБЛИК не разобьется?

НАЧАЛО

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

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

вверх

вправо

КОНЕЦ

Показать решение

Эффективным приёмом решения является проверка клеток группами. Начав движение из любой клетки столбца А, клеток В7, В8 Кораблик разобьется, выполняя команду вверх. Стартовав из любой клетки первой строки, Кораблик разобьется, выполняя команду вверх. Начав движение из любой клетки столбцов C, D, E, G, H, J, K, L, M, I Кораблик разобьется, выполняя команду вверх.

Начав движение из клетки F8 Кораблик не разобьется. Начав движение из клеток N7, N8, O7, O8 Кораблик не разобьется.

Ответ: 5
Задание 4 #12771

Исполнитель КОРАБЛИК «живет» в ограниченном прямоугольном водоеме-лабиринте, разделенном на клетки и изображенном на рисунке (вид сверху). Серые клетки — скалистые берега, светлые — свободное пространство, безопасное для передвижения КОРАБЛИКА. По краю водоема-лабиринта также находятся скалы с нанесенными на них номерами и буквами для удобства идентификации клеток.

Система команд исполнителя КОРАБЛИК:

\[\begin{array}{| l | l | l | l |} \hline \text{вверх} & \text{вниз} & \text{влево} & \text{вправо} \\ \hline \end{array}\]

При выполнении любой из этих команд КОРАБЛИК перемещается на одну клетку соответственно (по отношению к наблюдателю): вверх, вниз, влево, вправо. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится КОРАБЛИК (также по отношению к наблюдателю):

\[\begin{array}{| l | l | l | l |} \hline \text{сверху} & \text{снизу} & \text{слева} & \text{справа} \\ \text{свободно} & \text{свободно} & \text{свободно} & \text{свободно} \\ \hline \end{array}\]

Цикл

ПОКА < условие > команда

выполняется, пока условие истинно, иначе происходит переход на следующую строку.

При попытке передвижения на любую серую клетку КОРАБЛИК разбивается о скалы.

Сколько клеток приведенного лабиринта соответствуют требованию, что, стартовав в ней и выполнив предложенную. ниже программу, КОРАБЛИК не разобьется?

НАЧАЛО

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

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

вверх

вправо

КОНЕЦ

Показать решение

Разбиться Кораблик может только при выполнении команд “вверх” и “вправо”. Начав из любой клетки строк 1, 3 и клеток A3—A7, С3—С7, G5—O5 кораблик разобьётся, выполняя команду вверх. Стартовав из любой клетки строки 8, кроме клетки O8 и клеток A2, C2, E2, G2, I2, K2, M2, E6—J6, I4—K4 кораблик уцелеет.

Ответ: 25
Задание 5 #12772

Исследуя записи в тетради одного из пиратов, кладоискатели обнаружили следующие указания:

1.60 шагов на юг

2.30 шагов на восток

3.30 шагов на север

4.60 шагов на юг

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

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

Показать решение

Шестьдесят шагов на юг (2 клетки) можно сделать только из 7 клеток: А2, Б1, Б2, Б3, Г4, Д2, Д3. Потом нужно сделать 30 шагов на восток, это возможно сделать только из клеток А2-А4, В5, В6, Г5, Г4, Д3, Д4, Г2. На рисунке показаны клетки, из которых возможно выполнить первые две команды.

Проверив оставшиеся клетки, находим, что единственная клетка, стартуя из которой можно выполнить всю программу — А2. Следовательно, клетка в которой находится клад — Б5.

Ответ: Б5
Задание 6 #12773

Существует исполнитель РОБОТ, умеющий выполнять команды:

ВПРАВО <число шагов> — движение вправо на заданное число шагов;

ВВЕРХ <число шагов> — движение вверх на заданное число шагов;

ВНИЗ <число шагов> — движение вниз на заданное число шагов;

РАЗБИТЬ – разбить стену, стоящую прямо перед роботом по направлению движения;

ПОВТОРИТЬ <число повторений>[<повторяющиеся действия>] — команда повторения указанных действий.

Например, чтобы пройти путь, указанный на рисунке (стрелками указано направление движения), нужно последовательно выполнить команда ВПРАВО 1 ПОВТОРИТЬ2 \[РАЗБИТЬ ВПРАВО1\] ВВЕРХ1 ВПРАВ02 ВНИ31 ВПРАВ02.

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

1) ВПРАВ02 ВВЕРХ1 ПОВТОРИТЬ2 [ВПРАВО1 ВПРАВО1 РАЗБИТЬ] ПОВТОРИТЬ [ВПРАВО1 ВВЕРХ2] ВПРАВО1

2) ВПРАВО2 ВВЕРХ1 ВПРАВО2 РАЗБИТЬ ВПРАВО2 ПОВТОРИТЬ2[ВВЕРХ2 ВПРАВО1]

3) ВПРАВ02 ВВЕРХ1 ВПРАВ01 ПОВТОРИТЬ [ВПРАВ01 РАЗБИТЬ] ПОВТОРИТЬ2 [ВПРАВ01 ВВЕРХ2] ВПРАВО1

4) ВПРАВ02 ПОВТОРИТЬ2 [ВПРАВО 1 РАЗБИТЬ] ВПРАВ01 ПОВТОРИТЕ [ВПРАВО 1 ВВЕРХ2] ВПРАВО1

Показать решение

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

ВПРАВО2 ВВЕРХ1 ВПРАВО2 РАЗБИТЬ ВПРАВО2 ПОВТОРИТЬ2[ВВЕРХ2 ВПРАВО1].

Ответ: 2
Задание 7 #12774

Исполнитель Т1000 «живёт» на бесконечной в обе стороны ленте, разделенной на клетки (одна из клеток является текущей, в ней находится исполнитель). Система команд Т1000 включает следующие:

влево — переместиться на одну клетку влево;

вправо — переместиться на одну клетку вправо;

записать X — записать в текущую клетку число Х.

если X команда — выполнить команду, если в текущей клетке записано число Х.

пока X команда — выполнять команду, пока в текущей клетке записано число X.

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

Дана программа:

пока 1 влево

пока 0 влево

влево

пока 1

{вправо

записать 0}

пока 0 вправо

влево

записать 1

влево

пока 0 влево

влево

Она выполняется начиная с крайней правой клетки с числом 1 в следующей начальной конфигурации (все остальные ячейки бесконечной ленты заполнены нулями и не показаны на схеме):

\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{0} & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 1 & 1 & 0\\ \hline \end{array}\]

Как будет выглядеть лента после остановки программы?

1) 010001111110

2) 010100111110

3) 000111110010

4) 010110011110

Показать решение

Исполнитель находится в крайней правой клетке с числом 1. Начинаем выполнение программы. Пока в клетке в которой находится Т1000 записано число 1 исполнитель передвигается влево. Как только в ячейке ленты исполнитель встретит 0 он начнёт выполнять следующую команду “пока 0 влево”. Продолжая выполнять команды и дойдя до конца, увидим, что лента в конце будет выглядеть так: 010110011110

Ответ: 4

1

Рулетка
Вы можете получить скидку в рулетке!