要素が正の整数で、C++では合計がKであるサイズNの配列の数

nとkの2つの数が与えられます。合計がkであるn個の数を使用して形成できる配列の数を見つける必要があります。

合計KのサイズNの配列の数は、$ \ dbinom {k-1}{n-1}$です。

これは、合計がkであるn個の要素を使用して形成できる数の配列を見つけるための簡単な式です。例を見てみましょう。

入力

n = 1
k = 2

出力

1

形成できる唯一の配列は[2]

入力

n = 2
k = 4

出力

3

形成できるアレイは、[1、3]、[2、2]、[3、1]です。

アルゴリズム

• 番号nとkを初期化します。
• 数値の階乗を計算する関数を記述します。
• 次に、上記のように二項式を計算するためのメイン関数を記述します。
• 答えを返します。

実装

以下は、C++での上記のアルゴリズムの実装です

#include <bits/stdc++.h>
using namespace std;
int factorial(int n) {
   int result = 1;
   for (int i = 2; i <= n; i++) {
      result *= i;
   }
   return result;
}
int getNumberOfArraysCount(int n, int k) {
   return factorial(n) / (factorial(k) * factorial(n - k));
}
int main() {
   int N = 5, K = 8;
   cout << getNumberOfArraysCount(K - 1, N - 1) << endl;
   return 0;
}

出力

上記のコードを実行すると、次の結果が得られます。

35