问题“将N表示为K个非零整数的不同方式”在许多现实世界的用例中都有应用。
密码学 - 在密码学中，使用将一个数字N编码为K个非零整数之和的概念来设计特定的加密方法。
将一个整数N表示为K个非零整数的和可能会出现在优化方法的不同优化问题的子问题中。
机器学习− 在机器学习中，可以通过使用将整数N表示为K个非零整数之和的问题来创建描述数据点分布的特征向量。
Explanation
的中文翻译为：解释
现在让我们解码这个问题。
假设我们有两个正整数N和K，我们需要找到K个非零整数，它们的和等于N。例如，如果N=10且K=3，我们需要找到三个非零整数，它们的和等于10。在这种情况下可能的解决方案有−
1 + 4 + 5 2 + 3 + 5 2 + 4 + 4
请注意，在这些解决方案中，我们有K=3个非零整数，它们相加等于N=10。
解决这个问题有不同的方法，让我们讨论每一种方法。
递归方法
使用递归方法的逐步算法，找出用K个非零整数表示N的不同方式。
在主函数中输入N和K的值。
创建函数 f(N, K)，它返回N可以表示为K个非零整数的总方式数。
如果K = 1，当N超过0时返回1，否则返回0。（基本情况）。
如果 N == 0 或者 K > N，则返回 0。 (基本情况)。
创建一个变量 count 来存储结果。
将变量count的值设置为0。
从1到min(N-K+1, N-1)对于每个整数I
递归计算 f (N-i, K-1)。
将结果添加到计数中。
返回计数。
Example
上述算法的实现
#includeusing namespace std; int f(int N, int K) { if (K == 1) { return (N > 0) ? 1 : 0; // base case } if (N <= 0 || K > N) { return 0; // base case } int count = 0; for (int i = 1; i <= min(N-K+1, N-1); i++) { count += f(N-i, K-1); } return count; } int main() { int N = 5, K = 2; int ways = f(N, K); cout << "Number of ways to represent " << N << " as the sum of " << K << " non-zero integers: " << ways << endl; return 0; }
输出
Number of ways to represent 5 as the sum of 2 non-zero integers: 4
复杂性
时间复杂度: O(N ^ K).
空间复杂度: O(K)
二项式系数公式
星星和条纹组合方法可以用来得到一个正整数N可以表示为K个非零整数之和的方式的公式。
想象一排N颗星（*），它们代表给定整数的N个分区单元。可以使用K-1个竖线（|）将星星排成K个段，代表分区的K个非零整数。
以将10分成3个非零整数为例。下面的星号和横杠可以用来表示这个过程 −
* * | * * * | * * * * *
这个插图的第一部分描绘了数字2，第二部分描绘了数字3，第三部分描绘了数字5。
在N颗星星的一行中排列K-1个条的方式数量等于用K个非零整数表示N的方式数量。为了计算这个数量，我们使用公式：$\mathrm{C(N\:+\:K\:-\:1,\:K\:-\:1)}$。
根据二项式系数公式 $\mathrm{C(n,k)\:=\:n!\:/(k!*(n-k)!)}$。
但在我们的情况下，我们需要排除包含0的可能性。为了排除包含0作为其中一个加数的分割，我们可以使用以下方法−
从N中减去1得到N-1。
将N-1划分为K-1个非负整数。
将步骤2中获得的K-1个非负整数都加1，得到K个非零整数，它们的和为N。
这种方法有效的原因是每个加数的最小可能值是1（因为我们希望是非零整数），所以我们从N中减去1，以确保有足够的单位可以分配给K个加数。
因此，我们得到公式：ways = C(N-1, K-1)
假设我们想找到用4个非零整数表示6的方式的数量。我们可以使用之前推导出的公式，即 −
C(N-1, K-1) = C(6-1, 4-1) = C(5, 3) = 10
这告诉我们将6分成4个非零整数有10种方法。
他们是 −
1 + 1 + 1 + 3
1 + 1 + 2 + 2
1 + 1 + 3 + 1
1 + 2 + 1 + 2
1 + 2 + 2 + 1
1 + 3 + 1 + 1
2 + 1 + 1 + 2
2 + 1 + 2 + 1
2 + 2 + 1 + 1
3 + 1 + 1 + 1
方法
让我们讨论一下实现上述方法的逐步算法 -
在主函数中输入N和K的值。
使用上述公式计算方法的数量。
打印出变量 ways 的值。
现在让我们来写一些代码。
示例
使用二项式系数方法的代码实现
#includeusing namespace std; int binomial(int n, int k) { int res = 1; if (k > n - k) { k = n - k; } for (int i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res; } int main() { int N = 7, K = 2; int ways = binomial(N - 1, K - 1); cout << "Number of ways to represent " << N << " as the sum of " << K << " non-zero integers: " << ways << endl; return 0; }
输出
Number of ways to represent 7 as the sum of 2 non-zero integers: 6
复杂性
时间复杂度: O( K).
空间复杂度: O(1)
结论
在这篇文章中，我们尝试解释了一种找出将N表示为K个非零整数之和的方法。我希望这篇文章能帮助你更好地理解这个概念。
