分区功能的C ++ [英] Partition function in c++

问题描述

我需要为分区问题

简单的解释：查找得到一个数n的所有款项。 例如

• 输入：5
• 输出：
  • 11111
  • 2111
  • 311
  • 41
  • 5
  • 221
  • 23

这个问题似乎很容易，但我无法找到一个解决方案。我很接近，使这个暴力破解，因为最高输入为11。关于这个问题的文章是高度数学，我真的不明白这一点。

感谢大家！

解决方案

  / *
例如。
输入数字：5
五
1 4
1 1 3
1 1 1 2
1 1 1 1 1
1 2 2
2 3
* /
＃包括＆LT;的iostream＆GT;
＃包括＆LT;载体＆GT;

使用名字空间std;

无效打印（矢量＆lt; INT＆GT;＆安培; V，INT级）{
    的for（int i = 0; I＆LT; =水平;我++）
        COUT＆LT;＆LT; v [电流]其中;＆其中; ;
    COUT＆LT;＆LT; ENDL;
}

空隙部（INT N，矢量＆lt; INT＆GT;＆安培; V，INT级）{
    诠释第一; / *首先是前年* /

    如果（N小于1）的回报;
    v [等级] = N;
    印刷（V，水平）;

    第一=（水平== 0）？ 1设置：v [1级]。

    的for（int i =第一; I＆LT; = N / 2;我++）{
        v [等级] =我; / *替换最后一个* /
        部分第（n-I，V，平+ 1）;
    }
}

诠释的main（）{
    INT N;
    COUT＆LT;＆LT; 输入号码：;
    CIN＆GT;＆GT; N;

    矢量＆lt; int的＆GT; V（N）;

    部分（N，V，0）;
}
 

I need an algorithmic solution in c++ for the partition-problem

Simple explanation: Find all sums that get a number n. For example

• Input: 5
• Output:
  • 11111
  • 2111
  • 311
  • 41
  • 5
  • 221
  • 23

This problem seems so easy, but I couldn't find a solution. I'm close to make this bruteforce, because the highest input is 11. The articles about that problem are highly mathematic and I don't really get it.

Thank you all!

解决方案

/*
E.g.
input number:5
5
1 4
1 1 3
1 1 1 2
1 1 1 1 1
1 2 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 N;
    cout << "input number:";
    cin >> N;

    vector<int> v(N);

    part(N, v, 0);
}

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