Задание 12 ЕГЭ по информатике: страница 3

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить(v, w). Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить(111, 27) преобразует строку 05111150 в строку 0527150. Если в строке нет вхождений цепочки v, то выполнение команды заменить(v, w) не меняет эту строку.
Б) нашлось(v). Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Цикл ПОКА условие последовательность команд КОНЕЦ ПОКА выполняется, пока условие истинно. В конструкции ЕСЛИ условие ТО команда1 ИНАЧЕ команда2 КОНЕЦ ЕСЛИ выполняется команда1, если условие истинно, или команда2, если условие ложно.
Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось(48) ИЛИ нашлось(288) ИЛИ нашлось(8888)
ЕСЛИ нашлось(48)
ТО заменить(48, 8)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось(288)
ТО заменить(288, 84)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось(8888)
ТО заменить(8888, 2)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
На вход приведённой выше программе поступает строка, начинающаяся с цифры «4», а затем содержащая n цифр «8» (3<n<10 000).
Определите наименьшее значение n, при котором сумма цифр в строке, получившейся в результате выполнения программы, равна 56.

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Команда «заменить (v, w)» заменяет в строке первое слева вхождение цепочки v на цепочку w. Команда «нашлось (v)» проверяет, встречается ли цепочка v в строке, не изменяя её. Цикл выполняется, пока условие истинно.
Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (48) ИЛИ нашлось (288) ИЛИ нашлось (8888)
ЕСЛИ нашлось (48)
ТО заменить (48, 8)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (288)
ТО заменить (288, 84)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (8888)
ТО заменить (8888, 2)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
На вход программе поступает строка, начинающаяся с цифры «4», а затем содержащая n цифр «8», где 3<n<10000. Определите наименьшее значение n, при котором сумма цифр в строке, получившейся после выполнения программы, равна 64.

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Команда «заменить (v, w)» заменяет в строке первое слева вхождение цепочки v на цепочку w. Если в строке нет вхождений цепочки v, строка не изменяется. Команда «нашлось (v)» проверяет, встречается ли цепочка v в строке.
Цикл выполняется, пока условие истинно. В конструкции «ЕСЛИ условие ТО команда1 ИНАЧЕ команда2» выполняется команда1, если условие истинно, и команда2 — в противном случае.
Какая строка получится в результате применения программы к строке, состоящей из 70 идущих подряд цифр 8?
НАЧАЛО
ПОКА нашлось (2222) ИЛИ нашлось (8888)
ЕСЛИ нашлось (2222)
ТО заменить (2222, 88)
ИНАЧЕ заменить (8888, 22)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

Исполнитель Редактор получает на вход строку цифр. К строке, состоящей из 109 идущих подряд цифр 7, применяют программу: пока в строке встречается 33333 или 777, если встречается 33333, первое слева вхождение 33333 заменяется на 7, иначе первое слева вхождение 777 заменяется на 3. Какая строка получится в результате?

Исполнитель Редактор получает на вход строку цифр. Команда «заменить (v, w)» заменяет в строке первое слева вхождение цепочки v на цепочку w. Команда «нашлось (v)» проверяет, встречается ли цепочка v в строке, не изменяя её. Цикл выполняется, пока условие истинно.
К строке, состоящей из 82 идущих подряд цифр 1, применяют программу:
НАЧАЛО
ПОКА нашлось (11111) ИЛИ нашлось (888)
ЕСЛИ нашлось (11111)
ТО заменить (11111, 88)
ИНАЧЕ
ЕСЛИ нашлось (888)
ТО заменить (888, 8)
КОНЕЦ ЕСЛИ
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Какая строка получится в результате применения программы?

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Команда «заменить (v, w)» заменяет первое слева вхождение цепочки v на цепочку w. Команда «нашлось (v)» проверяет, встречается ли цепочка v в строке, не изменяя её. Цикл выполняется, пока условие истинно.
Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (25) ИЛИ нашлось (355) ИЛИ нашлось (555)
ЕСЛИ нашлось (25)
ТО заменить (25, 5)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (355)
ТО заменить (355, 52)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (555)
ТО заменить (555, 3)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
На вход программе поступает строка, начинающаяся с цифры «3», а затем содержащая n цифр «5», где n>3. Определите наименьшее значение n, при котором после выполнения программы в строке останутся только цифры «5».

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Команда «заменить (v, w)» заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочка v отсутствует, строка не изменяется. Команда «нашлось (v)» проверяет, встречается ли цепочка v в строке, не изменяя её.
Какая строка получится в результате применения приведённой программы к строке, состоящей из 83 идущих подряд цифр 1?
НАЧАЛО
ПОКА нашлось (11111) ИЛИ нашлось (888)
ЕСЛИ нашлось (11111)
ТО заменить (11111, 88)
ИНАЧЕ заменить (888, 8)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Команда «заменить (v, w)» заменяет в строке первое слева вхождение цепочки v на цепочку w. Команда «нашлось (v)» проверяет, встречается ли цепочка v в строке, не изменяя её. Цикл выполняется, пока условие истинно.
Определите количество нулей в строке, получившейся в результате применения программы к входной строке 100…00_⏟55, то есть к строке, состоящей из единицы, за которой следуют 55 нулей подряд.
Программа:
НАЧАЛО
ПОКА нашлось (1)
ЕСЛИ нашлось (10)
ТО заменить (10, 001)
ИНАЧЕ заменить (1, 00)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На ленте в соседних ячейках записано двоичное представление числа 1514 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей справа к последовательности ячейке. Определите результат выполнения программы. Запишите получившееся число в десятичной системе счисления.

Таблица команд машины Тьюринга

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Команда «заменить (v, w)» заменяет первое слева вхождение цепочки v на цепочку w, а команда «нашлось (v)» проверяет наличие цепочки v в строке, не изменяя её. Цикл выполняется, пока условие истинно.
Какая строка получится в результате применения приведённой программы к строке, состоящей из 84 идущих подряд цифр 1?

Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости, включает команды перемещения вверх, вниз, влево и вправо, а также проверки условий «сверху свободно», «снизу свободно», «слева свободно», «справа свободно». Если РОБОТ начинает движение в сторону стены, он разрушается, и выполнение программы прекращается. Цикл выполняется, пока условие истинно.
Сколько клеток лабиринта соответствуют требованию, что, начав в ней выполнение программы, РОБОТ уцелеет и остановится в закрашенной клетке (клетка А1)?
НАЧАЛО
ПОКА слева свободно ИЛИ сверху свободно
ЕСЛИ сверху свободно
ТО вверх
ИНАЧЕ влево
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На ленте в соседних ячейках записано двоичное представление числа 2025 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей справа к последовательности ячейке. Выполните программу работы исполнителя и определите результат в десятичной системе счисления.

Таблица команд машины Тьюринга

На вход программы поступает строка, начинающаяся с символа «>», а затем содержащая 23 цифры 1, 11 цифр 2 и 15 цифр 3, расположенных в произвольном порядке. Определите сумму числовых значений цифр строки, получившейся в результате выполнения программы.
Программа последовательно обрабатывает цифры, следующие за символом «>»: для цифры 1 выполняется замена «>1» на «2>», для цифры 2 — «>2» на «21>», для цифры 3 — «>3» на «11>».

Исполнитель Редактор получает на вход строку цифр. Команда «заменить (v, w)» заменяет первое слева вхождение цепочки v на цепочку w, а команда «нашлось (v)» проверяет наличие цепочки v в текущей строке. Какую строку получим после применения программы к строке, состоящей из 96 идущих подряд цифр 9?

Исполнитель Редактор получает на вход строку из 150 цифр, содержащую по 50 цифр 1, 2 и 3, расположенных в произвольном порядке. В цикле, пока в строке встречается хотя бы одна из цепочек 21, 31 или 32, выполняются следующие команды: если найдена цепочка 21, первое слева её вхождение заменяется на 12; если найдена цепочка 31, первое слева её вхождение заменяется на 13; если найдена цепочка 32, первое слева её вхождение заменяется на 23. Определите, какие цифры будут находиться на 10-м, 80-м и 140-м местах строки после выполнения программы. Запишите полученные цифры подряд без пробелов и разделителей.

Исполнитель Редактор получает на вход строку цифр. Команда «заменить (v, w)» заменяет первое слева вхождение цепочки v на цепочку w, а команда «нашлось (v)» проверяет наличие цепочки v в строке, не изменяя её. Какая строка получится в результате применения программы к строке, состоящей из 81 идущих подряд цифр 1?
НАЧАЛО
ПОКА нашлось (1111) ИЛИ нашлось (8888)
ЕСЛИ нашлось (1111)
ТО заменить (1111, 888)
ИНАЧЕ заменить (8888, 8)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На вход программе поступает строка из 120 цифр, содержащая по 40 цифр 4, 7 и 9, расположенных в произвольном порядке. Программа последовательно заменяет первое слева вхождение цепочек 47, 49 и 97 на цепочки 74, 94 и 79 соответственно, пока ни одна из этих цепочек не встречается. Определите, какие цифры будут находиться на 25-м, 73-м и 105-м местах получившейся строки.
Цифры в строке нумеруются слева направо, начиная с 1. Запишите три цифры подряд без пробелов и разделителей в порядке возрастания номеров мест.

Исполнитель Редактор получает на вход строку, начинающуюся с символа «>», а затем содержащую 15 цифр 1, 20 цифр 2 и 16 цифр 3, расположенных в произвольном порядке. Редактор выполняет программу:
ПОКА нашлось(>1) ИЛИ нашлось(>2) ИЛИ нашлось(>3)
ЕСЛИ нашлось(>1) ТО заменить(>1, 22>) КОНЕЦ ЕСЛИ
ЕСЛИ нашлось(>2) ТО заменить(>2, 2>) КОНЕЦ ЕСЛИ
ЕСЛИ нашлось(>3) ТО заменить(>3, 1>) КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
Команда заменить(v, w) заменяет первое слева вхождение цепочки v на цепочку w. Команда нашлось(v) проверяет наличие цепочки v в строке. Определите сумму числовых значений цифр строки, получившейся в результате выполнения программы.

Исполнитель Редактор получает на вход строку цифр и преобразует её. Команда «заменить (v, w)» заменяет первое слева вхождение цепочки v на цепочку w. Команда «нашлось (v)» проверяет наличие цепочки v, не изменяя строку. Цикл выполняется, пока условие истинно.
Какая строка получится в результате применения программы к строке, состоящей из 92 идущих подряд цифр 3?
НАЧАЛО
ПОКА нашлось (999) или нашлось (333)
ЕСЛИ нашлось (999)
ТО заменить (999, 3)
ИНАЧЕ заменить (333, 9)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

Исполнитель Редактор получает на вход строку цифр. Команда «заменить (v, w)» заменяет первое слева вхождение цепочки v на цепочку w, а команда «нашлось (v)» проверяет наличие цепочки v в строке. Какая строка получится в результате применения программы к строке, состоящей из 81 идущей подряд цифры 1?
НАЧАЛО
ПОКА нашлось (1111) ИЛИ нашлось (88888)
ЕСЛИ нашлось (1111)
ТО заменить (1111, 888)
ИНАЧЕ заменить (88888, 888)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ