关于整数划分的一个有关问题

关于整数划分的一个问题
整数划分的那个ACM题目里面求的是划分数，但我现在如果想要把所有的划分情况都能显示出来应该怎么编程啊？
比如我如果输入的是5
则显示出来的是：
5 = 4 + 1
5 = 3 + 2
5 = 3 + 1 + 1
5 = 2 + 2 + 1
5 = 2 + 1 + 1 +1
5 = 1 + 1 + 1 + 1 + 1

------解决方案--------------------
做回溯就可以了.

backtrace(n,m)表示用不超过m的数组成n, 用一个额外的数组记录就行了.
------解决方案--------------------

C/C++ code

#include <iostream>
#include <vector>
using namespace std;
void print_result(int n,vector<int> &ivec)
{
    cout<<n<<"=";
    for(vector<int>::iterator iter=ivec.begin();iter!=ivec.end();++iter)
    {
        cout<<*iter<<(iter==ivec.end()-1? "":"+");
    }
    cout<<endl;
    return;
}
int func(int n,int m,vector<int> &ivec, vector<vector<int> > &res);
int main()
{
    int n=5;
    vector<int> ivec;
    vector<vector<int> > res;
    func(n,n-1,ivec,res);
    return 0;
}
int func(int n, int m,vector<int> &ivec, vector<vector<int> > &res)
{
    for(int i=m;i>=1;--i)
    {
        ivec.push_back(i);
        if(n-i<=i)
        {
            ivec.push_back(n-i);
            print_result(5,ivec);
            res.push_back(ivec);
            ivec.pop_back();
        }
        if (n-i==1)
        {
            while(*ivec.rbegin()==1)
            {
                ivec.pop_back();
            }
            ivec.pop_back();
        }
        else
        {
            int temp=(i<n-i-1? i:n-i-1);
            func(n-i,temp,ivec,res);
        }
    }
    return 0;
}

------解决方案--------------------
用回溯很好解决的。

关于整数划分的一个有关问题

相关推荐