Условия всех задач из категории A13
Историческая справка и теоретические сведения
Современное формальное определение алгоритма было дано в 30—50-е годы XX века в работах Тьюринга, Поста, Чёрча (тезис Чёрча — Тьюринга), Н. Винера, А. А. Маркова.
Само слово «алгоритм» происходит от имени хорезмского учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми (алгоритм - аль-Хорезми).
Алгоритм – последовательность понятных для исполнителя действий, приводящих к решению поставленной задачи за разумное время.
Фундаментальные свойства алгоритма:
дискретность;
детерминированность;
массовость;
понятность;
результативность.
Исполнитель алгоритма – автомат (как правило, рассматривается персональный компьютер) или человек, способный выполнять определенный набор действий. Как правило, в роли конкретного исполнителя выступают следующие существа: Робот, Инвентор, Делитель, Сумматор, Дробитель, Утроитель, Вычитатель, Модулятор, Калькулятор и т. п.
Базовые характеристики исполнителя:
среда выполнения;
система элементарных действий;
система отказов (или обработка исключительных ситуаций).
Превалирующее большинство задач из данной категории связано с конкретным исполнителем Роботом, перемещающимся по некому квадратному или прямоугольному ячеистому лабиринту.
Конститутивная цель робота – финализировать свою траекторию в той клетки, с которой было начато его движение. При этом параллельно ведется подсчет подобных клеток.
Методические указания
Для успешного решения задач из данной категории вы должны уметь:
рассматривать предложенный алгоритм исполнителя на конкретных данных;
исследовать все возможные ячейки и отбирать только те ячейки, подходящие под заданные условия;
анализировать сложные алгоритмы, включающие вложенные циклы и условные выражения.
Задача №1
Дано:
система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:
| вверх | вниз | влево | вправо |
При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ: | |||
| сверху свободно | снизу свободно | слева свободно | справа свободно |
Цикл
ПОКА < условие > команда
выполняется, пока условие истинно, иначе происходит переход на следующую строку. Если РОБОТ начнёт движение в сторону стены, то он разрушится и программа прервётся.
Вопрос:
сколько клеток лабиринта соответствуют требованию, что, выполнив предложенную программу, РОБОТ уцелеет и остановится в той же клетке, с которой он начал движение?
НАЧАЛО
ПОКА < справа свободно > вправо
ПОКА < снизу свободно > вниз
ПОКА < слева свободно > влево
ПОКА < сверху свободно > вверх
КОНЕЦ
Варианты ответа
1) 1 2) 2 3) 3 4) 4
Задача №2
Дано:
система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:
| вверх | вниз | влево | вправо |
При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ: | |||
| сверху свободно | снизу свободно | слева свободно | справа свободно |
Цикл
ПОКА < условие > команда
выполняется, пока условие истинно, иначе происходит переход на следующую строку. Если РОБОТ начнёт движение в сторону стены, то он разрушится и программа прервётся.
Вопрос:
сколько клеток лабиринта соответствуют требованию, что, выполнив предложенную программу, РОБОТ уцелеет и остановится в той же клетке, с которой он начал движение?
НАЧАЛО
ПОКА < сверху свободно > вверх
ПОКА < слева свободно > влево
ПОКА < снизу свободно > вниз
ПОКА < справа свободно > вправо
КОНЕЦ
Варианты ответа
1) 1 2) 2 3) 3 4) 4
Задача №3
Дано:
исполнитель РОБОТ может передвигаться на одну клетку вверх, вниз, вправо и влево прямоугольного клетчатого поля, на котором расположены горизонтальные и вертикальные стенки. Двигаться вперед он может только тогда, когда стенок перед ним нет. Команда Крась закрашивает клетку, в которой стоит РОБОТ.
Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:
| сверху свободно | снизу свободно | слева свободно | справа свободно |
Цикл
ПОКА < условие > делать
команда 1
.....
команда n
КОНЕЦ
выполняется, пока условие истинно, иначе происходит переход на следующую строку.
Вопрос:
сколько клеток (К1) приведённого лабиринта соответствуют требованию, что, выполнив предложенную программу, РОБОТ остановится в той же клетке, с которой он начал движение? Сколько клеток (К2) приведённого лабиринта будут при этом закрашены? В ответе укажите сумму таких клеток (К1 + К2).
Варианты ответа:
1) 4 2) 5 3) 6 4) 7