Участник:Kirillskor/ex-braces-parse-in-logspace — Решение Кирилла Скорнякова — различия между версиями
Материал из DISCOPAL
(Новая страница: «Category:На проверку Скобочная последовательность правильная, если: число ) = числу (, не су…») |
StasFomin (обсуждение | вклад) (Массовая правка: замена :Проблемы в решении]] на :Уже не исправить]]) |
||
| (не показаны 3 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
| − | [[ | + | * [[Временная и пространственная сложность алгоритмов/Задачи/ex-braces-parse-in-logspace]] |
| + | |||
| + | |||
Скобочная последовательность правильная, если: число ) = числу (, не существует ситуации, что число ) больше числа ( если идти от начала слова. На двух-ленточной МТ алгоритм, считающий количество ( и ) и разность между ними на каждом шаге занимает 3 дополнительных ячейки на ленте, значит принадлежит logspace. | Скобочная последовательность правильная, если: число ) = числу (, не существует ситуации, что число ) больше числа ( если идти от начала слова. На двух-ленточной МТ алгоритм, считающий количество ( и ) и разность между ними на каждом шаге занимает 3 дополнительных ячейки на ленте, значит принадлежит logspace. | ||
| + | |||
| + | |||
| + | [[Участник:StasFomin|StasFomin]] ([[Обсуждение участника:StasFomin|обсуждение]]) 13:28, 19 мая 2015 (MSK): Откуда взялись «'''3''' дополнительных ячейки на ленте»? | ||
| + | |||
| + | [[Категория:Уже не исправить]] | ||
Текущая версия на 23:50, 20 мая 2020
Скобочная последовательность правильная, если: число ) = числу (, не существует ситуации, что число ) больше числа ( если идти от начала слова. На двух-ленточной МТ алгоритм, считающий количество ( и ) и разность между ними на каждом шаге занимает 3 дополнительных ячейки на ленте, значит принадлежит logspace.
StasFomin (обсуждение) 13:28, 19 мая 2015 (MSK): Откуда взялись «3 дополнительных ячейки на ленте»?