数的分解(华为2014年机试题——合肥——之一)

这次的题吊了...其实思路很清楚，但是为了更好的输出，我想了将近3小时。这远远没有达到华为的要求呀...唉...仅以此题来祭奠我被打击的自信心。

有没有大神可以提供更好的方法，或则把我的哪个代码修改一下....让他更好的输出。

题目描述：
整数分解，将整数n分解成不同因子的和，后一因子要比前一因子大，且最大因子要小于n，其中n<=1000

比如分解10

大家注意测试数据不要太大，不然会悲剧....

//分析：该题是一个求一个序列相加但是前数小雨后数的要求序列。实际上任何一个数都可以看成n = 1+(n-1)  n = 1+2+(n-3),这是一个递归的过程

#include <list>#include <iostream>using namespace std;void Separate_Base(int n,int min){//这是我们最先的思路，算是一个BASE版本把，接下来我们就来写一个正式版int fir = min+1;int sec = n - fir;if(sec < min || sec <= fir)return ;cout<<n<<"="<<fir<<"+"<<sec<<endl;Separate_Base(sec,fir);//把第二项继续拆分Separate_Base(n,fir);//把第一项最为最小一个数传入下一个}int Separate(int n,int min,int flag,list<list<int> > &data,list<int> &front){//我们分析BASE版发现得出的结果是没有区分两个递归函数到底调用的是哪一个，现在就用一个数据结构来存储,flag表示深度，分析可知，深度为0，一个表达式，为1两个以此类推//data用来存储数据的单元，front用来表示改表达式的上层表达式int fir = min+1;int sec = n - fir;if(sec < min || sec <= fir){return flag;}if(flag == 0){list<int> temp;temp.push_back(fir);temp.push_back(sec);data.push_back(temp);}else{list<int> temp = front;temp.pop_back();temp.push_back(fir);temp.push_back(sec);data.push_back(temp);}Separate(sec,fir,flag+1,data,data.back());//把第二项继续拆分Separate(n,fir,flag,data,front);//把第一项最为最小一个数传入下一个}#define DATA 100int main(int argc, char* argv[]){//Separate_Base(10,0);list<list<int> > data;Separate(DATA,0,0,data,data.back());for(list<list<int> >::iterator temp = data.begin();temp != data.end();temp++){cout<<DATA<<"=";for(list<int>::iterator p = temp->begin();p != temp->end();p++){cout<<*p;if(*p != temp->back()){cout<<"+";}}//copy(temp->begin(),temp->end(),ostream_iterator<int>(cout,"+"));cout<<endl;}return 0;}