Есть строка, в которой записаны круглые скобки и знаки вопроса. Нужно вычислить сколькими способами знаки вопроса можно заменить на скобки (открывающую или закрывающую) так, чтобы они составляли правильное выражение.
например:
????(?
ответ
2
Вообще задача по программированию, но у меня сильное ощущение, что перебор в цикле не пройдет по времени (строка до 80 символов, a значит при полном переборе на несколько лет вычислений должно хватить). A потому нужно как-то выразить ответ формулой... есть идеи?
скобки :)
скобки :)
Порядок скобок не особо важен, главное, чтоб закрывающие шли за открывающими.
Поэтому предлагаю решать так:
1. Написать нехватающие скобки, останется N свободных мест.
2. Решить задачу: сколько существует правильных последовательностей из N скобок.
Поэтому предлагаю решать так:
1. Написать нехватающие скобки, останется N свободных мест.
2. Решить задачу: сколько существует правильных последовательностей из N скобок.
Последний раз редактировалось Draeden 30 ноя 2019, 13:23, всего редактировалось 1 раз.
Причина: test
Причина: test
скобки :)
Draeden писал(а):Source of the post
Порядок скобок не особо важен, главное, чтоб закрывающие шли за открывающими.
Поэтому предлагаю решать так:
1. Написать нехватающие скобки, останется N свободных мест.
2. Решить задачу: сколько существует правильных последовательностей из N скобок.
Неверно, т.к.
????(???
==
1. ????()()
или
2. ????(())
Последний раз редактировалось Soul 30 ноя 2019, 13:23, всего редактировалось 1 раз.
Причина: test
Причина: test
скобки :)
Считаем ( 1,) -1,? 0.
Используем массив a[n,n/2], где a[i,s]- количество вариантов на i-ом знаке c суммой s.
Если i+1 знак ? то a[i+1,s]:=a[i,s-1]+a[i,s]+a[i,s+1];
Если i+1 знак ( то a[i+1,s]:=a[i,s-1];a[i+1,0]:=0;
Если i+1 знак ) то a[i+1,s]:=a[i,s+1];a[i+1,n/2]:=0;
Результат получается в a[n,0].
Для приведенного выше примера:
\ i 1 2 3 4 5 6
s
3 0 0 1 04 09 21
2 0 1 3 09 12 30
1 1 2 5 12 09 21
0 1 2 4 09 00 09
????()
??()()
?(?)()
(??)()
?()?()
(?)?()
()??()
()()()
(())()
Используем массив a[n,n/2], где a[i,s]- количество вариантов на i-ом знаке c суммой s.
Если i+1 знак ? то a[i+1,s]:=a[i,s-1]+a[i,s]+a[i,s+1];
Если i+1 знак ( то a[i+1,s]:=a[i,s-1];a[i+1,0]:=0;
Если i+1 знак ) то a[i+1,s]:=a[i,s+1];a[i+1,n/2]:=0;
Результат получается в a[n,0].
Для приведенного выше примера:
\ i 1 2 3 4 5 6
s
3 0 0 1 04 09 21
2 0 1 3 09 12 30
1 1 2 5 12 09 21
0 1 2 4 09 00 09
????()
??()()
?(?)()
(??)()
?()?()
(?)?()
()??()
()()()
(())()
Последний раз редактировалось malk 30 ноя 2019, 13:23, всего редактировалось 1 раз.
Причина: test
Причина: test
скобки :)
Считаем знак "(" 1, знак")" -1, знак"?" 0.
a[i,s]- количество вариантов где первые i чисел в сумме дают s.
Будем заполнять массив последовательно a[0,0],a[0,1];a[1,0],a[1,1],a[1,2];...
Ha первом шаге есть один вариант c суммой 0(первый знак "?") и один вариант c суммой 1(первый знак "("). Ha i+1-ом шаге сумму s можно получить в трех случаях: когда на i-ом шаге была сумма s-1,сумма s или сумма s+1.
Если сложить количества вариантов для этих случаев то получим количество вариантов для i+1-ого шага c суммой s. Если встречаем -1 или 1 то количество вариантов равно количество вариантов для i-ого шага c суммой s+1 или s-1. Ha самом последнем шаге (i=n) нас интересует количество вариантов c суммой 0 - то есть где открывающих и закрывающих скобок поровну. Ha всех шагах сумма не должна быть меньше 0 - иначе будет неправильное выражение, где закрывающих скобок слишком много.
Количество правильных вариантов расстановки скобок соответствует числам Каталана, a алгоритм использует метод построения треугольника Каталана.
Можно обойтись двумя массивами a[0..n/2].
Если требуется все знаки "?" превратить в скобки, то алгоритм легко изменить.
a[i,s]- количество вариантов где первые i чисел в сумме дают s.
Будем заполнять массив последовательно a[0,0],a[0,1];a[1,0],a[1,1],a[1,2];...
Ha первом шаге есть один вариант c суммой 0(первый знак "?") и один вариант c суммой 1(первый знак "("). Ha i+1-ом шаге сумму s можно получить в трех случаях: когда на i-ом шаге была сумма s-1,сумма s или сумма s+1.
Если сложить количества вариантов для этих случаев то получим количество вариантов для i+1-ого шага c суммой s. Если встречаем -1 или 1 то количество вариантов равно количество вариантов для i-ого шага c суммой s+1 или s-1. Ha самом последнем шаге (i=n) нас интересует количество вариантов c суммой 0 - то есть где открывающих и закрывающих скобок поровну. Ha всех шагах сумма не должна быть меньше 0 - иначе будет неправильное выражение, где закрывающих скобок слишком много.
Количество правильных вариантов расстановки скобок соответствует числам Каталана, a алгоритм использует метод построения треугольника Каталана.
Можно обойтись двумя массивами a[0..n/2].
Если требуется все знаки "?" превратить в скобки, то алгоритм легко изменить.
Последний раз редактировалось malk 30 ноя 2019, 13:23, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Дискретная математика»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 12 гостей