Модуль: Числа Каталана


Задача

1 /2


Количество чисел Каталана

Теория Нажмите, чтобы прочитать/скрыть

Где встречаются числа Каталана?
 
-Количество псп с заданным числом пар скобок
-Количество двоичных деревьев с заданным числом листьев
-Количество путей из левого нижнего угла в правый верхний в квадрате n * n, не касающихся диагонали

-Количество разбиений n-угольника на треугольники



Как считать?
 
1) Формула n-ного числа Каталана:



2)
•Пусть у нас есть ПСП P длины 2n
•Очевидно, что она начинается с открывающейся скобки
•Значит, скажем, что P = (A)B, где А и В – тоже псп (причём А и В могут быть пустыми)
•Если длина А = 2k, то последовательность A можно составить Ck способами
•Тогда длина В = 2(n – k - 1) и В можно составить Cn-k-1 способами
•Видим формулу для дп: Cn = sum(Ck * Cn-k-1) для всех k < n




Используемые материалы:

Задача

Вывести N-ное число Каталана

Входные данные
Первая строка входных данных содержит одно число N (\(1 <= N <= 20\)).
 
Выходные данные
Выведите одно число - N-ное число Каталана
 

 

Примеры
№ Входные данные Выходные данные
1 1 1

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6457
C#1
Python12
Комментарий учителя

Напишите программу

или выберите язык программирования и введите исходный код

Auto

       

Результат проверки программы 
Для проверки решения задачи необходимо зарегистрироваться или авторизоваться!