Условия всех задач из категории A13

Проверяемые элементы содержания: умение исполнить алгоритм для конкретного исполнителя с фиксированным набором команд
 
 
 
 

Историческая справка и теоретические сведения

Современное формальное определение алгоритма было дано в 30—50-е годы XX века в работах Тьюринга, Поста, Чёрча (тезис Чёрча — Тьюринга), Н. Винера, А. А. Маркова.

Само слово «алгоритм» происходит от имени хорезмского учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми (алгоритм - аль-Хорезми).

 

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

Фундаментальные свойства алгоритма:

  • дискретность;

  • детерминированность;

  • массовость;

  • понятность;

  • результативность.

Исполнитель алгоритма – автомат (как правило, рассматривается персональный компьютер) или человек, способный выполнять определенный набор действий. Как правило, в роли конкретного исполнителя выступают следующие существа: Робот, Инвентор, Делитель, Сумматор, Дробитель, Утроитель, Вычитатель, Модулятор, Калькулятор и т. п.

 

Базовые характеристики исполнителя:

  • среда выполнения;

  • система элементарных действий;

  • система отказов (или обработка исключительных ситуаций).

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

 

Методические указания

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

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

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

  3. анализировать сложные алгоритмы, включающие вложенные циклы и условные выражения.

 
 
 
 

Задача №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

 
 
 
 
 
 
© 2011-2019 ООО "СтадиМен". Все права сохранены.
Перепечатка и использование материалов с данного сайта, разрешена только по согласию с владельцем.
Владелец оставляет за собой право воспользоваться 146 статьей УК РФ при нарушении авторских и смежных прав.
 
 
 
 
Авторизация на сайте
 
 
 
Обнаружили
ошибку на сайте?