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

//分析：该题是一个求一个序列相加但是前数小雨后数的要求序列。实际上任何一个数都可以看成n = 1+(n-1)  n = 1+2+(n-3),这是一个递归的过程  
[cpp] view plaincopy
#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 100  
  
int 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;  
}