Участник:Kirillskor/ex-braces-parse-in-logspace — Решение Кирилла Скорнякова

Материал из DISCOPAL
< Участник:Kirillskor
Версия от 17:44, 9 мая 2015; Kirillskor (обсуждение | вклад) (Новая страница: «Category:На проверку Скобочная последовательность правильная, если: число ) = числу (, не су…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Скобочная последовательность правильная, если: число ) = числу (, не существует ситуации, что число ) больше числа ( если идти от начала слова. На двух-ленточной МТ алгоритм, считающий количество ( и ) и разность между ними на каждом шаге занимает 3 дополнительных ячейки на ленте, значит принадлежит logspace.