Изменения

Будем вести подсчет с использованием метода динамического программирования. Пусть Воспользуемся рекуррентной формулой <tex dpi = 120150>d[i][j]</tex> - число скобочных последовательностей длиной <tex dpi C_n = 120>\sum_{i</tex> с балансом <tex dpi = 120>j</tex>. Скобочную последовательность длиной <tex dpi = 120>i</tex> с балансом <tex dpi = 120>j</tex>, можно получить из скобочной последовательности длины <tex dpi = 120>i0}^{n -1</tex> с балансом или <tex dpi = 120>j-1</tex> (добавив в конец открывающуюся скобку), или <tex dpi = 120>j+1</tex> (добавив в конец закрывающуюся скобку), т.е. <tex dpi = 120>d[i][j] = d[i} C_i C_{n -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> n </tex> -ое число Каталана будет храниться в ячейке <tex dpi = 120>d[2n][0]</tex>описанной выше.

'''functionint''' CatalanNumbercatala_number(n: '''int''') '''int''' d[0n+1] <font color="Green">// создаем массив d, где будут храниться числа Каталана</font> d[0] = 1 '''for''' i = 1 '''to''' 2nn '''for''' j = 0 '''to''' ni-1 d[i][j] += d[i-1][j-1] + *d[i-1][-j+1] '''return''' d[2nn][0] ===Таблица значений===Найдем значения таблицы для <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|}