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

Слишком долгий перебор - нужно оптимизировать - C++

Восстановить пароль Регистрация
 
Veyron
 Аватар для Veyron
104 / 104 / 4
Регистрация: 02.06.2009
Сообщений: 579
28.04.2011, 18:42     Слишком долгий перебор - нужно оптимизировать #1
Задача с ацмп.ру:
Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок.

Задача легкая, но в голову что-то ничего не лезет. Написал алгоритм, но при крайних значениях работает слишком долго:
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
#include <fstream>
#include <stack>
#include <string>
 
using namespace std;
 
int N;
ifstream cin("INPUT.TXT");
ofstream cout("OUTPUT.TXT");
 
void recurse(string S);
 
int main()
{
    cin >> N;
    recurse("");
    return 0;
}
 
void recurse(string S)
{
    if (S.length()==N)
    {
        stack <char> G;
        bool flag=1;
        for (int i=0;i<S.length();i++)
        {
            if (S[i]=='(' || S[i]=='[') G.push(S[i]);
            else
            {
                if (!G.empty())
                {
                    if ((S[i]==')' && G.top()=='(') || (S[i]==']' && G.top()=='[')) G.pop();
                    else flag=0;
                }
                else
                {
                    flag=0;
                }
            }
        }
        if (G.empty() && flag)
            cout << S << endl;
    }
    else
    {
        int q=0,r=0;
        for (int i=0;i<S.length();i++)
            switch (S[i])
            {
                case '(':
                    r++;
                    break;
                case '[':
                    q++;
                    break;
                case ')':
                    r--;
                    break;
                case ']':
                    q--;
                    break;
            }
        if (q>=0 && r>=0)
        {
            recurse(S+'(');
            recurse(S+'[');
            recurse(S+')');
            recurse(S+']');
        }
    }
}
Помогите в поисках метода оптимального перебора!
Заранее спасибо!

ЗЫ: Сорри за быдлокод, ясно, что оно смотрится некрасиво, но я так думаю, что он неправильный, вот и не стал его оформлять нормально
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.04.2011, 18:42     Слишком долгий перебор - нужно оптимизировать
Посмотрите здесь:

C++ Слишком большие программы!
OpenMP долгий dinamic C++
C++ Нужно оптимизировать готовый код, чтобы не было стыдно показать
C++ Нужно оптимизировать
слишком много инициализаторов C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
olleg90
 Аватар для olleg90
34 / 34 / 6
Регистрация: 06.01.2011
Сообщений: 90
29.04.2011, 11:35     Слишком долгий перебор - нужно оптимизировать #2
лень переделывать))

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
#include<stdio.h>
#include<string.h>
#include<Ctype.h>
int main()
  { char *opsk="({[";
    char *clsk=")}]";
    FILE *in=fopen("brackets.in","r");
    FILE *out=fopen("brackets.out","w");
    int k,i,j,l,fl;
   char str[100],a[100];
   fscanf(in,"%d\n",&k);
    for ( i=1;i<=k;i++)
    {
      fgets(str,100,in); l=fl=0;
      for ( j=0;j<strlen(str);j++)
    if(strchr(opsk,str[j]))
     if(j+1<strlen(str) && isdigit(str[j+1])||strchr(opsk,str[j+1]))
       a[l++]=str[j] ;
       else { fl=1; break;}
    else
     if(strchr(clsk,str[j]))
      if(l<=0) { fl=1; break;}
       else
        if (strchr(clsk,str[j])-clsk!=strchr(opsk,a[l-1])-opsk)
          { fl=1;  break;}
          else
           if(isdigit(str[j-1])||strchr(clsk,str[j-1]))
           l--;
           else fl=1;
 
       if (fl==0)
     if (l==0)fprintf(out,"RIGHT\n");
     else fprintf(out,"WRONG\n");
       else fprintf(out,"WRONG\n");
 
    }
 
    }
Veyron
 Аватар для Veyron
104 / 104 / 4
Регистрация: 02.06.2009
Сообщений: 579
29.04.2011, 12:58  [ТС]     Слишком долгий перебор - нужно оптимизировать #3
Этот код проверяет, правильная СП или нет, я правильно понял? Если да, то это не совсем то. У меня работает программа, правильно, но очень медленно. Поэтому я спрашиваю о сокращении перебора.
olleg90
 Аватар для olleg90
34 / 34 / 6
Регистрация: 06.01.2011
Сообщений: 90
29.04.2011, 13:03     Слишком долгий перебор - нужно оптимизировать #4
она проверяет правильность расстановки скобок в выражении
Veyron
 Аватар для Veyron
104 / 104 / 4
Регистрация: 02.06.2009
Сообщений: 579
29.04.2011, 15:27  [ТС]     Слишком долгий перебор - нужно оптимизировать #5
Надо бы как-то сократить перебор... Проверка расстановки скобок в моем коде тоже есть...
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
29.04.2011, 15:34     Слишком долгий перебор - нужно оптимизировать #6
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
#include <fstream>
#include <vector>
 
using namespace std;
 
ifstream cin("input.txt");
ofstream cout("output.txt");
 
int n;
 
vector<char> v;
vector<char> ans;
 
void p(int pos)
{
    if(pos == n)
    {
        for(int i = 0; i < n; i++)
            cout << ans[i];
        cout << endl;        
        return;
    }
    if(n - pos - v.size() > 0)
    {
        v.push_back('(');
        ans[pos] = '(';
        p(pos+1);
        v.pop_back();
 
        v.push_back('[');
        ans[pos] = '[';
        p(pos+1);
        v.pop_back();
    }
    if(v.size() > 0)
    {
        char buf = v.back();
        if(buf == '[')
            ans[pos] = ']';
        else
            ans[pos] = ')';
        v.pop_back();
        p(pos+1);
        v.push_back(buf);
    }
}
 
int main()
{
    cin >> n;
    ans.resize(n);
    p(0);
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.04.2011, 15:53     Слишком долгий перебор - нужно оптимизировать
Еще ссылки по теме:

Оптимизировать перебор C++
C++ Нужно оптимизировать код
Слишком быстрый инпут C++

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

Или воспользуйтесь поиском по форуму:
Veyron
 Аватар для Veyron
104 / 104 / 4
Регистрация: 02.06.2009
Сообщений: 579
29.04.2011, 15:53  [ТС]     Слишком долгий перебор - нужно оптимизировать #7
Хохол, премного благодарен. Мне преподаватель про этот метод намекнул, но я чето не въехал, как его использовать (с одним массивом чаров). Теперича разобрался и акцептед.
Yandex
Объявления
29.04.2011, 15:53     Слишком долгий перебор - нужно оптимизировать
Ответ Создать тему
Опции темы

Текущее время: 00:13. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru