ru.algorithms

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

 Чет Янв 31 2002 22:44, I wrote to me:
 
   У меня почта неспешная. Я сам нашел ошибку со стеком, потом получил письма с
 аналогичными идеями, и еще через день - с их критикой. Hе обессудьте. И на
 идейку с глубиной вложения скобок ответа не получил еще. А опровержение
 придумал: [[[[[[[[ (((( ][ )))) ]]]]]]]] - мой алгоритм тупо удалит 8 круглых
 скобок вместо двух квадратных :((
   Hо есть новая идея - в первую очередь надо считать общую глубину вложения -
 без различия типа скобок! Точнее - во вторую, т.к. в первую очередь надо удалить
 очевидное - первые ЗС и последние ОС каждого типа, правильные пары и
 еще пары шириной 1, например (]).
  (Пара - это ОС левее ЗС одного типа, между которыми нет других скобок этого
 типа. Ширина - количество скобок другого типа внутри пары).
   Убрав внутреннюю скобку, мы не испортим решения, потому что нельзя затратить
 меньше одной скобки, чтобы исправить такой глюк. Если у внутренней скобки есть
 пара снаружи, то в любом случае на исправление потребуется ровно 2 скобки:
  [(]) -> [()]() или []([]). Поэтому, не обращая внимание на всю остальную
 строку, можно давить пары шириной 1, увеличивая общий счетчик исправлений на 1.
   Затем считаем общую глубину вложения. Максимальная глубина будет достигаться
 на четном числе непарных скобок - [) или (]. Видимо дальше надо двигаться
 по строке влево и вправо в поисках ближайших пар. Пар будет несколько, и какую
 выбрать, я пока не понял. Возможно, нужно выбрать макс. глубину отдельного типа,
 или минимальную ширину, или центральную из найденных пар (если их число
 нечетно). Может быть - дифференциальную ширину, т.е. перепад глубины другого
 типа внутри скобок: (][) - ширина 2, дифширина - 0. В худшем случае придется
 перебирать все, но тогда уже О(n*n) не хватит :(.
 
  VK>   Следует приписать каждой скобке (отдельно для каждого типа) глубину
  VK> вложения...
  VK>    +       01   23   45   5   5   5     4 - -3210
  VK>  [ ) [[[[[ (( ] (( ] (( ] ) ] ( ] ) ] [ ) ( )))))
  VK>  0   12345    5    4    3   2   1   0 +
  VK>                       ~~~~~   ~~~~~
  VK>   Здесь две "тривиальных" скобки и одна "правильная" пара. 
 
 аибольшая
 
  VK> глубина вложения обоих типов - 6. (В примере число ОС и ЗС каждого типа
  VK> одинаково. Если это не так, подсчет глубин вложения надо вести с более
  VK> "низкого" края, так что на другом появятся отрицательные глубины.)
  VK>   Из остальных выбираем "самые глубокие" пары, а среди них самую
  VK> "узкую", содержащую внутри себя меньше посторонних скобок. В примере
  VK> - две подчеркнутые пары при глубине 6 имет ширину 1.
  VK>   Убираем их, подбирая пары для "посторонних", считая их и выкидывая.
  VK> При этом глубины вложения меняются:
  VK>          01   23   4    43210                01   23   3210
  VK>  [ [[[[[ (( ] (( ] ( ]] )))))  ->  [ [ [ [[[ (( ] (( ] )))) ->
  VK> -2-10123    3    2   10           -4-3-2-101    1    0
  VK>                    ~~~~~~                          ~~~~~
  VK>             01   - -10                 - -
  VK>  [ [ [ [ [[ (( ] ( )))   -> [ [ [ [ [[ ( )
  VK> -5-4-3-2-10    0           -5-4-3-2-10
  VK>              ~~~~~~~~
  VK>   
 
 а шестом шаге парных скобок не осталось (глубины вложения <=0). Итого
 
  VK> потребовалось добавить 14 скобок (2+2+2+1+1+6).
 
  С уважением, Valentin
 
 --- * ---
  * Origin:  DIA --->> (-:!:-) <<--- LOG  (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