尝试编写一个递归函数来计算总和达到该数字 C++ 的序列数。

Question

好的，这就是我想做的。用户输入一个数字。我正在尝试编写一个递归函数来计算总和达到该数字（用户输入）的序列数。

例如：

那么总和为6的序列数为11（包括6本身）。

6
5+1
4+1+1
3+1+1+1
2+1+1+1+1
1+1+1+1+1+1
2+2+1+1
3+2+1
4+2
2+2+2
3+3

我还尝试不重复序列，例如 2+2+1+1 和 1+1+2+2。

我没有包含代码的原因是我无法找出一种递归方法来完成这项工作，所以我正在寻求一些指导。提前致谢！

添加：

好的，这就是我的思考过程。 6可以拆分为...

6
5+1
4+2
3+3

但还没有结束，如果你取5+1并认为+1部分已完成；您可以使用相同的技巧继续。

4+1+1
3+2+1

但然后他们开始重复......我没有比我的计划中的第二步更进一步。

好吧，就代码而言，这是我自己想出的。正在寻找解决此问题的建议。

int sum(int number, int min, int counter)
{
    int temp=0, n;
    n=number+temp;
    if (number>=(n/2)& number!=min)
    {
        while (number>=(n/2))
        {
            cout << number << "+"<< temp <<"\n";
            number --;
            temp ++;
            counter ++;
        }
    }
    sum(temp, 1,counter);
    return counter;
}

int main()
{
    int number;

    cout << "Please enter the number: ";
    cin >> number ;
    cout << "\n";

    sum(number, 1, 0);

    return 0;
}

我确实意识到这一切都很混乱。

Answer 1

提示：尝试找到一个函数，给出总和为 n 且项不大于 k 的序列数。

编辑：
如果这听起来很刺耳，请原谅我，但是......您更新的代码都是错误的。很难看出你的意图。我可以猜测，但这毫无意义。

这就是我的想法：序列应该是非递增的顺序，例如“2 2 1 1 1 1”。那么有多少个这样的序列加起来是 6 呢？好吧，找到从 1 开始的此类序列的数量，然后是从 2 开始的序列的数量，依此类推，直到 6，然后将它们相加。以 2 开头、加起来为 6 的序列有多少个？ （这就是递归发挥作用的地方。）在每个这样的序列中，第一项是 2，其余项加起来为 4，没有一项超过 2，因此我们必须找到的数量序列加起来为 4，且没有一项大于 2。所以先写签名，然后是迭代循环，然后是递归调用，就完成了。

编辑：
好吧，除了循环之外，这里是所有内容：

int partition(int n, int max)
{
  if(n==0)
    return(0);
  int ret = 0;
  if(n<=max)
    ret=1;
  for(...)
  {
    ...
  }
  return(ret);
}

你能填空吗？

Answer 2

我认为它接近概率论
给出总结 6 的集合 {1,2,3,4,5,6} 的组合数量

Answer 3

这些称为整数分区，有一种简单的方法可以使用中间函数计算任意数字的分区数。看一下这里：整数分区。

Answer 4

令 f(n) 为我们想要的函数，它生成与 n 相加的整数序列，无需排列

定义

f(n) = g(n,n)

g(n,p) = { i \in 1..min(n, p): [ig(ni,i)] }

Answer 5

这个问题很好地介绍了该算法。

Answer 6

定义 P(n) 为划分 n 的方式数，限制 n 为整数，n >= 1。

定义 p(n, k) 为使用不大于 k 的数字划分 n 的方式数，限制k为整数，k≥1，k≤n。

由此得出 P(n) = sum (i: 1..n) p(n, i)。

要找到 p(n, k)，首先请注意，我们通过简单地保持分区排序来巧妙地避免重复计算：首先取最大的块。因此，第一个块可以具有从 1 到 k 的任意大小，然后其余块必须占总数 n 的其余部分，并且不大于第一个块。

因此 p(n, k) = sum (i: 1..k) p(n - i, i)。

作为基本情况，p(1, 1) = 1。

---

示例实现，不保证完全有效，甚至无法编译（但它应该给您基本的想法） -剧透！

// A utility function to represent the result of appending to a vector,
// as a new vector (without affecting the previous one).
template <typename T>
vector<T> operator<<(vector<T> copy, T to_append) {
    // We passed by value to get a copy implicitly.
    copy.push_back(to_append);
    return copy;
}

// A utility function to append one vector to another.
template <typename T>
vector<T>& operator+=(vector<T>& original, const vector<T>& to_append) {
    // 'copy' is in namespace std:: and defined in <algorithm>.
    // 'back_inserter' is in namespace std:: and defined in <iterator>.
    copy(to_append.begin(), to_append.end(), back_inserter(original));
    return original;
}

vector<vector<int> > partitions(int remaining, int limit, vector<int> prefix) {
    // Finds the partitions of some larger number which start with the
    // numbers in 'prefix', such that the rest of the "chunks" sum to
    // 'remaining' and are all no larger than 'limit'.

    // 'max' is in namespace std:: and defined in <algorithm>. We restrict
    // the 'limit' to be no more than 'remaining'.
    limit = max(remaining, limit);

    vector<vector<int> > result;

    // Base case. 
    if (remaining == 1) {
        return result << (prefix << 1); // note the parentheses are required!
    }

    for (int i = limit; i > 0; --i) {
        result += partitions(remaining - i, i, prefix << i);
    }

    return result;
}