Задание 14
ТЕМА 14
"Алгоритм для конкретного исполнителя с фиксированным набором команд"
Пример 1
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах x и y обозначают цепочки цифр.
А) заменить (x, y).
Эта команда заменяет в строке первое слева вхождение цепочки x на цепочку y. Например, выполнение команды
заменить (321, 45)
преобразует строку 438321167 в строку 43845167.
Если в строке нет вхождений цепочки x, то выполнение команды
заменить (x, y) не меняет эту строку.
Б) нашлось (x).
Эта команда проверяет, встречается ли цепочка x в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 54 идущих подряд цифр 7? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (5555) ИЛИ нашлось (7777)
ЕСЛИ нашлось (5555)
ТО заменить (5555, 77)
ИНАЧЕ заменить (7777, 55)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Решение
Сначала данный алгоритм дважды заменит четыре первые семёрки на две пятерки, а затем заменит полученные четыре пятерки на две семёрки. Значит, восемь подряд идущих семёрок заменяются на две семерки (77777777 → 77). Применим последовательно данный алгоритм ко всей строке, получим:
В результате получим: 5577.
Ответ: 5577
Пример 2
Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости, состоит из 8 команд. Четыре команды - это команды-приказы: вверх, вниз, влево, вправо.
При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →.
Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ: сверху свободно, снизу свободно, слева свободно, справа свободно.
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно)
В конструкциях ПОКА и ЕСЛИ условие может содержать команды проверки, а также слова И, ИЛИ, НЕ, обозначающие логические операции.
Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится и программа прервётся.
Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и выполнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке F6?
НАЧАЛО
ПОКА снизу свободно ИЛИ справа свободно
ПОКА справа свободно
вправо
КОНЕЦ ПОКА
ЕСЛИ снизу свободнo
ТО
вниз
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Решение
В соответствии с программой РОБОТ сначала проверяет, свободна ли клетка справа или снизу от него, если это условие истинно, то РОБОТ двигается вправо в соответствии с циклом ПОКА справа свободно.
Как только это условие станет ложным, РОБОТ начинает выполнять второе условие. Проверяется условие: ЕСЛИ снизу свободнo, то РОБОТ будет переходить вниз.
Следовательно, РОБОТ будет двигаться вправо или вниз, пока выполняется условие в программе.
Если РОБОТ изначально находится в диапазоне А3:B6, то он не сможет попасть в клетку F6. Из остальных клеток поля робот выполнив программу, уцелеет и окажется в клетке F6. Таких клеток 28.
Ответ: 28
Пример 3
Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a, b), где a, b – целые числа. Эта команда перемещает Чертёжника из точки с координатами (x, y) в точку с координатами (x + a, y + b). Например, если Чертёжник находится в точке с координатами (3, 5), то команда сместиться на (-2, 3) переместит Чертёжника в точку (1, 8).
Цикл
ПОВТОРИ число РАЗ
последовательность команд
КОНЕЦ ПОВТОРИ
означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным).
Чертёжнику был дан для исполнения следующий алгоритм (количество повторений и смещения в первой из повторяемых команд неизвестны):
НАЧАЛО
Сместиться на (-2, -3)
ПОВТОРИ n РАЗ
Сместиться на (a, b)
Сместиться на (8, -5)
КОНЕЦ ПОВТОРИ
Сместиться на (26, 19)
КОНЕЦ
После выполнения этого алгоритма Чертёжник возвращается в исходную точку. Какое наибольшее число повторений могло быть указано в конструкции «ПОВТОРИ … РАЗ»?
Решение
Выполняя команды: сместиться на (-2, -3) и сместиться на (26, 19), Чертёжник перейдет в точку с координатами (24, 16).
Выполнив цикл, Чертёжник сместится на: n · (a + 8, b − 5).
Так как после выполнения алгоритма Четрёжник должен вернуться в исходную точку, то составим два уравнения, приравнивая х - координаты и y – координаты соответственно. Получим:
n · (a + 8) = 24
n · (b − 5) = 16
По условию задачи числа a, b – целые, n - натуральное. Значит, числа 24 и 16 должны быть кратны n. Необходимо найти наибольшее число повторений цикла n, кратное 24 и 16.
n = 8.
Ответ: 8
Комментарии, отзывы и предложения Вы можете направить на e-mail, указанный в контактах или оставить в гостевой книге, указав тему вопроса: перейти в гостевую книгу