将 N 表示为 K 个非零整数之和的不同方法
"将 N 表示为 K 个非零整数之和的不同方法"问题在现实世界中有许多用例。
密码学 − 在密码学中，使用将数字 N 编码为 K 个非零整数之和的概念设计特定的密码方法。
将整数 N 表示为 K 个非零整数之和可能在优化方法的背景下作为不同优化问题中的子问题出现。
机器学习 − 在机器学习中，可以通过使用将整数 N 表示为 K 个非零整数之和的问题来创建描述数据点分布的特征向量。
解释
现在让我们解码这个问题。
假设，我们有两个正整数 N 和 K，我们需要找到 K 个非零整数，它们的和等于 N。例如，如果 N=10 且 K=3，我们需要找到三个非零整数，它们的和等于 10。在这种情况下，一些可能的解决方案是 −
1 + 4 + 5 2 + 3 + 5 2 + 4 + 4
请注意，在每个解决方案中，我们都有 K=3 个非零整数，它们加起来等于 N=10。
有不同的方法可以解决这个问题，让我们讨论一下它们中的每一个。
递归方法
使用递归方法的分步算法来找到将 N 表示为 K 个非零整数之和的不同方法。
将 N 和 K 的值作为主函数的输入函数。
创建函数 f(N, K)，返回 N 可以表示为 K 个非零整数之和的总方式数。
如果 N 超过 0，则返回 1；如果 K = 1，则返回 0。(基本情况)。
如果 N == 0 或 K >，则返回 0 N.(基本情况)。
创建一个变量 count 来存储结果。
将变量 count 的值设置为 0。
对于每个整数 I，从 1 到 min(N-K+1, N-1)
递归计算 f (N-i, K-1)。
将结果添加到 count 中。
返回 count。
示例
上述算法的实现
#include <iostream>
using 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 << "将" << N << "表示为" << K << "个非零整数之和的方法数:" << ways << endl;
return 0;
}
输出
将 5 表示为 2 个非零整数之和的方式数量:4
复杂度
时间复杂度:O(N ^ K)。
空间复杂度:O(K)
二项式系数公式
星号和条形组合方法可用于获得将正整数 N 表示为 K 个非零整数之和的方式数量的公式。
想象一排 N 个星号 (*)，代表给定整数的 N 个分区单元。 K-1 条横线 (|) 将星号行分成 K 个段，可用于表示分区的 K 个非零整数。
以将 10 分成 3 个非零整数为例。下面的星号和横线行可用于表示这一点 −
* * | * * * | * * * * *
此图的第一部分表示数字 2，第二段表示数字 3，第三段表示数字 5。
因此，在 N 个星号行中排列 K-1 条横线的方法数等于将 N 表示为 K 个非零整数之和的方法数。为了计算这个，我们使用公式:$\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 个被加数。
因此，我们得出公式:方法 = C(N-1, K-1)
假设我们想要找到将 6 表示为 4 个非零整数之和的方法数。我们可以使用之前推导的公式，即 −
C(N-1, K-1) = C(6-1, 4-1) = C(5, 3) = 10
这告诉我们有 10 种方法可以将 6 分成 4 个非零整数。
它们是 −
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 的值作为主函数的输入。
使用上述公式计算方法的数量。
打印方法的值。
现在让我们编写一些代码。
示例
使用二项式系数方法的代码实现
#include <iostream>
using 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 << "将" << N << "表示为" << K << "个非零整数之和的方法数:" << ways << endl;
return 0;
}
输出
将 7 表示为 2 个非零整数之和的方法数:6
复杂度
时间复杂度:O(K)。
空间复杂度:O(1)
结论
在本文中，我们尝试解释找出将 N 表示为 K 个非零整数之和的不同方法的方法。我希望本文能帮助您更好地学习这个概念。
