Completion requirements
Задача с сайта ФИПИ. Демоверсия 2026.
Как мы видим, условие задачи очень большое. Придется сначала вникнуть в суть задания.
Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов A = {a0, a1, …, an–1}), включая специальный пустой символ a0.
Это можно представить в виде строки электронной таблицы, ячейки которой заполнены данными.
В примере буду представлять короткую последовательность символов двоичного алфавита для наглядности.
Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний Q = {q0, q1, …, qn–1}. В начальный момент времени головка находится в начальном состоянии q0.
Я предлагаю представить эти состояния, как скорости автомобиля или, если кто то знаком только с устройством коробки "автомат", для вас другой пример)
Представьте эти состояния, как некие уровни любой игры)
На определенном уровне определенные действия, разрешения, скиллы и так далее. В общем, состояние - специальная контролирующая штука)
На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может переместиться в ячейку справа или слева от текущей, не меняя находящийся в ней символ, или заменить символ в текущей ячейке без сдвига в соседнюю ячейку. После каждого такта головка переходит в новое состояние или остаётся в прежнем состоянии.
То есть в командах будет прописано точно, остались мы на этом же уровне или перешли на другой. Изменили ли символ или ничего не делали.
Программа работы исполнителя МТ задаётся в табличном виде.
Здесь я приведу пример свой для наглядности.
Заменим q0, q1 и так далее на уровни)
То есть на каждом уровне команды прописываются в ячейки.
В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце – возможные состояния головки. На пересечении i-й строки и j-го столбца находится команда, которую выполняет МТ, когда головка обозревает j-й символ, находясь в i-м состоянии. Если пара «символ – состояние» невозможна, то клетка для команды остаётся пустой. Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент – записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент – один из четырёх символов «L», «R», «N», «S». Символы «L» и «R» означают сдвиг в левую или правую ячейки соответственно, «N» – отсутствие сдвига, «S» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.
Ну, как будто бы всё сразу понятно. (1, L, q1) - записываем единицу, двигаемся влево, переходим в состояние q1, то есть спускаемся на уровень q1
В условии так и приведено.
Например, команда 0, L, q3 выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние q3.
Переходим к решению задания.
Задание короткое), главное дочитать до него)
На ленте в соседних ячейках записана последовательность из 1000 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.
Сразу приведу некий рисунок-черновик для наглядности.
Естественно, все 1000 ячеек делать не буду. Достаточно 10 штук)
Запишу также команды, благо их всего 4 штуки.
(λ, L, q1) - если находимся в состоянии q0 и в ячейке, где находится головка исполнителя символ λ, то значение этой ячейки заменяется на такой же λ и после этого двигается влево на одну ячейку и состояние меняется на q1
(λ, S, q1) - если находимся в состоянии q1 и в ячейке, где находится головка исполнителя символ λ, то значение этой ячейки заменяется на такой же λ и после этого останавливается движение и состояние меняется на q1
(0, S, q1) - если находимся в состоянии q1 и в ячейке, где находится головка исполнителя символ 1, то значение этой ячейки заменяется на 0 и после этого останавливается движение и состояние меняется на q1
(1, L, q1) - если находимся в состоянии q1 и в ячейке, где находится головка исполнителя символ 0, то значение этой ячейки заменяется на 1 и после этого двигается влево на одну ячейку и состояние меняется на q1
Упрощенный вариант)
(λ, L, q1) - если было q0 и символ λ, то ставится λ и двигается влево и состояние на q1
(λ, S, q1) - если было q1 и символ λ, то ставится λ и останавливается движение и состояние на q1
(0, S, q1) - если было q1 и символ 1, то заменяется на 0 и останавливается движение и состояние на q1
(1, L, q1) - если было q1 и символ 0, то заменяется на 1 и двигается влево и состояние на q1
Главный вопрос задачи:
После выполнения программы на ленте осталось ровно 343 нуля. Определите максимально возможное число нулей в исходной последовательности.
Что можем сказать по этому вопросу и как быстро решить задачу?
Давайте на нашем придуманном примере выше то же самое попробуем решить с 3 нулями.
То есть, программа остановилась, а на ленте осталось 3 нуля.
Сейчас пошагово распишу первые шаги программы.
Мы находимся в крайней правой ячейке и у нас символ λ (лямбда)
Состояние в начале q0, значит выполняется команда ((λ, L, q1) - если было q0 и символ λ, то ставится λ и двигается влево и состояние на q1)
Будет так
Тут в ячейке у нас 1, состояние q1, значит применяется команда ((0, S, q1) - если было q1 и символ 1, то заменяется на 0 и останавливается движение и состояние на q1)
Программа останавливается и значение в ячейке будет 0
В этом примере после завершения программы 5 нулей. Не подходит под наше вымышленное условие, где ожидалось 3 нуля.
Значит теперь нужно поразмыслить и придумать такое изначальное распределение 1 и 0, чтобы после завершения осталось три нуля.
После сложных умозаключений (шутка) я понял, что нужно сделать вначале такую раскладку.
Если возникает вопрос, почему же все-таки так, а никак иначе?
Наши команды дают только однозначное движение. Если в ячейке был 0, то он заменяется на 1 и движение идет влево.
Если была 1, то она заменяется на 0 и программа завершается.
Только вариант на картинке даст ровно 3 нуля в конце.
Пару шагов программы в виде скриншотов.
опять (1, L, q1) - если было q1 и символ 0, то заменяется на 1 и двигается влево и состояние на q1
И так далее
Пока не дойдем до ячейки с 1
Пропустим однотипные шаги и вот мы около ячейки с 1
Делаем последний раз ход (1, L, q1)
И теперь в ячейке не 0 на входе, а 1
Значит идет ход (0, S, q1) - если было q1 и символ 1, то заменяется на 0 и останавливается движение и состояние на q1
И всё) программа завершается.
На остатке ровно 3 нуля. Что нам и было нужно)
А изначально их было 9)
Теперь снова к самой демоверсии
На ленте в соседних ячейках записана последовательность из 1000 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.
После выполнения программы на ленте осталось ровно 343 нуля. Определите максимально возможное число нулей в исходной последовательности.
У нас 1000 символов изначально. Нужно, чтобы было 343 в конце. Значит изначально должна быть последовательность, где сначала идут 342 нуля потом одна единица и 1000-343=657 нулей (хотя, если мы уже поняли, то это и не нужно считать).
То есть максимальное количество нулей в начале может быть равно 999, так как одна единица должна быть на 343 ячейке.
Ну как будто бы и всё)
Я думаю, формулировки будут усложняться, так как подобные задачи решаются не долго)
Наверное, будут включать элементы комбинаторики, как в старой задаче № 12.
В спецификации написано по заданию № 12 вот что:
"11 класс, п. 113.7.3. Определение возможных результатов работы простейших алгоритмов управления исполнителями и вычислительных алгоритмов. Определение исходных данных, при которых алгоритм может дать требуемый результат"
Уровень сложности - Повышенный и примерное время выполнения 6 минут.
Значит будут усложнять 100%
Хотя, если ученик ни разу не читал это задание, то там все 6 минут только читать будет))
Last modified: Friday, 22 August 2025, 11:39 PM