Временная и пространственная сложность алгоритмов/Задачи/ex-braces-parse-in-logspace — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
| Строка 13: | Строка 13: | ||
</latex> | </latex> | ||
| − | [[Category: | + | [[Category:На проверку]] |
<!--Вообще-то, решения уже есть--> | <!--Вообще-то, решения уже есть--> | ||
| + | |||
| + | ===Стенина Мария, группа 974=== | ||
| + | <latex> | ||
| + | Рассмотрим МТ, у которой 2 ленты, одна входная, другая рабочая. Делать МТ будет следующее. Если длина входа $n=1$, то сразу ответ нет. При $n \geq 2$ МТ будет писать одно число на рабочей ленте. Перед началом обработки входа записываем на рабочую ленту 0. Посимвольно считываем вход. Если считанный символ (, то увеличиваем записанное число на единицу. Если считали ), то уменьшаем записанное число на единицу. Проверяем, какое число записано. Если отрицательное, то возвращаем ответ нет, если положительное или нуль, читаем следующий символ. Если после прочтения всего входа на рабочей ленте записан 0, то возвращаем ответ да, иначе возвращаем нет. | ||
| + | |||
| + | Если для записи числа использовать двоичную систему счисления, то количество задействованных ячеек на рабочей ленте не будет превышать $O(\log n)$, что и требовалось показать. | ||
| + | </latex> | ||
Версия 17:44, 9 ноября 2014
Стенина Мария, группа 974