ここで、関数は 2 つのパラメータを取ります n そして k 二項係数 C(n k) の値を返します。
例：
スイッチ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
O(n*k) 時間と O(k) 余剰空間アルゴリズムについては、 これ 役職。 C(n k) の値は、O(k) 時間と O(1) の追加スペースで計算できます。
アプローチ：
- r が n-r より大きい場合は、r を n-r に変更します。そして、答えを保存する変数を作成します。
- 0 から r-1 までループを実行する
- すべての反復で、ans を (ans*(n-i))/(i+1) として更新します。ここで、i はループカウンターです。
- したがって、答えは ((n/1)*((n-1)/2)*...*((n-r+1)/r) となり、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
次の実装では、上記の式を使用して C(n k) を計算します。
C++// Program to calculate C(n k) #include
// Program to calculate C(n k) #include
// 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.
// 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
複雑さの分析:
時間計算量: または） ループは 0 から r まで実行する必要があります。したがって、時間計算量は O(r) です。
npmキャッシュクリア補助スペース: O(1) 余分なスペースは必要ないので。
この記事は Aashish Barnwal によって編集され、GeeksforGeeks チームによってレビューされました。
クイズの作成