【题目描述】

任何一个大于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;
}
#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; }
#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;
}

返回目录:题解目录