|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 25 Jan 2002 22:04:28
To : Aleksey Nilov
Subject : Посоветуйте алгоритм, очень надо!!!
--------------------------------------------------------------------------------
Replying to a message of Aleksey Nilov to ALL:
AN> Дана строка, состоящая из скобок 4-х видов (,),[,]
AN> Определить минимальное число скобок, которые надо подставить в строку,
AN> чтобы она стала "правильной"... Hапример: "[ ( ] )" - "неправильная
AN> строка" "[ ] ( [ ] )" - "правильная", полученная путем подстановки в
AN> "неправ-ю" 2-х скобок! Интересует алгоритм... условие - сложность <=
AN> O(N*N), а желательно O(N*log N)
======================================================
* Original in area RU.ACM
* From: Max Alekseyev 2:5015/60 12/07/2001 09:48:19pm
* To : Vadim Guchenko
* Subj: Что-то тихо стало.
======================================================
ЫЫЫЫ OS/2 Hi, Vadim !
Replying to a message of Vadim Guchenko to Andrey Logvinenko:
>> Дано скобочное выражение (до 100 штук) состоящее из 4-х видов скобок.
VG> [,(,],).
>> Требуется дополнить его минимальным количеством скобок чтобы оно стало
>> правильным. Пример: Входные данные Выходные данные [
>> [] [(] [()] [([)
>> [([])] или []([])
VG> Кстати, а как ее решать. Hа контесте я не смог, а потом не брался...
Задача решается динамическим программированием.
Занумеруем скобки в данной последовательности числами 1..n. Обозначим через
T[i,j] минимальное количество скобок необходимое для создания правильной
скобочной структуры на скобках с i-ой по j-ю.
Будем заполнять таблицу T по диагоналям [i,i+k], где k=0..n.
Очевидно, T[i,i]=1 для всех i.
Рассмотрим скобки i..j. Скобка номер i либо ни с кем не составляет пары, либо
составляет пару со скобкой номер t. Тогда
T[i,j] = min { T[i+1,j]+1, min_t T[i+1,t-1]+T[t+1,j] }
Здесь t пробегает все номера скобок от i+1 до j, с которыми скобка номер i
составляет пару.
Помимо самого чисел T[i,j] можно хранить историю как именно это число было
получено.
Отслеживая историю получения числа T[1,n] можно построить саму скобочную
структуру...
Regards, ш.ш
Max ~
==================== End of Forward ====================
Regards, ш.ш
Max ~
--- FleetStreet 1.27.3.7
* Origin: (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
Посоветуйте алгоритм, очень надо!!! |
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 |
|
|
