Рубрики

Найти количество допустимых выражений в скобках заданной длины

По заданному числу n найдите количество допустимых выражений в скобках этой длины.
Примеры :

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 (()())

Это в основном применение каталонских номеров . Всего возможных допустимых выражений для ввода n — это n / 2'-е каталонское число, если n четное, и 0, если n нечетное.

Ниже приводится реализация:

C ++

// C ++ программа для поиска правильных аргументов длины n
// Большая часть кода взята из метода 3
// https://www.geeksforgeeks.org/program-nth-catalan-number/amp/
#include <bits/stdc++.h>

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);

}

  
// Функция для поиска возможных способов поставить баланс
// скобка в выражении длины n

unsigned long int findWays(unsigned n)

{

    // Если n нечетно, невозможно

    // создаем любые допустимые скобки

    if (n & 1)

        return 0;

  

    // Иначе вернем n / 2'-й каталонский номер

    return catalan(n / 2);

}

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

int main()

{

    int n = 6;

    cout << "Total possible expressions of length "

         << n << " is " << findWays(6);

    return 0;

}

Джава

// Java-программа для поиска правильных аргументов длины n
// Большая часть кода взята из метода 3
// https://www.geeksforgeeks.org/program-nth-catalan-number/amp/

  

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);

    }

  

    // Функция для поиска возможных способов поставить баланс

    // скобка в выражении длины n

    static long findWays(int n)

    {

        // Если n нечетно, невозможно

        // создаем любые допустимые скобки

        if ((n & 1) != 0)

            return 0;

  

        // Иначе вернем n / 2'-й каталонский номер

        return catalan(n / 2);

    }

  

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

    public static void main(String[] args)

    {

        int n = 6;

        System.out.println("Total possible expressions of length "

                                          n + " is " + findWays(6));

    }

}

  
// Этот код предоставлен Smitha Dinesh Semwal

python3

# Python3 программа для поиска действительного
# парантезации длины n
# Большая часть кода занята
# из метода 3
# https: # www.geeksforgeeks.org / program-nth-catalan-number /

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

def 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 in range(k): 

        res *= (n - i);

        res /= (i + 1);

  

    return int(res);

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

def catalan(n):

      

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

    c = binomialCoeff(2 * n, n);

  

    # return 2nCn / (n + 1)

    return int(c / (n + 1));

  
# Функция поиска возможного
# способы поставить сбалансированную скобку
# в выражении длины n

def findWays(n):

      

    # Если n нечетно, невозможно

    # создать любые допустимые скобки

    if(n & 1):

        return 0;

  

    # В противном случае вернуть n / 2'th

    # Каталонский Нумер

    return catalan(int(n / 2));

  
Код водителя

n = 6;

print("Total possible expressions of length"

                       n, "is", findWays(6));

      
# Этот код предоставлен mits

C #

// C # программа для поиска правильных паратезаций
// длины n Большая часть кода занята
// из метода 3
// https://www.geeksforgeeks.org/program-nth-catalan-number/amp/

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);

    }

  

    // Функция поиска возможных способов размещения

    // сбалансированная скобка в выражении

    // длины n

    static long findWays(int n)

    {

        // Если n нечетно, невозможно

        // создаем любые допустимые скобки

        if ((n & 1) != 0)

            return 0;

  

        // Иначе вернем n / 2'th

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

        return catalan(n / 2);

    }

  

    // Программа драйвера для тестирования

    // вышеуказанные функции

    public static void Main()

    {

        int n = 6;

        Console.Write("Total possible expressions"

                       + "of length " + n + " is " 

                                   + findWays(6));

    }

}

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

PHP

<?php
// PHP-программа для поиска верного
// парантезации длины n
// Большая часть кода занята
// из метода 3
// https://www.geeksforgeeks.org/program-nth-catalan-number/amp/

  
// Возвращает значение бинома
// Коэффициент 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 /= ($i + 1);

    }

  

    return $res;

}

  
// Биномиальный коэффициент
// основанная функция для поиска
// каталонский номер
// Вовремя

function catalan($n)

{

      

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

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

  

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

    return $c / ($n + 1);

}

  
// Функция для поиска возможного
// способы поставить баланс
// скобка в выражении
// длины n

function findWays($n)

{

      

    // Если n нечетно, невозможно

    // создаем любые допустимые скобки

    if ($n & 1)

        return 0;

  

    // Иначе вернем n / 2'th

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

    return catalan($n / 2);

}

  

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

    $n = 6;

    echo "Total possible expressions of length "

                    , $n , " is " , findWays(6);

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


Выход:

Total possible expressions of length 6 is 5

Сложность времени: O (n)

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

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

Найти количество допустимых выражений в скобках заданной длины

0.00 (0%) 0 votes