Задание 12 · Исполнение алгоритма для исполнителя
Практика и итог
Вся тема на одной странице: как решилась задача темы, главное из подтем, порядок решения и частые ошибки.
Одна задача — вся тема
Задача темы — наибольшее число нулей во входе из 12 цифр, если после работы машины осталось ровно 5 нулей, — решается приёмами подтем по очереди. Пролистай решение: в подписи каждого шага — подтема, откуда приём.
- Подтема 1. Учимся на слове 10100: головка в пустой ячейке справа, состояние q0. Такт — запись, сдвиг, новое состояние.
- Подтемы 2 и 3. Таблица задачи темы идёт справа налево до первой единицы: нули хвоста становятся единицами, единица — нулём. 20 → 19: минус один.
- Подтема 4. Обратно: в результате 5 нулей — 4 в части P и новый. Больше всего нулей у входа 0000 1 0000000: 4 + 7 = 11. Ответ задачи темы — 11.
Машину не прогоняли по всей ленте: хватило нескольких тактов, чтобы понять смысл таблицы — «минус один», — а дальше ответ получился рассуждением. Подтемы 5 и 6 разбирают таблицы с фазами и ограничения на сумму цифр.
Карта темы
Каждая подтема дала один способ понять таблицу, и любое решение собирается из них. Сверху — путь от таблицы к ответу, ниже — по блоку на подтему. Заголовок блока ведёт на подтему.
- Тактызапись, сдвиг, новое состояние
- Смыслчто таблица делает с любой строкой
- Ответчисло, слово, количество или граница
1Лента, команда и такт
- λ, L, q1записать → сдвинуться → сменить состояние
- Sзапись и остановка; такт считается
- λпустая ячейка — свой столбец, не ноль
2Однократный проход и количества
- заменакаждая ячейка меняется сама по себе
- количестваиз результата обратно во вход
- два символа в одинвыбор — для наименьшего и наибольшего
3Двоичное число на ленте
- 20 → 19таблица задачи темы: минус один
- N + 2ᵏединица дописана слева
- 2N + 1единица дописана справа
- 2ᵏ − 1 − Nинверсия всех цифр
4Хвост и обратная задача
- P 1 0ᵗ → P 0 1ᵗменяется только хвост
- обратный вопросот результата к входу, пример на границе
5Состояния и фазы
- фазачто делает и чем заканчивается
- тактысумма по фазам, например 2k + 4
6Сумма, простота и ограничениядополнительный урок
- S = 7a + 8b + 3cсумма через количества цифр
- простоебольше 1, делители до √x
Как решать
Любое задание 12 решается одним порядком из пяти шагов. Каждому шагу ты уже учился — под ним номера подтем:
Для обратного вопроса ответ подтверждают входом, на котором достигается граница: в задаче темы это 0000 1 0000000.
Частые ошибки
Восемь ошибок встречаются чаще других, и каждую ловит один вопрос к себе. Выбери ошибку — увидишь, как её исправить, и вопрос, который её ловит:
- запись при S
- при S запись пропустили → сначала запись, потом остановка. Спроси себя: что команда пишет в ячейку при S?подтема 1
- запись после сдвига
- символ записали в новую ячейку → запись — в текущую, потом сдвиг. Спроси себя: где стояла головка, когда читали символ?подтема 1
- начальная ячейка
- головка начала на последней цифре → в пустой ячейке справа. Спроси себя: где головка по условию?подтема 1
- λ — ноль
- пустой символ λ прочитали как 0 → λ — свой столбец таблицы. Спроси себя: какой столбец таблицы я читаю?подтема 1
- q0 — стоп
- состояние q0 приняли за остановку → остановку задаёт только S. Спроси себя: есть ли в команде S?подтема 1
- слово и число
- длину взяли по числу без ведущих нулей → ведущие нули — тоже ячейки слова. Спроси себя: сколько ячеек занимает слово?подтема 3
- выборка вместо границы
- максимум взяли из нескольких запусков → граница рассуждением и пример на ней. Спроси себя: почему больше быть не может?подтема 4
- не та величина
- записали результат, а спрашивали такты → ответ — то, что спрашивают. Спроси себя: число, слово, такты или вход?подтема 5
Итог
Тема пройдена: задача темы решена от первых тактов до ответа 11. Вот что взять с собой.
- ПорядокТакты, смысл, вопрос, граница, проверка.
- ТактЗапись в текущую ячейку, сдвиг, новое состояние.
- СмыслЗамена, ±1 и цифры на краях, хвост или фазы.
- ГраницаРассуждение и вход, на котором она достигается.
- Задача темы0000 1 0000000: 4 + 7 = 11 нулей.
Проверьте себя
Ответь сначала сам, потом открой ответ.
Что таблица задачи темы сделает со словом 10111000?
ОтветСкрыть ответ
10110111: хвост из трёх нулей станет единицами, единица перед ним — нулём. Это 184 − 1 = 183.
Сколько тактов таблица задачи темы делает на слове с хвостом из t нулей?
ОтветСкрыть ответ
t + 2: вход в строку, t нулей хвоста и остановочная замена единицы.
Почему в задаче темы во входе не может быть 12 нулей?
ОтветСкрыть ответ
Без единицы машине нечего вычесть: ей нужна остановочная единица. Значит, нулей не больше 11.
Таблица дописывает единицу справа от двоичного числа N. Какое число получится?
ОтветСкрыть ответ
2N + 1: сдвиг на разряд и единица.
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Программа на числе 45
На ленте записано двоичное представление числа 45 без ведущих нулей. Головка в ближайшей справа от последовательности ячейке. Программа:
| Состояние | λ | 0 | 1 |
|---|---|---|---|
| q0 | λ, L, q1 | — | — |
| q1 | λ, S, q1 | 1, L, q1 | 0, L, q1 |
Определи результат выполнения программы. В ответе запиши получившееся число в десятичной системе счисления.
Введите число.
Подсказка
Каждая цифра меняется на противоположную.
Решение
Машина проходит запись справа налево и меняет каждую цифру на противоположную. 45 = 101101, после инверсии 010010 = 18, то есть 2⁶ − 1 − 45.
Ответ: 18
Такты на числе 95
На ленте записано двоичное представление числа 95 без ведущих нулей. Головка в ближайшей справа от последовательности ячейке. Программа:
| Состояние | λ | 0 | 1 |
|---|---|---|---|
| q0 | λ, L, q1 | — | — |
| q1 | 1, S, q1 | 1, S, q1 | 0, L, q1 |
Сколько тактов выполнит исполнитель, включая такт с остановкой?
Введите число.
Подсказка
Единицы справа становятся нулями, пока не встретится ноль.
Решение
Таблица прибавляет единицу. 95 = 1011111: вход — один такт, пять единиц справа — пять тактов, запись единицы вместо нуля с остановкой — седьмой.
Ответ: 7
Двойки исходной строки
На ленте записана строка из цифр 0, 1, 2. Головка в ближайшей справа от строки ячейке. Программа:
| Состояние | λ | 0 | 1 | 2 |
|---|---|---|---|---|
| q0 | λ, L, q1 | — | — | — |
| q1 | λ, S, q1 | 1, L, q1 | 2, L, q1 | 0, L, q1 |
После выполнения в строке пять нулей, три единицы и две двойки. Сколько двоек было в исходной строке?
Введите число.
Подсказка
Найди, из какой цифры получается конечный ноль.
Решение
Машина один раз заменяет 0 → 1, 1 → 2, 2 → 0. Конечный ноль получается только из двойки, поэтому двоек было пять.
Ответ: 5
Наибольшее число нулей
На ленте записана строка длины 15 из нулей и единиц (начальные нули допускаются). Головка в ближайшей справа от строки ячейке. Программа:
| Состояние | λ | 0 | 1 |
|---|---|---|---|
| q0 | λ, L, q1 | — | — |
| q1 | λ, S, q1 | 1, L, q1 | 0, S, q1 |
После выполнения в строке ровно шесть нулей. Какое наибольшее количество нулей могло быть в исходной строке?
Введите число.
Подсказка
Нули результата — нули левой части и один новый.
Решение
Таблица меняет нули справа на единицы и ближайшую единицу на ноль. Шесть нулей результата — пять нулей левее единицы и один новый. Больше всего нулей при одной единице: пять нулей, единица, девять нулей — 14.
Ответ: 14
Программа на числе 100
На ленте записано двоичное представление числа 100 без ведущих нулей. Головка в ближайшей слева от последовательности ячейке. Программа:
| Состояние | λ | 0 | 1 |
|---|---|---|---|
| q0 | λ, R, q1 | — | — |
| q1 | 0, L, q2 | 0, R, q1 | 1, R, q1 |
| q2 | 1, S, q2 | 0, L, q2 | 1, L, q2 |
Определи результат выполнения программы. В ответе запиши получившееся число в десятичной системе счисления.
Введите число.
Подсказка
Цифры не меняются, справа дописывается 0, слева 1.
Решение
Машина проходит запись вправо, дописывает справа 0, возвращается и дописывает слева 1. 100 = 1100100, семь цифр: справа 0 даёт 200, единица слева от восьми цифр — 2⁸ = 256. Итог 456.
Ответ: 456