You are currently viewing Пространственно-временной эффективный биномиальный коэффициент

Пространственно-временной эффективный биномиальный коэффициент

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

Пример:

Input: n = 4 and k = 2
Output: 6
Explanation: 4 C 2 is 4!/(2!*2!) = 6

Input: n = 5 and k = 2
Output: 10
Explanation: 5 C 2 is 5!/(3!*2!) = 20

Мы обсудили алгоритм 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)  
// r can be changed to n-r if r > n-r 
  1. Измените r на n-r, если r больше n-r. и создайте переменную для хранения ответа.
  2. Выполните цикл от 0 до r-1
  3. На каждой итерации обновляйте ans как (ans*(n-i))/(i+1), где i-счетчик циклов.
  4. Таким образом, ответ будет равен ((n/1)*((n-1)/2)*…*((n-r+1)/r!) что равно nCr.

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

C++
// Program to calculate C(n, k) #include <bits/stdc++.h> using namespace std; // Returns value of Binomial Coefficient C(n, k) int binomialCoeff(int n, int k) { 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; } // Driver Code int main() { int n = 8, k = 2; cout << "Value of C(" << n << ", " << k << ") is " << binomialCoeff(n, k); return 0; } // This is code is contributed by rathbhupendra
C
// Program to calculate C(n, k) #include <stdio.h> // Returns value of Binomial Coefficient C(n, k) int binomialCoeff(int n, int k) { 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; } /* Driver program to test above function*/ int main() { int n = 8, k = 2; printf( "Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k)); return 0; }
Java
// Program to calculate C(n, k) in java class BinomialCoefficient { // Returns value of Binomial Coefficient C(n, k) static int binomialCoeff(int n, int k) { 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; } /* Driver program to test above function*/ public static void main(String[] args) { int n = 8; int k = 2; System.out.println("Value of C(" + n + ", " + k + ") " + "is" + " " + binomialCoeff(n, k)); } } // This Code is Contributed by Saket Kumar
Python
# Python program to calculate C(n, k) # 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 # Driver program to test above function n = 8 k = 2 res = binomialCoefficient(n, k) print("Value of C(% d, % d) is % d" %(n, k, res)) # This code is contributed by Aditi Sharma
C#
// C# Program to calculate C(n, k) using System; class BinomialCoefficient { // Returns value of Binomial // Coefficient C(n, k) static int binomialCoeff(int n, int k) { 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; } // Driver Code public static void Main() { int n = 8; int k = 2; Console.Write("Value of C(" + n + ", " + k + ") " + "is" + " " + binomialCoeff(n, k)); } } // This Code is Contributed by // Smitha Dinesh Semwal.
PHP
<?php // Program to calculate C(n, k) // 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; } // Driver Code $n = 8; $k = 2; echo " Value of C ($n, $k) is ", binomialCoeff($n, $k); // This code is contributed by ajit. ?>
Javascript
<script> // Program to calculate C(n, k) // 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; } // Driver Code let n = 8; let k = 2; document.write("Value of C(" + n + ", " + k + ") " + "is" + " " + binomialCoeff(n, k)); </script>

Выход: 

Value of C(8, 2) is 28

Анализ сложности: 

  • Временная сложность: O(r).
    Цикл должен выполняться от 0 до r. Таким образом, временная сложность равна O(r).
  • Вспомогательное пространство: O(1).
    Поскольку дополнительное пространство не требуется.