c++ - 整数分区 + 分区数

Question

整数 n 的分区是将 n 写为正整数之和的一种方式。对于

例如，对于 n=7，分区为 1+1+5。我需要一个程序来找到所有的

整数“n”的分区使用“r”个整数。比如n=7

的所有分区

使用 r=3 整数是 1+1+5, 1+2+4, 1+3+3 ，2+2+3。

这是我目前所拥有的:

#include <iostream>
#include <vector>

using namespace std;

void print (vector<int>& v, int level){
    for(int i=0;i<=level;i++)
        cout << v[i] << " ";
    cout << endl;
}

void part(int n, vector<int>& v, int level){
    int first; /* first is before last */

    if(n<1) return ;
    v[level]=n;
    print(v, level);

    first=(level==0) ? 1 : v[level-1];

    for(int i=first;i<=n/2;i++){
        v[level]=i; /* replace last */
        part(n-i, v, level+1);
    }
}

int main(){
    int num;
    cout << "Enter a number:";
    cin >> num;

    vector<int> v(num);

    part(num, v, 0);
}

这个程序的输出是:

Enter a number:5
5
1 4
1 1 3
1 1 1 2
1 1 1 1 1
1 2 2
2 3

Process returned 0 (0x0)   execution time : 1.837 s
Press any key to continue.

我怎样才能更改我的代码以便我可以拥有那个“r”变量？

编辑:

如果不清楚，“r”值表示每个分区的整数数量。所以在上面的例子中，如果 r=2，那么分区中只能有两个整数。分区将是 4+1 和 3+2。 “r”值应由用户输入。

Answer 1

基本上是 Codor 所说的，一旦找到目标长度的分区，您就不需要进一步递归 part()，因为它们会更长:

#include <iostream>
#include <vector>

using namespace std;

void print (vector<int>& v, int level){
    for(int i=0;i<=level;i++)
        cout << v[i] << " ";
    cout << endl;
}

void part(int n, vector<int>& v, int level, int r){
    int first; /* first is before last */

    if(n<1) return ;
    v[level]=n;
    if( level+1 == r ) {
        print(v, level);
        return;
    }

    first=(level==0) ? 1 : v[level-1];

    for(int i=first;i<=n/2;i++){
        v[level]=i; /* replace last */
        part(n-i, v, level+1, r);
    }
}

int main(){
    int num,r;
    cout << "Enter a number:";
    cin >> num;
    cout << "Enter size (r):";
    cin >> r;

    vector<int> v(num);

    part(num, v, 0, r);
}

输出:

Enter a number:5
Enter size (r):2
1 4
2 3