Блог

Напишите функцию, которая принимает два параметра 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).

// 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).
  Поскольку дополнительное пространство не требуется.