Задание 12. Выполнение алгоритмов исполнителей с фиксированным набором команд. ЕГЭ 2026 по информатике

За это задание ты можешь получить 1 балл. На решение дается около 6 минут. Уровень сложности: повышенный.
Средний процент выполнения: 49%
Ответом к заданию 12 по информатике может быть цифра (число) или слово.

Алгоритм решения задания 12:

  1. Внимательно прочитай описание исполнителя и список его команд.
  2. Зафиксируй начальное состояние (позиция, направление, значения параметров) из условия.
  3. Выполняй команды алгоритма строго по порядку.
  4. После каждой команды фиксируй новое состояние исполнителя.
  5. Если команда зависит от условия, проверяй условие по текущему состоянию и выполняй нужную ветвь.
  6. Доведи выполнение до конца алгоритма и получи итоговое состояние.
  7. Ответь на вопрос задания по итоговому состоянию.
  8. Запиши ответ в требуемом формате.

Задачи для практики

Задача 1

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

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

На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка может:

  • Переместиться в соседнюю ячейку слева или справа, не меняя символ в текущей ячейке;
  • Или заменить символ в текущей ячейке без перемещения;
  • После выполнения действия перейти в новое состояние или остаться в прежнем.

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

Каждая команда имеет три элемента, разделённых запятой:

  1. Символ, записываемый в текущую ячейку;
  2. Действие: L (сдвиг влево), R (сдвиг вправо), N (без сдвига), S (завершение работы);
  3. Новое состояние головки после выполнения команды.

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

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

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

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

λ 1 0
q0 λ, R, q1
q1 λ, S, q1 0, R, q2 1, L, q1
q2 λ, S, q2 1, R, q2 0, S, q2

После выполнения программы на ленте осталось ровно 320 единиц.

Вопрос

Определите максимально возможное число единиц в исходной последовательности.

Решение
Анализ программы

Состояния и команды:

  • q0, λ → R, q1: стартовая команда, головка переходит в q1, ничего не меняя.
  • q1, 1 → 0, R, q2: единица превращается в ноль, головка идёт вправо и переходит в q2.
  • q1, 0 → 1, L, q1: ноль превращается в единицу, головка идёт влево, остаётся в q1.
  • q1, λ → S, q1: пустая клетка останавливает машину.
  • q2, 1 → 1, R, q2: единицы остаются, головка идёт вправо, остаётся в q2.
  • q2, 0 → 0, S, q2: ноль останавливает программу.
  • q2, λ → λ, S, q2: пустая клетка останавливает программу.
Логика работы

1. Машина стартует слева на λ, идёт в q1 на первый символ последовательности.

2. В q1:

  • Если символ = 1 → заменяет на 0 и переходит в q2. Это единственное место, где меняется единица.
  • Если символ = 0 → заменяет на 1 и идёт влево к λ, где встречает команду остановки. В этом случае изменяется только первая ячейка.

3. В q2 головка идёт вправо по единицам, не изменяя их, и останавливается на первом встречном 0 или λ. Остальные единицы остаются нетронутыми.

4. Таким образом, в ходе работы изменяется ровно одна ячейка — самая левая из 600.

Решение

Чтобы найти максимально возможное число единиц в исходной последовательности:

  1. Учти, что после работы на ленте осталось 320 единиц.
  2. Первая ячейка могла быть 1 → превратилась в 0, тогда исходно было 320 + 1 = 321 единица.
  3. Если первая ячейка была 0 → превратилась в 1, тогда исходно было 320 − 1 = 319 единиц.
  4. Максимально возможное число единиц в исходной последовательности = 321.
Ответ: 321
Показать решение
Бесплатный интенсив

Задача 2

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

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

На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка может:

  • Переместиться в соседнюю ячейку слева или справа, не меняя символ в текущей ячейке;
  • Или заменить символ в текущей ячейке без перемещения;
  • После выполнения действия перейти в новое состояние или остаться в прежнем.

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

Каждая команда имеет три элемента, разделённых запятой:

  1. Символ, записываемый в текущую ячейку;
  2. Действие: L (сдвиг влево), R (сдвиг вправо), N (без сдвига), S (завершение работы);
  3. Новое состояние головки после выполнения команды.

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

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

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

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

λ 1 0
q0 λ, L, q1
q1 λ, S, q1 0, L, q1 1, L, q1

После работы Машины Тьюринга у нас осталась двоичная запись числа 240. Найдите десятичную запись наименьшего числа, которое могли записать на ленте до того, как началась работа исполнителя.

Решение

1. Анализ программы: Исполнитель заменяет каждую 1 на 0, и каждый 0 на 1, двигаясь по числу справа налево.

2. Конечное число: 24010 = 111100002.

3. Определение исходного числа: Чтобы получить 11110000 после инверсии, исходная последовательность битов (той же длины) должна была быть 00001111.

4. Условие "без ведущих нулей": Исходное число не могло начинаться с нулей. Для того чтобы после инверсии ведущий ноль появился, в исходном числе на этой позиции должна была быть 1.

  • Минимальное исходное число, удовлетворяющее условию: 1000011112.

5. Перевод в десятичное:

1000011112 = 28 + 23 + 22 + 21 + 20 = 256 + 8 + 4 + 2 + 1 = 271.

Ответ: 271
Показать решение
Бесплатный интенсив

Задача 3

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

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

На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка может:

  • Переместиться в соседнюю ячейку слева или справа, не меняя символ в текущей ячейке;
  • Или заменить символ в текущей ячейке без перемещения;
  • После выполнения действия перейти в новое состояние или остаться в прежнем.

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

Каждая команда имеет три элемента, разделённых запятой:

  1. Символ, записываемый в текущую ячейку;
  2. Действие: L (сдвиг влево), R (сдвиг вправо), N (без сдвига), S (завершение работы);
  3. Новое состояние головки после выполнения команды.

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

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

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

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

λ 1 0
q0 λ, R, q1
q1 λ, S, q1 0, R, q1 1, S, q1

После выполнения программы на ленте осталось ровно 457 единиц.

Вопрос: Определите максимально возможное число единиц в исходной последовательности.

Решение

1. Машина стартует слева от последовательности в состоянии q0 и сразу переходит в q1, не изменяя символ.

2. В состоянии q1:
- Если головка видит 1, она превращает её в 0 и движется вправо.
- Если головка видит 0, она превращает её в 1 и останавливается.
- Пустая λ останавливает программу.

3. После выполнения программы осталось 457 единиц. Это означает, что 457 единиц находятся справа от того нуля, который остановил машину.

4. Чтобы максимально увеличить число единиц в исходной последовательности, нужно, чтобы все символы слева от нуля (который остановил программу) были единицами. Во время работы они превратятся в нули, но при этом они учитываются в исходном числе единиц.

5. Длина последовательности = 800, машина остановилась на первом нуле, который превратился в 1. Все остальные единицы слева были уничтожены. Таким образом, максимально возможное число единиц в исходной последовательности:

800 − 1 = 799

Ответ: 799
Показать решение
Бесплатный интенсив

Задача 4

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

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

На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка может:

  • Переместиться в соседнюю ячейку слева или справа, не меняя символ в текущей ячейке;
  • Или заменить символ в текущей ячейке без перемещения;
  • После выполнения действия перейти в новое состояние или остаться в прежнем.

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

Каждая команда имеет три элемента, разделённых запятой:

  1. Символ, записываемый в текущую ячейку;
  2. Действие: L (сдвиг влево), R (сдвиг вправо), N (без сдвига), S (завершение работы);
  3. Новое состояние головки после выполнения команды.

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

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

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

Программа работы исполнителя:
λ 1 0
q0 λ, L, q1
q1 λ, R, q2 0, L, q1 1, L, q1
q2 λ, S, q2 0, R, q2 1, S, q1

После работы Машины Тьюринга у нас осталось ровно 125 нулей. Найдите минимальное количество нулей на ленте до того, как началась работа исполнителя.

Решение
  1. Чтобы в итоге получилось 125 нулей, изначально в строке должно быть 129 нулей и 126 единиц.
  2. Пример строки: сначала 129 нулей, потом 126 единиц.
  3. Как работает машина:
    • Сначала голова встаёт на конец строки.
    • Идёт влево и меняет каждый символ на противоположный (0 → 1, 1 → 0).
    • Когда достигает левого конца, идёт вправо по единицам. При первой встрече с нулём превращает его в единицу и останавливается.
  4. После работы машины количество нулей становится 125, как требуется.
Ответ: 129
Показать решение
Бесплатный интенсив

Задача 5

Изменения ЕГЭ-2026

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

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

На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка может:

  • Переместиться в соседнюю ячейку слева или справа, не меняя символ в текущей ячейке;
  • Или заменить символ в текущей ячейке без перемещения;
  • После выполнения действия перейти в новое состояние или остаться в прежнем.

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

Каждая команда имеет три элемента, разделённых запятой:

  1. Символ, записываемый в текущую ячейку;
  2. Действие: L (сдвиг влево), R (сдвиг вправо), N (без сдвига), S (завершение работы);
  3. Новое состояние головки после выполнения команды.

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

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

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

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

λ 1 0
q0 λ, R, q1
q1 λ, S, q1 1, R, q1 0, R, q1

После выполнения программы число нулей на ленте стало половиной числа единиц.

Вопрос

Сколько единиц содержалось в исходной последовательности?

Решение
  1. Головка стартует в q0 на пустой клетке слева и сразу идёт вправо в q1.
  2. В q1:
    - если видит 1, оставляет её единицей и идёт вправо;
    - если видит 0, идёт вправо и оставляет ноль;
  3. После прохождения ленты остаётся такое соотношение: число нулей на ленте = половине числа единиц.
  4. Пусть исходное число единиц = X, нулей = Y. После выполнения программы условие: Y_new = (1/2) * X_new. Составляем уравнение, учитывая, какие символы меняются и какие остаются.
  5. Решив уравнение, получаем, что максимально возможное исходное число единиц: 800.
800 единиц

Ответ: 800
Показать решение
Бесплатный интенсив

Задача 6

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

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

На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка может:

  • Переместиться в соседнюю ячейку слева или справа, не меняя символ в текущей ячейке;
  • Или заменить символ в текущей ячейке без перемещения;
  • После выполнения действия перейти в новое состояние или остаться в прежнем.

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

Каждая команда имеет три элемента, разделённых запятой:

  1. Символ, записываемый в текущую ячейку;
  2. Действие: L (сдвиг влево), R (сдвиг вправо), N (без сдвига), S (завершение работы);
  3. Новое состояние головки после выполнения команды.

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

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

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

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

λ 1 0
q0 λ, L, q1
q1 λ, R, q2 0, R, q2 1, L, q1
q2 λ, S, q2 1, R, q2 1, R, q2

После выполнения программы на ленте осталось ровно 100 нулей.

Вопрос: Определите максимально возможное число нулей в исходной последовательности.

Решение

1. Машина стартует справа от последовательности в q0, видит λ и сразу смещается влево в q1, не меняя символ.

2. В состоянии q1:
– На 0: делает 1 и идёт влево.
– На 1: делает 0 и уходит вправо в q2 — это момент разворота.
– Слева λ возвращает её вправо в q2.

3. В состоянии q2 машина идёт вправо, превращая любой символ в 1, и останавливается на правой пустой λ.

4. Значит нули могут сохраниться только слева от той единицы, на которой произошёл разворот. Эти нули машина не трогает. Все остальные нули превращаются в 1.

5. После работы осталось 100 нулей = (нулей слева, нетронутых) + 1 ноль от той самой единицы, где машина развернулась. Значит нетронутых нулей слева было 99.

6. Чтобы максимизировать число нулей в исходной строке, все остальные символы (кроме одной правой единицы) можно сделать нулями — всё равно они потом превратятся в 1.

7. Следовательно, максимальное число нулей до работы:

500 – 1 = 499.

Пример строки: 0(499 шт) + 1. После работы останется ровно 100 нулей.

Ответ: 499
Показать решение
Бесплатный интенсив

Задача 7

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

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

На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка может:

  • Переместиться в соседнюю ячейку слева или справа, не меняя символ в текущей ячейке;
  • Или заменить символ в текущей ячейке без перемещения;
  • После выполнения действия перейти в новое состояние или остаться в прежнем.

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

Каждая команда имеет три элемента, разделённых запятой:

  1. Символ, записываемый в текущую ячейку;
  2. Действие: L (сдвиг влево), R (сдвиг вправо), N (без сдвига), S (завершение работы);
  3. Новое состояние головки после выполнения команды.

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

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

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

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

λ 1 0
q0 λ, L, q1
q1 λ, S, q1 0, L, q1 1, L, q1

После выполнения программы на ленте осталось ровно 5 нулей.

Вопрос: Определите число нулей в исходной последовательности.

Решение

1. Машина стартует справа от последовательности в q0, видит λ и смещается влево в q1.

2. В состоянии q1:
– На 1 пишет 0 и идёт влево.
– На 0 пишет 1 и идёт влево.
– На левую λ сразу останавливается.

3. Значит машина просто проходит всю последовательность слева направо и инвертирует каждый символ: 0 → 1, 1 → 0.

4. После работы осталось 5 нулей. Это значит, что в преобразованной последовательности ровно 5 нулей, то есть ровно 5 исходных единиц превратились в нули.

5. Поэтому в исходной последовательности было ровно 5 единиц, а остальные символы — нули.

6. Исходная длина — 709, значит:

Число нулей в исходной последовательности = 709 − 5 = 704.

Ответ: 704
Показать решение
Бесплатный интенсив

Задача 8

Изменения ЕГЭ-2026

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

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

На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка может:

  • Переместиться в соседнюю ячейку слева или справа, не меняя символ в текущей ячейке;
  • Или заменить символ в текущей ячейке без перемещения;
  • После выполнения действия перейти в новое состояние или остаться в прежнем.

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

Каждая команда имеет три элемента, разделённых запятой:

  1. Символ, записываемый в текущую ячейку;
  2. Действие: L (сдвиг влево), R (сдвиг вправо), N (без сдвига), S (завершение работы);
  3. Новое состояние головки после выполнения команды.

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

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

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

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

λ 1 0
q0 λ, R, q1 0, R, q0 0, R, q1
q1 λ, S, q1 0, R, q0 1, R, q1

После выполнения программы на ленте осталось ровно 50 нулей.

Вопрос

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

Решение
  1. Головка стартует слева в состоянии q0.
  2. В q0:
    • Если символ 1 → превращается в 0, головка идёт вправо и остаётся в q0.
    • Если символ 0 → превращается в 0, головка идёт вправо, переходит в q1.
    • Если символ λ → остаётся лямбда, уходит в q1.
  3. В q1:
    • Если символ 1 →превращается в 0, головка идёт вправо и переходит в q0.
    • Если символ 0 → превращается в 1, головка идёт вправо и остаётся в q1.
    • Если символ λ → программа останавливается.
  4. Проследив движение головки и влияние команд, получаем, что сначала могут идти 0, которые заменятся на 1, потом можно чередовать 0 и 1, они будут все превращаться в 0.
  5. Так как длина последовательности 900, максимально возможное число нулей в исходной последовательности составляет 875, а число единиц 25.

Ответ: 875 нулей

Ответ: 875
Показать решение
Бесплатный интенсив

Задача 9

Изменения ЕГЭ-2026

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

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

На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка может:

  • Переместиться в соседнюю ячейку слева или справа, не меняя символ в текущей ячейке;
  • Или заменить символ в текущей ячейке без перемещения;
  • После выполнения действия перейти в новое состояние или остаться в прежнем.

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

Каждая команда имеет три элемента, разделённых запятой:

  1. Символ, записываемый в текущую ячейку;
  2. Действие: L (сдвиг влево), R (сдвиг вправо), N (без сдвига), S (завершение работы);
  3. Новое состояние головки после выполнения команды.

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

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

В начальный момент времени на ленте подряд записана последовательность из 600 символов, включающая только 0 и 1. Остальные ячейки заполнены λ. Головка расположена на левой границе последовательности (не на пустом символе) и находится в состоянии q1.

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

λ 0 1
q1 λ, S, q1 1, R, q1 0, R, q2
q2 λ, S, q2 0, L, q1 1, R, q2

После выполнения программы на ленте образовалась последовательность вида: сначала идут нули, потом единицы. Левая группа нулей и правая группа единиц не могут быть пустыми.

Вопрос:определите максимально возможное количество нулей в исходной последовательности

Решение

Ответ: максимально возможное количество нулей в исходной последовательности — 598.

Краткое обоснование

  1. По таблице переходов: в начале головка находится на первом символе в состоянии q1.
  2. В состоянии q1 при чтении 1 машина записывает 0 и переходит в q2, а в q2 идёт вправо по единицам, возвращаясь в q1 только при встрече 0. При чтении 0 в q1 он записывает 1 и идёт вправо.
  3. Чтобы по окончании получилась строка вида 0^a1^b с ненулевыми обеими группами, необходимо иметь по крайней мере две единицы в исходной строке. При одной единице (или нуле единиц) получить непустую правую группу единиц невозможно.
  4. Следовательно максимум нулей = длина 600 минус минимум необходимых единиц 2, то есть 600 − 2 = 598. Пример, достигающий этого: исходная строка 11 + 0 повторённый 598 раз; после работы машины получается строка с ровно одним нулём слева и 599 единицами справа.
Ответ: 598
Показать решение
Бесплатный интенсив

Задача 10

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

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

На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка может:

  • Переместиться в соседнюю ячейку слева или справа, не меняя символ в текущей ячейке;
  • Или заменить символ в текущей ячейке без перемещения;
  • После выполнения действия перейти в новое состояние или остаться в прежнем.

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

Каждая команда имеет три элемента, разделённых запятой:

  1. Символ, записываемый в текущую ячейку;
  2. Действие: L (сдвиг влево), R (сдвиг вправо), N (без сдвига), S (завершение работы);
  3. Новое состояние головки после выполнения команды.

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

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

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

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

λ 1 0
q0 λ, L, q1
q1 1, L, q2 0, L, q3
q2 λ, S, q2 0, L, q3 1, L, q2
q3 λ, S, q3 1, L, q2 0, L, q3

Определите число нулей на ленте после выполнения программы.

Решение

  • Машина начинает работу в состоянии q0, находясь справа от последовательности на пустом символе. Согласно программе, при чтении пустого символа она сдвигается влево и переходит в состояние q1. Таким образом, головка оказывается на последнем нуле последовательности.
  • В состоянии q1 при чтении нуля машина не изменяет содержимое ячейки, сдвигается влево и переходит в состояние q3. Далее, находясь в состоянии q3, машина при каждом шаге читает ноль, оставляет его без изменений и продолжает движение влево, не меняя состояние.
  • Такое поведение сохраняется до тех пор, пока головка не дойдёт до левой границы последовательности нулей. При встрече пустого символа машина остаётся в том же состоянии и прекращает активные действия, фактически завершая работу. За всё время выполнения программы ни один ноль не был изменён, поэтому исходная последовательность остаётся неизменной.

    • Ответ: 120
    Показать решение
    Бесплатный интенсив

    Задача 11

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

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

    На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка может:

    • Переместиться в соседнюю ячейку слева или справа, не меняя символ в текущей ячейке;
    • Или заменить символ в текущей ячейке без перемещения;
    • После выполнения действия перейти в новое состояние или остаться в прежнем.

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

    Каждая команда имеет три элемента, разделённых запятой:

    1. Символ, записываемый в текущую ячейку;
    2. Действие: L (сдвиг влево), R (сдвиг вправо), N (без сдвига), S (завершение работы);
    3. Новое состояние головки после выполнения команды.

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

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

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

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

    λ 1 0
    q0 λ, L, q1
    q1 λ, S, q1 0, L, q1 1, L, q1

    После выполнения программы на ленте осталось ровно 10 единиц.

    Вопрос: Определите число единиц в исходной последовательности.

    Решение

    1. Машина стартует справа от последовательности в q0, видит λ и смещается влево в q1.

    2. В состоянии q1:
    – На 1 пишет 0 и идёт влево.
    – На 0 пишет 1 и идёт влево.
    – На левую λ сразу останавливается.

    3. Значит машина проходит всю последовательность слева направо (от правого края к левому) и **инвертирует каждый символ**:
    0 → 1, 1 → 0.

    4. После выполнения программы осталось 10 единиц. Это значит, что в исходной последовательности было 10 нулей, потому что нули превращаются в единицы.

    5. Длина строки — 15, значит исходных единиц было:

    15 − 10 = 5.

    Ответ: 5 единиц в исходной последовательности.

    Ответ: 5
    Показать решение
    Бесплатный интенсив

    Задача 12

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

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

    На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка может:

    • Переместиться в соседнюю ячейку слева или справа, не меняя символ в текущей ячейке;
    • Или заменить символ в текущей ячейке без перемещения;
    • После выполнения действия перейти в новое состояние или остаться в прежнем.

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

    Каждая команда имеет три элемента, разделённых запятой:

    1. Символ, записываемый в текущую ячейку;
    2. Действие: L (сдвиг влево), R (сдвиг вправо), N (без сдвига), S (завершение работы);
    3. Новое состояние головки после выполнения команды.

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

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

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

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

    λ 1 0
    q0 λ, L, q1
    q1 λ, S, q1 0, L, q1 1, L, q1

    После выполнения программы на ленте осталось ровно 100 нулей.

    Вопрос: Определите число нулей в исходной последовательности.

    Решение
    1. Сначала головка в состоянии q0 идёт влево до конца последовательности и переходит в q1.
    2. В состоянии q1 головка идёт влево и инвертирует каждый символ:
      • 0 → 1
      • 1 → 0
    3. После работы программы количество нулей стало 100.
    4. Так как последовательность полностью инвертируется, количество исходных нулей = количество единиц после работы.
    5. Длина последовательности = 456, значит, количество единиц после работы = 456 − 100 = 356.
    6. Следовательно, исходное количество нулей = 356.
    Ответ: 356
    Показать решение
    Бесплатный интенсив

    Задача 13

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

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

    На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка может:

    • Переместиться в соседнюю ячейку слева или справа, не меняя символ в текущей ячейке;
    • Или заменить символ в текущей ячейке без перемещения;
    • После выполнения действия перейти в новое состояние или остаться в прежнем.

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

    Каждая команда имеет три элемента, разделённых запятой:

    1. Символ, записываемый в текущую ячейку;
    2. Действие: L (сдвиг влево), R (сдвиг вправо), N (без сдвига), S (завершение работы);
    3. Новое состояние головки после выполнения команды.

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

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

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

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

    λ 1 0
    q0 λ, L, q1
    q1 λ, R, q2 0, R, q2 1, L, q1
    q2 λ, S, q2 1, R, q2 1, R, q2

    После выполнения программы на ленте осталось ровно 100 нулей.

    Вопрос: Определите максимально возможное число нулей в исходной последовательности.

    Решение

    1. Машина стартует справа от последовательности в q0, видит λ и смещается влево в q1, не изменяя символ.

    2. В состоянии q1:
    – На 0 она пишет 1 и идёт влево.
    – На 1 она пишет 0 и уходит вправо в q2 — это точка разворота.
    – На левую λ возвращается вправо в q2.

    3. В состоянии q2 машина идёт вправо, превращая любой символ в 1, и останавливается на правой λ.

    4. Значит после работы нули могут остаться только слева от той единственной единицы, на которой машина развернулась. Эти нули машина не трогает. Все остальные нули превращаются в 1.

    5. Осталось 100 нулей = (нетронутые слева) + 1 ноль из разворотной единицы. Значит нетронутых слева было 99.

    6. Чтобы максимизировать число нулей в исходной строке, все остальные 901 символ можно сделать нулями — всё равно машина их превратит в единицы.

    7. Максимальное число нулей в исходной последовательности:

    1000 − 1 = 999.

    Пример строки: 0(999 шт) + 1. После работы останется ровно 100 нулей.

    Ответ: 999
    Показать решение
    Бесплатный интенсив

    Задача 14

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

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

    На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка может:

    • Переместиться в соседнюю ячейку слева или справа, не меняя символ в текущей ячейке;
    • Или заменить символ в текущей ячейке без перемещения;
    • После выполнения действия перейти в новое состояние или остаться в прежнем.

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

    Каждая команда имеет три элемента, разделённых запятой:

    1. Символ, записываемый в текущую ячейку;
    2. Действие: L (сдвиг влево), R (сдвиг вправо), N (без сдвига), S (завершение работы);
    3. Новое состояние головки после выполнения команды.

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

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

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

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

    λ 1 0
    q0 λ, L, q1
    q1 λ, R, q2 0, R, q2 1, L, q1
    q2 λ, S, q2 1, R, q2 1, L, q1

    После выполнения программы на ленте осталось ровно 200 нулей.

    Вопрос: Определите максимально возможное число единиц в исходной последовательности.

    Решение

    1. Машина стартует справа в q0, видитλ и смещается влевов q1.

    2. В состоянии q1:
    – На 0 пишет 1 и идёт влево.
    – На 1 пишет 0 и идётвправо в q2 — это точка разворота.
    – На левую λ возвращается вправо в q2.

    3. В состоянии q2:
    – На 1 пишет 1 и идёт вправо.
    – На 0 пишет 1 и идёт влево в q1 — повторноевхождение в q1.
    – На λ — остановка.

    4. Значит машина можетнесколько раз “заходить” в q1 и сновавозвращаться вправо. В q1 она идёт влевои **переписывает всю пройденную зону**, меняя 0→1 и1→0.

    5. Ноль появляется только в q1, когда машина встречает 1 и превращаетего в 0.

    6. После работыосталось 200 нулей. Значит машина могла взять единицу в самом начале, поменять её на 0 и остановиться.

    7. Чтобы получить максимально возможное число единиц в исходной строке, можно сделать всю остальную часть строки единицами и 199 нолями. Двухсотый ноль получитя после замены крайней единицы на 0

    8. Длина строки 10000, значит максимально единиц было:

    10000 − 199 = 9801.

    Ответ: 9801
    Показать решение
    Бесплатный интенсив

    Задача 15

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

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

    На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка может:

    • Переместиться в соседнюю ячейку слева или справа, не меняя символ в текущей ячейке;
    • Или заменить символ в текущей ячейке без перемещения;
    • После выполнения действия перейти в новое состояние или остаться в прежнем.

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

    Каждая команда имеет три элемента, разделённых запятой:

    1. Символ, записываемый в текущую ячейку;
    2. Действие: L (сдвиг влево), R (сдвиг вправо), N (без сдвига), S (завершение работы);
    3. Новое состояние головки после выполнения команды.

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

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

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

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

    λ 1 0
    q0 λ, L, q1
    q1 λ, S, q1 0, S, q1 1, L, q1

    После выполнения программы на ленте осталось ровно 356 нулей.

    Вопрос: Определите минимальное возможное число нулей в исходной последовательности.

    Решение

    1. Машина стартует справа от последовательности в состоянии q0 и сразу переходит в q1, не изменяя символ.

    2. В состоянии q1:
    - Если головка видит 1, она превращает её в 0 и останавливается.
    - Если головка видит 0, она превращает её в 1 и движется влево.
    - Пустая λ останавливает программу.

    3. После выполнения программы осталось 356 нулей. Это означает, что 355 нулей находятся слева от той единицы, которая остановила машину.

    4. Чтобы минимально взять нули в исходной последовательности, нужно, чтобы нули исходной последовательности никто не тронул. Для этого в крайнюю правую часть последовательности поставим 1, тогда когда машина в неё попадёт, она заменит её на 0 и остановит свою работу.

    5. Длина последовательности = 1000, машина остановилась на первой единице, которая превратилась в 0. Все остальные символы тронуты не были. Таким образом, минимальное возможное число нулей в исходной последовательности:

    356 − 1 = 355. Пример строки: 1(644шт) + 0(355шт) + 1. Машина первую единицу заменит на ноль и остановится. Получится 356 нулей.

    Ответ: 355
    Показать решение
    Бесплатный интенсив

    Задача 16

    2024 Открытый

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

    А) заменить (v, w).
    Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды
    заменить (111, 27)
    преобразует строку 05111150 в строку 0527150.
    Если в строке нет вхождений цепочки v, то выполнение команды
    заменить (v, w)
    не меняет эту строку.
    Б) нашлось (v).
    Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
    Цикл

    ПОКА условие
    последовательность команд
КОНЕЦ ПОКА

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

    ЕСЛИ условие
    ТО команда1
    ИНАЧЕ команда2
КОНЕЦ ЕСЛИ

    выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

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

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

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

    Решение
    s = '7' * 45
while "7777" in s or '6666' in s:
    if '6666' in s:
        s = s.replace('6666',"7",1)
    else:
        s = s.replace('7777','66',1)
print(s)
    Ответ: 777
    Показать решение
    Бесплатный интенсив

    Задача 17

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

    А) заменить (v, w).
    Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды
    заменить (111, 27)
    преобразует строку 05111150 в строку 0527150.
    Если в строке нет вхождений цепочки v, то выполнение команды
    заменить (v, w)
    не меняет эту строку.
    Б) нашлось (v).
    Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
    Цикл

    ПОКА условие
    последовательность команд
КОНЕЦ ПОКА

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

    ЕСЛИ условие
    ТО команда1
    ИНАЧЕ команда2
КОНЕЦ ЕСЛИ

    выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

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

    НАЧАЛО 
ПОКА нашлось(99) ИЛИ нашлось(555)
заменить(99, 551)
заменить(5, 229) 
КОНЕЦ ПОКА
КОНЕЦ

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

    Решение
    s = '9' * 36
while "99" in s or '555' in s:
    s = s.replace('99', "551", 1)
    s = s.replace('5', '229', 1)
print(s.count('2'))
    Ответ: 36
    Показать решение
    Бесплатный интенсив

    Задача 18

    2024

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

    А) заменить (v, w).
    Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды
    заменить (111, 27)
    преобразует строку 05111150 в строку 0527150.
    Если в строке нет вхождений цепочки v, то выполнение команды
    заменить (v, w)
    не меняет эту строку.
    Б) нашлось (v).
    Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
    Цикл

    ПОКА условие
    последовательность команд
КОНЕЦ ПОКА

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

    ЕСЛИ условие
    ТО команда1
    ИНАЧЕ команда2
КОНЕЦ ЕСЛИ

    выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

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

    НАЧАЛО 
ПОКА нашлось(2222) 
заменить(222, 44) 
заменить(4, 22) 
КОНЕЦ ПОКА
КОНЕЦ

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

    Решение
    for n in range(1, 100):
    s = '2' * n
    while "2222" in s:
        s = s.replace('222', '44', 1)
        s = s.replace('4', '22', 1)
    if s.count('4') >= 8:
        print(n)
        break
    Ответ: 16
    Показать решение
    Бесплатный интенсив

    Задача 19

    2024

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

    А) заменить (v, w).
    Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды
    заменить (111, 27)
    преобразует строку 05111150 в строку 0527150.
    Если в строке нет вхождений цепочки v, то выполнение команды
    заменить (v, w)
    не меняет эту строку.
    Б) нашлось (v).
    Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
    Цикл

    ПОКА условие
    последовательность команд
КОНЕЦ ПОКА

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

    ЕСЛИ условие
    ТО команда1
    ИНАЧЕ команда2
КОНЕЦ ЕСЛИ

    выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

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

    НАЧАЛО 
ПОКА нашлось(8888) 
заменить(8888, 44) 
заменить(4444, 848) 
КОНЕЦ ПОКА
КОНЕЦ

    На вход приведённой выше программе поступает строка, содержащая n цифр «8» (3 < n < 1000). Определите наименьшее возможное количество цифр «8» в строке, при котором cумма цифр строки, получившейся в результате выполнения программы, равна не менее 52.

    Решение
    def SumDigit(n):
    n = int(n)
    sum_digit = 0
    while n > 0:
        sum_digit += n % 10
        n //= 10
    return sum_digit


for n in range(1, 100):
    s = '8' * n
    while "8888" in s:
        s = s.replace('8888', '44', 1)
        s = s.replace('4444', '848', 1)
    if SumDigit(s) >= 52:
        print(n)
        break
    Ответ: 18
    Показать решение
    Бесплатный интенсив

    Задача 20

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

    А) заменить (v, w).
    Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды
    заменить (111, 27)
    преобразует строку 05111150 в строку 0527150.
    Если в строке нет вхождений цепочки v, то выполнение команды
    заменить (v, w)
    не меняет эту строку.
    Б) нашлось (v).
    Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
    Цикл

    ПОКА условие
    последовательность команд
КОНЕЦ ПОКА

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

    ЕСЛИ условие
    ТО команда1
    ИНАЧЕ команда2
КОНЕЦ ЕСЛИ

    выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

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

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

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

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

    Решение
    for n in range(3, 100):
    s = '3' + '5' * n
    while '25' in s or '355' in s or '555' in s:
        if '25' in s:
            s = s.replace('25', '5', 1)
        if '355' in s:
            s = s.replace('355', '52', 1)
        if '555' in s:
            s = s.replace('555', '3', 1)
    if sum(map(int, s)) == 22:
        print(n)
        break
    Ответ: 33
    Показать решение
    Бесплатный интенсив
    Показать еще

    Рекомендуемые курсы подготовки

    егэ по информатике информатика 10 класс информатика 11 класс информатика с нуля
    Популярные материалы
    • Без воды
    • Ламповая атмосфера
    • Крутые преподаватели

    ЕГЭ 2026: бесплатный курс
    по информатике

    На бесплатном демо-курсе ты:
    • Узнаешь как кодируется изображение
    • Поймешь как решать 7 номер ЕГЭ
    • Разберешься с паролями
    • Потренируешь 11 и 4 номер ЕГЭ
    Получи бесплатный демо-доступ
    Оставь заявку и займи место
    на бесплатном курсе Турбо ЕГЭ
    Нажимая на кнопку «Отправить», вы принимаете положение об обработке персональных данных.