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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Проблемы в решении]] на :Уже не исправить]])
 
Строка 7: Строка 7:
 
[[Участник:StasFomin|StasFomin]] ([[Обсуждение участника:StasFomin|обсуждение]]) 13:28, 19 мая 2015 (MSK): Откуда взялись «'''3''' дополнительных ячейки на ленте»?
 
[[Участник:StasFomin|StasFomin]] ([[Обсуждение участника:StasFomin|обсуждение]]) 13:28, 19 мая 2015 (MSK): Откуда взялись «'''3''' дополнительных ячейки на ленте»?
  
[[Категория:Проблемы в решении]]
+
[[Категория:Уже не исправить]]

Текущая версия на 23:50, 20 мая 2020


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


StasFomin (обсуждение) 13:28, 19 мая 2015 (MSK): Откуда взялись «3 дополнительных ячейки на ленте»?