分区整数+分区数 [英] Partition of an Integer + Number of partitions

问题描述

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

A partition of an integer n is a way of writing n as a sum of positive integers. For

示例，对于n = 7，分区为1 + 1 + 5。我需要一个程序，使用'r'整数找到整数'n'的所有

example, for n=7, a partition is 1+1+5. I need a program that finds all the

分区。例如， n = 7

的所有分区使用 r = code>整数为 1 + 1 + 5 ， 1 + 2 + 4 ， 1 + 3 + 3 ， 2 + 2 + 3 。

using r=3 integers are 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'变量？

How can I change my code so I can have that 'r' variable?

编辑：

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

In case it was not clear, the 'r' value represents the number of integers per partition. So in the case above, if r=2, then the partitions can only have two integers in them. The partitions would be 4+1, and 3+2. The 'r' value should be entered by the user.

推荐答案

Codor说，一旦你找到了一个目标长度的分区，因为它们会更长，所以需要进一步递归到 part（）：

Essentially what Codor said, plus you don't need to recurse further into part() once you found a partition of the target length since they would be longer:

#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

这篇关于分区整数+分区数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！