Dado un número n, encuentre el número de expresiones de paréntesis válidas de esa longitud.
Ejemplos:
Input: 2 Output: 1 There is only possible valid expression of length 2, "()" Input: 4 Output: 2 Possible valid expression of length 4 are "(())" and "()()" Input: 6 Output: 5 Possible valid expressions are ((())), ()(()), ()()(), (())() and (()())
Esta es principalmente una aplicación de Números catalanes . El total de posibles expresiones válidas para la entrada n es n/2′ número catalán si n es par y 0 si n es impar.
A continuación se muestra la implementación:
C++
// C++ program to find valid paranthesisations of length n
// The majority of code is taken from method 3 of
// https://www.geeksforgeeks.org/program-nth-catalan-number/
#include <bits/stdc++.h>
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);
}
// Function to find possible ways to put balanced
// parenthesis in an expression of length n
unsigned long int findWays(unsigned n)
{
// If n is odd, not possible to
// create any valid parentheses
if (n & 1)
return 0;
// Otherwise return n/2'th Catalan Number
return catalan(n / 2);
}
// Driver program to test above functions
int main()
{
int n = 6;
cout << "Total possible expressions of length "
<< n << " is " << findWays(6);
return 0;
}
Java
// Java program to find valid paranthesisations of length n
// The majority of code is taken from method 3 of
// https://www.geeksforgeeks.org/program-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);
}
// Function to find possible ways to put balanced
// parenthesis in an expression of length n
static long findWays(int n)
{
// If n is odd, not possible to
// create any valid parentheses
if ((n & 1) != 0)
return 0;
// Otherwise return n/2'th Catalan Number
return catalan(n / 2);
}
// Driver program to test above functions
public static void main(String[] args)
{
int n = 6;
System.out.println("Total possible expressions of length " +
n + " is " + findWays(6));
}
}
// This code is contributed by Smitha Dinesh Semwal
Python3
# Python3 program to find valid
# paranthesisations of length n
# The majority of code is taken
# from method 3 of
# https:#www.geeksforgeeks.org/program-nth-catalan-number/
# Returns value of Binomial
# Coefficient C(n, k)
def 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 in range(k):
res *= (n - i);
res /= (i + 1);
return int(res);
# A Binomial coefficient based
# function to find nth catalan
# number in O(n) time
def catalan(n):
# Calculate value of 2nCn
c = binomialCoeff(2 * n, n);
# return 2nCn/(n+1)
return int(c / (n + 1));
# Function to find possible
# ways to put balanced parenthesis
# in an expression of length n
def findWays(n):
# If n is odd, not possible to
# create any valid parentheses
if(n & 1):
return 0;
# Otherwise return n/2'th
# Catalan Number
return catalan(int(n / 2));
# Driver Code
n = 6;
print("Total possible expressions of length",
n, "is", findWays(6));
# This code is contributed by mits
C#
// C# program to find valid paranthesisations
// of length n The majority of code is taken
// from method 3 of
// https://www.geeksforgeeks.org/program-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);
}
// Function to find possible ways to put
// balanced parenthesis in an expression
// of length n
static long findWays(int n)
{
// If n is odd, not possible to
// create any valid parentheses
if ((n & 1) != 0)
return 0;
// Otherwise return n/2'th
// Catalan Number
return catalan(n / 2);
}
// Driver program to test
// above functions
public static void Main()
{
int n = 6;
Console.Write("Total possible expressions"
+ "of length " + n + " is "
+ findWays(6));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to find valid
// paranthesisations of length n
// The majority of code is taken
// from method 3 of
// https://www.geeksforgeeks.org/program-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 /= ($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 $c / ($n + 1);
}
// Function to find possible
// ways to put balanced
// parenthesis in an expression
// of length n
function findWays($n)
{
// If n is odd, not possible to
// create any valid parentheses
if ($n & 1)
return 0;
// Otherwise return n/2'th
// Catalan Number
return catalan($n / 2);
}
// Driver Code
$n = 6;
echo "Total possible expressions of length "
, $n , " is " , findWays(6);
// This code is contributed by nitin mittal
?>
Javascript
<script>
// Javascript program to find valid
// paranthesisations of length n
// The majority of code is taken
// from method 3 of
// https://www.geeksforgeeks.org/program-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 /= (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
let c = binomialCoeff(2 * n, n);
// return 2nCn/(n+1)
return c / (n + 1);
}
// Function to find possible
// ways to put balanced
// parenthesis in an expression
// of length n
function findWays(n)
{
// If n is odd, not possible to
// create any valid parentheses
if (n & 1)
return 0;
// Otherwise return n/2'th
// Catalan Number
return catalan(n / 2);
}
// Driver Code
let n = 6;
document.write("Total possible expressions of length " +
n + " is " + findWays(6));
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
Total possible expressions of length 6 is 5
Complejidad de tiempo: O(n)
Espacio auxiliar: O(1)
Este artículo es una contribución de Sachin . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA