Задание 12 ЕГЭ: что программа сделает с числом на ленте, сколько получится нулей и единиц, какое число было до программы
Работа начинается в q0. Смотрим, что под головкой, и
берём клетку на пересечении строки состояния и столбца символа. Команда
1, L, q2: записать 1, шаг влево, перейти в q2. S
— записать и остановиться. Порядок столбцов в шапке бывает разный
(λ, 0, 1 или λ, 1, 0) — сверяйся с шапкой, а не с памятью.
| В строке состояния | Что оно делает |
|---|---|
0 → 0, L, q1 и 1 → 1, L, q1 | идёт влево по цифрам, ничего не меняя, — до края числа |
0 → 1 и 1 → 0, остаётся в себе | инверсия: меняет каждую цифру на противоположную |
1 → 0, L (в себя), 0 → 1, R (дальше) | прибавляет 1: единицы справа становятся нулями, первый 0 — единицей |
0 → 1, L (в себя), 1 → 0, R (дальше) | вычитает 1: нули справа становятся единицами, первая 1 — нулём |
λ → 1, R, q3 на пустой клетке | дописывает 1 рядом с числом |
1 → λ, L | стирает цифру |
Дальше прогони программу на коротком числе (пять-шесть цифр) на черновике — правило станет видно — и примени его к своему числу.
| Программа | Число x (n двоичных цифр) превращается в |
|---|---|
дописала справа 11 | x · 4 + 3 (k цифр s справа: x · 2k + s) |
дописала слева 1 | x + 2n (слева 10: x + 2n+1) |
| прибавила 1 и дописала 1 | (x + 1) · 2 + 1 |
| инверсия всех цифр | 2n − 1 − x |
| стёрла последнюю цифру | x // 2 |
Если головка идёт по ряду из 57 единиц и переходит q1 → q2 → q3 → q2 → q3 …, состояния ходят по кругу. Выпиши первые клетки, найди блок, который повторяется, и посчитай: сколько полных блоков, что в остатке.
Пойми правило и сними действия в обратном порядке: убрать дописанные цифры, отменить инверсию или «+1». Инверсия теряет длину: у результата впереди могли быть нули, поэтому исходных чисел много — бери наименьшее или наибольшее, как спрашивают.
Задание 12 ЕГЭ: что программа сделает с числом на ленте, сколько получится нулей и единиц, какое число было до программы
Работа начинается в q0. Смотрим, что под головкой, и
берём клетку на пересечении строки состояния и столбца символа. Команда
1, L, q2: записать 1, шаг влево, перейти в q2. S
— записать и остановиться. Порядок столбцов в шапке бывает разный
(λ, 0, 1 или λ, 1, 0) — сверяйся с шапкой, а не с памятью.
| В строке состояния | Что оно делает |
|---|---|
0 → 0, L, q1 и 1 → 1, L, q1 | идёт влево по цифрам, ничего не меняя, — до края числа |
0 → 1 и 1 → 0, остаётся в себе | инверсия: меняет каждую цифру на противоположную |
1 → 0, L (в себя), 0 → 1, R (дальше) | прибавляет 1: единицы справа становятся нулями, первый 0 — единицей |
0 → 1, L (в себя), 1 → 0, R (дальше) | вычитает 1: нули справа становятся единицами, первая 1 — нулём |
λ → 1, R, q3 на пустой клетке | дописывает 1 рядом с числом |
1 → λ, L | стирает цифру |
Дальше прогони программу на коротком числе (пять-шесть цифр) на черновике — правило станет видно — и примени его к своему числу.
| Программа | Число x (n двоичных цифр) превращается в |
|---|---|
дописала справа 11 | x · 4 + 3 (k цифр s справа: x · 2k + s) |
дописала слева 1 | x + 2n (слева 10: x + 2n+1) |
| прибавила 1 и дописала 1 | (x + 1) · 2 + 1 |
| инверсия всех цифр | 2n − 1 − x |
| стёрла последнюю цифру | x // 2 |
Если головка идёт по ряду из 57 единиц и переходит q1 → q2 → q3 → q2 → q3 …, состояния ходят по кругу. Выпиши первые клетки, найди блок, который повторяется, и посчитай: сколько полных блоков, что в остатке.
Пойми правило и сними действия в обратном порядке: убрать дописанные цифры, отменить инверсию или «+1». Инверсия теряет длину: у результата впереди могли быть нули, поэтому исходных чисел много — бери наименьшее или наибольшее, как спрашивают.