COEFICIENT BINOMI EFICIENT ESPAI I TEMPS

Aquí la funció pren dos paràmetres n i k i retorna el valor del coeficient binomial C(n k).

Exemple:

tipus de proves

  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!) = 10

Hem parlat de l'algorisme O (n * k) temps i O (k) espai addicional això publicació. El valor de C(n k) es pot calcular en O(k) temps i O(1) espai addicional.

Enfocament:

Canvia r a n-r si r és més gran que n-r. i creeu una variable per emmagatzemar la resposta.
Executeu un bucle de 0 a r-1
En cada iteració actualitzeu ans com (ans*(n-i))/(i+1) on i és el comptador de bucles.
Per tant, la resposta serà igual a ((n/1)*((n-1)/2)*...*((n-r+1)/r) que és igual a nCr.

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

La implementació següent utilitza la fórmula anterior per calcular C(n k).

el somriure més bonic del món

C++

// Program to calculate C(n k) #include    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  // 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

Python3

# 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. ?>

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>

Sortida

Value of C(8 2) is 28

Anàlisi de complexitat:

Complexitat temporal: O(r) S'ha d'executar un bucle de 0 a r. Per tant, la complexitat temporal és O(r).

Espai auxiliar: O(1) Com que no cal espai addicional.

Aquest article està compilat per Aashish Barnwal i revisat per l'equip de GeeksforGeeks.

Crea un qüestionari

TechCodeview

Coeficient binomi eficient espai i temps