TÉR- ÉS IDŐHATÉKONY BINOMIÁLIS EGYÜTTHATÓ

Itt a függvény két paramétert vesz fel n és k és a C(n k) binomiális együttható értékét adja vissza.

Példa:

tömb rendezése java

  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

Az O(n*k) idő és az O(k) extra tér algoritmusát itt tárgyaltuk ez hozzászólás. A C(n k) értéke O(k) időben és O(1) extra térben számítható.

Megközelítés:

Módosítsa r-et n-r-re, ha r nagyobb, mint n-r. és hozzon létre egy változót a válasz tárolására.
Futtasson egy hurkot 0-tól r-1-ig
Minden iterációs frissítésben az ans as (ans*(n-i))/(i+1) ahol i a hurokszámláló.
Tehát a válasz egyenlő lesz ((n/1)*((n-1)/2)*...*((n-r+1)/r), ami egyenlő nCr-rel.

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

A következő megvalósítás a fenti képletet használja a C(n k) kiszámításához.

listakészítés java-ban

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>

Kimenet

Value of C(8 2) is 28

Komplexitáselemzés:

Időbeli összetettség: Vagy) A hurkot 0-tól r-ig kell futtatni. Tehát az időbonyolultság O(r).

Segédtér: O(1) Mivel nincs szükség extra helyre.

Ezt a cikket Aashish Barnwal állította össze, és a GeeksforGeeks csapata értékelte.

Kvíz létrehozása

TechCodeview

Tér- és időhatékony binomiális együttható