Модуль: Вопрос 12. Машина Тьюринга

Известен результат — найти вход

До сих пор мы шли вперёд: дана лента, дана программа, посчитай результат.

Теперь наоборот. Известно, что получилось. Спрашивают, что было.

И обычно не просто «что было», а «наибольшее из возможных». Значит, вариантов несколько.

Почему вариантов несколько

Инверсия зависит от длины ленты. Перевернуть 101 — получится 010. Перевернуть 00101 — получится 11010.

Одно и то же число, разная длина записи — разный результат.

Отсюда связь: если на ленте длиной L было число X, то после инверсии значение равно 2^L − 1 − X.

Разворачиваем: X = 2^L − 1 − M, где M — то, что получилось.

Микропаттерн: длина ленты — это и есть перебираемый параметр.

Разбор реальной задачи

Головка слева, программа переворачивает все биты. После работы на ленте оказалась двоичная запись числа 415. Найти наибольшее число, меньшее 70000, которое могло быть на ленте до начала работы.

Идём по длинам ленты и каждый раз считаем X = 2^L − 1 − 415:

• L = 14: X = 15968;
• L = 15: X = 32352;
• L = 16: X = 65120 — ещё меньше 70000;
• L = 17: X = 130656 — уже больше, не подходит.

Наибольшее подходящее — 65120.

Проверка обязательна: 65120 в двоичной записи имеет ровно 16 разрядов и начинается с единицы — значит запись действительно без ведущих нулей, лента такой длины возможна.

Где здесь теряют балл

Первое: забыть проверить длину. Формула даст число при любом L, но запись без ведущих нулей обязана занимать ровно L разрядов. Если не занимает — вариант недопустим.

Второе: остановиться на первом подходящем. Спрашивают наибольшее — значит надо дойти до границы и убедиться, что следующий шаг её уже пробивает.

Третье: перепутать, что известно. M — это результат, X — то, что ищем. Подставить их местами легко, а ответ получится совсем другой.

Регламент для «не более / наибольшее»: нашёл кандидата — проверь соседний. Соседний обязан не проходить. Только тогда ответ верен.

Проверь себя

Порядок действий

1. Опознай программу: что именно она сделала с лентой.
2. Выпиши связь «было — стало» формулой.
3. Перебирай длину ленты от малой к большой.
4. Каждого кандидата проверь на два условия: попадает в границу и имеет нужное число разрядов.
5. Убедись, что следующий кандидат границу уже нарушает.