|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
13.09.2009, 03:04 | #1 |
Пользователь
Регистрация: 01.03.2009
Сообщений: 11
|
скобочные выражения Visual C++
Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок.
Ограничения: 1 <= N <= 14 Примеры (()) [[]] [()] ()[] []() ()() ([]) [][] проверку на правильность я написал, а вот генерация не очень. может кто подскажет хотя бы как сгенерировать все возможные комбинации а потом уж я их буду проверять. вот решение но оно во первых на паскале и написанно не понятно может кто-нибудь поможет разобратся Тема: перебор-построение, скобочные выражения. Общая идея решения такова: ставим на первое место все скобки, которые могут присутствовать на первом месте в правильном скобочном выражении, на второе — все скобки такие, что сочетание первой и второй скобок может быть началом правильного скобочного выражения, на третье место ставим все скобки такие, что сочетание первых трех скобок может быть началом правильного скобочного выражения, и т. д. К примеру, пусть построено следующее начало: ([][() Какая скобка может быть следующей? Очевидно, можно закрыть последнюю открытую и не закрытую квадратную скобку. Теперь посмотрим, можно ли поставить открывающую скобку. В правильном скобочном выражении длиной N ровно N/2 открывающих скобок. Если уже использовано N/2 открывающих скобок, то еще одну поставить нельзя. Если же в построенном начале менее N/2 открывающих скобок, то еще одну открывающую (причем любого типа) поставить можно. Итак, для приведенного начала выражения ответ таков: если N> 8, to на следующее место наряду с ] можно поставить и (, и [, а если N= 8, то выбора нет — следующая скобка обязана быть ]. Стоит сказать, что N< 8 быть не может, поскольку, ставя все предыдущие открывающие скобки, мы заботились о том, чтобы их суммарное число не превысило N/2. Глобальные объявления: const maxn = 14; type stack = array [l..maxn div 2] of char; var n : integer: result : array [l..maxn] of char; Здесь n — входные данные, result — переменная под строящийся результат. Определяем тип stack — для хранения порядка открытых и не закрытых к данному моменту скобок. Будем передавать этот массив как параметр-значение. Это несколько упрощает рекурсивную процедуру перебора скобочных выражений по сравнению с процедурой, использующей глобальный стек. В качестве упражнения можете реализовать приведенный далее алгоритм, а затем реализовать то же самое с глобальным стеком. Расходы на передачу стека незначительны — он занимает всего 7 байт. Это сравнимо с размером остальных параметров процедуры вместе взятых. Рекурсивная процедура перебора: procedure p(place, toOpen, sp : integer; s : stack); Полное название процедуры может выглядеть так: «Перебрать все правильные скобочные выражения длиной n, у которых первая pl асе - 1 скобка определена в первых элементах массива result». Параметры процедуры обозначают следующее: pl асе — на какое место нужно ставить очередную скобку, toOpen — сколько еще осталось открывать скобок, sp — количество открытых, но не закрытых к данному моменту скобок; в элементах s от 1-го до sp-го хранятся сами открытые, но не закрытые скобки (в s[sp] — последняя). При вызове этой процедуры заполнены элементы массива result от 1-го до (place-l)-гo. Процедура работает так. Если pl асе = n + 1, то все скобки расставлены, и комбинация выводится. Если place <= n, то на место place массива result устанавливаются по очереди все скобки такие, что первые place элементов массива result содержат допустимое начало правильного скобочного выражения длиной n. Для каждого варианта процедура вызывает себя рекурсивно, чтобы расставить скобки с (pl асе+1)-й до п-й. Рассмотрим работу процедуры более подробно. Конечный случай. Если pl асе = n + 1, то поставлены всеЛ^скобок, и можно выводить очередную комбинацию, полученную в массиве result. Продолжение рекурсии (place <= n): • Если открывать скобки можно, то есть toOpen > 0, то ставим на место pl асе открывающую круглую скобку, отмечаем ее в s и вызываем процедуру рекурсивно со следующими параметрами: pl асе + 1 — ставить очередную скобку на следующее место; toOpen - 1 — количество скобок, которые предстоит открыть, уменьшилось; sp + 1 — стек незакрытых скобок увеличился; s — в этом вызове процедуры стек один. Затем проделываем то же самое для открывающей квадратной скобки, только нужно не забывать, что она ставится не после открытой ранее круглой скобки, а вместо нее. • Если есть еще незакрытые скобки, то есть sp > 0, то ставим на место pl асе скобку, соответствующую последней незакрытой, и вызываем процедуру рекурсивно с параметрами place + 1 — ставить очередную скобку на следующее место, toOpen — число открывающих скобок не изменилось ^р - 1 —размер стека уменьшился, s — передаем тот же стек. Вызов рекурсии: p(l. n div 2, 0, s); В первый раз вызванная процедура будет устанавливать первый элемент массива result, предстоит открыть JV/2 скобок, открытых и не закрытых скобок еще нет, четвертым параметром является объявленная глобально переменная-стек. |
13.09.2009, 15:36 | #2 |
Участник клуба
Регистрация: 08.10.2007
Сообщений: 1,185
|
Поиск уже не рулит?
https://programmersforum.ru/showthread.php?t=48236 |
14.09.2009, 01:18 | #3 |
Пользователь
Регистрация: 01.03.2009
Сообщений: 11
|
с одним типом скобок я написал
а вот с двумя я уже не знаю |
14.09.2009, 15:54 | #4 |
Участник клуба
Регистрация: 08.10.2007
Сообщений: 1,185
|
Как работает код из той темы, разобрался? Нет. Тогда разберись.
Подсказка. Надо всего только скопипастить 9 строчек с минимальными изменениями. |
15.09.2009, 01:47 | #5 |
Пользователь
Регистрация: 01.03.2009
Сообщений: 11
|
спасибо разобрался
просто добавил то же для квадратных скобок респект |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Регулярные выражения | ACE Valery | PHP | 5 | 14.10.2009 11:37 |
Регулярные выражения | AnalogXP | Общие вопросы Delphi | 0 | 01.08.2009 23:12 |
Скобочные выражения(язык C) | HellForce | Помощь студентам | 6 | 08.05.2009 23:42 |
Арифметические выражения | spirit0k | Общие вопросы C/C++ | 0 | 26.10.2008 18:06 |