Рубрики

Способы умножения n элементов с помощью ассоциативной операции

Учитывая число n, найдите количество способов умножить n элементов с помощью ассоциативной операции.

Примеры :

Input : 2
Output : 2
For a and b there are two ways to multiply them.
1. (a * b)        
2. (b * a)

Input : 3
Output : 12

Пояснение (пример 2):

For a, b and c there are 12 ways to multiply them.
1.  ((a * b) * c)     2.  (a * (b * c))
3.  ((a * c) * b)     4.  (a * (c * b))
5.  ((b * a) * c)     6.  (b * (a * c))
7.  ((b * c) * a)     8.  (b * (c * a))
9.  ((c * a) * b)     10.  (c * (a * b))
11.  ((c * b) * a)    12.  (c * (b * a))

Подход: во- первых, мы пытаемся выяснить рекуррентное соотношение. Из приведенных примеров видно, что h (1) = 1, h (2) = 2, h (3) = 12. Теперь для n элементов будет n — 1 умножение и n — 1 скобки. И, (a1, a2,…, an) можно получить из (a1, a2,…, a (n — 1)) ровно одним из двух способов:

  1. Возьмите умножение (a1, a2,…, a (n — 1)) (которое имеет n — 2 умножения и n — 2 скобки) и вставьте n-й элемент 'an' по обе стороны от любого фактора в один из n — 2 умножения. Таким образом, для каждой схемы для n — 1 чисел приведено 2 * 2 * (n — 2) = 4 * (n — 2) схем для n чисел таким способом.
  2. Возьмите схему умножения для (a1, a2, .., a (n-1)) и умножьте влево или вправо на ('an'). Таким образом, для каждой схемы для n — 1 чисел приводятся две схемы для n чисел таким способом.

Таким образом, после добавления выше двух, мы получаем, h (n) = (4 * n — 8 + 2) * h (n — 1), h (n) = (4 * n — 6) * h (n — 1) , Это рекуррентное соотношение с тем же начальным значением удовлетворяется псевдокаталонским числом. Следовательно, h (n) = (2 * n — 2)! / (n — 1)!

C ++

// код CPP, чтобы найти количество способов умножения n
// элементы с ассоциативной операцией
# include <bits/stdc++.h>

using namespace std;

  
// Функция для поиска необходимого факториала

int fact(int n)

{

    if (n == 0 || n == 1)    

        return 1 ;

  

    int ans = 1;   

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

        ans = ans * i ; 

  

    return ans ;

}

  
// Функция для поиска nCr

int nCr(int n, int r)

{

    int Nr = n , Dr = 1 , ans = 1;

    for (int i = 1 ; i <= r ; i++ ) {

        ans = ( ans * Nr ) / ( Dr ) ;

        Nr-- ;

        Dr++ ;

    }

    return ans ;

}

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

int solve ( int n )

{

    int N = 2*n - 2 ;

    int R = n - 1 ;    

    return nCr (N, R) * fact(n - 1) ;

}

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

int main()

{

    int n = 6 ;

    cout << solve (n) ;    

    return 0 ;

}

Джава

// Java-код для поиска номера
// способы умножения n элементов
// с ассоциативной операцией

import java.io.*;

  

class GFG 

{
// Функция для поиска
// требуется факториал

static int fact(int n)

{

    if (n == 0 || n == 1

        return 1 ;

  

    int ans = 1

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

        ans = ans * i ; 

  

    return ans ;

}

  
// Функция для поиска nCr

static int nCr(int n, int r)

{

    int Nr = n , Dr = 1 , ans = 1;

    for (int i = 1 ; i <= r ; i++ ) 

    {

        ans = ( ans * Nr ) / ( Dr ) ;

        Nr-- ;

        Dr++ ;

    }

    return ans ;

}

  
// функция для поиска
// количество способов

static int solve ( int n )

{

    int N = 2 * n - 2 ;

    int R = n - 1

    return nCr (N, R) * fact(n - 1) ;

}

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

public static void main (String[] args) 

{

int n = 6 ;

System.out.println( solve (n)) ; 
}
}

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

python3

# Python3 код для поиска номера
# способов умножения n
# элементы с
# ассоциативная операция

  
# Функция для поиска
# требуется факториал

def fact(n):

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

        return 1;

  

    ans = 1

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

        ans = ans * i; 

  

    return ans;

  
# Функция для поиска nCr

def nCr(n, r):

    Nr = n ; Dr = 1 ; ans = 1;

    for i in range(1, r + 1):

        ans = int((ans * Nr) / (Dr));

        Nr = Nr - 1;

        Dr = Dr + 1;

    return ans;

  
# функция для поиска
# количество способов

def solve ( n ):

    N = 2* n - 2;

    R = n - 1

    return (nCr (N, R) * 

            fact(n - 1));

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

n = 6 ;

print(solve (n) ); 

  
# Этот код добавлен
# по митсам

C #

// C # код для поиска номера
// способы умножения n элементов
// с ассоциативной операцией

using System;

  

class GFG {

      

    // Функция для поиска

    // требуется факториал

    static int fact(int n)

    {

        if (n == 0 || n == 1) 

            return 1 ;

      

        int ans = 1; 

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

            ans = ans * i ; 

      

        return ans ;

    }

      

    // Функция для поиска nCr

    static int nCr(int n, int r)

    {

        int Nr = n , Dr = 1 , ans = 1;

        for (int i = 1 ; i <= r ; i++ ) 

        {

            ans = ( ans * Nr ) / ( Dr ) ;

            Nr-- ;

            Dr++ ;

        }

        return ans ;

    }

      

    // функция для поиска

    // количество способов

    static int solve ( int n )

    {

        int N = 2 * n - 2 ;

        int R = n - 1 ; 

        return nCr (N, R) * fact(n - 1) ;

    }

      

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

    public static void Main () 

    {

        int n = 6 ;

        Console.WriteLine( solve (n)) ; 

    }

}

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

PHP

<?php
// PHP-код для поиска номера
// способов умножить n
// элементы с
// ассоциативная операция

  
// Функция для поиска
// требуется факториал

function fact($n)

{

    if ($n == 0 || $n == 1) 

        return 1;

  

    $ans = 1; 

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

        $ans = $ans * $i

  

    return $ans;

}

  
// Функция для поиска nCr

function nCr($n, $r)

{

    $Nr = $n ; $Dr = 1 ; $ans = 1;

    for ($i = 1 ; $i <= $r ; $i++ )

    {

        $ans = ($ans * $Nr) / 

                      ($Dr);

        $Nr--;

        $Dr++;

    }

    return $ans ;

}

  
// функция для поиска
// количество способов

function solve ( $n )

{

    $N = 2* $n - 2 ;

    $R = $n - 1 ; 

    return nCr ($N, $R) * 

           fact($n - 1) ;

}

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

$n = 6 ;

echo solve ($n) ; 

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

Выход :

30240

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

Способы умножения n элементов с помощью ассоциативной операции

0.00 (0%) 0 votes