Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 06.09.2010, 12:05
Новичок

Отправить личное сообщение для zhandos Посмотреть профиль Найти все сообщения от zhandos
 
Регистрация: 07.01.2010
Сообщений: 7

Восстановление скобок
Вот есть задача и решение. Можете объяснить это на человеческом?
  #2  
Старый 06.09.2010, 14:27
гость

 
Сообщений: n/a

решение не читал, но тут тривиально решается динамическим программированием. Объясняю на пальцах - чтобы проверить, что последовательность из скобок является правильной, используется следущий алгоритм. Заводим счетчик, изначально он 0, и проходим по последовательности. После каждой открывающей скоби увеличиваем его на 1, после закрывающей - уменьшаем. Последовательност правильная iff счетчик в конце - ноль, и никогда не принималь отрицательные значения.

Соответственно, в динамике ты должен рассмотреть все возможные пути изменения этого счетчика. Состояние в динамике - пара (сколько символом было просмотрено, состояние счетчика).
  #3  
Старый 07.09.2010, 16:45
Новичок

Отправить личное сообщение для zhandos Посмотреть профиль Найти все сообщения от zhandos
 
Регистрация: 07.01.2010
Сообщений: 7

Вот здесь сказано что в ходе вычисления матрицы появляются большие и не нужные числа. Почему ???
  #4  
Старый 07.09.2010, 18:45
гость

 
Сообщений: n/a

Сообщение от zhandos Посмотреть сообщение
Вот здесь сказано что в ходе вычисления матрицы появляются большие и не нужные числа. Почему ???
ну, хех, потому что скобочных последовательностей экспоненциально много. (точное число выражается числами каталана, если мне не изменяет память)

примерЖ на входе 100 знаков вопрос, затем 100 закрывающих скобок. Очевидно, что конечный ответ равен единице, но в процессе динамического программирования у тебя получится промежуточное число, равное общему числу скобочных последовательностей из 100 скобок. оно очень большое.

а теперь почему на эту проблему можно на самом деле тупо "забить": вычисления в компьютере, в случае когда используются лишь операции +, -, * (но не деления - это отдельная история) фактически выполняются по правилам модульной арифметики, т.е. когда происходит переполнение, у тебя на самом деле получается **правильный** результат, но просто он по модулю 2^32 или 2^64. В задаче сказано, что в конце получается маленькое число, заведомо меньше 2^32, поэтому вычисления по модулю тут вполне оправданы, у тебя в конце будет правильный ответ.
  #5  
Старый 08.09.2010, 07:10
Новичок

Отправить личное сообщение для zhandos Посмотреть профиль Найти все сообщения от zhandos
 
Регистрация: 07.01.2010
Сообщений: 7

ОО спасибо Наконец я все понял !!!
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Восстановление вектора входных параметров по выходному в нейронных сетях Geck Искусственный интеллект, нейронные сети 11 07.12.2009 02:34
Восстановление скобок гость Задачи 9 27.07.2008 21:51
Восстановление 3d тела по его проекциям Tur Вычислительная геометрия 0 17.04.2007 15:58