12

12 задание ЕГЭ информатика

Исполнитель МТ (машина Тьюринга)

1 балл ≈ 6 мин уровень П Исполнение алгоритма (машина Тьюринга)

Задание 12 – исполнитель МТ: лента с символами, головка в одном из состояний q0, q1, … Программа – таблица «состояние × символ → команда». Команда «символ, сдвиг, новое состояние»: записать символ, сдвинуться (L – влево, R – вправо, N – на месте, S – стоп), перейти в состояние. Нужно понять, что делает программа, и ответить на вопрос о результате. 1 балл.

Алгоритм

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

Симулятор на Python

tape = list("λ" + "0110100" + "λλ")
pos = len(tape) - 2              # головка справа от последовательности
rules = {
    ("q0", "λ"): ("λ", "L", "q1"),
    ("q1", "0"): ("1", "L", "q1"),
    ("q1", "1"): ("0", "L", "q1"),
    ("q1", "λ"): ("λ", "S", "q1"),
}
state = "q0"
while True:
    sym, move, state = rules[(state, tape[pos])]
    tape[pos] = sym
    if move == "S":
        break
    if move == "L":
        pos -= 1
    elif move == "R":
        pos += 1
print("".join(tape))             # λ1001011λλ

Разобранный пример. Программа выше: в q0 на пустой клетке шагает влево и переходит в q1; в q1 меняет 0 на 1 и 1 на 0, двигаясь влево; на пустой клетке слева останавливается. То есть она инвертирует всю последовательность. Вопрос: «после выполнения на ленте 343 нуля из 1000 символов; сколько нулей было исходно?» Нули стали единицами и наоборот: было 1000 − 343 = 657 нулей.

Ловушки: сдвиг выполняется после записи символа; команда S тоже сначала записывает символ, потом останавливает; «максимально возможное» число – значит, программа обрабатывает не всю ленту (например, останавливается на первом нуле), и надо подобрать худший/лучший случай.

На экзамене
  • Прогони программу руками на ленте из 4–5 символов – смысл становится понятен.
  • Если программа останавливается на определённом символе – подумай, где он может стоять, чтобы получить «максимум» или «минимум».
  • Симулятор на Python – 15 строк, его стоит написать заранее и держать в голове.

Разобранные задания 12 из открытого банка ФИПИ

Пример 1 · код ФИПИ 5F9BD1

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

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

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

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

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

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

Цикл

ПОКА  условие 

         последовательность команд

КОНЕЦ ПОКА

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

В конструкции

ЕСЛИ  условие

     ТО команда1

     ИНАЧЕ команда2

КОНЕЦ ЕСЛИ

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

 

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

НАЧАЛО

ПОКА нашлось (52) ИЛИ нашлось (1122) ИЛИ нашлось (2222)

    ЕСЛИ нашлось (52)

      ТО заменить (52, 11)

    КОНЕЦ ЕСЛИ

    ЕСЛИ нашлось (2222)

       ТО заменить (2222, 5)

КОНЕЦ ЕСЛИ

    ЕСЛИ нашлось (1122)

       ТО заменить (1122, 25)

    КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

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

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

Показать ответ и решение

Ответ: 78

Программа промоделирована для n=4, 5, …; сумма цифр 37 впервые получается при n=78.

Пример 2 · код ФИПИ F82D52

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

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

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

заменить (111, 27)

преобразует строку 05111150 в строку 0527150.

Если в строке нет вхождений цепочки v, то выполнение команды

заменить (v, w) не меняет эту строку.

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

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

Цикл

ПОКА  условие 

         последовательность команд

КОНЕЦ ПОКА

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

В конструкции

ЕСЛИ  условие

     ТО команда1

     ИНАЧЕ команда2

КОНЕЦ ЕСЛИ

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

 

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

НАЧАЛО

ПОКА нашлось (73) ИЛИ нашлось (322) ИЛИ нашлось (2222)

    ЕСЛИ нашлось (73)

      ТО заменить (73, 2)

    КОНЕЦ ЕСЛИ

    ЕСЛИ нашлось (322)

       ТО заменить (322, 27)

    КОНЕЦ ЕСЛИ

    ЕСЛИ нашлось (2222)

       ТО заменить (2222, 3)

    КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

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

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

Показать ответ и решение

Ответ: 12

Моделируем программу для строк «7» + n двоек при n = 4, 5, …

Первое n, при котором сумма цифр результата равна 15, – 12.

Пример 3 · код ФИПИ 53AFEE

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

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

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

заменить (111, 27)

преобразует строку 05111150 в строку 0527150.

Если в строке нет вхождений цепочки v, то выполнение команды

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

не меняет эту строку.

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

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

Цикл

ПОКА  условие 

         последовательность команд

КОНЕЦ ПОКА

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

В конструкции

ЕСЛИ  условие

     ТО команда1

     ИНАЧЕ команда2

КОНЕЦ ЕСЛИ

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

 

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

НАЧАЛО

ПОКА  нашлось (33333)  ИЛИ нашлось (999) 

         ЕСЛИ  нашлось (33333) 

              ТО заменить (33333, 99)

              ИНАЧЕ заменить (999, 3)

         КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Показать ответ и решение

Ответ: 33399

Моделируем программу (102 девятки): 999→3, пять троек → 99 и т.д.

Результат симуляции: 33399.

Частые вопросы о задании 12

Сколько баллов даёт задание 12 ЕГЭ по информатике?

Максимум – 1 первичный балл. Норма времени на экзамене – около 6 мин. Уровень сложности – П.

Что проверяет задание 12?

Задание 12 – исполнитель МТ: лента с символами, головка в одном из состояний q0, q1, … Программа – таблица «состояние × символ → команда». Команда «символ, сдвиг, новое состояние»: записать символ, сдвинуться (L – влево, R – вправо, N – на месте, S – стоп), перейти в состояние. Нужно понять, что делает программа, и ответить на вопрос о результате. 1 балл.

Как подготовиться к заданию 12?

Прочитайте теорию выше: алгоритм, нужные факты и ловушки. Затем решите подход из 10 заданий с автопроверкой и разбором – первые без регистрации – и вернитесь к ошибкам. В пробниках Сотки номер встречается в полных вариантах ФИПИ с подсчётом баллов.

Упражнения к заданию 12

10 заданий подряд с проверкой и разбором · первые 7 – без регистрации