Напишите функцию, которая принимает два параметра 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
- Измените r на n-r, если r больше n-r. и создайте переменную для хранения ответа.
- Выполните цикл от 0 до r-1
- На каждой итерации обновляйте ans как (ans*(n-i))/(i+1), где i-счетчик циклов.
- Таким образом, ответ будет равен ((n/1)*((n-1)/2)*…*((n-r+1)/r!) что равно nCr.
Следующая реализация использует приведенную выше формулу для вычисления C(n, k).
// 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
// 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;
}
// 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 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# 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
// 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.
?>
<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).
Поскольку дополнительное пространство не требуется.