ЕГЭ задание 12. Циклические алгоритмы

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов A = {a₀, a₁, … a_n-1}), включая специальный пустой символ a₀.

Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний Q = {q₀, q₁, … q_n-1}. В начальный момент времени головка находится в начальном состоянии q₀.

На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может переместиться в ячейку справа или слева от текущей, не меняя находящийся в ней символ, или заменить символ в текущей ячейке без сдвига в соседнюю ячейку. После каждого такта головка переходит в новое состояние или остаётся в прежнем состоянии.

Программа работы исполнителя МТ задаётся в табличном виде.

	a₀	a₁	…	a_n-1
q₀	команда	команда	…	команда
q₁	команда	команда	…	команда
…	…	…	…	…
q_n-1	команда	команда	…	команда

В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце — возможные состояния головки. На пересечении i-й строки и j-го столбца находится команда, которую выполняет МТ, когда головка обозревает j-й символ, находясь в i-м состоянии. Если пара «символ — состояние» невозможна, то клетка для команды остаётся пустой. Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент — записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент — один из четырёх символов «L», «R», «N», «S». Символы «L» и «R» означают сдвиг в левую или правую ячейки соответственно, «N» — отсутствие сдвига, «S» — завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент — новое состояние головки после выполнения команды.

Например, команда 0, L, q3 выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние q3.

Приведём пример выполнения программы, заданной таблично.

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

Программа

	λ	Z
q₀	λ, L, q₀	X, L, q₁
q₁	λ, S, q₁	X, L, q₁

заменяет на ленте все символы «Z» на «X» и останавливает исполнителя в первой ячейке слева от последовательности символов «X».

Возможное начальное состояние исполнителя:

…	λ	λ	Z	Z	Z	Z	λ	λ	…
								▲ q₀

Конечное состояние исполнителя после завершения выполнения программы:

…	λ	λ	X	X	X	X	λ	λ	…
		▲ q₁

Выполните задание.

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

Программа работы исполнителя:

	λ	1	0
q₀	λ, L, q₁
q₁	λ, S, q₁	0, S, q₁	1, L, q₁

После выполнения программы на ленте осталось ровно 605 нулей. Определите минимально возможное число нулей в исходной последовательности.

СтатГрад 23 октября 2025 года

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов A = {a₀, a₁, … a_n-1}), включая специальный пустой символ a₀.

Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний Q = {q₀, q₁, … q_n-1}. В начальный момент времени головка находится в начальном состоянии q₀.

На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может переместиться в ячейку справа или слева от текущей, не меняя находящийся в ней символ, или заменить символ в текущей ячейке без сдвига в соседнюю ячейку. После каждого такта головка переходит в новое состояние или остаётся в прежнем состоянии.

Программа работы исполнителя МТ задаётся в табличном виде.

	a₀	a₁	…	a_n-1
q₀	команда	команда	…	команда
q₁	команда	команда	…	команда
…	…	…	…	…
q_n-1	команда	команда	…	команда

В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце — возможные состояния головки. На пересечении i-й строки и j-го столбца находится команда, которую выполняет МТ, когда головка обозревает j-й символ, находясь в i-м состоянии. Если пара «символ — состояние» невозможна, то клетка для команды остаётся пустой. Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент — записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент — один из четырёх символов «L», «R», «N», «S». Символы «L» и «R» означают сдвиг в левую или правую ячейки соответственно, «N» — отсутствие сдвига, «S» — завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент — новое состояние головки после выполнения команды.

Например, команда 0, L, q3 выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние q3.

Приведём пример выполнения программы, заданной таблично.

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

Программа

	λ	Z
q₀	λ, L, q₀	X, L, q₁
q₁	λ, S, q₁	X, L, q₁

заменяет на ленте все символы «Z» на «X» и останавливает исполнителя в первой ячейке слева от последовательности символов «X».

Возможное начальное состояние исполнителя:

…	λ	λ	Z	Z	Z	Z	λ	λ	…
								▲ q₀

Конечное состояние исполнителя после завершения выполнения программы:

…	λ	λ	X	X	X	X	λ	λ	…
		▲ q₁

Выполните задание.

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

Программа работы исполнителя:

	λ	1	0
q₀	λ, L, q₁
q₁	λ, S, q₁	0, S, q₁	1, L, q₁

После выполнения программы на ленте осталось ровно 343 нуля. Определите максимально возможное число нулей в исходной последовательности.

Демонстрационный вариант 2026 года

Редактор получает на вход строку символов и преобразовывает её. Редактор может выполнять две команды, в обеих командах \(v\) и \(w\) обозначают цепочки цифр.

заменить \((v, w)\)

Эта команда заменяет в строке первое слева вхождение цепочки \(v\) на цепочку \(w\).

нашлось \((v)\)

Эта команда проверяет, встречается ли цепочка \(v\) в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Дана программа для исполнителя Редактор:

НАЧАЛО
ПОКА нашлось (727) ИЛИ нашлось (777) ИЛИ нашлось (222)
  ЕСЛИ нашлось (222)
  ТО заменить (222, 7)
  ИНАЧЕ
    ЕСЛИ нашлось (777)
    ТО заменить (777, 7)
    ИНАЧЕ заменить (727, 2)
    КОНЕЦ ЕСЛИ
  КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

Какая строка получится в результате применения приведённой выше программы к строке вида 2…27…7 (77 цифр «2», затем 22 цифр «7»)? В ответе запишите полученную строку.

МЦКО-2025. 10 класс, 7 мая 2025

Редактор получает на вход строку символов и преобразовывает её. Редактор может выполнять две команды, в обеих командах \(v\) и \(w\) обозначают цепочки цифр.

заменить \((v, w)\)

Эта команда заменяет в строке первое слева вхождение цепочки \(v\) на цепочку \(w\).

нашлось \((v)\)

Эта команда проверяет, встречается ли цепочка \(v\) в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Дана программа для исполнителя Редактор:

НАЧАЛО
ПОКА нашлось (35) ИЛИ нашлось (355) ИЛИ нашлось (3444)
  ЕСЛИ нашлось (35)
  ТО заменить (35, 4)
  ИНАЧЕ
    ЕСЛИ нашлось (355)
    ТО заменить (355, 4)
    ИНАЧЕ заменить (3444, 3)
    КОНЕЦ ЕСЛИ
  КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

Какая строка получится в результате применения приведённой выше программы к строке вида 3…34…4 (6 цифр «3», затем 75 цифр «4»)? В ответе запишите полученную строку.

МЦКО-2025. Демонстрационный вариант 10 класс

Исполнитель Редактор получает на вход строку символов и преобразовывает её. Редактор может выполнять две команды, в обеих командах \(v\) и \(w\) обозначают цепочки символов.

А) заменить \((v, w)\).

Эта команда заменяет в строке первое слева вхождение цепочки \(v\) на цепочку \(w\). Например, выполнение команды заменить \((111, 27)\) преобразует строку 05111150 в строку 0527150.

Если в строке нет вхождений цепочки v, то выполнение команды заменить \((v, w)\) не меняет эту строку.

Б) нашлось \((v)\).

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 81 идущей подряд цифры 1? В ответе запишите полученную строку.

НАЧАЛО
ПОКА нашлось (11111) ИЛИ нашлось (888)
  ЕСЛИ нашлось (11111)
	ТО заменить (11111, 88)
	ИНАЧЕ заменить (888,8)
  КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

Демонстрационный вариант 2025 года

Исполнитель Редактор получает на вход строку символов и преобразовывает её. Редактор может выполнять две команды, в обеих командах \(v\) и \(w\) обозначают цепочки символов.

А) заменить \((v, w)\).

Эта команда заменяет в строке первое слева вхождение цепочки \(v\) на цепочку \(w\). Например, выполнение команды заменить \((111, 27)\) преобразует строку 05111150 в строку 0527150.

Если в строке нет вхождений цепочки v, то выполнение команды заменить \((v, w)\) не меняет эту строку.

Б) нашлось \((v)\).

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Дана программа для Редактора:

НАЧАЛО
    ПОКА нашлось (1111) ИЛИ нашлось (8888)
        ЕСЛИ нашлось (1111)
            ТО заменить (1111, 8)
        ИНАЧЕ заменить (8888, 11) 
        КОНЕЦ ЕСЛИ
    КОНЕЦ ПОКА
КОНЕЦ

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 82 идущих подряд цифр 8? В ответе запишите полученную строку.

Федеральная апробация КЕГЭ 15 мая 2024 года

Исполнитель Редактор получает на вход строку символов и преобразовывает её. Редактор может выполнять две команды, в обеих командах \(v\) и \(w\) обозначают цепочки символов.

А) заменить \((v, w)\).

Эта команда заменяет в строке первое слева вхождение цепочки \(v\) на цепочку \(w\). Например, выполнение команды заменить \((111, 27)\) преобразует строку 05111150 в строку 0527150.

Если в строке нет вхождений цепочки v, то выполнение команды заменить \((v, w)\) не меняет эту строку.

Б) нашлось \((v)\).

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Дана программа для Редактора:

НАЧАЛО
    ПОКА нашлось (1111) ИЛИ нашлось (7777)
        ЕСЛИ нашлось (1111)
            ТО заменить (1111, 77)
        ИНАЧЕ заменить (7777, 1) 
        КОНЕЦ ЕСЛИ
    КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «7», а затем содержащая \( n \) цифр «1» \( (3 < n < 10000) \).

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

ЕГКР 27 апреля 2024 года (Московский пробник)

Исполнитель Редактор получает на вход строку символов и преобразовывает её. Редактор может выполнять две команды, в обеих командах \(v\) и \(w\) обозначают цепочки символов.

А) заменить \((v, w)\).

Эта команда заменяет в строке первое слева вхождение цепочки \(v\) на цепочку \(w\). Например, выполнение команды заменить \((111, 27)\) преобразует строку 05111150 в строку 0527150.

Если в строке нет вхождений цепочки v, то выполнение команды заменить \((v, w)\) не меняет эту строку.

Б) нашлось \((v)\).

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Дана программа для Редактора:

НАЧАЛО
    ПОКА нашлось (1111) ИЛИ нашлось (8888)
        ЕСЛИ нашлось (1111)
            ТО заменить (1111, 88)
        ИНАЧЕ заменить (8888, 11) 
        КОНЕЦ ЕСЛИ
    КОНЕЦ ПОКА
КОНЕЦ

Определите строку, которая получится в результате применения приведённой выше программы к входной строке, содержащей 45 цифр «8».

В ответе укажите только полученную строку.

Досрочный период КЕГЭ 9 апреля 2024 года

Исполнитель Редактор получает на вход строку символов и преобразовывает её. Редактор может выполнять две команды, в обеих командах \(v\) и \(w\) обозначают цепочки символов.

А) заменить \((v, w)\).

Эта команда заменяет в строке первое слева вхождение цепочки \(v\) на цепочку \(w\). Например, выполнение команды заменить \((111, 27)\) преобразует строку 05111150 в строку 0527150.

Если в строке нет вхождений цепочки v, то выполнение команды заменить \((v, w)\) не меняет эту строку.

Б) нашлось \((v)\).

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Дана программа для Редактора:

НАЧАЛО
    ПОКА нашлось (72) ИЛИ нашлось (522) ИЛИ нашлось (2222) 
        ЕСЛИ нашлось (72)
            ТО заменить (72, 22) 
        КОНЕЦ ЕСЛИ
        ЕСЛИ нашлось (522)
            ТО заменить (522, 25)
        КОНЕЦ ЕСЛИ
        ЕСЛИ нашлось (2222)
            ТО заменить (2222, 5)
        КОНЕЦ ЕСЛИ
    КОНЕЦ ПОКА 
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «5», а затем содержащая \( n \) цифр «2» \( (3 < n < 10 000) \).

Определите наименьшее значение \( n \), при котором сумма числовых значений цифр в строке, получившейся в результате выполнения программы, будет равна 63.

Апробация КЕГЭ 5 марта 2024 года

Исполнитель Редактор получает на вход строку символов и преобразовывает её. Редактор может выполнять две команды, в обеих командах \(v\) и \(w\) обозначают цепочки символов.

А) заменить \((v, w)\).

Эта команда заменяет в строке первое слева вхождение цепочки \(v\) на цепочку \(w\). Например, выполнение команды заменить \((111, 27)\) преобразует строку 05111150 в строку 0527150.

Если в строке нет вхождений цепочки v, то выполнение команды заменить \((v, w)\) не меняет эту строку.

Б) нашлось \((v)\).

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Дана программа для Редактора:

НАЧАЛО
ПОКА нашлось (52) ИЛИ нашлось (2222) ИЛИ нашлось (1122)
    ЕСЛИ нашлось (52)
        ТО заменить (52, 11)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (2222)
        ТО заменить (2222, 5)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (1122)
        ТО заменить (1122, 25)
    КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «5», а затем содержащая \( n \) цифр «2» \( (3 < n < 10 000) \). Определите наибольшее значение \( n \), при котором сумма цифр в строке, получившейся в результате выполнения программы, равна 64.

Демонстрационный вариант 2024 года