Задание 12
тема 2 из 4

Исполнитель Редактор и машина Тьюринга

Редактор в цикле ищет цепочки цифр и заменяет первое слева вхождение, пока условие цикла истинно. Короткую программу удобно проследить вручную и найти повторяющийся шаг, длинную — повторить на Python через in и replace(v, w, 1). Машина Тьюринга работает по таблице команд: в каждой клетке записаны новый символ, сдвиг головки и новое состояние.

Главная тема в задании12На карте навыков

Как выполнить программу Редактора и машины Тьюринга

Редактор меняет строку командами «нашлось» и «заменить» внутри цикла ПОКА. Машина Тьюринга меняет символы на ленте по таблице команд.

  • «нашлось (v)» — проверка, есть ли цепочка v в строке. «заменить (v, w)» меняет только первое слева вхождение v.
  • Python: «нашлось (v)» — v in s, «заменить (v, w)» — s = s.replace(v, w, 1), ПОКА — while, ЕСЛИ — if, ИНАЧЕ — else.
  • Вручную: выполните несколько проходов цикла, найдите шаг, который повторяется, и посчитайте, сколько раз он сработает.
  • Поиск nn: перебирайте nn циклом for, для каждого запускайте программу и проверяйте условие на результат.
  • Машина Тьюринга: найдите в таблице клетку «состояние — символ», запишите символ, сдвиньте головку, смените состояние. Повторяйте до команды с S.

Команды Редактора

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

Цикл «ПОКА условие … КОНЕЦ ПОКА» повторяет свои команды, пока условие истинно. Условие проверяется перед каждым проходом. Конструкция «ЕСЛИ условие ТО команда1 ИНАЧЕ команда2 КОНЕЦ ЕСЛИ» выполняет ровно одну из двух команд.

Пример

Строка равна 2112112. Редактор выполняет команду «заменить (11, 2)». Что вернёт затем команда «нашлось (22)»?

  1. 1.Ищем первое слева вхождение 11: это вторая и третья цифры строки 2112112.
  2. 2.Меняем его на 2: строка становится 22112. Вторая пара 11 не меняется.
  3. 3.В строке 22112 есть цепочка 22, поэтому «нашлось (22)» возвращает «истина».

Ответ: строка 22112, «нашлось (22)» — истина

Редактор на Python

Строку Редактора хранят в переменной s. «нашлось (v)» записывают как v in s, логическое ИЛИ — как or. «заменить (v, w)» записывают как s = s.replace(v, w, 1): третий аргумент 1 заменяет только первое вхождение. Строку из 82 восьмёрок задают как '8' * 82, строку из единицы и 70 двоек — как '1' + '2' * 70.

Ответ берут из итоговой строки: саму строку печатают print(s), число цифр 2 считают через s.count('2'), сумму цифр — через sum(int(c) for c in s). Если в строке есть нецифровой символ, его пропускают: sum(int(c) for c in s if c.isdigit()).

Цикл с ЕСЛИ–ИНАЧЕ: одна замена за проход

Если в теле цикла стоит «ЕСЛИ … ТО … ИНАЧЕ …», за один проход выполняется ровно одна замена. Сначала проверяется первое условие. Вторая замена работает, только когда первой цепочки в строке нет. Вложенная конструкция «ИНАЧЕ ЕСЛИ» на Python — elif.

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

Пример

К строке из 30 цифр 8 применили программу: ПОКА нашлось (1111) ИЛИ нашлось (8888): ЕСЛИ нашлось (1111) ТО заменить (1111, 8) ИНАЧЕ заменить (8888, 11). Какая строка получится?

  1. 1.Единиц нет, работает «заменить (8888, 11)»: 11 и 26 восьмёрок.
  2. 2.Цепочки 1111 ещё нет, снова «заменить (8888, 11)»: 1111 и 22 восьмёрки.
  3. 3.Теперь есть 1111, она заменяется на 8: 23 восьмёрки. Группа из трёх замен убрала 7 восьмёрок.
  4. 4.Группа работает, пока восьмёрок не меньше 8: 30→23→16→9→230 \to 23 \to 16 \to 9 \to 2.
  5. 5.В строке 88 нет ни 1111, ни 8888, цикл заканчивается. Программа печатает 88.

Ответ: 88

Несколько ЕСЛИ подряд: до трёх замен за проход

Если в теле цикла стоят три отдельных конструкции «ЕСЛИ … ТО … КОНЕЦ ЕСЛИ» без ИНАЧЕ, за один проход могут сработать все три. Они проверяются по порядку, и каждое ЕСЛИ видит строку, которую уже изменили предыдущие. Цепочка, которая появилась после первого ЕСЛИ, первым ЕСЛИ в этом проходе уже не проверяется.

На Python это три отдельных if подряд. Запись через elif даст другой результат: после первой замены остальные проверки в проходе пропускаются.

Пример

Программа: ПОКА нашлось (31) ИЛИ нашлось (411) ИЛИ нашлось (1111): ЕСЛИ нашлось (31) ТО заменить (31, 1); ЕСЛИ нашлось (411) ТО заменить (411, 13); ЕСЛИ нашлось (1111) ТО заменить (1111, 4). На вход подана строка 411111: четвёрка и 5 единиц. Какая строка получится?

  1. 1.Проход 1. Цепочки 31 нет. Есть 411: строка 13111. Цепочки 1111 нет: после 3 стоят только три единицы.
  2. 2.Проход 2. Есть 31: строка 1111. Цепочки 411 нет. Есть 1111: строка 4.
  3. 3.В строке 4 нет ни 31, ни 411, ни 1111. Цикл заканчивается.

Ответ: 4

Поиск наименьшего n: перебор программой

Вопрос «найдите наименьшее nn, при котором сумма цифр результата равна 20» решают перебором. Программу Редактора оформляют функцией run(s): она получает строку и возвращает результат. Цикл for n in range(4, 10000) строит входную строку, вызывает функцию и проверяет условие. Первое подходящее nn печатают и останавливают цикл через break.

Если спрашивают наибольшее nn, break не ставят: в переменную записывают каждое подходящее nn, и после цикла в ней остаётся последнее. Перебор до 10000 со строками в тысячи символов идёт несколько минут, это нормально.

Пример

На вход программе из предыдущего примера подают строку из цифры 4 и nn цифр 1, 3<n<100003 < n < 10000. Найдите наименьшее nn, при котором сумма цифр результата равна 20.

  1. 1.Функция run повторяет цикл с тремя отдельными if.
  2. 2.Для каждого nn строим строку '4' + '1' * n и считаем сумму цифр результата.
  3. 3.Первое nn с суммой 20 программа печатает и выходит из цикла: 47.

Ответ: 47

Строка со стрелкой: каждая цифра меняется отдельно

В части задач строка начинается со знака >, а все замены имеют вид «> и цифра». Знак > идёт по строке слева направо. Каждая замена либо переносит его за цифру и меняет эту цифру, например заменить (>1, 22>), либо меняет цифру справа от него, не сдвигаясь, например заменить (>2, >3). Цифры слева от > больше не меняются.

Поэтому каждая цифра превращается в свою цепочку независимо от остальных, и порядок цифр во входной строке не важен. Проследите одну цифру каждого вида до момента, когда > пройдёт за неё. Сумма цифр результата — сумма вкладов всех цифр, она линейно зависит от nn. Затем проверьте n=1,2,3,…n = 1, 2, 3, \ldots на простоту суммы.

Пример задания

Открытый банк ФИПИ

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

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

 

В конструкции
   ЕСЛИ условие
      ТО команда1
      ИНАЧЕ команда2
   КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (>1) ИЛИ нашлось (>2) ИЛИ нашлось (>0)
   ЕСЛИ нашлось (>1)
      ТО заменить (>1, 22>)
   КОНЕЦ ЕСЛИ
   ЕСЛИ нашлось (>2)
      ТО заменить (>2, 2>)
   КОНЕЦ ЕСЛИ
   ЕСЛИ нашлось (>0)
      ТО заменить (>0, 1>)
   КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ 

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

Машина Тьюринга: лента, головка, таблица команд

Машина Тьюринга (в ЕГЭ — исполнитель МТ) — это бесконечная лента из ячеек и головка, которая читает и пишет символы. В каждой ячейке стоит один символ алфавита. Пустой символ обозначают λ\lambda. Головка в каждый момент находится в одном из состояний q0,q1,…q_0, q_1, \ldots; работа начинается в состоянии q0q_0.

Программа — таблица: строки — состояния, столбцы — символы. В клетке «состояние — символ» записана команда из трёх частей: символ, который пишется в текущую ячейку; сдвиг L (влево), R (вправо) или S (стоп); новое состояние. Сначала пишется символ, затем головка сдвигается. После команды с S машина останавливается. За один такт выполняется одна команда.

Пример

На ленте записано 10110210110_2, вокруг пустые ячейки. Головка стоит в ближайшей пустой ячейке справа, состояние q0q_0. Таблица: q0q_0 и λ\lambda — λ, L, q1; q1q_1 и 0 — 0, L, q1; q1q_1 и 1 — 1, L, q1; q1q_1 и λ\lambda — 1, L, q2; q2q_2 и λ\lambda — λ, S, q2. Какое число будет на ленте?

  1. 1.q0q_0, пустая ячейка: пишем λ\lambda, сдвиг влево, состояние q1q_1. Головка на последней цифре 0.
  2. 2.В q1q_1 цифры 0 и 1 переписываются без изменений, головка идёт влево через все пять цифр.
  3. 3.q1q_1, пустая ячейка слева от числа: пишем 1, сдвиг влево, состояние q2q_2.
  4. 4.q2q_2, пустая ячейка: команда λ, S, q2, машина останавливается.
  5. 5.На ленте 1101102=32+16+4+2=54110110_2 = 32 + 16 + 4 + 2 = 54: программа приписала 1 слева.

Ответ: 54

Машина Тьюринга на Python

Длинную ленту удобнее пройти программой. Таблицу команд хранят в словаре rules: ключ — пара (состояние, символ), значение — тройка (символ, сдвиг, состояние). Ленту хранят в словаре tape: ключ — номер ячейки, значение — символ. Ячейки, которых нет в словаре, пустые: tape.get(pos, 'λ').

Цикл берёт команду для текущей пары, пишет символ, при S останавливается, иначе сдвигает номер ячейки pos на −1-1 или +1+1. В конце непустые символы склеивают слева направо и переводят в десятичную систему через int(res, 2): перевод в десятичную систему.

Пример

На ленте записано двоичное представление числа 2025, головка стоит в ближайшей пустой ячейке справа, состояние q0q_0. Программа та же, что в предыдущем примере. Какое число в десятичной системе будет на ленте?

  1. 1.bin(2025)[2:] даёт запись 11111101001, её символы кладём в ячейки 0–10.
  2. 2.Головка начинает в ячейке 11, сразу справа от числа.
  3. 3.Программа приписывает 1 слева: 211+2025=2048+2025=40732^{11} + 2025 = 2048 + 2025 = 4073. Программа печатает 4073.

Ответ: 4073

Что делает программа: найдите смысл таблицы

По таблице часто видно, какую операцию машина выполняет с числом. Пример: головка идёт от правого края влево, каждую 1 меняет на 0 и идёт дальше, а на первом 0 или на пустой ячейке пишет 1 и останавливается. Так в столбик прибавляют единицу к двоичному числу: 10112+1=110021011_2 + 1 = 1100_2. Если смысл найден, ответ считают без трассировки по шагам. Проверить смысл можно программой из предыдущего блока.

Пример задания

Открытый банк ФИПИ

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

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

  a0 a1 … an–1
q0 команда команда … команда
q1 команда команда … команда
… … … … …
qn–1 команда команда … команда


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

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

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

Программа

  λ Z
q0 λ, L, q0 X, L, q1
q1 λ, L, q1 X, L, q2
q2 λ, S, q2 X, L, q2


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

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

… λ λ Z Z Z Z λ λ …
▲ q0


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

… λ λ X X X X λ λ …
▲ q2


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

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


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

Потренируйте навык

Все задания на этот навык

Решать