Определите максимально возможное число нулей в исходной
Условие
| Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов A = {a₀, a₁, ..., a_(n − 1)}), включая специальный пустой символ a₀. Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний Q = {q₀, q₁, ..., q_(n − 1)}. В начальный момент времени головка находится в начальном состоянии q₀.На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может переместиться в ячейку справа или слева от текущей, не меняя находящийся в ней символ, или заменить символ в текущей ячейке без сдвига в соседнюю ячейку. После каждого такта головка переходит в новое состояние или остаётся в прежнем состоянии. Программа работы исполнителя МТ задаётся в табличном виде. | a₀ | a₁ | ... | aₙ₋₁ |
|---|---|---|---|---|
| q₀ | команда | команда | ... | команда |
| q₁ | команда | команда | ... | команда |
| ... | ... | ... | ... | ... |
| qₙ₋₁ | команда | команда | ... | команда |
В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце — возможные состояния головки. На пересечении 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 | λ | \underbrace\lambda_q_0 | ... |
| Конечно состояние исполнителя после завершения выполнения программы. ... | λ | \underbrace\lambda_q_0 | X | X | X | X | λ | λ | ... |
Выполните задание.
На ленте в соседних ячейках записана последовательность из 1200 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.
| Программа работы исполнителя. | λ | 1 | 0 |
|---|---|---|---|
| q₀ | λ, L, q₁ | ||
| q₁ | λ, S, q₁ | 0, S, q₁ | 1, L, q₁ |
После выполнения программы оказалось, что на ленте осталось столько единиц, что их сумма является простым числом. Определите максимально возможное число нулей в исходной последовательности, если известно, что их количество четное число.
Ответ
Ответ и полный разбор откроются после входа
Посмотреть ответРешение по шагам
Как рассуждать
Решение. Рассмотрим программу исполнителя МТ. Исполнитель находится в ближайшей ячейке справа от последовательности. Следовательно, исполнитель выполнит команду влево. Как только исполнитель встретит символ «1» или «λ», то программа исполнителя закончится. Если встретит символ «0», то заменит его на символ «1» и перейдет в левую ячейку. Если последовательность из 1200 символов будет состоять только из символов «0», то исполнитель заменит все на символ «1».Так как нам необходимо найти максимально возможное число «0» в ленте. Самое большое простое число, меньшее 1200, это
Осталось ещё 3 шага
Следовательно, исполнитель заменит 1193 «0» в…
Но так как символов «0» четное число, то…
Приведём решение Егора Чернецова на языке…
Бесплатно · займёт минуту