Задание 12. Информатика. ЕГЭ. Поляков-8322

Если в исходной последовательности все символы будут нулями, то конечная последовательность тоже будет состоять из одних нулей. На первом шаге состояние переключается в \(q_1.\) Рассмотрим последовательность из двух символов \(10.\) Вначале головка исполнителя стоит на \(0.\) Далее, состояние меняется на \(q_2\) и головка сдвигается к \(1.\) На следующем шаге состояние переключается в \(q_3,\) а головка возвращается вправо к \(0.\) Наконец, этот \(0\) меняется на \(1,\) состояние сбрасывается в \(q_1\) и головка смещается влево. Таким образом, получаем, что из последовательности \(10\) появляется последовательность \(11.\) Значит, если мы хотим оставить на ленте ровно \(290\) нулей, мы должны поместить после них справа \(\cfrac{1000 - 290}{2} = 355\) пар \(10.\) Окончательно, максимальное число нулей на ленте вначале равно \(290 + 355 = 645.\)

Python

tab = {('q0', 'l'): 'l,L,q1',
       ('q1', 'l'): 'l,S,q1', ('q1', '0'): '0,L,q2', ('q1', '1'): '1,L,q1',
       ('q2', 'l'): 'l,S,q2', ('q2', '0'): '0,L,q2', ('q2', '1'): '1,R,q3',
       ('q3', 'l'): 'l,S,q3', ('q3', '0'): '1,L,q1',}
move = {'L': -1, 'R': 1, 'S': 0, 'N': 0}

#strip = ['l'] + ['0'] * 1000 + ['l']
strip = ['l'] + ['0'] * 290 + list('10'* ((1000 - 290) // 2)) + ['l']

print('Количество 0 в начальной строке', strip.count('0'))
p = len(strip) - 1
act = 'L'
state = 'q0'

while act != 'S':
    strip[p], act, state = tab[(state, strip[p])].split(',')
    p += move[act]
print('Количество 0 в конечной строке', strip.count('0'))

Ответ: \(645\)