Задание 12 ЕГЭ по информатике: Алгоритмы и исполнители: страница 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)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

Исполнитель Редактор получает на вход строку, начинающуюся с цифры «5», а затем содержащую n цифр «2», где 3<n<10000. Программа последовательно заменяет первое вхождение 72 на 2, первое вхождение 522 на 27 и первое вхождение 2222 на 5, пока в строке встречается хотя бы одна из этих цепочек. Определите наименьшее значение n, при котором сумма цифр в получившейся строке равна 66.

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

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

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Команда «заменить (v, w)» заменяет в строке первое слева вхождение цепочки цифр v на цепочку w. Если в строке нет вхождений цепочки v, строка не изменяется. Команда «нашлось (v)» проверяет наличие цепочки v в строке, не изменяя её. Цикл выполняется, пока условие истинно.
Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (73) ИЛИ нашлось (322) ИЛИ нашлось (2222)
ЕСЛИ нашлось (73)
ТО заменить (73, 2)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (322)
ТО заменить (322, 27)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (2222)
ТО заменить (2222, 3)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
На вход программе поступает строка, начинающаяся с цифры «7», а затем содержащая n цифр «2», где 3<n<10 000. Определите наименьшее значение n, при котором сумма цифр в строке, получившейся в результате выполнения программы, равна 15.