Блог

Главная - JavaScript язык программирования - Программа для n-го Catalan Number (каталонского номера)
You are currently viewing Программа для n-го Catalan Number (каталонского номера)

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

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

  1. Подсчитайте количество выражений, содержащих n пар скобок, которые правильно подобраны. Для n = 3 возможными выражениями являются ((())), ()(()), ()()(), (())(), (()()).
  2. Подсчитайте количество возможных деревьев двоичного поиска с n ключами.
  3. Подсчитайте количество полных двоичных деревьев (корневое двоичное дерево заполнено, если у каждой вершины есть два дочерних элемента или нет дочерних элементов) с n+1 листьями.
  4. Учитывая число n, верните количество способов, которыми вы можете нарисовать n аккордов в круге с 2 точками x n, чтобы никакие 2 аккорда не пересекались.

Видеть этот для большего количества приложений.
Первые несколько каталонских чисел для n = 0, 1, 2, 3, … являются 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …

Рекурсивное Решение

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

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

#include <iostream>
using namespace std;

// A recursive function to find nth catalan number
unsigned long int catalan(unsigned int n)
{
	// Base case
	if (n <= 1)
		return 1;

	// catalan(n) is sum of
	// catalan(i)*catalan(n-i-1)
	unsigned long int res = 0;
	for (int i = 0; i < n; i++)
		res += catalan(i)
			* catalan(n - i - 1);

	return res;
}

// Driver code
int main()
{
	for (int i = 0; i < 10; i++)
		cout << catalan(i) << " ";
	return 0;
}

class CatalnNumber {

	// A recursive function to find nth catalan number

	int catalan(int n)
	{
		int res = 0;

		// Base case
		if (n <= 1)
		{
			return 1;
		}
		for (int i = 0; i < n; i++)
		{
			res += catalan(i)
				* catalan(n - i - 1);
		}
		return res;
	}

	// Driver Code
	public static void main(String[] args)
	{
		CatalnNumber cn = new CatalnNumber();
		for (int i = 0; i < 10; i++)
		{
			System.out.print(cn.catalan(i) + " ");
		}
	}
}

# A recursive function to
# find nth catalan number
def catalan(n):
	# Base Case
	if n <= 1:
		return 1

	# Catalan(n) is the sum
	# of catalan(i)*catalan(n-i-1)
	res = 0
	for i in range(n):
		res += catalan(i) * catalan(n-i-1)

	return res


# Driver Code
for i in range(10):
	print catalan(i),
# This code is contributed by
# Nikhil Kumar Singh (nickzuck_007)

// A recursive C# program to find
// nth catalan number
using System;

class GFG {

	// A recursive function to find
	// nth catalan number
	static int catalan(int n)
	{
		int res = 0;

		// Base case
		if (n <= 1)
		{
			return 1;
		}
		for (int i = 0; i < n; i++)
		{
			res += catalan(i)
				* catalan(n - i - 1);
		}
		return res;
	}

	// Driver Code
	public static void Main()
	{
		for (int i = 0; i < 10; i++)
			Console.Write(catalan(i) + " ");
	}
}

// This code is contributed by
// nitin mittal.

<?php
// PHP Program for nth
// Catalan Number

// A recursive function to
// find nth catalan number
function catalan($n)
{
	
	// Base case
	if ($n <= 1)
		return 1;

	// catalan(n) is sum of
	// catalan(i)*catalan(n-i-1)
	$res = 0;
	for($i = 0; $i < $n; $i++)
		$res += catalan($i) *
				catalan($n - $i - 1);

	return $res;
}

// Driver Code
for ($i = 0; $i < 10; $i++)
	echo catalan($i), " ";

// This code is contributed aj_36
?>

Выход:

1 1 2 5 14 42 132 429 1430 4862

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

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

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

#include <iostream>
using namespace std;

// A dynamic programming based function to find nth
// Catalan number
unsigned long int catalanDP(unsigned int n)
{
	// Table to store results of subproblems
	unsigned long int catalan[n + 1];

	// Initialize first two values in table
	catalan[0] = catalan[1] = 1;

	// Fill entries in catalan[] using recursive formula
	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 last entry
	return catalan[n];
}

// Driver code
int main()
{
	for (int i = 0; i < 10; i++)
		cout << catalanDP(i) << " ";
	return 0;
}

class GFG {

	// A dynamic programming based function to find nth
	// Catalan number
	static int catalanDP(int n)
	{
		// Table to store results of subproblems
		int catalan[] = new int[n + 2];

		// Initialize first two values in table
		catalan[0] = 1;
		catalan[1] = 1;

		// Fill entries in catalan[]
		// using recursive formula
		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 last entry
		return catalan[n];
	}

	// Driver code
	public static void main(String[] args)
	{
		for (int i = 0; i < 10; i++) {
			System.out.print(catalanDP(i) + " ");
		}
	}
}
// This code contributed by Rajput-Ji

# A dynamic programming based function to find nth
# Catalan number


def catalan(n):
	if (n == 0 or n == 1):
		return 1

	# Table to store results of subproblems
	catalan =[0]*(n+1)

	# Initialize first two values in table
	catalan[0] = 1
	catalan[1] = 1

	# Fill entries in catalan[]
	# using recursive formula
	for i in range(2, n + 1):
		for j in range(i):
			catalan[i] += catalan[j]* catalan[i-j-1]

	# Return last entry
	return catalan[n]


# Driver code
for i in range(10):
	print(catalan(i), end=" ")
# This code is contributed by Ediga_manisha

using System;

class GFG {

	// A dynamic programming based
	// function to find nth
	// Catalan number
	static uint catalanDP(uint n)
	{
		// Table to store results of subproblems
		uint[] catalan = new uint[n + 2];

		// Initialize first two values in table
		catalan[0] = catalan[1] = 1;

		// Fill entries in catalan[]
		// using recursive formula
		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 last entry
		return catalan[n];
	}

	// Driver code
	static void Main()
	{
		for (uint i = 0; i < 10; i++)
			Console.Write(catalanDP(i) + " ");
	}
}

// This code is contributed by Chandan_jnu

<?php
// PHP program for nth Catalan Number

// A dynamic programming based function
// to find nth Catalan number
function catalanDP( $n)
{
	
	// Table to store results
	// of subproblems
	$catalan= array();

	// Initialize first two
	// values in table
	$catalan[0] = $catalan[1] = 1;

	// Fill entries in catalan[]
	// using recursive formula
	for ($i = 2; $i <= $n; $i++)
	{
		$catalan[$i] = 0;
		for ( $j = 0; $j < $i; $j++)
			$catalan[$i] += $catalan[$j] *
				$catalan[$i - $j - 1];
	}

	// Return last entry
	return $catalan[$n];
}

	// Driver Code
	for ($i = 0; $i < 10; $i++)
		echo catalanDP($i) , " ";

// This code is contributed anuj_67.
?>

<script>
// Javascript program for nth Catalan Number

// A dynamic programming based function
// to find nth Catalan number
function catalanDP(n)
{
	
	// Table to store results
	// of subproblems
	let catalan= [];

	// Initialize first two
	// values in table
	catalan[0] = catalan[1] = 1;

	// Fill entries in catalan[]
	// using recursive formula
	for (let i = 2; i <= n; i++)
	{
		catalan[i] = 0;
		for (let j = 0; j < i; j++)
			catalan[i] += catalan[j] *
				catalan[i - j - 1];
	}

	// Return last entry
	return catalan[n];
}

	// Driver Code
	for (let i = 0; i < 10; i++)
		document.write(catalanDP(i) + " ");

// This code is contributed _saurabh_jaiswal
</script>

Выход:

1 1 2 5 14 42 132 429 1430 4862

Временная сложность: Временная сложность вышеуказанной реализации составляет O(n2)

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

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

// C++ program for nth Catalan Number
#include <iostream>
using namespace std;

// Returns value of Binomial Coefficient C(n, k)
unsigned long int binomialCoeff(unsigned int n,
								unsigned int k)
{
	unsigned long int res = 1;

	// Since C(n, k) = C(n, n-k)
	if (k > n - k)
		k = n - k;

	// Calculate value of [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;
}

// A Binomial coefficient based function to find nth catalan
// number in O(n) time
unsigned long int catalan(unsigned int n)
{
	// Calculate value of 2nCn
	unsigned long int c = binomialCoeff(2 * n, n);

	// return 2nCn/(n+1)
	return c / (n + 1);
}

// Driver code
int main()
{
	for (int i = 0; i < 10; i++)
		cout << catalan(i) << " ";
	return 0;
}

// Java program for nth Catalan Number

class GFG {

	// Returns value of Binomial Coefficient C(n, k)
	static long binomialCoeff(int n, int k)
	{
		long res = 1;

		// Since C(n, k) = C(n, n-k)
		if (k > n - k) {
			k = n - k;
		}

		// Calculate value of [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;
	}

	// A Binomial coefficient based function
	// to find nth catalan number in O(n) time
	static long catalan(int n)
	{
		// Calculate value of 2nCn
		long c = binomialCoeff(2 * n, n);

		// return 2nCn/(n+1)
		return c / (n + 1);
	}

	// Driver code
	public static void main(String[] args)
	{
		for (int i = 0; i < 10; i++) {
			System.out.print(catalan(i) + " ");
		}
	}
}

# Python program for nth Catalan Number
# Returns value of Binomial Coefficient C(n, k)


def binomialCoefficient(n, k):

	# since C(n, k) = C(n, n - k)
	if (k > n - k):
		k = n - k

	# initialize result
	res = 1

	# Calculate value of [n * (n-1) *---* (n-k + 1)]
	# / [k * (k-1) *----* 1]
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return res

# A Binomial coefficient based function to
# find nth catalan number in O(n) time


def catalan(n):
	c = binomialCoefficient(2*n, n)
	return c/(n + 1)

# Driver Code
for i in range(10):
	print(catalan(i), end=" ")

# This code is contributed by Aditi Sharma

// C# program for nth Catalan Number
using System;
class GFG {

	// Returns value of Binomial Coefficient C(n, k)
	static long binomialCoeff(int n, int k)
	{
		long res = 1;

		// Since C(n, k) = C(n, n-k)
		if (k > n - k) {
			k = n - k;
		}

		// Calculate value of [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;
	}

	// A Binomial coefficient based function to find nth
	// catalan number in O(n) time
	static long catalan(int n)
	{
		// Calculate value of 2nCn
		long c = binomialCoeff(2 * n, n);

		// return 2nCn/(n+1)
		return c / (n + 1);
	}

	// Driver code
	public static void Main()
	{
		for (int i = 0; i < 10; i++) {
			Console.Write(catalan(i) + " ");
		}
	}
}

// This code is contributed
// by Akanksha Rai

<?php
// PHP program for nth Catalan Number

// Returns value of Binomial
// Coefficient C(n, k)
function binomialCoeff($n, $k)
{
	$res = 1;

	// Since C(n, k) = C(n, n-k)
	if ($k > $n - $k)
		$k = $n - $k;

	// Calculate value of [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;
}

// A Binomial coefficient based function
// to find nth catalan number in O(n) time
function catalan($n)
{
	// Calculate value of 2nCn
	$c = binomialCoeff(2 * ($n), $n);

	// return 2nCn/(n+1)
	return floor($c / ($n + 1));
}

// Driver code
for ($i = 0; $i < 10; $i++)
echo catalan($i), " " ;

// This code is contributed by Ryuga
?>

<script>
// Javascript program for nth Catalan Number

// Returns value of Binomial
// Coefficient C(n, k)
function binomialCoeff(n, k)
{
	let res = 1;

	// Since C(n, k) = C(n, n-k)
	if (k > n - k)
		k = n - k;

	// Calculate value of [n*(n-1)*---*(n-k+1)] /
	//				 [k*(k-1)*---*1]
	for (let i = 0; i < k; ++i)
	{
		res *= (n - i);
		res = Math.floor(res / (i + 1));
	}

	return res;
}

// A Binomial coefficient based function
// to find nth catalan number in O(n) time
function catalan(n)
{

	// Calculate value of 2nCn
	c = binomialCoeff(2 * (n), n);

	// return 2nCn/(n+1)
	return Math.floor(c / (n + 1));
}

// Driver code
for (let i = 0; i < 10; i++)
document.write(catalan(i) + " " );

// This code is contributed by _saurabh_jaiswal
</script>

Выход:

1 1 2 5 14 42 132 429 1430 4862

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

Используйте многоточную библиотеку: В этом методе мы использовали многоточную библиотеку boost, и мотив ее использования заключается только в том, чтобы иметь точность при нахождении большого числа каталонцев и обобщенную технику, использующую цикл for для вычисления каталонских чисел .

For example: N = 5

Initially set cat_=1 then, print cat_ ,

then, iterate from i = 1 to i < 5

for i = 1; cat_ = cat_ * (4*1-2)=1*2=2
cat_ = cat_ / (i+1)=2/2 = 1


For i = 2; cat_ = cat_ * (4*2-2)=1*6=6
cat_ = cat_ / (i+1)=6/3=2

For i = 3 :- cat_ = cat_ * (4*3-2)=2*10=20
cat_ = cat_ / (i+1)=20/4=5

For i = 4 :- cat_ = cat_ * (4*4-2)=5*14=70
cat_ = cat_ / (i+1)=70/5=14

Псевдокод:

a) initially set cat_=1 and print it
b) run a for loop i=1 to i<=n
            cat_ *= (4*i-2)
            cat_ /= (i+1)
            print cat_
c) end loop and exit   
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using boost::multiprecision::cpp_int;
using namespace std;

// Function to print the number
void catalan(int n)
{
	cpp_int cat_ = 1;

	// For the first number
	cout << cat_ << " "; // C(0)

	// Iterate till N
	for (cpp_int i = 1; i <=n; i++)
	{
		// Calculate the number
		// and print it
		cat_ *= (4 * i - 2);
		cat_ /= (i + 1);
		cout << cat_ << " ";
	}
}

// Driver code
int main()
{
	int n = 5;

	// Function call
	catalan(n);
	return 0;
}

import java.util.*;
class GFG
{

// Function to print the number
static void catalan(int n)
{
	int cat_ = 1;

	// For the first number
	System.out.print(cat_+" "); // C(0)

	// Iterate till N
	for (int i = 1; i < n; i++)
	{
		// Calculate the number
		// and print it
		cat_ *= (4 * i - 2);
		cat_ /= (i + 1);
		System.out.print(cat_+" ");
	}
}

// Driver code
public static void main(String args[])
{
	int n = 5;

	// Function call
	catalan(n);
}
}

// This code is contributed by Debojyoti Mandal

# Function to print the number
def catalan(n):
	
	cat_ = 1

	# For the first number
	print(cat_, " ", end = '')# C(0)

	# Iterate till N
	for i in range(1, n):
		
		# Calculate the number
		# and print it
		cat_ *= (4 * i - 2);
		cat_ //= (i + 1);
		print(cat_, " ", end = '')

# Driver code
n = 5

# Function call
catalan(n)

# This code is contributed by rohan07

using System;

public class GFG {

	// Function to print the number
	static void catalan(int n) {
		int cat_ = 1;

		// For the first number
		Console.Write(cat_ + " "); // C(0)

		// Iterate till N
		for (int i = 1; i < n; i++) {
			// Calculate the number
			// and print it
			cat_ *= (4 * i - 2);
			cat_ /= (i + 1);
			Console.Write(cat_ + " ");
		}
	}

	// Driver code
	public static void Main(String []args) {
		int n = 5;

		// Function call
		catalan(n);
	}
}

// This code is contributed by Rajput-Ji

<script>

// Function to print the number
function catalan(n)
{
	let cat_ = 1;

	// For the first number
	document.write(cat_ + " "); // C(0)

	// Iterate till N
	for (let i = 1; i < n; i++)
	{
		// Calculate the number
		// and print it
		cat_ *= (4 * i - 2);
		cat_ /= (i + 1);
		document.write(cat_ + " ");
	}
}

// Driver code
	let n = 5;

	// Function call
	catalan(n);

//This code is contributed by Mayank Tyagi
</script>

Выход:

1 1 2 5 14

Временная сложность: O(n)
Вспомогательное пространство: O(1)

Другое решение с использованием BigInteger на java:

  • Найти значения каталонских чисел для N>80 невозможно даже с помощью long в java, поэтому мы используем BigInteger
  • Здесь мы находим решение с использованием метода биномиальных коэффициентов, как обсуждалось выше

import java.io.*;
import java.util.*;
import java.math.*;

class GFG
{
	public static BigInteger findCatalan(int n)
	{
		// using BigInteger to calculate large factorials
		BigInteger b = new BigInteger("1");

		// calculating n!
		for (int i = 1; i <= n; i++) {
			b = b.multiply(BigInteger.valueOf(i));
		}

		// calculating n! * n!
		b = b.multiply(b);

		BigInteger d = new BigInteger("1");

		// calculating (2n)!
		for (int i = 1; i <= 2 * n; i++) {
			d = d.multiply(BigInteger.valueOf(i));
		}

		// calculating (2n)! / (n! * n!)
		BigInteger ans = d.divide(b);

		// calculating (2n)! / ((n! * n!) * (n+1))
		ans = ans.divide(BigInteger.valueOf(n + 1));
		return ans;
	}

	// Driver Code
	public static void main(String[] args)
	{
		int n = 5;
		System.out.println(findCatalan(n));
	}
}
// Contributed by Rohit Oberoi

Выход:

42
Метки: