212
правок
Изменения
Нет описания правки
<tex dpi = 120> 14 + 5 + 2 \cdot 2 + 5 + 14 = 42 </tex>
способа. Следуя такому походу, можно вычислять количество правильных скобочных последовательностей дальше.
==Подсчет чисел Каталана==
Будем вести подсчет с использованием метода динамического программирования. Пусть <tex dpi = 120>d[i][j]</tex> - число скобочных последовательностей длиной <tex dpi = 120>i</tex> с балансом <tex dpi = 120>j</tex>. Скобочную последовательность длиной <tex dpi = 120>i</tex> с балансом <tex dpi = 120>j</tex>, можно получить из скобочной последовательности длины <tex dpi = 120>i-1</tex> с балансом или <tex dpi = 120>j-1</tex> (добавив в конец открывающуюся скобку), или <tex dpi = 120>j+1</tex> (добавив в конец закрывающуюся скобку), т.е. <tex dpi = 120>d[i][j] = d[i-1][j-1]+d[i-1][j+1]</tex>. База <tex dpi = 120>d[0][0]</tex> = 1. Так же можно заметить, что максимальный баланс правильной скобочной последовательности длины <tex dpi = 120>2n</tex>, равен <tex dpi = 120>n</tex>. Числа Каталана будут храниться в строке <tex dpi = 120>j</tex> = 0.
'''Псевдокод:'''
d[0][0] = 1
'''for''' i = 1 '''to''' 2n
'''for''' j = 0 '''to''' n
d[i][j] = d[i-1][j-1] + d[i-1][j+1]
===Таблица значений===
Найдем значения таблицы для <tex dpi = 120>n</tex> = 4
{| class="wikitable"
|-
!width="20"| i\j
!width="40"| 0
!width="40"| 1
!width="40"| 2
!width="40"| 3
!width="40"| 4
!width="40"| 5
!width="40"| 6
!width="40"| 7
!width="40"| 8
|-
! 0
| 1
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| 0
|-
! 1
| 0
| 1
| 0
| 0
| 0
| 0
| 0
| 0
| 0
|-
! 2
| 1
| 0
| 1
| 0
| 0
| 0
| 0
| 0
| 0
|-
! 3
| 0
| 2
| 0
| 1
| 0
| 0
| 0
| 0
| 0
|-
! 4
| 2
| 0
| 3
| 0
| 1
| 0
| 0
| 0
| 0
|-
! 5
| 0
| 5
| 0
| 4
| 0
| 0
| 0
| 0
| 0
|-
! 6
| 5
| 0
| 9
| 0
| 4
| 0
| 0
| 0
| 0
|-
! 7
| 0
| 14
| 0
| 13
| 0
| 0
| 0
| 0
| 0
|-
! 8
| 14
| 0
| 27
| 0
| 13
| 0
| 0
| 0
| 0
|}
==Смотри также==
