Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.80/15: Рейтинг темы: голосов - 15, средняя оценка - 4.80
 Аватар для Fixer_84
1505 / 969 / 812
Регистрация: 30.04.2016
Сообщений: 3,337

Вывести все правильные скобочные выражения длины N, состоящие из круглых и квадратных скобок

26.06.2017, 19:22. Показов 2973. Ответов 11
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Здравствуйте! Решил данную задачу, но один тест не проходит по времени...Можно ли как-то оптимизировать данный код?

Мое решение:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <stack>
#include <string>
 
using namespace std;
 
bool Brackets(char opening, char closing)
{
    if (opening == '(' && closing == ')')
        return true;
    else if (opening == '[' && closing == ']')
        return true;
    return false;
}
 
bool BalancedParentheses(string b)
{
    stack<char> a;
    for (int i = 0; i < b.length(); i++)
    {
        if (b[i] == '(' || b[i] == '[')
            a.push(b[i]);
        else if (b[i] == ')' || b[i] == ']')
        {
            if (a.empty() || !Brackets(a.top(), b[i]))
                return false;
            else
                a.pop();
        }
    }
    return a.empty();
}
 
void F(string str, string s, int N)
{
    if (s.size() == N)
    {
        if (BalancedParentheses(s))
            printf("%s\n", s.c_str());
        return;
    }
    for (int i = 0; i < str.size(); i++)
    {
        F(str, s + str[i], N);
    }
}
 
void Perm(string str, int N)
{
    F(str, "", N);
}
 
int main()
{
    int N;
    cin >> N;
    Perm("()[]", N);
    system("pause");
    return 0;
}
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
26.06.2017, 19:22
Ответы с готовыми решениями:

Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок
Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок. Технические условия Входные...

Вывести все правильные скобочные выражения (оптимизировать алгоритм, ускорить работу кода)
есть код, нужно cout и cin перевести на printf и scanf дополнительных библиотек не подключать! проблема в том что при вводе 14 работает...

Вывести все корректные комбинации пар круглых скобок, которые можно сформировать из n скобок
Вывести все корректные комбинации пар круглых скобок, которые можно сформировать из n скобок, которые закрываются и открываются. Количество...

11
7804 / 6568 / 2988
Регистрация: 14.04.2014
Сообщений: 28,705
26.06.2017, 19:52
str и b передавай по ссылке.
1
 Аватар для Fixer_84
1505 / 969 / 812
Регистрация: 30.04.2016
Сообщений: 3,337
26.06.2017, 20:24  [ТС]
nmcf, спасибо за ваш ответ. Стало немного быстрее, но последний тест все равно валится по времени

Добавлено через 10 минут
Здесь либо оптимизация при выводе нужна (но вроде использую printf()), либо рекурсивную функцию перебора убирать нужно. Хотя здесь размещения с повторениями и все вроде правильно, перебирает все варианты с повторами...Лимит времени 2 секунды, а последний тест занимает три и не знаю, что делать теперь...
0
354 / 135 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
26.06.2017, 21:14
Нужно убрать next_permutation
И генерировать самому. Как это делать - или подумать или загуглить. На том же емаксе все есть
0
7804 / 6568 / 2988
Регистрация: 14.04.2014
Сообщений: 28,705
26.06.2017, 21:17
Цитата Сообщение от Ромаха Посмотреть сообщение
Нужно убрать next_permutation
А где такое?
0
 Аватар для Fixer_84
1505 / 969 / 812
Регистрация: 30.04.2016
Сообщений: 3,337
26.06.2017, 21:26  [ТС]
Ромаха, здравствуйте! Вот как раз next_permutation() здесь не подходит, так как размещения с повторениями нужны, поэтому и использую рекурсивную функцию. А вообще, встроенные функции работают довольно быстро Похожую задачу сдал с помощью next_permutation(), а что с этой делать - не знаю.
0
354 / 135 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
26.06.2017, 21:27
Проглядел. Там самописный перебор. Несильно лучше
0
Диссидент
Эксперт C
 Аватар для Байт
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
26.06.2017, 22:30
В строках 42-45 ты перебираешь ВСЕ варианты. В итоге их у тебя выходит 4N. Но очевидно, что за "(" не может следовать "]", за "[" - ")". Если ты будешь пропускать такие комбинации, то как раз эту секунду и сбросишь

Добавлено через 8 минут
Fixer_84, это не предел оптимизаций. Когда получено больше половины строки, можно подсчитать количество открытые - закрытые. И если оно больше числа оставшихся символов, то на фига строку генерить дальше? Все равно все скобки не закроются.
Вообще, очень полезно вместе с каждой строкой держать счетчики скобок. Ведь если у тебя N = 40, а строка начинается с "())", дальше с этим огрызком можно не работать, все равно строка будет не сбалансирована..
Все это вместе и называется, кажется, "метод ветвей и границ"
1
354 / 135 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
27.06.2017, 13:09
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
const
     SIZE = 14;
 
var
   n : Integer;
   res : string;
    
 
procedure P(place, ToOpen, Open : Integer; s : string);
var
   t : Char;
begin
     if place = n+1 then begin
        WriteLn(res);
//        res := '';
        Exit
     end;
      
     if ToOpen > 0 then begin
        s := s + '(';
        res := res + '(';
        P(place+1, ToOpen-1, open+1, s);
        s[Length(s)] := '[';
        res[Length(res)] := '[';
        P(place+1, ToOpen-1, open+1, s);
        res := Copy(res, 1, Length(res)-1);
        s := Copy(s, 1, Length(s)-1)
     end;
      
     if Open > 0 then begin
        t := s[Length(s)];
        if s[Length(s)] = '(' then
           res := res + ')'
        else
            res := res + ']';
        s := Copy(s, 1, Length(s)-1);
        P(place+1, ToOpen, Open-1, s);
        res := Copy(res, 1, Length(res)-1);
        s := s+t
     end;
      
end;
 
begin
     ReadLn(n);
      
     P(1, n div 2, 0, '')
end.
Вот нашел свой дико старый код.
2
 Аватар для zarko97
279 / 39 / 13
Регистрация: 11.10.2015
Сообщений: 405
27.06.2017, 14:15
Fixer_84, стринги по значению передавать это хардкор дичайший
1
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
27.06.2017, 14:22
Цитата Сообщение от zarko97 Посмотреть сообщение
стринги по значению передавать это хардкор дичайший
Стринги вообще передавать негигиенично.

Кстати, в некоторых случая компилятор может это дело заменить мув семантикой (если увидит что дальше строка не используется). Но лучше конечно использовать lvalue ссылку на const.
1
Диссидент
Эксперт C
 Аватар для Байт
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
27.06.2017, 23:19
Цитата Сообщение от zarko97 Посмотреть сообщение
стринги по значению передавать это хардкор дичайший
Цитата Сообщение от MrGluck Посмотреть сообщение
Стринги вообще передавать негигиенично.
Скорее всего вы правы. Но дело то отнюдь не в этом! Алгоритм ТС перебирает ВСЕ возможные расстановки скобок, в то время как есть ясные признаки того, что дальнейший перебор бессмысленен. И вот отбрасывание этих, заведомо неподходящих вариантов (обрезка ветвей), и даст значительно более весомый выигрыш в скорости, чем все синтаксические выкрутасы.
Имхо, главное - алгоритм. Но, конечно, и средства языка следует использовать грамотно.

ЗЫ. А алгоритм у ТС и впрямь лобовой и ломовой.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
27.06.2017, 23:19
Помогаю со студенческими работами здесь

Удаление фигурных, квадратных, круглых скобок
Нужно удалить из строки все фигурные, квадратные и круглые скобки. Как это лучше сделать? В регуляторных выражениях, как ни пытался, не...

Проверить правильность расстановки круглых и квадратных скобок в выражениях
2 дана строка символов проверить правильность расстановки круглых и квадратных скобок в выражениях

Проверить правильность расстановки круглых и квадратных скобок в выражениях
дана строка символов проверить правильность расстановки круглых и квадратных скобок в выражениях

Проверить правильность расстановки круглых и квадратных скобок в выражениях
задание дана строка символов проверить правильность расстановки круглых и квадратных скобок в выражениях

Вывести все корректные комбинации пар круглых скобок
Вывести все корректные комбинации пар круглых скобок, которые можно сформировать из n скобок, которые закрываются и открываются. Количество...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Новые блоги и статьи
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru