Программа для n-го каталонского номера

01.01.2020Динамическое программирование, Математика, Разное

Каталонские числа представляют собой последовательность натуральных чисел, которая встречается во многих интересных проблемах подсчета, таких как следующие.

1) Подсчитайте количество выражений, содержащих n пар скобок, которые правильно сопоставлены. Для n = 3 возможными выражениями являются ((())), () (()), () () (), (()) (), (() ()).

2) Подсчитайте количество возможных деревьев бинарного поиска с n ключами (см. Это )

3) Подсчитайте количество полных двоичных деревьев (корневое двоичное дерево заполнено, если у каждой вершины есть либо два потомка, либо нет потомков) с n + 1 листом.

Смотрите это для других приложений.

Первые несколько каталонских чисел для n = 0, 1, 2, 3,… являются 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,…

Рекурсивное решение
Каталонские числа удовлетворяют следующей рекурсивной формуле.

Ниже приведена реализация приведенной выше рекурсивной формулы.

C ++

#include<iostream>

using namespace std;

// Рекурсивная функция для поиска n-го каталонского числа

unsigned long int catalan(unsigned int n)

{

// Базовый вариант

if (n <= 1) return 1;

// каталанский (n) - сумма каталанского (i) * каталанского (ni-1)

unsigned long int res = 0;

for (int i=0; i<n; i++)

res += catalan(i)*catalan(n-i-1);

return res;

}

// Программа драйвера для проверки вышеуказанной функции

int main()

{

for (int i=0; i<10; i++)

cout << catalan(i) << " ";

return 0;

}

Джава

class CatalnNumber {

// Рекурсивная функция для поиска n-го каталонского числа

int catalan(int n) {

int res = 0;

// Базовый вариант

if (n <= 1) {

return 1;

}

for (int i = 0; i < n; i++) {

res += catalan(i) * catalan(n - i - 1);

}

return res;

}

public static void main(String[] args) {

CatalnNumber cn = new CatalnNumber();

for (int i = 0; i < 10; i++) {

System.out.print(cn.catalan(i) + " ");

}

питон

# Рекурсивная функция для поиска n-го каталонского числа

def catalan(n):

# Базовый вариант

if n <=1 :

return 1

# Каталанский (n) - сумма каталанского (i) * каталонского (ni-1)

res = 0

for i in range(n):

res += catalan(i) * catalan(n-i-1)

return res

Программа # Driver для проверки вышеуказанной функции

for i in range(10):

print catalan(i),

# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// Рекурсивная программа на C # для поиска
// каталонский номер

using System;

class GFG {

// Рекурсивная функция для поиска

// каталонский номер

static int catalan(int n) {

int res = 0;

// Базовый вариант

if (n <= 1) {

return 1;

}

for (int i = 0; i < n; i++)

{

res += catalan(i)

* catalan(n - i - 1);

}

return res;

}

public static void Main()

{

for (int i = 0; i < 10; i++)

Console.Write(catalan(i)

+ " ");

}

// Этот код предоставлен
// нитин митталь.

PHP

<?php
// PHP программа для nth
// каталонский номер

// Рекурсивная функция для
// найти номер каталонца

function catalan($n)

{

// Базовый вариант

if ($n <= 1)

return 1;

// каталонский (n) является суммой

// каталанский (i) * каталанский (ni-1)

$res = 0;

for($i = 0; $i < $n; $i++)

$res += catalan($i) *

catalan($n - $i - 1);

return $res;

}

// Код драйвера

for ($i = 0; $i < 10; $i++)

echo catalan($i), " ";

// Этот код добавлен aj_36
?>

Выход :

1 1 2 5 14 42 132 429 1430 4862

Временная сложность вышеуказанной реализации эквивалентна n-му каталонскому числу.

Значение n-го каталонского числа является экспоненциальным, что делает сложность времени экспоненциальной.

Решение для динамического программирования
Мы можем заметить, что вышеописанная рекурсивная реализация выполняет много повторяющихся операций (мы можем сделать то же самое, рисуя дерево рекурсии). Поскольку существуют перекрывающиеся подзадачи, мы можем использовать для этого динамическое программирование. Ниже приводится реализация на основе динамического программирования.

C ++

#include<iostream>

using namespace std;

// Функция на основе динамического программирования для поиска nth
// каталонский номер

unsigned long int catalanDP(unsigned int n)

{

// Таблица для хранения результатов подзадач

unsigned long int catalan[n+1];

// Инициализируем первые два значения в таблице

catalan[0] = catalan[1] = 1;

// Заполняем записи в catalan [] используя рекурсивную формулу

for (int i=2; i<=n; i++)

{

catalan[i] = 0;

for (int j=0; j<i; j++)

catalan[i] += catalan[j] * catalan[i-j-1];

}

// Возвращаем последнюю запись

return catalan[n];

}

// Программа драйвера для проверки вышеуказанной функции

int main()

{

for (int i = 0; i < 10; i++)

cout << catalanDP(i) << " ";

return 0;

}

Джава

class GFG{

// Функция на основе динамического программирования для поиска nth
// каталонский номер

static int catalanDP(int n) {

// Таблица для хранения результатов подзадач

int catalan[] = new int[n + 2];

// Инициализируем первые два значения в таблице

catalan[0] = 1;

catalan[1] = 1;

// Заполняем записи в catalan [] используя рекурсивную формулу

for (int i = 2; i <= n; i++) {

catalan[i] = 0;

for (int j = 0; j < i; j++) {

catalan[i] += catalan[j] * catalan[i - j - 1];

}

// Возвращаем последнюю запись

return catalan[n];

}

// Код драйвера

public static void main(String[] args) {

for (int i = 0; i < 10; i++) {

System.out.print(catalanDP(i) + " ");

}

}
// Этот код предоставлен Rajput-Ji

питон

# Функция на основе динамического программирования, чтобы найти nth
# Каталонский номер

def catalan(n):

if (n == 0 or n == 1):

return 1

# Таблица для хранения результатов подзадач

catalan = [0 for i in range(n + 1)]

# Инициализировать первые два значения в таблице

catalan[0] = 1

catalan[1] = 1

# Заполните записи в каталонском [], используя рекурсивную формулу

for i in range(2, n + 1):

catalan[i] = 0

for j in range(i):

catalan[i] = catalan[i] + catalan[j] * catalan[i-j-1]

# Вернуть последнюю запись

return catalan[n]

# Код драйвера

for i in range (10):

print (catalan(i),end=" ")

# Этот код предоставлен Адити Шарма

C #

using System;

class GFG

{

// Динамическое программирование на основе
// функция для поиска nth
// каталонский номер

static uint catalanDP(uint n)

{

// Таблица для хранения результатов подзадач

uint[] catalan = new uint[n + 2];

// Инициализируем первые два значения в таблице

catalan[0] = catalan[1] = 1;

// Заполняем записи в каталонском []

// используя рекурсивную формулу

for (uint i = 2; i <= n; i++)

{

catalan[i] = 0;

for (uint j = 0; j < i; j++)

catalan[i] += catalan[j] * catalan[i - j - 1];

}

// Возвращаем последнюю запись

return catalan[n];

}

// Код драйвера

static void Main()

{

for (uint i = 0; i < 10; i++)

Console.Write(catalanDP(i) + " ");

}
}

// Этот код предоставлен Chandan_jnu

PHP

<?php
// PHP-программа для n-го каталонского номера

// Функция на основе динамического программирования
// найти каталонское число

function catalanDP( $n)

{

// Таблица для хранения результатов

// подзадач

$catalan= array();

// Инициализируем первые два

// значения в таблице

$catalan[0] = $catalan[1] = 1;

// Заполняем записи в каталонском []

// используя рекурсивную формулу

for ($i = 2; $i <= $n; $i++)

{

$catalan[$i] = 0;

for ( $j = 0; $j < $i; $j++)

$catalan[$i] += $catalan[$j] *

$catalan[$i - $j - 1];

}

// Возвращаем последнюю запись

return $catalan[$n];

}

// Код драйвера

for ($i = 0; $i < 10; $i++)

echo catalanDP($i) , " ";

// Этот код предоставлен anuj_67.
?>

Выход:

1 1 2 5 14 42 132 429 1430 4862

Сложность времени: временная сложность вышеописанной реализации составляет O (n ² )

Использование биномиального коэффициента
Мы также можем использовать приведенную ниже формулу, чтобы найти n-е каталонское число за O (n) время.

Мы обсудили O (n) подход, чтобы найти биномиальный коэффициент nCr .

C ++

// C ++ программа для n-го каталонского номера
#include<iostream>

using namespace std;

// Возвращает значение биномиального коэффициента C (n, k)

unsigned long int binomialCoeff(unsigned int n, unsigned int k)

{

unsigned long int res = 1;

// Поскольку C (n, k) = C (n, nk)

if (k > n - k)

k = n - k;

// Рассчитать значение [n * (n-1) * --- * (n-k + 1)] / [k * (k-1) * --- * 1]

for (int i = 0; i < k; ++i)

{

res *= (n - i);

res /= (i + 1);

}

return res;

}

// Функция на основе биномиального коэффициента для поиска n-го каталонского
// число за O (n) время

unsigned long int catalan(unsigned int n)

{

// Рассчитать значение 2nCn

unsigned long int c = binomialCoeff(2*n, n);

// вернуть 2nCn / (n + 1)

return c/(n+1);

}

// Программа драйвера для проверки вышеуказанных функций

int main()

{

for (int i = 0; i < 10; i++)

cout << catalan(i) << " ";

return 0;

}

Джава

// Java-программа для n-го каталонского номера

class GFG {

// Возвращает значение биномиального коэффициента C (n, k)

static long binomialCoeff(int n, int k) {

long res = 1;

// Поскольку C (n, k) = C (n, nk)

if (k > n - k) {

k = n - k;

}

// Рассчитать значение [n * (n-1) * --- * (n-k + 1)] / [k * (k-1) * --- * 1]

for (int i = 0; i < k; ++i) {

res *= (n - i);

res /= (i + 1);

}

return res;

}

// Функция на основе биномиального коэффициента для поиска n-го каталонского
// число за O (n) время

static long catalan(int n) {

// Рассчитать значение 2nCn

long c = binomialCoeff(2 * n, n);

// вернуть 2nCn / (n + 1)

return c / (n + 1);

}

// Программа драйвера для проверки вышеуказанной функции

public static void main(String[] args) {

for (int i = 0; i < 10; i++) {

System.out.print(catalan(i) + " ");

}

python3

# Программа Python для n-го каталонского номера
# Возвращает значение биномиального коэффициента C (n, k)

def binomialCoefficient(n, k):

# так как C (n, k) = C (n, n - k)

if (k > n - k):

k = n - k

# инициализировать результат

res = 1

# Рассчитать значение [n * (n-1) * --- * (nk + 1)]

# / [k * (k-1) * ---- * 1]

for i in range(k):

res = res * (n - i)

res = res / (i + 1)

return res

# Функция на основе биномиального коэффициента для
# найти n-е каталонское число за O (n) время

def catalan(n):

c = binomialCoefficient(2*n, n)

return c/(n + 1)

for i in range (10):

print (catalan(i),end=" ")

# Этот код предоставлен Адити Шарма

C #

// C # программа для n-го каталонского номера

using System;

class GFG

{

// Возвращает значение биномиального коэффициента C (n, k)

static long binomialCoeff(int n, int k)

{

long res = 1;

// Поскольку C (n, k) = C (n, nk)

if (k > n - k)

{

k = n - k;

}

// Рассчитать значение [n * (n-1) * --- * (n-k + 1)] / [k * (k-1) * --- * 1]

for (int i = 0; i < k; ++i)

{

res *= (n - i);

res /= (i + 1);

}

return res;

}

// Функция на основе биномиального коэффициента для поиска n-го каталонского

// число за O (n) время

static long catalan(int n)

{

// Рассчитать значение 2nCn

long c = binomialCoeff(2 * n, n);

// вернуть 2nCn / (n + 1)

return c / (n + 1);

}

// Программа драйвера для проверки вышеуказанной функции

public static void Main()

{

for (int i = 0; i < 10; i++) {

Console.Write(catalan(i) + " ");

}

// Этот код добавлен
// Аканкша Рай

PHP

<?php
// PHP-программа для n-го каталонского номера

// Возвращает значение бинома
// Коэффициент C (n, k)

function binomialCoeff($n, $k)

{

$res = 1;

// Поскольку C (n, k) = C (n, nk)

if ($k > $n - $k)

$k = $n - $k;

// Рассчитать значение [n * (n-1) * --- * (n-k + 1)] /

// [k * (k-1) * --- * 1]

for ($i = 0; $i < $k; ++$i)

{

$res *= ($n - $i);

$res = floor($res / ($i + 1));

}

return $res;

}

// Функция на основе биномиального коэффициента
// найти n-е каталонское число за O (n) время

function catalan($n)

{

// Рассчитать значение 2nCn

$c = binomialCoeff(2 * ($n), $n);

// вернуть 2nCn / (n + 1)

return floor($c / ($n + 1));

}

// Код драйвера

for ($i = 0; $i < 10; $i++)

echo catalan($i), " " ;

// Этот код предоставлен Ryuga
?>

Выход:

1 1 2 5 14 42 132 429 1430 4862

Сложность времени: временная сложность вышеописанной реализации составляет O (n).

Мы также можем использовать приведенную ниже формулу, чтобы найти n-е каталонское число за O (n) время.

Ссылки:
http://en.wikipedia.org/wiki/Catalan_number

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Программа для n-го каталонского номера

0.00 (0%) 0 votes