ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Valentin Kononov                     2:5035/38.9    31 Jan 2002  23:44:04
 To : Valentin Kononov
 Subject : re: Посоветyйте алгоpитм, очень надо!!!
 -------------------------------------------------------------------------------- 
 

 Втp Янв 29 2002 23:07, I соwrал-te to Alexei Nilov:
 
  AN>>> Имеется задача:
  AN>>> Дана стpока, состоящая из скобок 4-х видов (,),[,]
  AN>>> Опpеделить минимальное число скобок, котоpые надо подставить в
 
                   ~~~~~~~~~~~
 Пардон, не заметил слова "минимальное".
 
  AN>>> стpокy, чтобы она стала "пpавильной"... Hапpимеp: "[ ( ] )" -
  AN>>> "непpавильная стpока" "[ ] ( [ ] )" - "пpавильная", полyченная пyтем
  AN>>> подстановки в "непpав-ю" 2-х скобок! Интеpесyет алгоpитм... yсловие -
  AN>>> сложность <= O(N*N), а желательно O(N*log N)
 
  VK>   Во-первых, условие неоднозначно. Приведенную строчку можно
  VK> исправить и так: "[ ( ) ] ( )" или так "[ ( [ ] ) ]". Так что стоит
  VK> доопределить - есть ли иерархия у скобок, например. Hо O(N) хватит,
  VK> ИМХО, в любом случае.
 
 Конечно, нет.
 
  VK> 1) Проще всего действовать тривиально:
  VK> нашел скобку, подставь рядом (либо слева, либо справа) парную :))
  VK> 2) А реально примерно так. Держим стек, в который записываем все
  VK> открывающиеся скобки. Если же находим закрывающуюся, смотрим верх стека.
  VK> Если там скобка того же типа, выкидываем ее, если другого или стек пуст,
  VK> то ставим перед этой парную открывающуюся.
 
 .....
 
  VK> ЗЫ: В первом и третьем вариантах строка получится длиннее - в
  VK> первом примерно в 1.5 раза, в 3-ем - в 1.25 (на глазок). А во втором
  VK> - минимально необходимая длина (тоже раза в полтора больше исходной,
  VK> неправильной строки).
 
   И поспешил с оценками. Минимального решения так просто не найти. Я
 прокрутил несколько алгоритмов, но все удалось опровергнуть :( -
 Вот этот пока работает вроде бы правильно.
 (Для простоты буду открывающиеся скобки называть ОС, а закрывающиеся - ЗС)
   Следует приписать каждой скобке (отдельно для каждого типа) глубину
 вложения. При этом первые ЗС и последние ОС помечаем "+", считаем и
 выкидываем - их можно исправить только тривиальным способом. Парные
 ("правильные") скобки помечаем "-" и выкидываем. Вот так:
 
    +       01   23   45   5   5   5     4 - -3210
  [ ) [[[[[ (( ] (( ] (( ] ) ] ( ] ) ] [ ) ( )))))
  0   12345    5    4    3   2   1   0 +
                       ~~~~~   ~~~~~
   Здесь две "тривиальных" скобки и одна "правильная" пара. аибольшая
 глубина вложения обоих типов - 6. (В примере число ОС и ЗС каждого типа
 одинаково. Если это не так, подсчет глубин вложения надо вести с более
 "низкого" края, так что на другом появятся отрицательные глубины.)
   Из остальных выбираем "самые глубокие" пары, а среди них самую "узкую",
 содержащую внутри себя меньше посторонних скобок. В примере - две
 подчеркнутые пары при глубине 6 имет ширину 1.
   Убираем их, подбирая пары для "посторонних", считая их и выкидывая. При
 этом глубины вложения меняются:
          01   23   4    43210                01   23   3210
  [ [[[[[ (( ] (( ] ( ]] )))))  ->  [ [ [ [[[ (( ] (( ] )))) ->
 -2-10123    3    2   10           -4-3-2-101    1    0
                    ~~~~~~                          ~~~~~
             01   - -10                 - -
  [ [ [ [ [[ (( ] ( )))   -> [ [ [ [ [[ ( )
 -5-4-3-2-10    0           -5-4-3-2-10
              ~~~~~~~~
   а шестом шаге парных скобок не осталось (глубины вложения <=0). Итого
 потребовалось добавить 14 скобок (2+2+2+1+1+6).
   Кажется, теперь минимально. о я этого не доказал, могу и соврать!
 А сложность ... по крайней мере < О(n*n).
 
 С уважением, Valentin
 
 --- * ---
  * Origin:  Ложка дегтя в бочке меда: два вкуса, две удачи! (Kursk 2:5035/38.9)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Посоветуйте алгоритм, очень надо!!!   Aleksey Nilov   24 Jan 2002 20:46:28   Re: Посоветуйте алгоритм, очень надо!!!   Grandalf Gray   25 Jan 2002 19:44:12   Re: Посоветуйте алгоритм, очень надо!!!   Grandalf Gray   25 Jan 2002 20:52:01   Re: Посоветуйте алгоритм, очень надо!!!   Aleksey Nilov   26 Jan 2002 03:00:47   Re^2: Посоветуйте алгоритм, очень надо!!!   Sergey Politov   26 Jan 2002 06:50:50   Посоветуйте алгоритм, очень надо!!!   Max Alekseyev   25 Jan 2002 23:15:54   Посоветуйте алгоритм, очень надо!!!   Max Alekseyev   26 Jan 2002 03:40:34   Посоветуйте алгоритм, очень надо!!!   Max Alekseyev   25 Jan 2002 22:08:58   Re: Посоветуйте алгоритм, очень надо!!!   Grandalf Gray   26 Jan 2002 12:46:42   Посоветуйте алгоритм, очень надо!!!   Max Alekseyev   26 Jan 2002 02:30:30   Re: Посоветуйте алгоритм, очень надо!!!   Grandalf Gray   26 Jan 2002 12:46:43   Посоветуйте алгоритм, очень надо!!!   Max Alekseyev   25 Jan 2002 22:04:28   Посоветуйте алгоритм, очень надо!!!   Aleksey Nilov   29 Jan 2002 01:53:54   Посоветуйте алгоритм, очень надо!!!   Max Alekseyev   28 Jan 2002 16:49:14   Re: Посоветуйте алгоритм, очень надо!!!   Sergey Politov   29 Jan 2002 06:34:29   Re: Посоветуйте алгоритм, очень надо!!!   Aleksey Nilov   31 Jan 2002 02:43:30   Re: Посоветуйте алгоритм, очень надо!!!   Ilya Potrepalov   31 Jan 2002 09:41:58   Re: Посоветуйте алгоритм, очень надо!!!   Ilya Potrepalov   31 Jan 2002 13:11:33   Re^2: Посоветуйте алгоритм, очень надо!!!   Sergey Politov   01 Feb 2002 06:43:50   Re: Re^2: Посоветуйте алгоритм, очень надо! !!   Ilya Potrepalov   01 Feb 2002 15:46:36   Посоветуйте алгоритм, очень надо!!!   Sergey Ezhov   26 Jan 2002 14:03:07   Посоветyйте алгоpитм, очень надо!!!   Stanislav Aranovsky   27 Jan 2002 02:28:38   Посоветyйте алгоpитм, очень надо!!!   Sergey Ezhov   27 Jan 2002 22:36:11   Посоветyйте алгоpитм, очень надо!!!   Stanislav Aranovsky   28 Jan 2002 14:08:18   Re: Посоветyйте алгоpитм, очень надо!!!   Sergey Politov   30 Jan 2002 07:23:33   Посоветyйте алгоpитм, очень надо!!!   Sergey Ezhov   30 Jan 2002 22:54:47   Посоветуйте алгоритм, очень надо!!!   Nickita A Startcev   30 Jan 2002 02:18:38   Посоветyйте алгоpитм, очень надо!!!   Stanislav Aranovsky   27 Jan 2002 02:39:02   Re: Посоветyйте алгоpитм, очень надо!!!   Sergey Politov   27 Jan 2002 06:23:28   Посоветyйте алгоpитм, очень надо!!!   Stanislav Aranovsky   28 Jan 2002 03:18:38   Re: Посоветyйте алгоpитм, очень надо!!!   Sergey Politov   28 Jan 2002 06:46:54   Посоветyйте алгоpитм, очень надо!!!   Stanislav Aranovsky   29 Jan 2002 15:25:24   Посоветyйте алгоpитм, очень надо!!!   Oleg Yanchenkov   30 Jan 2002 22:03:08   Посоветyйте алгоpитм, очень надо!!!   Stanislav Aranovsky   01 Feb 2002 02:45:34   re: Посоветyйте алгоpитм, очень надо!!!   Valentin Kononov   30 Jan 2002 00:07:05   Re: Посоветyйте алгоpитм, очень надо!!!   Andrew Ezhguroff   31 Jan 2002 01:40:00   Посоветyйте алгоpитм, очень надо!!!   Stanislav Aranovsky   31 Jan 2002 02:19:28   Re^2: Посоветyйте алгоpитм, очень надо!!!   Sergey Politov   31 Jan 2002 05:25:21   re: Посоветyйте алгоpитм, очень надо!!!   Valentin Kononov   31 Jan 2002 23:44:04   re:Посоветyйте алгоpитм, очень надо!!!   Valentin Kononov   04 Feb 2002 00:16:36   Re: re:Посоветyйте алгоpитм, очень надо!!!   Ilya Potrepalov   05 Feb 2002 07:58:56   Посоветyйте алгоpитм, очень надо!!!   Oleg Yanchenkov   28 Jan 2002 08:30:07   Re: Посоветyйте алгоpитм, очень надо!!!   Sergey Politov   29 Jan 2002 06:08:00   Посоветyйте алгоpитм, очень надо!!!   Stanislav Aranovsky   29 Jan 2002 15:27:40   Re: Посоветуйте алгоритм, очень надо!!!   Michael Leontyev   29 Jan 2002 14:46:19   Посоветyйте алгоpитм, очень надо!!!   Stanislav Aranovsky   30 Jan 2002 04:25:30   Re: Посоветyйте алгоpитм, очень надо!!!   Michael Leontyev   30 Jan 2002 10:45:03   Re^2: Посоветуйте алгоритм, очень надо!!!   Sergey Politov   30 Jan 2002 07:55:24   Посоветyйте алгоpитм, очень надо!!!   Oleg Yanchenkov   01 Feb 2002 00:31:21   Re: Посоветуйте алгоритм, очень надо!!!   Zapadinsky Anatoly \\(ZAB\\)   30 Jan 2002 18:06:09   Re: Посоветуйте алгоритм, очень надо!!!   Michael Leontyev   30 Jan 2002 18:59:35