Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.54/13: Рейтинг темы: голосов - 13, средняя оценка - 4.54
1 / 1 / 0
Регистрация: 23.02.2018
Сообщений: 10
1

Количество способов вставить скобки в правильную скобочную последовательность

23.02.2018, 12:49. Показов 2495. Ответов 14

Здравствуйте!
Задача:
Вводится строка из символов "(" и ")" .Строка всегда будет правильной скобочной последовательностью.
Нужно посчитать количество способов вставить скобки "(" и ")" (по одной) чтоб последовательность оставалась правильной.

Пример:
()
Ответ:
7

Пример:
()(())
Ответ:
35

У меня есть идея:
1.Присвоить каждой скобке цифру.
Например если есть последовательность () то добавив 2 скобки мы получим стартовую последовательность (()).Далее считаем количество перестановок (4!).После чего нам нужно посчитать количество вариантов которые нас не устраивают(если строка начинается на ")" или заканчивается на "(").Таких у нас 4/2*3!+4/2*2.Итого 4!- 4/2*3!+4/2*2=8.Всего 8 вариантов которые нас устраивают.Но все равно не правильно.

Подскажите идею.
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.02.2018, 12:49
Ответы с готовыми решениями:

Сформировать правильную скобочную последовательность
Здравствуйте, помогите, пожалуйста, решить. Срочно Назовём скобочную последовательность,...

Проверить, содержит ли строка правильную скобочную запись
Дана символьная строка, содержащая скобки четырех видов ( {}, , () и <> ) и заканчивающаяся точкой....

Нужно вставить в программу правильную формулу
Привет всем)) Помогите пожалуйста вставить в прогу правильную формулу. Вот сама задача: Должны...

Установите правильную последовательность элементов
Установите правильную последовательность элементов, составляющих условный оператор для выбора...

14
1462 / 1170 / 551
Регистрация: 08.01.2012
Сообщений: 4,513
23.02.2018, 13:02 2
на 7 фантазии не хватает
()()
(())
(())
(())
(())
()()
0
1 / 1 / 0
Регистрация: 23.02.2018
Сообщений: 10
23.02.2018, 13:09  [ТС] 3
()()
1
Эксперт C
25699 / 16049 / 3441
Регистрация: 24.12.2010
Сообщений: 35,115
23.02.2018, 13:24 4
()()

Добавлено через 1 минуту
dddddoooosssss, вы на 1/2 секунду пересекли ленточку раньше. Поздравляю! за одно и с праздником!

Добавлено через 12 минут
Цитата Сообщение от dddddoooosssss Посмотреть сообщение
Подскажите идею.
Я бы сделал вложенные циклы.
Сначала берем открывающую скобку "(". Ее можно поставить на любое место. А закрывающую - на любое из оставшихся. Что продемонстрировал на примере уважаемый MansMI. Это дает Сn+22 способов. Тут даже цикла не надо. n - первоначальное количество скобок.
Если первая вставляемая скобка закрывающая "(", тут уже посложнее. Ее можно поставить не на любое место. А только такое, где счетчик "открывающие - закрывающие" > 0 И вторую "(" тоже можно ставить не на любое место. Вот тут уже можно вложить 2 цикла для подсчета...

Добавлено через 32 секунды
Я не очень сумбурно объяснил?
0
302 / 214 / 74
Регистрация: 23.05.2011
Сообщений: 970
23.02.2018, 13:38 5
Лучший ответ Сообщение было отмечено dddddoooosssss как решение

Решение

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

Тогда будет:
1. Пусть A — примитивная последовательность
(A), ()A, A() — три варианта.
2. Много правильных склеенных примитивов.
a1, a2, a3, ... an
Мы можем обернуть каждую — n
Можем по два: n-1
И т.д.: https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{k=1}^{n}n-k+1 склейкой подряд идущих, включая вырожденные случаи.
3. Далее, можем вкладывать скобки в промежутки между ними: n+1 случай.

Итого, для n независимо правильных подпоследовательностей будет https://www.cyberforum.ru/cgi-bin/latex.cgi?q(n) = n+1 + \sum_{k=1}^{n}n-k+1
И да, нужно n — это количество подпоследовательностей вида (T), где T — правильная подпоследовательность.

4. Рассмотрим теперь каждый примитив вида (T). Мы можем разделить T на n примитивов, затем обработать так же, а ещё можем вставить комбинации ()(T), (T)()
Итак, для этого будет ответ: https://www.cyberforum.ru/cgi-bin/latex.cgi?f(p) = 2+q(n) + \sum_{i=1}^{n}f(pp_i), где p — примитив, pp — массив подпримитивов, n — длина pp.
Итак, алгоритм:
1. сначала делим всю пословательность на примитивы и применяем первую формулу: s = q(n)
2. Для каждого примитива считаем f(p) и добавляем к s
0
539 / 265 / 89
Регистрация: 09.02.2018
Сообщений: 617
23.02.2018, 13:56 6
Цитата Сообщение от dddddoooosssss Посмотреть сообщение
Далее считаем количество перестановок (4!)
Но скобки №1 и №2 местами не меняем, значить на самом деле 4!/2! перестановок.
Цитата Сообщение от dddddoooosssss Посмотреть сообщение
Количество вариантов которые нас не устраивают(если строка начинается на ")" или заканчивается на "(").Таких у нас 4/2*3!+4/2*2
На самом деле их меньше, так как строка не кончиться на скобку №1 и не начнется с №2

)(()
4312
- не так

)(()
4132
- не так

)()(
4123
- не так

()()
3412
- прально

()()
1432
- прально

())(
1423
- не так

(())
3142
- прально

(())
1342
- прально

())(
1243
- не так

(())
3124
- прально

(())
1324
- прально

()()
1234
- прально

Получаецца 7 вариантов.
0
1 / 1 / 0
Регистрация: 23.02.2018
Сообщений: 10
23.02.2018, 14:21  [ТС] 7
Цитата Сообщение от New man Посмотреть сообщение
Подсказываю идею: примитивная скобочная последовательность или примитив. Суть в том, что мы не пытаемся вставить скобки внутрь неё, а только снаружи.

Тогда будет:
1. Пусть A — примитивная последовательность
(A), ()A, A() — три варианта.
2. Много правильных склеенных примитивов.
a1, a2, a3, ... an
Мы можем обернуть каждую — n
Можем по два: n-1
И т.д.: https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{k=1}^{n}n-k+1 склейкой подряд идущих, включая вырожденные случаи.
3. Далее, можем вкладывать скобки в промежутки между ними: n+1 случай.

Итого, для n независимо правильных подпоследовательностей будет https://www.cyberforum.ru/cgi-bin/latex.cgi?q(n) = n+1 + \sum_{k=1}^{n}n-k+1
И да, нужно n — это количество подпоследовательностей вида (T), где T — правильная подпоследовательность.

4. Рассмотрим теперь каждый примитив вида (T). Мы можем разделить T на n примитивов, затем обработать так же, а ещё можем вставить комбинации ()(T), (T)()
Итак, для этого будет ответ: https://www.cyberforum.ru/cgi-bin/latex.cgi?f(p) = 2+q(n) + \sum_{i=1}^{n}f(pp_i), где p — примитив, pp — массив подпримитивов, n — длина pp.
Итак, алгоритм:
1. сначала делим всю пословательность на примитивы и применяем первую формулу: s = q(n)
2. Для каждого примитива считаем f(p) и добавляем к s
где p — примитив, pp — массив подпримитивов, n — длина pp.
Как понять массив подпримитивов??
0
302 / 214 / 74
Регистрация: 23.05.2011
Сообщений: 970
23.02.2018, 14:39 8
(())()(()())

массив: (()),(), (()())
0
1 / 1 / 0
Регистрация: 23.02.2018
Сообщений: 10
23.02.2018, 14:58  [ТС] 9
Цитата Сообщение от Байт Посмотреть сообщение
()()

Добавлено через 1 минуту
dddddoooosssss, вы на 1/2 секунду пересекли ленточку раньше. Поздравляю! за одно и с праздником!

Добавлено через 12 минут
Я бы сделал вложенные циклы.
Сначала берем открывающую скобку "(". Ее можно поставить на любое место. А закрывающую - на любое из оставшихся. Что продемонстрировал на примере уважаемый MansMI. Это дает Сn+22 способов. Тут даже цикла не надо. n - первоначальное количество скобок.
Если первая вставляемая скобка закрывающая "(", тут уже посложнее. Ее можно поставить не на любое место. А только такое, где счетчик "открывающие - закрывающие" > 0 И вторую "(" тоже можно ставить не на любое место. Вот тут уже можно вложить 2 цикла для подсчета...

Добавлено через 32 секунды
Я не очень сумбурно объяснил?
И вторую "(" тоже можно ставить не на любое место
А какое исключение для "(" ?
0
Эксперт C
25699 / 16049 / 3441
Регистрация: 24.12.2010
Сообщений: 35,115
23.02.2018, 15:46 10
Цитата Сообщение от dddddoooosssss Посмотреть сообщение
А какое исключение для "(" ?
Количество закрывающих (с учетом вставленной) > количества открывающих.
Это все видно на том примере, который мы с вами придумали...
Тут важно понять принцип устройства правильной скобочной последовательности
В любой точке f (k) = "Отрывающих - закрывающих" >= 0. В конечной точке f(n) = 0
0
539 / 265 / 89
Регистрация: 09.02.2018
Сообщений: 617
23.02.2018, 16:08 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
#include <iostream>
using namespace std;
bool check(char *s,int n){
    int i,k;
    k=0;
    for(i=0;i<n;i++){
        if(s[i]=='(') k++;
        else if(s[i]==')'){
            k--;
            if(k<0) return false;
        }
    
    }
    return true;
}
int main(){
    int i,j,k,n,m;
    char s[100],z[100];
    cout<<"Skobki?"<<endl;
    cin>>s;
    for(n=0;n<100;n++) if(s[n]=='\0') break;
    m=(n+1)*2;
    j=k=0;
    for(i=0;i<m+n;i++) z[i]=' ';
    for(i=2;i<m+n;i+=3) z[i]=s[j++];
    for(i=0;i<m-1;i+=2){
        z[i+i/2]=')';
        for(j=i+1;j<m;j+=2){
            k++;
            z[j+j/2]='(';
            if(check(z,m+n)) k++;
            z[j+j/2]=' ';
        }
        z[i+i/2]=' ';
    }
    cout<<k<<endl;
    cin.get(); cin.get();
    return 0;
}
Прога написана по описанию Байта из поста Количество способов вставить скобки в правильную скобочную последовательность
1
1 / 1 / 0
Регистрация: 23.02.2018
Сообщений: 10
23.02.2018, 16:22  [ТС] 12
Цитата Сообщение от Байт Посмотреть сообщение
Количество закрывающих (с учетом вставленной) > количества открывающих.
Это все видно на том примере, который мы с вами придумали...
Тут важно понять принцип устройства правильной скобочной последовательности
В любой точке f (k) = "Отрывающих - закрывающих" >= 0. В конечной точке f(n) = 0
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
#include <bits/stdc++.h>
 
using namespace std;
int main()
{
    long long dynamic[1000]= {0,};
    string ssss;
    cin>>ssss;
    long long length_=0,answear=0;
    for(int i=1; i<=ssss.length()+1; i++)
        answear+=i;
    long long calk=0;
    for(int i=0; i<s.length(); i++)
    {
        if(s[i]=='(')
            calk++;
        else
            calk--;
        dynamic[i]=calk;
    }
    dynamic[s.length()]=1;
    for(int i=0; i<s.length()-1; i++)
    {
        if(dynamic[i]>=0)
        {
            int y=0;
            for(; y<s.length(); y++)
            {
                if(dynamic[y]==0)
                {
                    answear++;
                    if(dynamic[y+1]!=0)
                        break;
                }
            }
        }
    }
    cout<<answear;
    return 0;
}
Написал код по вашей идее.Не проходит второй пример.Где я не правильно мыслю???

Добавлено через 9 минут
Цитата Сообщение от КулХацкеръ Посмотреть сообщение
Кароч все сделал:

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
#include <iostream>
using namespace std;
bool check(char *s,int n){
    int i,k;
    k=0;
    for(i=0;i<n;i++){
        if(s[i]=='(') k++;
        else if(s[i]==')'){
            k--;
            if(k<0) return false;
        }
    
    }
    return true;
}
int main(){
    int i,j,k,n,m;
    char s[100],z[100];
    cout<<"Skobki?"<<endl;
    cin>>s;
    for(n=0;n<100;n++) if(s[n]=='\0') break;
    m=(n+1)*2;
    j=k=0;
    for(i=0;i<m+n;i++) z[i]=' ';
    for(i=2;i<m+n;i+=3) z[i]=s[j++];
    for(i=0;i<m-1;i+=2){
        z[i+i/2]=')';
        for(j=i+1;j<m;j+=2){
            k++;
            z[j+j/2]='(';
            if(check(z,m+n)) k++;
            z[j+j/2]=' ';
        }
        z[i+i/2]=' ';
    }
    cout<<k<<endl;
    cin.get(); cin.get();
    return 0;
}
Прога написана по описанию Байта из поста Количество способов вставить скобки в правильную скобочную последовательность
Частично работает не правильно,ищу ошибку.
0
539 / 265 / 89
Регистрация: 09.02.2018
Сообщений: 617
23.02.2018, 16:34 13
Цитата Сообщение от dddddoooosssss Посмотреть сообщение
Частично работает не правильно,ищу ошибку.
Что значит частично не работает? Точнее плиз!
0
1 / 1 / 0
Регистрация: 23.02.2018
Сообщений: 10
23.02.2018, 16:35  [ТС] 14
30% из 100% проходит
0
539 / 265 / 89
Регистрация: 09.02.2018
Сообщений: 617
23.02.2018, 16:51 15
Цитата Сообщение от dddddoooosssss Посмотреть сообщение
30% из 100% проходит
Если дадите ссылку на сайт тестирования, попробую доработать!
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
23.02.2018, 16:51

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Рекурсия: выстроить из костяшек домино правильную последовательность максимальной длины
Всем доброго времени суток. Задача: Имеется N костей из нескольких комплектов домино. Выстроить...

Сколько нужно убрать из данной последовательности скобок, чтобы получить правильную последовательность?
Сколько надо убрать скобок из данной последовательности скобок что бы получить правильную...

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

Вставить в заданный текст недостающие скобки
вставить в заданный текст недостающие скобки.


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

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

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