限制部件数量和部件尺寸-在c++中

Question

我正试图从oeis.org网站重新构建以下"零件数量限制和零件尺寸限制"公式:

假设将n≤k≤m n的组合物分成n个部分，每个部分的大小不大于m。我循环遍历代码，直到返回0。

C_3(3,3)的预期结果为1,3,6,7,6,3,1(如现场表格所示)。我得到的是1369121212

我只是看不出我的代码哪里错了。我已经看了两天了，还是不明白。

#include <iostream>
int C(int m, int n, int j)
{
if (n == 0 && j == 0)
{
return 1;
}
if (j < 0 || j > (m - 1) * n)
{
return 0;
}
int sum = 0;
for (int i = j - ((m - 1) * n); i <= j; ++i)
{
sum += C(m, n - 1, i);
}
return sum;
}
int main()
{
constexpr int m = 3;
constexpr int n = 3;
int counter = 0;
while (int result = C(m, n, counter++))
{
std::cout << result;
}
std::cin.ignore();
return 0;
}

Answer 1

所以这是一个递归函数用于生成m个元素的受限组合的数量为n个部分的大小不超过m但是这个函数的公式似乎是不正确的

递归公式应为:

C(m, n, j) = C(m, n-1, j-1) + C(m, n-1, j-2) + ... + C(m, n-1, j-m)

对于给定的n值，m个元素组成n个大小不超过m的零件的次数等于m-1个元素组成n-1个大小不超过m的零件的次数，加上m-2个元素组成n-1个大小不超过m的零件的次数，以此类推，直到0个元素组成n-1个大小不超过m的零件的次数。

递归的基本情况是当n = 0且j = 0时，在这种情况下，函数应该返回1(因为只有一种方法将0个元素组成0个部分)。如果n <0或j <0，因为这些情况无效。

#include <iostream>
int C(int m, int n, int j)
{
if (n == 0 && j == 0)
{
return 1;
}
if (n < 0 || j < 0)
{
return 0;
}
int sum = 0;
for (int i = j; i >= j - m + 1; --i)
{
sum += C(m, n - 1, i);
}
return sum;
}
int main()
{
constexpr int m = 3;
constexpr int n = 3;
int counter = 0;
while (int result = C(m, n, counter++))
{
std::cout << result << " ";
}
std::cin.ignore();
return 0;
}

检查j>(m-1)*n应包括:

int C(int m, int n, int j)
{
if (n == 0 && j == 0)
{
return 1;
}
if (n < 0 || j < 0 || j > (m - 1) * n)
{
return 0;
}
int sum = 0;
for (int i = j; i >= j - m + 1; --i)
{
sum += C(m, n - 1, i);
}
return sum;
}