COEFFICIENT BINOMIAL EFFICACE EN TERMES D'ESPACE ET DE TEMPS

Ici la fonction prend deux paramètres n et k et renvoie la valeur du coefficient binomial C(nk).

Exemple:

ordre lexicographique

  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

Nous avons discuté du temps O(n*k) et de l'algorithme d'espace supplémentaire O(k) dans ce poste. La valeur de C(n k) peut être calculée en temps O(k) et en espace supplémentaire O(1).

Approche:

Remplacez r par n-r si r est supérieur à n-r. et créez une variable pour stocker la réponse.
Exécuter une boucle de 0 à r-1
À chaque itération, mettez à jour ans as (ans*(ni))/(i+1) où i est le compteur de boucle.
La réponse sera donc égale à ((n/1)*((n-1)/2)*...*((n-r+1)/r) qui est égal à 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 mise en œuvre suivante utilise la formule ci-dessus pour calculer C(nk).

chaîne.format java

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>

Sortir

Value of C(8 2) is 28

Analyse de complexité :

Complexité temporelle : Ou) Une boucle doit être exécutée de 0 à r. La complexité temporelle est donc O(r).

Espace auxiliaire : O(1) Comme aucun espace supplémentaire n’est requis.

Cet article est compilé par Aashish Barnwal et révisé par l'équipe GeeksforGeeks.

Créer un quiz

TechCodeview

Coefficient binomial efficace en termes d'espace et de temps