Задание 12. Информатика. ЕГЭ 2026. Крылов. Вариант 19

На ленте в соседних ячейках записано двоичное представление целого положительного числа без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «\(\lambda\)». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

Программа работы исполнителя:

	\(\lambda\)	\(1\)	\(0\)
\(q_0\)	\(\lambda , \, L, \, q_1\)
\(q_1\)	\(\lambda , \, S, \, q_1\)	\(0, \, L, \, q_1\)	\(1, \, L, \, q_1\)

После выполнения программы на ленте оказалась двоичная запись числа \(240.\) Определите десятичное значение наименьшего числа на ленте, которое могло быть записано на ленте до начала выполнения программы.

com = {('q0', 'l'): 'l,L,q1', ('q1', 'l'): 'l,S,q1',
       ('q1', '1'): '0,L,q1', ('q1', '0'): '1,L,q1'}
step = {'L': -1, 'R': 1, 'S': 0}

for n in range(1, 1000):
    s = ['l'] + list(f'{n:b}') + ['l']

    p = len(s) - 1
    state = 'q0'
    act = 'L'

    while act != 'S':
        ch, act, st = com[(state, s[p])].split(',')
        s[p] = ch
        state = st
        p += step[act]

    if int(''.join(s[1:-1]), 2) == 240:
        print(n)
        break