数的拆分(1)

【题目描述】

任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。例如：当n=7时

7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4
total=14

【输入描述】

一个数N

【输出描述】

一个数，表示多少种拆分的方式

【样例输入】

3

【样例输出】

3=1+1+1
3=1+2
total=2

【题目分析】

【参考代码1】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
int a[100000]={1};int n,tot;
void dfs(int,int);
void print(int);
int main()
{
    cin>>n;
    dfs(n,1);
    cout<<"total="<<tot;
    return 0;
}
void dfs(int p,int q)
{
    int i;
    for(i=a[q-1];i<=p;i++)
    {
        if(i<n)
        {
            a[q]=i;
            p-=i;
            if(p==0)print(q);
            else dfs(p,q+1);
            p+=i;
        }
    }
}
void print(int j)
{
    tot++;
    cout<<n<<"=";
    for(int i=1;i<=j;i++)
    {
        if(i!=j)
        cout<<a[i]<<"+";
        else cout<<a[i];
    }
    cout<<endl;
}

返回目录：题解目录