C++ 中求解方程 x1 + x2 +…. + xN = k 的整数解个数
方程的解为
- 该方程的非负整数解个数为 (n−k+1 k)
- 该方程的正整数解个数为 (k−1 n−1)
将两者相加即可得到所需答案。让我们来看一个例子。
输入
n = 4 k = 7
输出
140
算法
- 初始化数字 n 和 k。
- 找到非负数和正数的整数解。
- 将两者相加。
- 返回答案。
实现
以下是上述算法在 C++ 中的实现
#include <bits/stdc++.h> using namespace std; int factorial(int n) { int product = 1; for (int i = 2; i <= n; i++) { product *= i; } return product; } int nCr(int n, int r) { return factorial(n) / (factorial(n - r) * factorial(r)); } int main() { int n = 4; int k = 7; cout << nCr(n + k - 1, k) + nCr(k - 1, n - 1) &l<t; endl; return 0; }
Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.
输出
如果运行以上代码,则会得到以下结果。
140
广告