Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.74/35: Рейтинг темы: голосов - 35, средняя оценка - 4.74
6 / 6 / 3
Регистрация: 06.03.2011
Сообщений: 269
1

Задача про скобки

18.10.2011, 20:38. Показов 6451. Ответов 3
Метки нет (Все метки)

Всем привет. Недавно показали мне такую задачу:
Построить все слова длины n>0 в алфавите скобок "(" и ")", представляющие правильные скобочные записи.
... намекнув на рекурсию. Кто-нибудь знает, как это решается?

Спасибо

Добавлено через 1 час 22 минуты
Nobody knows?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.10.2011, 20:38
Ответы с готовыми решениями:

вопрос про скобки
Здравствуйте, получил задание написать программу, смысл которой заключается в умножении матрицы на...

Задача: Убрать лишние скобки
Описание Преобразовать математическое выражение, удалив в нём лишние скобки, которые не влияют...

Для каждой открывающей скобки найти позицию ей соответствующей закрывающей скобки
Доброго времени суток. Подскажите пожалуйста алгоритм или путь к решению задачи, используя СТЕК ...

Фигурные скобки: Мне пишут что ошибка в закрытие скобки после return.
#include <iostream> using namespace std; int main(){ int *ptr_number = new int; int *sum =...

__________________

Записывайтесь на профессиональные курсы C++ разработчиков
3
31 / 31 / 6
Регистрация: 24.02.2011
Сообщений: 126
18.10.2011, 21:03 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
using namespace std;
bool search(char* s)
{
    int open_brackets=0,close_brackets=0;
    int i;
    for (i=strlen(s)-1;i>=0;i--)
    {
        if (s[i]==')') 
            close_brackets++; 
        else 
            open_brackets++;
        if (open_brackets<close_brackets && s[i]=='(') 
            break;
    }
    if (i==0 || i==-1) 
        return false;
    open_brackets=0;
    close_brackets=0;
    for (int k=0;k<i;k++)
            if (s[k]=='(') 
                open_brackets++; 
            else 
                close_brackets++;
    s[i]=')'; 
    close_brackets++;
    for (int j=i+1;j<strlen(s);j++)
    {
        while(strlen(s)/2>open_brackets)
        {
            s[j++]='('; 
            open_brackets++; 
        }
        while(j<strlen(s))
        {
            s[j++]=')';  
            close_brackets++;
        }
    }
    return true;
}
int main()
{
    int n;
    cin>>n;
    char *s=new char[n+1];
    for (int i=0;i<n/2;i++)
        s[i]='(';
    for (int i=n/2;i<n;i++)
        s[i]=')';
    s[n]=0;
    cout<<s<<endl;
    while (search(s))
        cout<<s<<endl;
    return 0;
}
только без рекурсии)
1
Эксперт С++
3206 / 1733 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
18.10.2011, 21:56 3
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
/////////////////////////////////////////////////////////////////////////////////////////
//Построить все слова длины n > 0 в алфавите скобок "(" и ")", представляющие 
//правильные скобочные записи.
//... намекнув на рекурсию.
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <iterator>
#include <set>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string      T_str;
typedef std::set<T_str>  T_brackets_expressions;
/////////////////////////////////////////////////////////////////////////////////////////
void  make_brackets_expressions
    (
        int                         len,         
        T_brackets_expressions&     brackets_expressions,
        const T_str&                s = ""
    )
{
    if(s.size() == len)
    {
        brackets_expressions.insert(s);
    }
    else
    {
        make_brackets_expressions
            (
                len,                
                brackets_expressions,
                T_str("()") + s
            );
 
        make_brackets_expressions
            (
                len,                
                brackets_expressions,
                s + "()"
            );
 
        make_brackets_expressions
            (
                len,                
                brackets_expressions,
                T_str("(") + s + ")"
            );
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    int  len = 0;
    do
    {
        std::cout << "Введите четную длину выражения из круглых скобок: ";
        std::cin >> len;        
        if(len <= 0) exit(1);
    }while(len % 2);  
        
    T_brackets_expressions  brackets_expressions;
    make_brackets_expressions
        (
            len,                         
            brackets_expressions
        );
 
    std::copy
        (
            brackets_expressions.begin(),
            brackets_expressions.end(),
            std::ostream_iterator<T_brackets_expressions::value_type>(std::cout, "\n")
        );
}
2
Заблокирован
19.10.2011, 07:53 4
рекурсивный вариант:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <string>
void f( int n, int k, std ::string &s ) {
    if( 0 == n ) {
        if( 0 == k )
            std ::cout << s << std ::endl;
        return ;
    }
    f( n - 1, k + 1, s + '(' );
    if( k > 0 )
        f( n - 1, k - 1, s + ')' );
}
int main() {
    int n;
    std ::cin >> n;
    f( n , 0, std ::string( "" ) );
}
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.10.2011, 07:53

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

Дана строка, содержащая латинские буквы и скобки. Если скобки расставлены правильно - вывести 0. Иначе - номер позиции, где есть ошибочная скобка
Дана строка, содержащая латинские буквы и круглые скобки. Если скобки расставлены правильно (то...

Задача про кузнечиков
Даны n последовательных столбиков. Кузнечик находится на первом столбе, умеет прыгать на 1,2,...,k...

задача про графы
Написать программу отыскания кратчайших путей между всеми парами вершин ориентированного графа по...

Задача про птичек
4. Птицы летят клином: в 1-м ряду —1 птица, во 2-м ряду — 3 птицы, в 3-м ряду — 5 птиц и т.д....


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

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