74
правки
Изменения
Нет описания правки
Научимся считать <tex> number(l, b) </tex> {{---}} число последовательностей длины <tex> l </tex> и баланса <tex> b </tex>). Если <tex> l = 0 </tex>, то ответ понятен сразу: <tex> number[0][0] = 1 </tex>, все остальные <tex> number[0][b] = 0 </tex>. Пусть теперь <tex> i > 0 </tex>, тогда переберём, чему мог быть равен последний символ этой последовательности. Если он был равен <tex> '(' </tex>, то до этого символа мы находились в состоянии <tex> (l-1,b-1) </tex>. Если он был равен <tex>')'</tex>, то предыдущим было состояние <tex>(l-1,b+1)</tex>. Таким образом, получаем формулу:
<tex>number[il][jb] = number[il-1][jb-1] + number[il-1][jb+1]</tex>
(считается, что все значения <tex>dnumber[il][jb]</tex> при отрицательном <tex>j</tex> равны нулю). Этот преподсчет можно выполнить за <tex>O(n^2)</tex>. Будем строить префикс следующим образом: на каждом шаге интервал случайных чисел <tex> [0, s] </tex> (где <tex> s = number[n - l][b] </tex>) , будет разбиваться на два диапазона размерами <tex> number[n - l - 1][b + 1] </tex> и <tex> number[n - l - 1][b - 1] </tex> , и к префиксу будет прибавляться <tex>'('</tex> или <tex>')'</tex> если случайное число попало в первый или второй диапазон соответственно. '''string''' randomObject(n: '''int'''): <font color = green> // <tex> n </tex> {{---}} длина скобочной последовательности. </font> b = 0 l = 0 '''for''' i = 2 '''to''' n s = number[n - l][b] r = random(1, s) '''if''' number[n - l - 1][b + 1] >= r l = l + 1 b = b + 1 result = result + '(' '''else''' l = l + 1 b = b - 1 result = result + ')' '''return''' result Итоговая сложность алгоритма {{---}} <tex> O(n) + O(n^2) </tex> на преподсчет.
