Программа машины используется во всех задачах
Исполнитель — головка, движущаяся по бесконечной ленте. В каждой ячейке —
символ 0, 1 или пустой символ λ.
Команда имеет вид новый_символ, движение, новое_состояние; движение —
L (влево), R (вправо), N (стоять) или
S (завершить после команды). Пустая клетка в таблице — недопустимая
ситуация для корректной работы.
| состояние | λ | 1 | 0 |
|---|---|---|---|
| q0 | λ, L, q1 | — | — |
| q1 | λ, S, q1 | 0, S, q1 | 1, L, q1 |
Начальное состояние — q0. Головка стартует в ближайшей пустой ячейке
справа от исходной строки.
Теория
- Лента — бесконечная последовательность ячеек, по одному символу в каждой.
- Головка — устройство, которое читает символ текущей ячейки и записывает в неё новый.
- Состояние — внутренний «режим» головки. В этой программе их два:
q0иq1. - λ — пустой символ; обозначает ячейку, в которую ничего не записано.
- Команда
символ, движение, состояниечитается так: «записать символ, сдвинуться, перейти в состояние». - Движения:
L— влево,R— вправо,N— стоять,S— остановиться после выполнения текущей команды. - Строки таблицы — состояния, столбцы — символы под головкой. На пересечении — что делать.
- В этой задаче ключевое — правый конец строки: именно туда сначала смотрит головка, и именно справа налево идёт замена нулей.
Как думать в таких задачах
- Понять, что машина делает с правым концом строки.
- Обозначить через
tколичество нулей на самом конце строки. - Понять, сколько нулей исчезает и сколько появляется в результате работы.
- Для строки, в которой есть хотя бы одна единица, получается формула
K = Z − t + 1, гдеZ— число нулей в исходной строке. - Отдельно разобрать случай, когда строка состоит из одних нулей.
- Для минимума числа нулей в исходной строке нужно сделать
tкак можно меньше — то есть пусть строка заканчивается единицей. - Для максимума — почти всю строку сделать нулями, оставив всего одну единицу.
Краткий разбор формулы
Если строка не состоит из одних нулей, её можно записать как u 1 0t,
где 0t — хвост из t нулей,
а единица перед ним — ближайшая слева от этого хвоста.
Программа превращает хвостовые нули в единицы, а эту единицу — в ноль:
u 1 0t → u 0 1t.
Значит, в исходной строке было Z нулей, а после работы стало
K = Z − t + 1, откуда Z = K + t − 1.
Если строка состоит только из нулей (длины N), все нули
превратятся в единицы, и K = 0. В этом случае
и минимум, и максимум числа нулей в исходной последовательности равны N.
Генератор задач
Случайные N от 50 до 2000 и корректное K от 0 до N.
Чаще выбирается K > 0, чтобы задача не сводилась к особому случаю.
Готовые примеры
Эти задачи используются и для проверки функции решения.
Ручной режим
Задайте свои N и K и выберите, что искать.
Текущая задача
Задача ещё не выбрана. Сгенерируйте новую, загрузите готовую или задайте параметры вручную.
Симулятор машины Тьюринга
Введите короткую двоичную строку (до 200 символов). Машина выполнит программу по шагам или целиком.
Самопроверка функции решения
Автоматическая проверка функции solveTask на эталонных случаях.