Рубрики

Эффективность пространства и времени Биномиальный коэффициент

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

Напишите функцию, которая принимает два параметра n и k и возвращает значение биномиального коэффициента C (n, k). Например, ваша функция должна возвращать 6 для n = 4 и k = 2, и она должна возвращать 10 для n = 5 и k = 2.

В этом посте мы обсудили алгоритм O (n * k) времени и O (k) дополнительного пространства. Значение C (n, k) может быть рассчитано за время O (k) и дополнительное пространство O (1).

C(n, k) = n! / (n-k)! * k!
        = [n * (n-1) *....* 1]  / [ ( (n-k) * (n-k-1) * .... * 1) * 
                                    ( k * (k-1) * .... * 1 ) ]
After simplifying, we get
C(n, k) = [n * (n-1) * .... * (n-k+1)] / [k * (k-1) * .... * 1]

Also, C(n, k) = C(n, n-k)  // we can change r to n-r if r > n-r

Следующая реализация использует приведенную выше формулу для расчета C (n, k)

C ++

// Программа для расчета C (n, k)
#include <bits/stdc++.h>

using namespace std;

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

int binomialCoeff(int n, int k) 

{ 

    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; 

} 

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

int main() 

{ 

    int n = 8, k = 2; 

    cout << "Value of C(" << n << ", " 

         << k << ") is " << binomialCoeff(n, k); 

    return 0; 

} 

  
// Это код, предоставленный rathbhupendra

С

// Программа для расчета C (n, k)
#include <stdio.h>

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

int binomialCoeff(int n, int k)

{

    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;

}

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

int main()

{

    int n = 8, k = 2;

    printf ("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k) );

    return 0;

}

Джава

// Программа для вычисления C (n, k) в Java

class BinomialCoefficient

{

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

    static int binomialCoeff(int n, int k)

    {

        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;

    }

      

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

    public static void main(String[] args)

    {

        int n = 8;

        int k = 2;

        System.out.println("Value of C("+ n + ", " + k+ ") "

                                + "is" + " "+ binomialCoeff(n, k));

    }

  
}
// Этот код предоставлен Сакет Кумар

питон

# Python программа для расчета C (n, k)

  
# Возвращает значение биномиального коэффициента
# 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 = 8

k = 2

res = binomialCoefficient(n, k)

print("Value of C(%d, %d) is %d" %(n, k, res))

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

C #

// C # Программа для расчета C (n, k)

using System;

  

class BinomialCoefficient

{

      

    // Возвращает значение бинома

    // Коэффициент C (n, k)

    static int binomialCoeff(int n, int k)

    {

        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;

    }

      

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

    public static void Main()

    {

        int n = 8;

        int k = 2;

        Console.Write("Value of C("+ n + ", " + k+ ") "

                       + "is" + " "+ binomialCoeff(n, k));

    }

  
}

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

PHP

<?php
// Программа для расчета C (n, k)
// Возвращает значение бинома
// Коэффициент 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;

}

  

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

    $n = 8;

    $k = 2;

    echo " Value of C ($n, $k) is ",

             binomialCoeff($n, $k);

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

Value of C(8, 2) is 28

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

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

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

Эффективность пространства и времени Биномиальный коэффициент

0.00 (0%) 0 votes