Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.72
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
#1

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

11.09.2011, 16:25. Просмотров 3513. Ответов 17
Метки нет (Все метки)

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



Технические условия
Входные данные

В первой строке находится единственное число N (1  ≤  N  ≤  14, N – чётное).

Выходные данные

Каждое выражение выводится в отдельной строке.

Пример входных данных
4

Пример выходных данных
(())
[[]]
[()]
()[]
[]()
()()
([])
[][]


Вот мой код:

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
#include <iostream>
#include <cstring>
using namespace std;
 
int N;
 
void vokrug(char vir[], int type);
void right(char vir[], int type);
int main()
{
 char str[20];
 cin >> N;
 str[0]='\0';
 if (N==2) cout << "()" << endl << "[]" << endl;
 else
  {
   right(str,0);
   right(str,1);
  }
 return 0;
}
 
void vokrug(char vir[], int type)
{
 char str[20];
 int n=strlen(vir),i;
 if (n==N) return;
 for (i=0; i<n; i++) str[i+1]=vir[i];
 if (!type) str[0]='(',str[n+1]=')',str[n+2]='\0';
 else str[0]='[',str[n+1]=']',str[n+2]='\0';
 if (n==N-2) cout << str << endl;
 vokrug(str,0);
 vokrug(str,1);
 right(str,0);
 right(str,1);
}
 
void right(char vir[], int type)
{
 char str[20];
 int n=strlen(vir),i;
 if (n==N) return;
 for (i=0; i<n; i++) str[i]=vir[i];
 if (!type) str[n]='(',str[n+1]=')',str[n+2]='\0';
 else str[n]='[',str[n+1]=']',str[n+2]='\0';
 if (n==N-2) cout << str << endl;
 vokrug(str,0);
 vokrug(str,1);
 right(str,0);
 right(str,1);
}
Вроде всё выдавать должно. Но проходит все лишь 2 теста. Помогите в чём ошибка.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.09.2011, 16:25
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок (C++):

Вывести все правильные скобочные выражения длины N, состоящие из круглых и квадратных скобок - C++
Здравствуйте! Решил данную задачу, но один тест не проходит по времени...Можно ли как-то оптимизировать данный код? Мое решение: ...

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

Проверка записи на соответствие условию: правильная скобочная запись из круглых и квадратных скобок - C++
Здравствуйте! Задача: проверка записи на соответствие условию: правильная скобочная запись из круглых и квадратных скобок, внутри...

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

Баланс круглых скобок - C++
Проверить, соблюдается ли в тексте баланс круглых скобок. Для каждой открывающей скобки ‘(‘ должна быть найдена соответствующая закрывающая...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.09.2011, 16:41 #2
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Вроде всё выдавать должно.
Я проверил Ваш код. Например, при N==6 не увидел в ответе:
()([])
не до конца проработанный код.
1
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
11.09.2011, 16:50  [ТС] #3
valeriikozlov, а как это можно исправить?

Добавлено через 5 минут
Исправил так:
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
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <cstring>
using namespace std;
 
int N;
 
void vokrug(char vir[], int type);
void right(char vir[], int type);
void left(char vir[], int type);
int main()
{
 char str[20];
 cin >> N;
 str[0]='\0';
 if (N==2) cout << "()" << endl << "[]" << endl;
 else
  {
   right(str,0);
   right(str,1);
  }
 return 0;
}
 
void vokrug(char vir[], int type)
{
 char str[20];
 int n=strlen(vir),i;
 if (n==N) return;
 for (i=0; i<n; i++) str[i+1]=vir[i];
 if (!type) str[0]='(',str[n+1]=')',str[n+2]='\0';
 else str[0]='[',str[n+1]=']',str[n+2]='\0';
 if (n==N-2) cout << str << endl;
 vokrug(str,0);
 vokrug(str,1);
 right(str,0);
 right(str,1);
 left(str,0);
 left(str,1);
}
 
void right(char vir[], int type)
{
 char str[20];
 int n=strlen(vir),i;
 if (n==N) return;
 for (i=0; i<n; i++) str[i]=vir[i];
 if (!type) str[n]='(',str[n+1]=')',str[n+2]='\0';
 else str[n]='[',str[n+1]=']',str[n+2]='\0';
 if (n==N-2) cout << str << endl;
 vokrug(str,0);
 vokrug(str,1);
 right(str,0);
 right(str,1);
}
 
void left(char vir[], int type)
{
 char str[20];
 int n=strlen(vir),i;
 if (n==N) return;
 for (i=0; i<n; i++) str[i+2]=vir[i];
 if (!type) str[0]='(',str[1]=')',str[n+2]='\0';
 else str[0]='[',str[1]=']',str[n+2]='\0';
 if (n==N-2) cout << str << endl;
 vokrug(str,0);
 vokrug(str,1);
 right(str,0);
 right(str,1);
}
Прошло 3 теста, 2 не проходит.
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.09.2011, 17:11 #4
Цитата Сообщение от AvengerAlive Посмотреть сообщение
а как это можно исправить?
я бы обошелся одной функцией. Например так:
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
void func(int col_krug, int col_right, int col)
{
    if(col==N)
    {
        // вывод строки str[] на экран
        return;
    }
    if(col+(col_krug+col_right)<N)
    {
        str[col]='(';
        func(col_krug+1, col_right, col+1);
        str[col]='[';
        func(col_krug, col_right+1, col+1);
    }
    if(col_krug>0 && str[col-1]!='[')
    {
        str[col]=')';
        func(col_krug-1, col_right, col+1);
    }
    if(col_right>0 && str[col-1]!='(')
    {
        str[col]=']';
        func(col_krug, col_right-1, col+1);
    }
}
Первый вызов:
func(0, 0, 0);

Добавлено через 15 минут
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
void func(int col_krug, int col_right, int col)
{
    if(col==N)
    {
        // вывод строки str[] на экран
        return;
    }
    if(col+(col_krug+col_right)<N)
    {
        str[col]='(';
        func(col_krug+1, col_right, col+1);
        str[col]='[';
        func(col_krug, col_right+1, col+1);
    }
    if(col_krug>0)
    {
        int fl=0;
        int tmp=col-1;
        while(str[tmp]!='(')
        {
            if(str[tmp]=='[')
                fl++;
            if(str[tmp]==']')
                fl--;
            tmp--;
        }
            if(fl==0)
            {
                str[col]=')';
                func(col_krug-1, col_right, col+1);
            }
    }
    if(col_right>0 && str[col-1]!='(')
    {
        int fl=0;
        int tmp=col-1;
        while(str[tmp]!='[')
        {
            if(str[tmp]=='(')
                fl++;
            if(str[tmp]==')')
                fl--;
            tmp--;
        }
            if(fl==0)
            {
                str[col]=']';
                func(col_krug, col_right-1, col+1);
            }
    }
}
1
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
11.09.2011, 17:35  [ТС] #5
valeriikozlov, опять прошло 2 теста(
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.09.2011, 17:50 #6
AvengerAlive, Ссылку на задачу можете дать?
0
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
11.09.2011, 19:05  [ТС] #7
valeriikozlov, вот http://www.e-olimp.com/problems/855
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.09.2011, 19:06 #8
Поискал эту задачу, нашел. Оказывается я ее уже когда-то решал. Вот код:
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <stdio.h>
void pr(char *mas, int N)
{
    for(int i=0; i<N; i++)
    {
        printf("%c", mas[i]);
  
    }
    printf("\n");
}
 
void rec(char *mas, int j, int N, int temp1, int temp2)
{
    if(j==N)
        pr(mas, N);
    else
    {
    int t1=0, t2=0, i, fl=1;
    for(i=j-1;fl && i>=0; i--)
    {
        if(mas[i]=='(') t1--;
        if(mas[i]=='[') t2--;
        if(mas[i]==')') t1++;
        if(mas[i]==']') t2++;
        if(t1<0 || t2<0)
            fl=0;
    }
    if(fl)
    {
        mas[j]='(';
        rec(mas, j+1, N, temp1+1, temp2);
        mas[j]='[';
        rec(mas, j+1, N, temp1, temp2+1);
    }
    else
    {
        if(t1<0)
        {
            mas[j]=')';
            rec(mas, j+1, N, temp1, temp2);
            if(temp1+temp2<N/2)
            {
                mas[j]='(';
                rec(mas, j+1, N, temp1+1, temp2);
                mas[j]='[';
                rec(mas, j+1, N, temp1, temp2+1);
            }
        }
        if(t2<0)
        {
            mas[j]=']';
            rec(mas, j+1, N, temp1, temp2);
            if(temp1+temp2<N/2)
            {
                mas[j]='(';
                rec(mas, j+1, N, temp1+1, temp2);
                mas[j]='[';
                rec(mas, j+1, N, temp1, temp2+1);
            }
        }
    }
    }
}
 
 
 
int main() {
     int N;
    char *mas;
    scanf("%d", &N);
    mas=new char[N];
    mas[0]='(';
    rec(mas, 1, N, 1, 0);
    mas[0]='[';
    rec(mas, 1, N, 0, 1);
    return 0;
}
1
accept
4822 / 3243 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
12.09.2011, 04:04 #9
Цитата Сообщение от AvengerAlive
Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок.
используй стек
0
accept
4822 / 3243 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
12.09.2011, 04:04 #10
Цитата Сообщение от AvengerAlive
Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок.
используй стек
0
accept
4822 / 3243 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
12.09.2011, 04:06 #11
Цитата Сообщение от AvengerAlive
Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок.
используй стек
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
12.09.2011, 21:10 #12
accept, а чем лучше стек, чем простой массив для этой задачи?
0
accept
4822 / 3243 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
13.09.2011, 01:25 #13
проверка правильности скобок делается через стек
если в конце стек пуст, то скобки правильные

Цитата Сообщение от valeriikozlov
C++
1
2
3
4
        if(mas[i]=='(') t1--;
        if(mas[i]=='[') t2--;
        if(mas[i]==')') t1++;
        if(mas[i]==']') t2++;
([)]
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
13.09.2011, 07:04 #14
Цитата Сообщение от accept Посмотреть сообщение
проверка правильности скобок делается через стек
согласен, но можно так же и через простой массив.

Цитата Сообщение от accept Посмотреть сообщение
если в конце стек пуст, то скобки правильные
если я правильно понимаю, то Ваше предложение - генерировать все возможные комбинации скобок, а в конце проверять каждую комбинацию на правильность. Мне кажется по времени не уложитесь.
Очередной раз ставя скобку ')' или ']' Вам придется проверять уже имеющуюся комбинацию. Я не вижу здесь премущества стека.
0
accept
4822 / 3243 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
13.09.2011, 07:23 #15
Цитата Сообщение от valeriikozlov
если я правильно понимаю, то Ваше предложение - генерировать все возможные комбинации скобок, а в конце проверять каждую комбинацию на правильность
нет, скобки считываются в стек и снимаются со стека
это классическая задача
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.09.2011, 07:23
Привет! Вот еще темы с ответами:

Перегрузка круглых скобок как ravalue - C++
Не могу понять, как перегрузить () для того чтобы можно было использовать a(1, 2)=2; вместо a=3; ошибся, наверное не rvalue, а...

Проверить баланс круглых скобок, используя очередь - C++
Добрый день. Преподавателем поставлена следующая задача: дан текстовый файл с программой на алгоритмическом языке. За один просмотр...

Строки. Проверить правильность задания круглых скобок - C++
Проверить, правильно ли в заданном тексте расставлены круглые скобки (т. е. находится ли справа от каждой открывающей скобки...

Проверить правильность расстановки в тексте круглых скобок - C++
Задача: Проверить правильность расстановки в тексте круглых скобок. #include &lt;iostream&gt; #include &lt;cstring&gt; using namespace...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
13.09.2011, 07:23
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru