Статья Автор: Деникина Н.В., Деникин А.В.

МТ - счётные задачи

Когда ленту нельзя перебрать

«На ленте последовательность из 1000 символов». Дальше спрашивают не число, а количество нулей.

Первый порыв — написать программу и перебрать. Но вариантов 2¹⁰⁰⁰. Это больше, чем атомов во Вселенной.

Перебор отпадает. Значит, нужен инвариант.

Что программа делает со счётом

Возьмём знакомое вычитание единицы. Оно не трогает всю ленту — только правый хвост.

Хвостовые нули превращаются в единицы. Первая справа единица превращается в ноль. Всё левее не меняется.

Считаем изменение: потеряли t нулей (те, что стали единицами), приобрели один (та единица, что стала нулём).

Отсюда инвариант: нулей после = z − t + 1, где z — нулей было, t — хвостовых нулей.

На нашем сквозном примере: z = 4, t = 3, значит после работы нулей 4 − 3 + 1 = 2. Прогон подтверждает: 2.

Как из инварианта достать экстремум

Пусть лента длиной n, после работы осталось k нулей. Из инварианта z = k − 1 + t.

Дальше двигаем t к нужному краю:

наибольшее число нулей — берём t как можно больше. Ограничение: нужна хотя бы одна единица, иначе программа не остановится там, где надо. Значит z ≤ n − 1. Ответ: n − 1;
наименьшее число нулей — t = 0, то есть последний символ единица. Ответ: k − 1;
наибольшее число единиц — это n минус наименьшее число нулей. Ответ: n − k + 1.

Микропаттерн: выразил z через t — дальше смотри только, в какую сторону двигать t.

Проверим инвариант кодом: сравниваем формулу и реальную работу МТ

def run(seq):
    tape = list(seq)
    i = len(tape) - 1
    while i >= 0:
        if tape[i] == '0':
            tape[i] = '1'
            i = i - 1
        else:
            tape[i] = '0'
            break
    return ''.join(tape)

seq = '1011000'
after = run(seq)
z = seq.count('0')
t = len(seq) - len(seq.rstrip('0'))
print(seq, '->', after)
print('formula:', z - t + 1)
print('fact   :', after.count('0'))

Вырожденный случай — заготовленная ловушка

Спрашивают наибольшее число нулей на ленте длиной n. Рука сама тянется написать n: пусть все символы нули.

Проверим. Если единиц нет вообще, головка превратит все нули в единицы и уедет в пустоту. Нулей останется ноль.

Значит вариант «все нули» не подходит никогда. Ответ на единицу меньше: n − 1.

Регламент: получил ответ по формуле — проверь вырожденный случай отдельно. Он почти всегда и есть приманка.

Проверь себя

Лента длиной 1000 символов, после работы программы вычитания единицы осталось 343 нуля. Каково наибольшее возможное количество нулей в исходной последовательности?

Проверить ответ

Лента длиной 600 символов, после работы осталось 421 нуль. Наименьшее возможное количество нулей в исходной последовательности? Запиши только число.

Проверить ответ

Инвариант: нулей после = z − t + 1. Отметь верное.

Проверить ответ

Регламент счётной задачи

Определи, какой хвост ленты трогает программа.
Запиши инвариант: сколько символов потеряли, сколько приобрели.
Вырази z через k и t.
Двинь t к нужному краю, учитывая ограничение «нужна хотя бы одна единица».
Проверь вырожденный случай.
Построй конкретную последовательность и убедись, что она даёт нужное k.

Печать