拆分自然数(c++题解)

本文主要是介绍拆分自然数(c++题解)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。

输入格式

输入只有1行，包含1个整数n，表示待拆分的数字。

输出格式

对于每组输入输出n的拆分方法，每种拆分方法占1行，最后输出一共有多少种拆分方案。

样例

样例输入

复制4

样例输出

复制4=1+1+1+1
4=1+1+2
4=1+3
4=2+2
4

数据范围与提示

n在45以内

#include <bits/stdc++.h>
using namespace std;
int a[100005],n,ans;
void f(int x,int y){if(n==x){int z=0;for(int i=1;i<=n;i++){if(a[i]!=0){z=i;break;}}if(z==n){return;}ans++;cout<<n<<"=";cout<<z;for(int i=1;i<a[z];i++){cout<<"+"<<z;	    }for(int i=z+1;i<=n;i++){for(int j=1;j<=a[i];j++){cout<<"+"<<i;	    }}cout<<endl;	return;}for(int i=y;i<=n-x;i++){a[i]++;f(i+x,i);a[i]--;}
}
int main(){cin>>n;f(0,1);cout<<ans;
}

_____________________________________________________________________________

写作不易，点个赞呗!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 

_____________________________________________________________________________

这篇关于拆分自然数(c++题解)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---