Задание EGEINFB08376: Черепаха, Чертёжник и Робот

ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий

Открыть решение ↓ Ошибка или пожелание

Тип задачи: Черепаха, Чертёжник и Робот.

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

Впишите правильный ответ.

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

Команды-приказы:

вверх

вниз

влево

вправо

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

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

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

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

снизу свободно

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

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

 

Цикл

ПОКА  условие 

         последовательность команд

КОНЕЦ ЦИКЛА

выполняется, пока условие истинно.

 

В конструкции

ЕСЛИ  условие

     ТО команда1

     ИНАЧЕ команда2

КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно) или команда2 (если условие ложно). В качестве условий в конструкциях ПОКА и ЕСЛИ допускаются перечисленные выше элементарные условия и их комбинации с помощью союзов И и ИЛИ.

 

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

 

НАЧАЛО

ПОКА  слева свободно  ИЛИ сверху свободно 

         ЕСЛИ  сверху свободно

              ТО вверх

              ИНАЧЕ влево

         КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

 

Рисунок из условия ФИПИ

 



i
СВОЙСТВА ЗАДАНИЯ
КЭС:
3.1 Формализация понятия алгоритма. Машина Тьюринга как универсальная модель вычислений
3.2 Оценка сложности вычислений. Время работы и объём используемой памяти, их зависимость от размера исходных данных. Оценка асимптотической сложности алгоритмов. Алгоритмы полиномиальной сложности. Переборные алгоритмы. Примеры различных алгоритмов решения одной задачи, которые имеют различную сложность
3.3 Определение возможных результатов работы простейших алгоритмов управления исполнителями и вычислительных алгоритмов. Определение исходных данных, при которых алгоритм может дать требуемый результат
Тип ответа:Краткий ответ
Номер: B08376
НЕ РЕШЕНО Ответить

Решение задания EGEINFB08376

Ответ: 25

Решение.
В цикле сначала проверяется, свободен ли хотя бы один из двух проходов: влево или вверх. Если оба закрыты, Робот останавливается. Если проход вверх свободен, он выбирает его; иначе идёт влево.
Робот не разобьётся: шаг вверх выполняется только после проверки, а при закрытом верхнем проходе истинность условия цикла гарантирует свободный проход влево.
При каждом шаге уменьшается либо номер строки, либо номер столбца. Обратно вниз или вправо Робот не движется, поэтому цикл обязательно заканчивается.
Нужно выяснить, из каких клеток конечной будет A1. Разбираем начальные клетки построчно с учётом восьми внутренних перегородок на исходной схеме.
Строка 1: A1, B1, C1, D1, E1, F1; всего 6.
Строка 2: A2, B2, C2, D2, E2, F2; всего 6.
Строка 3: A3, B3, E3, F3; всего 4.
Строка 4: A4, B4, E4, F4; всего 4.
Строка 5: A5, B5, E5, F5; всего 4.
Строка 6: F6; всего 1.
В C3 останавливаются: C3, D3, C4, D4, C5, D5, C6, D6, E6 (9 клеток).
В A6 останавливаются: A6, B6 (2 клеток).
Число подходящих клеток: 6 + 6 + 4 + 4 + 4 + 1 = 25.
Проверка: в A1 приходят 25 стартов, в C3 — девять, в A6 — два. Получаем 25 + 9 + 2 = 36, то есть все клетки таблицы 6 × 6 учтены ровно один раз. Старт в самой A1 тоже подходит: цикл сразу завершается.
Ответ: 25.

Помочь улучшить сайт

Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINFB08376.

Сообщение увидит только команда сайта: на странице оно не публикуется.

Комментарии к решению

Комментарии видны всем посетителям сайта.

Комментариев пока нет. Будьте первым.

Чтобы оставить комментарий, войдите или зарегистрируйтесь.