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