RYMD- OCH TIDSEFFEKTIV BINOMIAL KOEFFICIENT

Här tar funktionen två parametrar n och k och returnerar värdet av binomialkoefficienten C(n k).

Exempel:

cp kommando i linux

  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

Vi har diskuterat O(n*k) tid och O(k) extra rymdalgoritm i detta posta. Värdet på C(n k) kan beräknas i O(k) tid och O(1) extra utrymme.

Närma sig:

Ändra r till n-r om r är större än n-r. och skapa en variabel för att lagra svaret.
Kör en slinga från 0 till r-1
Uppdatera i varje iteration ans som (ans*(n-i))/(i+1) där i är loopräknaren.
Så svaret blir lika med ((n/1)*((n-1)/2)*...*((n-r+1)/r) vilket är lika med 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

Följande implementering använder ovanstående formel för att beräkna C(n k).

java lokal datumtid

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>

Produktion

Value of C(8 2) is 28

Komplexitetsanalys:

Tidskomplexitet: Eller) En slinga måste köras från 0 till r. Så tidskomplexiteten är O(r).

Hjälputrymme: O(1) Eftersom inget extra utrymme krävs.

Den här artikeln är sammanställd av Aashish Barnwal och granskad av GeeksforGeeks-teamet.

Skapa frågesport

TechCodeview

Rymd- och tidseffektiv binomial koefficient